Задачи 2 тура областной олимпиады по информатике 2009

Со временем клавиатура компьютера изнашивается и клавиши на ней перестают работать. Конечно, некоторое время такую клавиатуру еще можно использовать.

При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие – нет.

Требуется написать программу, определяющую для каких клавиш в процессе заданного варианта эксплуатации клавиатуры будет обнаружена их неработоспособность.

Первая строка входного файла содержит целое число `n` (`1\ ≤\ n\ ≤\ 100`) – количество клавиш на клавиатуре. Вторая строка содержит `n` целых чисел – `с_1,\ с_2,\ …\ ,\ с_n`, где `с_i` (`1\ ≤\ с_i\ ≤\ 100\ 000`) – количество нажатий, выдерживаемых `i`-ой клавишей. Третья строка содержит целое число `k` (`1 ≤ k ≤ 100\ 000`) – общее количество нажатий клавиш, и последняя строка содержит `k` целых чисел `p_j` (`1 ≤ p_j ≤ n`) – последовательность нажатых клавиш в процессе эксплуатации клавиатуры.

В выходной файл необходимо вывести `n` строк, содержащих информацию о неисправностях клавиш, обнаруженных в процессе заданного варианта эксплуатации клавиатуры. `i`-ая строка должна содержать слово "yes" (без кавычек), если `i`-ая клавиша сломалась, иначе слово "no".

5
1 50 3 4 3
16
1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5

yes
no
no
no
yes

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

Федя хочет доказать Володе, что его способ сложения не обладает свойством ассоциативности. В частности, Федя утверждает, что существуют три числа, для которых важен порядок, в котором их складывают (при этом разрешается складывать числа в любом порядке, например, можно сначала сложить первое число и третье, а затем прибавить к ним второе). Федя привел даже пример трех таких чисел.

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

Входной файл содержит в одной строке три целых числа `a`, `b` и `c` (`1 ≤ a, b, c ≤ 1 000 000`). Все числа в строке разделены пробелом.

В первую строку выходного файла необходимо вывести слово YES, если данные три числа можно сложить разными способами и получить разные суммы. В противном случае, необходимо вывести слово NO.

В последующих строках выходного файла необходимо вывести все возможные суммы, которые можно получить, складывая числа `a`, `b` и `c`. Суммы следует выводить по одной на строке и в порядке их возрастания.

30 239 566

YES
7945
71215

643 733 553

NO
18129

Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел таких, что если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа смогла вывести не произвольные числа, а только те, что не превосходят `C` и не имеют ведущих нулей.

Чтобы ответить на поставленный вопрос, Вова решил написать программу, которая позволит ему найти число различных последовательностей неотрицательных целых чисел, в каждой из которых любое число не превосходит `C`. Он понимал, что такое число могло быть достаточно большим, поэтому ограничился поиском только последних `k` цифр этого числа.

Требуется написать программу, которая покажет Вове, как можно правильно решить поставленную им задачу.

Первая строка входного файла содержит три целых числа – `n`, `C` и `k` (`1 ≤ n ≤ 50\ 000`, `1 ≤ C ≤ 10^8`, `1 ≤ k ≤ 18`). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из `n` цифр.

В выходной файл выведите последние `k` цифр искомого количества последовательностей без ведущих нулей.

3 11 2
111

3

10 9 1
0123456789876543210

1

1 8 3
9

0

Решения, работающие только для `k ≤ 9`, будут оцениваться из 70 баллов.

Задано множество из `n` различных натуральных чисел. Перестановку элементов этого множества назовем `k`-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее `k`. Например, если задано множество элементов `S\ =\ {6,\ 3,\ 9,\ 8}`, то перестановка `{8,\ 6,\ 3,\ 9}` является 2-перестановкой, а перестановка `{6,\ 8,\ 3,\ 9}` – нет.

Перестановка `{p_1,\ p_2,\ …,\ p_n}` будет лексикографически меньше перестановки `{q_1,\ q_2,\ …,\ q_n}`, если существует такое натуральное число `i` (`1\ ≤\ i\ ≤\ n`), для которого `p_j\ =\ q_j` при всех `j\ <\ i` и `p_i\ <\ q_i`.

В качестве примера упорядочим все `k`-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества `S`: `{3,\ 9,\ 6,\ 8}`, `{8,\ 6,\ 3,\ 9}`, `{8,\ 6,\ 9,\ 3}` и `{9,\ 3,\ 6,\ 8}`. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество `{3,\ 9,\ 6,\ 8}`, а четвертой – множество `{9,\ 3,\ 6,\ 8}`.

Требуется написать программу, позволяющую найти `m`-ую `k`-перестановку в этом порядке.

Входной файл в первой строке содержит три натуральных числа – `n` (`1 ≤ n ≤ 16`), `m` и `k` (`1 ≤ m, k ≤ 10^9`). Вторая строка содержит `n` различных натуральных чисел, не превосходящих `10^9`. Все числа в строках разделены пробелом.

В выходной файл необходимо вывести `m`-ую `k`-перестановку заданного множества или `-1`, если такой нет.

4 1 2
6 8 3 9

3 9 6 8

4 4 2
6 8 3 9

9 3 6 8

4 5 2
6 8 3 9

-1

Решения, работающие только для `n ≤ 10`, будут оцениваться из 50 баллов.