Страница: << 51 52 53 54 55 56 57 >> Отображать по:

#111288

Телефонный номер

Темы: [Динамическое программирование]

Источники: [ Командные олимпиады, ВКОШП, 2011, Задача C ]

Недавно Васе продиктовали номер телефона. Он записал его, разделив числа дефисами, но потом начал сомневаться, не ошибся ли он в записи номера. Ведь бывают различные телефонные номера, которые произносятся одинаково. Например, все четыре номера «3000-100-1», «3000-101», «3100-1», «3101» читаются как «три тысячи сто один». Теперь он хочет выяснить, какие номера произносятся также, как и записанный им номер.

Вася считает, что при произношении телефонного номера не употребляются числа, состоящие более чем из девяти цифр. Напомним, как произносятся числа от $1$ до $999\,999\,999$.

Если число больше или равно $1\,000\,000$, то сначала произносится число миллионов в мужском роде, затем слово «миллион», «миллиона» или «миллионов», по следующим правилам. Если число миллионов, взятое по модулю 100, не равно 11 и дает остаток 1 по модулю 10, то произносится слово «миллион». Если число миллионов, взятое по модулю 100, не равно 12, 13 или 14 и дает остаток 2, 3 или 4 по модулю 10, то произносится слово «миллиона». Иначе произносится слово «миллионов».

Если число по модулю $1\,000\,000$ больше или равно $1\,000$, то затем произносится число тысяч в женском роде, затем слово «тысяча», «тысячи» или «тысяч», по следующим правилам. Если число тысяч, взятое по модулю 100, не равно 11 и дает остаток 1 по модулю 10, то произносится слово «тысяча». Если число тысяч, взятое по модулю 100, не равно 12, 13 или 14 и дает остаток 2, 3 или 4 по модулю 10, то произносится слово «тысячи». Иначе произносится слово «тысяч».

Затем, если число по модулю $1\,000$ отлично от нуля, в мужском роде произносится число единиц.

Например, число $978\,121\,014$ произносится как «девятьсот семьдесят восемь миллионов сто двадцать одна тысяча четырнадцать», а число $1\,000\,142$ как «один миллион сто сорок два». Заметим, что перед словом «миллион» нельзя опускать слово «один», перед словом «тысяча» слово «одна», а числа от $11$ до $19$ произносятся одним словом.

Помогите Васе найти все телефонные номера, которые произносятся так же, как тот, который он записал.

Входные данные

На входе единственная строка, содержащая номер записанного Васей телефона. Номер телефона --- это целые числа, разделенные символом «-» (ASCII код 39). Каждое число в записи положительно, содержит не более девяти цифр и не содержит ведущих нулей. Гарантируется, что в записанном Васей номере встречается не больше 50 цифр.

Выходные данные

В первой строке выведите количество телефонных номеров, которые читаются так же, как и записанный Васей номер. В следующих строках выведите эти номера телефонов. Каждый номер должен находиться в отдельной строке. Каждый номер должен состоять из чисел от 1 до $999\,999\,999$, разделенных дефисами.

Порядок телефонов в ответе не важен. Гарантируется, что количество номеров в ответе не превышает $100\,000$. Учтите, что в ответе могут встречаться и номера, составленные более чем из 50 цифр.

Примеры тестов

Входные данные

3000-101

Выходные данные

#111295

Поезда

Темы: [Генерация по номеру] [Динамическое программирование]

Источники: [ Командные олимпиады, ВКОШП, 2011, Задача J ]

Маленький Вася очень любит поезда. На день рождения ему подарили игрушечную железную дорогу. В комплект к железной дороге входит поезд, состоящий из $n$ вагонов, пронумерованных числами от 1 до $n$.

Любимым занятием Васи стала сортировка поездов с использованием специального сортировочного тупика. $\text{[math]}$

Справа к тупику подъезжает поезд, составленный из всех $n$ вагонов. Затем вагоны по одному загоняются в сортировочный тупик и выгоняются из него налево. Васе нравится, если ему удается отсортировать поезд с помощью сортировочного тупика — добиться того, чтобы слева от тупика вагоны были расположены по порядку от 1 до $n$.

Например, пусть в исходном поезде 4 вагона, которые следуют в порядке 3, 1, 2, 4. Его можно отсортировать следующим образом. Загоняем вагон 3 в тупик. Загоняем вагон 1 в тупик. Выгоняем вагон 1 из тупика. Загоняем вагон 2 в тупик. Выгоняем вагон 2 из тупика. Выгоняем вагон 3 из тупика. Загоняем вагон 4 в тупик. Выгоняем вагон 4 из тупика.

Не все поезда можно отсортировать таким образом. Например, поезд из 3 вагонов, следующих в порядке 2, 3, 1, отсортировать нельзя.

Вася выписал на листке в лексикографическом порядке все поезда длины $n$, которые можно отсортировать с помощью тупика. Поезд $(a_1, a_2, \ldots, a_n)$ идет раньше поезда $(b_1, b_2, \ldots, b_n)$ в лексикографическом порядке, если существует такое $i$ ($1 \le i \le n$), что для всех $j < i$ выполняется $a_j = b_j$, а $a_i < b_i$. Например, все поезда из трех вагонов, которые можно отсортировать с помощью тупика, в лексикографическом порядке выписываются следующим образом: $(1, 2, 3)$, $(1, 3, 2)$, $(2, 1, 3)$, $(3, 1, 2$), $(3, 2, 1)$.

Вася потерял свой листок, и его интересует вопрос: какой поезд был выписан на его листке под номером $k$. Помогите ему выяснить это.

Входные данные

Входной файл содержит два целых числа — $n$ и $k$ ($1 \le n \le 30$, $1 \le k \le 10^{18}$).

Выходные данные

Выведите в выходной файл $n$ целых чисел: $k$-й в лексикографическом порядке поезд из $n$ вагонов, который можно отсортировать с помощью тупика.

Если с помощью тупика можно отсортировать менее $k$ поездов из $n$ вагонов, выведите $-1$.

Примеры тестов

Входные данные

4 1

Выходные данные

1 2 3 4

Входные данные

4 3

Выходные данные

1 3 2 4

Входные данные

4 15

Выходные данные

-1

#111426

Раздел имущества

Темы: [meet in the middle]

В этой задаче входные данные записаны в файле exchange.in, вывод нужно записать в файл exchange.out.

Вася — профессиональный юрист, и сейчас он рассматривает очередное дело о разделе имущества. Всего имеется N наследников, каждый из них имеет значимость R_i. Богатый дедушка оставил им состояние в размере L иностранных тугриков. Логично раздать наследство пропорционально значимости, в этом случае i-ый наследник получит $\text{[math]}$ иностранных тугриков. Однако, наследники очень привередливы, поэтому наследник желает получить кругленькую сумму, т.е. ту, которая делится на S_i.

Чтобы выполнить просьбу наследников, Вася может округлять числа A_i до ближайшего, делящегося на S_i (в случае, если делимость не имеет места). При этом, Вася сам выбирает, округлить очередное число вниз или вверх. Пусть B_i означает, сколько в итоге получит очередной наследник. Так как Вася — честный человек, он хочет минимизировать $\text{[math]}$ . В случае нескольких вариантов, он выбирает тот, при котором $\text{[math]}$ будет наименьшей.

Входные данные

В первой строке входных данных содержится два целых числа N и L — количество наследников и размер состояния, соответственно (1 ≤ N ≤ 30, 1 ≤ L ≤ 10⁹). В следующей строке содержатся значимости наследников R_i ( $\text{[math]}$ ). В следующей строк содержатся числа S_i (1 ≤ S_i ≤ 10⁹).

Выходные данные

Выведите единственное число — искомую оптимальную сумму $\text{[math]}$ .

Примеры тестов

Входные данные

2 250
1 2
100 150

Выходные данные

Входные данные

3 1000
25 25 50
34 77 52

Выходные данные

Входные данные

3 10
1 1 0
50 50 50

Выходные данные

#111485

Дубы

Темы: [Динамическое программирование по подстрокам]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Санкт-Петербург, 2008, Задача B ]

На аллее перед зданием Министерства Обороны в ряд высажены $n$ дубов. В связи с грядущим приездом главнокомандующего, было принято решение срубить несколько деревьев для придания аллее более милитаристического вида.

Внутренние распорядки министерства позволяют срубать дуб только в двух случаях:

* Если и ближайший дуб слева, и ближайший дуб справа строго ниже, чем данный дуб.

* Если и ближайший дуб слева, и ближайший дуб справа строго выше, чем данный дуб.

В частности, согласно этому правилу, нельзя срубить крайний левый и крайний правый дуб.

Министр хочет выработать такой план вырубки, чтобы в итоге осталось несколько дубов, высоты которых образуют неубывающую последовательность, то есть чтобы каждый дуб был не ниже, чем все дубы, стоящие слева от него. При этом, как человек любящий флору, министр хочет, чтобы было срублено минимальное возможное количество деревьев.

Помогите сотрудникам министерства составить оптимальный план вырубки аллеи или выяснить, что срубить дубы соответствующим образом невозможно.

Входные данные

Первая строка входного файла содержит целое число $n$ — количество дубов, растущих на аллее ($2\le n \le 200$). Вторая строка содержит $n$ чисел — высоты дубов, приведенные слева направо. Высоты дубов — положительные целые числа, не превышающие 1000.

Выходные данные

Если оставить последовательность дубов с неубывающими высотами невозможно, выходной файл должен содержать только одно число $-1$.

В случае, если искомый план существует, в первую строку выходного файла выведите целое число $m$ — минимальное количество дубов, которые необходимо срубить. В следующие $m$ строк выведите оптимальный план вырубки деревьев — номера дубов в том порядке, в котором их следует срубать, по одному номеру на строке.

Дубы нумеруются слева направо натуральными числами от $1$ до $n$.

Если планов с наименьшим числом срубаемых дубов несколько, выведите любой из них.

Система оценки

В 50 баллов оценивается решение для случая, когда все высоты дубов попарно различны.

Примеры

Входные данные

5
3 2 4 8 5

Выходные данные

2
2
4

Входные данные

5
4 5 5 5 6

Выходные данные

Входные данные

6
1 1 3 3 2 2

Выходные данные

-1

Входные данные

6
400 300 310 300 310 500

Выходные данные

-1

#111490

A + B = C

Темы: [Динамическое программирование: последовательности]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2013, 1 день, Задача C ]

Часто для пробного тура на различных олимпиадах по информатике предлагается задача «A + B», в которой по заданным целым числам $A$ и $B$ требуется найти их сумму.

При проведении городской олимпиады по информатике председатель жюри решил сам подготовить тесты для такой задачи. Для этого он использовал свою оригинальную методику, которая заключалась в следующем: сначала готовятся предполагаемые правильные ответы, а затем подбираются входные данные, соответствующие этим ответам.

Пусть председатель жюри выбрал число $C$, запись которого состоит из $n$ десятичных цифр и не начинается с нуля. Теперь он хочет подобрать такие целые положительные числа $A$ и $B$, чтобы их сумма была равна $C$, и запись каждого из них также состояла из $n$ десятичных цифр и не начиналась с нуля. В дополнение к этому председатель жюри старается подобрать такие числа $A$ и $B$, чтобы каждое из них было красивым. Красивым в его понимании является число, запись которого не содержит двух одинаковых подряд идущих цифр. Например, число 1272 считается красивым, а число 1227 — нет.

Требуется написать программу, которая для заданного натурального числа $C$ вычисляет количество пар красивых положительных чисел $A$ и $B$, сумма которых равна $C$. Поскольку количество пар красивых чисел может быть большим, необходимо вывести остаток от деления этого количества на число $10^9+7$.

Входные данные

Входной файл содержит одно целое положительное число $C$. Число $C$ не начинается с нуля. Количество цифр в записи числа $С$ не превышает $10000$.

Выходные данные

Выходной файл должен содержать одно целое число — остаток от деления количества искомых пар красивых чисел $A$ и $B$ на число $10^9+7$.

Система оценивания

Правильные решения для тестов, в которых 1 ≤ C ≤ 999 (1 ≤ n ≤ 3), будут оцениваться из 25 баллов.

Правильные решения для тестов, в которых 1 ≤ C ≤ 999 999 (1 ≤ n ≤ 6), будут оцениваться из 50 баллов.

Несмотря на выделение отдельных групп тестов для различных длин числа C, на окончательную проверку будут приниматься только решения, правильно работающие для всех тестов из условия задачи.

Пояснения к тестам

Число 22 можно представить в виде суммы двузначных чисел тремя способами: 10 + 12, 11 + 11, 12 + 10. Способ 11 + 11 не подходит, поскольку число 11 не является красивым. Следовательно, ответ для числа 22 равен 2.

Число 200 можно представить в виде суммы трехзначных чисел единственным способом: 100 + 100. Этот способ не подходит, поэтому ответ для числа 200 равен 0.

Число 1000 нельзя представить в виде суммы четырехзначных чисел, поэтому ответ для числа 1000 аналогично равен 0.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

Входные данные

Выходные данные

Входные данные

Выходные данные

Страница: << 51 52 53 54 55 56 57 >> Отображать по:

Выбрано

Отменить

Добавить в контест