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

print5. Клавиатура

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

Со временем клавиатура компьютера изнашивается и клавиши на ней перестают работать. Конечно, некоторое время такую клавиатуру еще можно использовать.
При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие – нет.
Требуется написать программу, определяющую для каких клавиш в процессе заданного варианта эксплуатации клавиатуры будет обнаружена их неработоспособность.
Формат входных данных
Первая строка входного файла содержит целое число `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".
Пример входных и выходных данных

input.txt

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

output.txt

yes
no
no
no
yes
Источник: региональный этап Всероссийской олимпиады по информатике 2008/2009, http://neerc.ifmo.ru/school/

print6. Неправильное сложение

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

Володя написал программу, которая складывает два числа столбиком. К сожалению, он не разобрался, как правильно переносить единицу из одного разряда в следующий. Поэтому программа стала выполняться следующим образом. Сначала она складывает последние цифры обоих чисел и записывает результат, как в случае, если он однозначный, так и в случае, если он двузначный. Затем программа складывает предпоследние цифры обоих чисел и результат сложения приписывает слева к результату предыдущего сложения. Далее процесс повторяется для всех разрядов. Если в одном числе цифр меньше, чем в другом, то программа размещает нули в соответствующих разрядах более короткого числа.
Федя хочет доказать Володе, что его способ сложения не обладает свойством ассоциативности. В частности, Федя утверждает, что существуют три числа, для которых важен порядок, в котором их складывают (при этом разрешается складывать числа в любом порядке, например, можно сначала сложить первое число и третье, а затем прибавить к ним второе). Федя привел даже пример трех таких чисел.
Требуется написать программу, которая поможет Феде и Володе определить, верно ли утверждение, что, складывая заданные три числа в разном порядке, можно получить разные суммы.
Формат входных данных
Входной файл содержит в одной строке три целых числа `a`, `b` и `c` (`1 ≤ a, b, c ≤ 1 000 000`). Все числа в строке разделены пробелом.
Формат выходных данных
В первую строку выходного файла необходимо вывести слово YES, если данные три числа можно сложить разными способами и получить разные суммы. В противном случае, необходимо вывести слово NO.
В последующих строках выходного файла необходимо вывести все возможные суммы, которые можно получить, складывая числа `a`, `b` и `c`. Суммы следует выводить по одной на строке и в порядке их возрастания.
Примеры входных и выходных данных

input.txt

30 239 566

output.txt

YES
7945
71215

input.txt

643 733 553

output.txt

NO
18129
Источник: региональный этап Всероссийской олимпиады по информатике 2008/2009, http://neerc.ifmo.ru/school/

print7. Числа

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

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

input.txt

3 11 2
111

output.txt

3

input.txt

10 9 1
0123456789876543210

output.txt

1

input.txt

1 8 3
9

output.txt

0
Примечание
Решения, работающие только для `k ≤ 9`, будут оцениваться из 70 баллов.
Источник: региональный этап Всероссийской олимпиады по информатике 2008/2009, http://neerc.ifmo.ru/school/

print8. Перестановки

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

Задано множество из `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`, если такой нет.
Примеры входных и выходных данных

input.txt

4 1 2
6 8 3 9

output.txt

3 9 6 8

input.txt

4 4 2
6 8 3 9

output.txt

9 3 6 8

input.txt

4 5 2
6 8 3 9

output.txt

-1
Примечание
Решения, работающие только для `n ≤ 10`, будут оцениваться из 50 баллов.
Источник: региональный этап Всероссийской олимпиады по информатике 2008/2009, http://neerc.ifmo.ru/school/
loading