#1115

Шкафы

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

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

Региональное отделение одного крупного банка заказало два несгораемых шкафа для хранения личных дел своих клиентов. Каждый шкаф имеет несколько ящиков различной высоты, при просмотре снизу вверх ящики в первом шкафу имеют высоту a₁, a₂, ..., a_m, а ящики во втором шкафу высоту b₁, b₂, ..., b_n.

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

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

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

Первая строка входного файла содержит два целых числа: m и n — количество ящиков в первом и во втором шкафу, соответственно (1 ≤ m, n ≤ 100000). Вторая строка содержит m целых чисел: a₁, a₂, ..., a_m высоты ящиков в первом шкафу. Третья строка содержит n целых чисел: b₁, b₂, ..., b_n — высоты ящиков во втором шкафу. Высоты ящиков положительные и не превышают 10⁹.

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

На первой строке входного файла выведите два числа k и l количество ящиков, которые следует использовать в первом и втором шкафу, соответственно. Сумму k + l вам следует максимизировать. На второй строке выведите k целых чисел номера ящиков в первом шкафу, которые следует использовать. На третьей строке выведите l целых чисел номера ящиков во втором шкафу, которые следует использовать. Если оптимальных решений несколько, выведите любое.

Примеры

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

5 5
1 2 3 4 5
6 4 3 2 1

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

4 3
1 2 3 4 
3 4 5

#1849

Плитки

Темы: [Динамическое программирование по профилю] ["Длинная" арифметика]

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

У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1×1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:

К

С

З

К

З

К

С

(Буквой К обозначена красная плитка, С – синяя, З – зеленая)

После этого Петя заполняет следующую таблицу:

	красный	синий	зеленый
красный	Y	Y	Y
синий	Y	N	Y
зеленый	Y	Y	N

В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали – если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.

Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски.

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

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

С

К

З

К

З

С

К

не совпадает с полоской, приведенной в начале условия.)

Формат входных данных

Первая строка входного файла содержит число N. (1  N  100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична.

Формат выходных данных

Выведите в выходной файл количество полосок длины N, имеющих приведенную во входном файле диаграмму смежности.

Примеры

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

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

10

YYY

YNY

YYN

4596

3

YYY

0

#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

#111824

Спасти котенка

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

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

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

Поле для выполнения задания представляет собой прямоугольник размером $n \times m$ метров, разбитый на квадраты единичной площади. В одном из квадратов исходно находится Артур, в некотором другом квадрате находится котенок. Кроме того, один из квадратов содержит лифт, встав на который вместе с котенком, Артур успешно выполняет задание.

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

Выяснив, сколько шагов ему придется сделать, Артур заинтересовался, сколько существует различных способов дойти до котенка, а затем с ним до лифта, сделав в сумме минимальное число шагов. Помогите ему это выяснить. Это число может быть довольно большим, поэтому Артур просит найти его по модулю $10^9+7$.

Формат входного файла

Первая строка входного файла содержит два натуральных числа $n$ и $m$ - размеры поля для выполнения задания ($2 \le n, m \le 100$).

Вторая строка содержит два целых числа $x_A$ и $y_A$ - координаты квадрата, на котором исходно находится Артур ($1 \le x_A \le n$, $1 \le y_A \le m$). Третья строка содержит два целых числа $x_K$ и $y_K$ - координаты квадрата, на котором сидит котенок ($1 \le x_K \le n$, $1 \le y_K \le m$). Четвертая строка содержит два целых числа $x_E$ и $y_E$ - координаты квадрата, на котором находится лифт ($1 \le x_E \le n$, $1 \le y_E \le m$). Эти три квадрата попарно различны.

Формат выходного файла

В единственной строке выходного файла выведите одно число - число способов дойти до котенка и затем до лифта, не наступая на один квадрат два раза, совершив при этом минимальное количество шагов. Число необходимо вывести по модулю $10^9+7$.

Пояснения к примеру

$\text{[math]}$

Два способа для поля, приведенного в примере.

Примеры

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

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

Страница: << 1 2 3 4 Отображать по:

Выбрано

:

Отменить

|

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