Задачи открытого командного чемпионата 2003

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

Напишите программу, которая по результатам соревнований определит баллы, назначаемые задачам для получения распределения мест, требующегося жюри. Минимальная оценка для задачи – один балл, а максимальная – 200 баллов. Результат, полученный любым местным школьником, должен быть как минимум на один балл больше результата иногороднего школьника.

Во входном файле в первой строке содержится три целых числа, разделенных пробелами – количество задач `K`, количество участников `N` и количество местных участников `M` (`3\ ≤\ K\ ≤\ 8`, `1\ ≤\ M\ <\ N\ ≤\ 100`). Далее следует `N` строк, содержащих по `K` символов + (плюс) и - (минус) – результаты участников, плюс на `i`-й позиции строки означает, что участник решил `i`-ю задачу, а минус – что не решил (`1\ ≤\ i\ ≤\ K`). Первые `M` строк соответствуют результатам местных участников. Все участники решили как минимум по одной задаче.

В выходной файл вывести `K` строк, содержащих по одному целому числу. На `i`-й строке нужно вывести оценку `i`-й задачи (`1\ ≤\ i\ ≤\ K`). Если возможно несколько вариантов, то нужно вывести любой (один) из них. Если оценить задачи требуемым образом невозможно, то в файл вывести одну строку с сообщением IMPOSSIBLE.

4 4 2
-++-
++--
+-++
-+-+

20
40
15
10

На столе разложены по порядку карточки с числами от 1 до `N`. Первоначально все карточки лежат числами вверх. На первом шаге переворачиваются все карточки. На втором шаге переворачивается каждая вторая карточка (т.е. карточки с числами 2, 4, 6 и т.д.). На третьем шаге переворачивается каждая третья карточка (т.е. карточки с числами 3, 6, 9 и т.д.). На `K`-м шаге переворачивается каждая `K`-я карточка. После выполнения `N` шагов некоторые карточки будут лежать числами вверх, а некоторые – числами вниз.

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

Во входном файле содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 2000000000`).

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

10

7

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

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

Во входном файле содержится одна или более строк длиной не более 200 символов, в которых содержится текст, состоящий не более чем из 100000 слов. Количество различных слов в тесте от 10 до 10000. Максимальная длина слов не превышает 20 букв. Текст состоит из латинских букв и знаков препинания. Регистр букв игнорируется. Словом будем называть последовательность прописных и строчных латинских букв ("x-ray" состоит из 2 слов X и RAY, "It's words" состоит из 3 слов IT, S и WORDS).

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

Kill All Humans.
Bite My Shiny Metal Ass.
I was near the scene of another crime at the time, officer.

the
another
officer
humans
crime
metal
scene
shiny
bite
kill

В Американских Соединенных Мистериях (American Connected Mysteries) были запрещены все числа, которые содержат в своей записи три шестерки подряд или число 13. Например, для автомобиля нельзя использовать номер 2666 или 7134, но можно 6266, 7314 или 1734. Напишите программу, которая определяет количество запрещенных чисел среди `K`-значных чисел.

Во вводе содержится одно целое число `K\ (1≤K≤1000)`.

Вывести одно целое число – количество запрещенных чисел среди чисел в диапазоне от `10^{K–1}` до `10^K–1`.

3

20

Эми (далее A) и Бендер (B) играют в следующую азартную игру. Перед началом игры A отдает B `P`$. Затем B бросает монетку. Если выпал орел, B отдает A 1$, и игра заканчивается. Если выпала решка, то B бросает монету во второй раз. Если выпадает орел, то B отдает 2$, иначе бросает монету снова. Если орел выпадает после `N` решек, то B платит A `2^N`$ и игра заканчивается, иначе B продолжает бросать монету, но не более чем `K` раз. Если орел не выпал и после `К` подбрасываний монеты, то игра завершается и B платит A `2^K`$. Определите математическое ожидание выигрыша A. Например, для `P=3` и `K=5` математическое ожидание можно рассчитать следующим образом. Вероятность выпадения орла при первом броске равна `1/2`. При этом выигрыш равен `1-3\ =\ -2`. Если орел выпадет только при втором броске (вероятность этого события равна `1/4`), то выигрыш составит `2-3\ =\ -1`. Аналогично для третьего броска вероятность равна `1/8`, а выигрыш `4-3\ =\ 1`. Для четвертого броска вероятность равна `1/16`, а выигрыш `8-3\ =\ 5`, для пятого: `1/32` и `16-3\ =\ 13`. Вероятность, что пять раз выпадет решка, равна `1/32`, а выигрыш при этом будет равен `32-3\ =\ 29`. Перемножая вероятности и выигрыши и суммируя результаты, получаем математическое ожидание выигрыша `(-2)/2\ +\ (-1)/4\ +\ 1/8\ +\ 5/16\ +\ 13/32\ +\ 29/32\ =\ 0.50`$ (полдоллара).

Во входном файле содержится два целых числа через пробел – `P` и `K` (`1\ ≤\ P\ ≤\ 10^9`, `1\ ≤\ K\ ≤\ 10^9`).

В выходной файл вывести математическое ожидание выигрыша A с двумя десятичными знаками.

3 5

0.50

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

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

Во входном файле содержится одна строка с цифрами от 1 до 9. Длина строки от 1 до 1000 символов.

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

4211311

4311121

На большом складе загорелись несколько бочек с горючими материалами. Пожарные пытаются их потушить. Один пожарный с огнетушителем не может потушить загоревшуюся бочку, он может только контролировать возгорание, не давая огню перекинуться на другие бочки. Несколько пожарных могут справиться с одним возгоранием. Для тушения одной бочки `K` пожарным (`K\ >\ 1`) потребуется `10/K` минут. Тушение бочки происходит равномерно, с постоянной скоростью. Если к тушению очага пожара присоединяется новые пожарные, то время тушения остатков огня вычисляется по формуле `X*10/K`, где `X` – доля очага возгорания, непогашенного за предыдущий период времени, а `K` – новое количество пожарных. Если горящую бочку никто не контролирует, то от огня могут загореться другие бочки. Поэтому возле каждого возгорания должен быть как минимум один пожарный с огнетушителем. Если пожарный приступил к тушению какой-нибудь бочки, то он не отходит от нее, пока она не будет погашена. После завершения тушения он может помочь потушить бочку, которую уже тушат другие пожарные. Также будем считать, что время на переход от одного очага пожара до другого равно 0.

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

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

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

3 4

10.000000

A palindrome is a string of characters which can be read forward and backward and still result in the same word, e.g. "mumdadmum". So by definition the empty string, all strings containing 1 character, and all strings containing 2 equal characters are palindromes. The length of a palindrome is the number of characters in the palindrome.

A palinword is a string of characters that contains at least 2 different palindromes each with a length of at least 3. (Here the position is immaterial: the same palindrome occurring in another position is not considered as different.) Neither of these 2 palindromes may be embedded in the other palindrome (for example the palindrome "mum" is embedded in the palindrome "amuma", and "aaa" is embedded in "aaaa") but they may partially overlap. Also see the examples below.

Your program's task is to copy only the palinwords from the input file to the output file.

The input for your program is a textfile. Each line in this file is empty or consists of one or more words (uppercase letters 'A' through 'Z' only) separated by one or more spaces (each line in the input file contains at most 255 characters in all).

The output file is a textfile and must have one palinword per line in order of occurrence in the input file.

MOEILIJKHEDEN INVOER
VERNEDEREN
AMUMA AMAMA MUMMUM
AMATRAMA AAAA ABATRABAR
DUMMY WORDS

MOEILIJKHEDEN
VERNEDEREN
AMAMA
MUMMUM