Задачи личного первенства областной олимпиады школьников по информатике 2004

Дан набор различных натуральных чисел. Будем называть число "простым для заданного набора", если число не делится ни на одно из чисел набора, кроме самого себя.

Во входном файле в первой строке содержится целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество чисел в наборе. Во второй строке файла содержатся `N` различных целых чисел от 1 до 1000000, разделенных пробелами.

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

6
10 5 3 15 6 8

5 3 8

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

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка. Напишите программу, которая по координате `X_0` точки появления капли над землей вычисляет координату X точки соприкосновения капли с землей (`Y\ =\ 0`).

Во входном файле в первой строке содержатся два целых числа через пробел – координата `X_0` точки появления капли (`0\ <\ X_0\ <\ 10000`) и количество отрезков-препятствий `N` (`0\ ≤\ N\ ≤\ 100`). Далее следует `N` строк, каждая из которых содержит четыре разделенные пробелами числа `x_1`, `y_1`, `x_2`, `y_2` – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от 0 до 10000, `x_1\ <\ x2`, `y1\ ≠\ y2`). Отрезки не пересекаются и не соприкасаются.

В выходной файл вывести одно целое число – координату `X` точки соприкосновения капли с землей.

30 4
25 35 40 30
1 32 20 30
33 22 50 29
18 10 33 19

18

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

Во входном файле в первой строке содержатся два целых числа `N` и `K`, где `N` (`1\ ≤\ N\ ≤\ 100`) – количество шпионских групп, а `K` (`1\ ≤\ K\ ≤\ N`) – номер шпионской группы, которой стала известна важная информация. Далее следует `N` строк содержащих по `N` целых чисел от –1 до 100, разделенных пробелами – таблица времени передачи сообщений между группами. В `i`-ой строке `j`-ого столбца стоит время `A_{ij}` передачи сообщения от `i`-ой группы `j`-ой группе. При этом всегда `A_"ii"\ =\ 0` (`1\ ≤\ i\ ≤\ N`). Если `A_{ij}\ =\ -1`, то передать сообщение непосредственно от `i`-ой группы `j`-ой группе невозможно.

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

4 1
0 -1 2 6
2 0 4 1
3 3 0 1
-1 -1 5 0

5
1 3
3 4
3 2

Будем строить бесконечную последовательность цифр следующим образом. Первые три цифры последовательности являются заданными. Очередные цифры последовательности получаем, суммируя три последних цифры в последовательности и приписывая цифры результата к последовательности. Например, цифры 123 дают бесконечную последовательность, начинающуюся с цифр 12361181091010, а 971 – с цифр 971179171715. Полученную последовательность будем считать дробной частью некоторой десятичной дроби (ее целую часть можно считать равной нулю). Напишите программу, которая вводит три первые цифры двух последовательностей и печатает `N`-ую цифру дробной части суммы двух десятичных дробей, соответствующих введенным данным.

Во входном файле в первой строке содержатся первые три цифры первой последовательности, во второй строке – первые три цифры второй последовательности, далее следует одна или более строк, каждая из которых содержит целое число `N_i` (`1\ ≤\ N_i\ <\ 10^100`, `1\ ≤\ i\ ≤\ 20`).

В выходной файл для каждого `N_i` вывести строку, содержащую `N_i`-ую цифру дробной части суммы двух десятичных дробей, соответствующих введенным данным.

123
971
4
7

7
9

Однажды тете Полли в голову пришла мысль сделать дома ремонт. Начать она решила, конечно, с забора. "В прошлый раз ты прекрасно справился с работой", – сказала тетя Полли Тому Сойеру, – "но сейчас модно красить заборы не одним цветом, а несколькими цветами, чтобы получился красивый узор. Вот тебе банки с краской, вот кисточка, вот образец из журнала, как надо покрасить забор".

Том Сойер вышел на улицу и с тоской оглядел огромный забор. Из-за угла появился Билли Гейл с удочкой и ведерком. "Что, старик, работать приходится?" – спросил Билли. Том обернулся. "А ты хотел бы немножко покрасить?" "А что ты мне за это дашь?" Том понял, что Билли – единственный мальчик в городе, который не будет платить за удовольствие покрасить забор. К счастью, у Тома оставалось еще много вещей, полученных за предыдущую покраску забора. "У меня есть бумажный змей, дохлая крыса на веревочке, губная гармоника, ржавый ключ, …" "Хорошо", – прервал его Билли, – "я согласен, но ты будешь отдавать мне одну вещь за каждую непрерывную полосу забора, покрашенную одним цветом". Том решил придумать такой способ покраски забора, чтобы отдать как можно меньше вещей алчному Билли. Например, образец AABBCBBAA можно покрасить тремя полосами. Первый раз макаем кисть в краску A и красим весь забор, получается AAAAAAAAA. Далее макаем кисть в краску B и красим середину забора, получается AABBBBBAA. И последний раз макаем в краску C и красим одну доску в самой середине, получается AABBCBBAA.

В первой строке входного файла содержится число `N` (`1\ ≤\ N\ ≤\ 20`) – количество образцов раскраски. В следующих `N` строках даны образцы раскраски забора. Каждая строка содержит от 1 до 200 прописных латинских букв. Одна буква соответствует одной доске забора. Различные цвета обозначены различными буквами.

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

2
AABBCBBAA
ABCD

3
4