.RU

Код программы: a := a xor B; b := a xor B; a := a xor B; Разобраться в ней не так уж сложно. Задача g6 1002: Трамвайные билеты - страница 5


Задача g6_1054: Автобусный диспетчер (XIV Всероссийская олимпиада по информатике)

На кольцевом маршруте №54 протяженностью S, проходящем мимо пансионата "Энергетик", работает N автобусов. Автобусы пронумерованы числами от 1 до N в порядке их следования по маршруту. Автобус с номером 1 движется за автобусом с номером N. Расписание составлено таким образом, что автобусы движутся с одинаковой скоростью V0 и с равными интервалами между ними. Движение автобусов контролирует диспетчер.
В 12 часов дня некоторые K автобусов одновременно снимаются с маршрута и отправляются на обед. Для восстановления равенства интервалов между автобусами, продолжающими движение по маршруту, потребуется некоторое время Т и, возможно, изменение скорости некоторых автобусов по команде диспетчера. В течение этого времени автобусы должны двигаться с постоянными скоростями из интервала [Vmin, Vmax], назначенными диспетчером. Изменение скорости движения автобуса происходит мгновенно. По истечении времени Т автобусы возобновляют движение по маршруту со скоростью V0.
Требуется написать программу для автоматического диспетчера, которая вычисляет минимальное время Tmin, за которое интервалы движения между оставшимися автобусами станут равными, и скорости движения каждого из них в течение этого времени.

Входные данные
Входной файл bus.in содержит две строки.
В первой строке находятся натуральные числа N, К, S, Vmin, Vmax и V0, где K < N <= 10000, S <= 10000, Vmin < Vmax <= 10000, Vmin <= V0 <= Vmax.
Во второй строке расположены в порядке возрастания K чисел - номера автобусов, снятых с маршрута. Все данные в строках разделены пробелами.

Выходные данные
В первой строке выходного файла bus.out должно находиться значение Tmin.
В каждой из последующих N - K строк должны быть по два разделенных пробелом числа - номер автобуса на маршруте и скорость его движения в течение времени Tmin. Номера автобусов упорядочить по возрастанию. Значения Tmin и скоростей выводить с точностью до 4-х значащих цифр после десятичной точки.

Пример 1
Входной файл bus.in
4 1 60 21 70 60
3
Выходной файл bus.out
0.2041
1 45.5
2 21
4 70

Пример 2
Входной файл bus.in
4 2 40 30 80 50
2 4
Выходной файл bus.out
0
1 50
3 50

Решение g6_1054: предоставлено С.В. Густокашиным

При решении этой задачи не обошлось без пеньков, о которые я споткнулся, ну а число этих пеньков, как обычно - роковое: три.
Начну со второго, как наиболее крупного и наиболее часто встречающегося. Когда программа уже отлажена и начинаю сверять решение с контрольным примером - числа сходятся, но их порядок другой. Недоумение, поиск ошибок в алгоритме - ничего.
Читаю задачу близким, убеждаю их, что ответы должны идти именно в таком порядке, а иначе автобусы должны ехать задом наперед и тут при очередном прочтении условия осеняет - О, Боже!
Они действительно едут не первый за вторым, второй за третьим и т.д., а второй за первым, третий за вторым и т.д. А это значит мною была невыполнена первая заповедь: внимательно читать условие задачи и не додумывать того, чего нет. Да и рисунки делать только сверяясь с каждым предложением задачи, я ведь нарисовал колечко и написал номера автобусов, только номера-то надо было подписывать согласуясь с условиями, а не просто используя стандартный числовой ряд - 1, 2, 3, 4. Теперь сам разбор и по ходу об остальных "граблях".
Из чего исходим: автобус, проезжающий за время TMin самый длинный путь должен иметь скорость VMax. Значит определив самый длинный путь и имея VMax из условия задачи можно рассчитать TMin. Ну, а имея время и пройденные пути за это время для других автобусов, определить скорости не составит труда.

До определения пройденных путей за время TMin сначала определим расстояния между автобусами после снятия некоторых из них с маршрута. Заодно совместим эту процедуру с запоминанием номеров оставшихся автобусов:

J:= N - K + 1;

for I:= N downto 1 do

if M[I] = 0 then inc(MDist[J])

else begin dec(J); MDist[J]:= 1; MNum[J]:= I; end;

MDist[1]:= MDist[1] + MDist[N - K + 1];

Необходимо отметить, что расстояние между оставшимися автобусами MDist[J] рассчитываем как число первоначальных интервалов между автобусами. Это первый пенек, о который я споткнулся. Сначала, не мало сумняшись, был объявлен массив MDist: array[1..10000] of real; и расчет реального расстояния, возникшего между автобусами. Понятно, что Turbo Pascal 7.0 такого громадного массива вкупе с другими (M[I] и MNum[J]) не потянул, потому появилось объявление MDist: array[1..10000] of integer; и подсчет расстояния в виде числа первоначальных интервалов между автобусами. (этой проблемы можно избежать, если использовать компилятор FreePascal)
Далее привожу текст расчета минимального времени.
Исходим из того, что первый автобус неподвижен (едет с минимальной скоростью), и рассчитываем пути пройденные остальными автобусами, запоминая максимальный и минимальный, чтобы в конце по полученным значениям рассчитать время.

MaxWeg:= 0; MinWeg:= 0; D:= 0; Flag:= false; T:= 0; VVV:= V0;

for I:= 2 to N - K do begin

Work:= MDist[I] * FInt - LInt + D;

if abs(Work) < 5.E-10 then Work:= 0;

if Work MaxWeg then Flag:= true;

if Work > MaxWeg then MaxWeg:= Work;

if Work < MinWeg then MinWeg:= Work;

D:= Work;

end;

Теперь определяем время и скорость первого автобуса.

if Flag then begin

T:= (MaxWeg - MinWeg)/(VMax - VMin); VVV:= -MinWeg/T + VMin;

end;

writeln(Out, T:1:4); writeln(Out, MNum[1], ' ', VVV:1:4);

Последнее усилие:

D:= 0;

for I:= 2 to N - K do begin

Work:= MDist[I] * FInt - LInt + D;

if Flag then VVV:= (Work - MinWeg)/T + VMin;

writeln(Out, MNum[I], ' ', VVV:1:4);

D:=Work;

end;

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

if abs(Work) < 5.E-10 then Work:= 0;

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


Задача g6_1055: Кубики (XV Всеукраинская олимпиада по информатике)

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

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

Входные данные
В первой строке входного файла CUBES.DAT находятся три числа N, M и К, которые задают размеры проекций (1 < N, M, K < 100). Дальше задаются две проекции: сначала фронтальная, а затем правая. Проекция задается N строками, каждая из которых состоит из чисел 0 и 1, разделенных пробелами. Для фронтальной проекции таких чисел будет M, а для правой - K. 0 означает свободную клетку проекции, 1 - заполненную.

Пример входных данных
2 2 3
1 0
1 1
0 0 1
1 1 1

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

Пример выходных данных
4 7

Решение g6_1055:
Сейчас я начал активные тренировки на украинских задачках. К ним прилагаются тесты, так что вы сможете проверить, насколько верно вы решили ее.
Разобьем изображения фигуры на вертикальные слои. Для нижнего слоя получим:
11 - вид спереди, 111 - вид справа.
Для минимального количества кубиков вид сверху будет выглядеть так:

100

010

001

а для максимального так:

111

111

111

Для того чтобы найти минимальное количество кубиков в слое достаточно среди количества кубиков во фронтальной и боковой проекции выбрать наибольшее. Действительно, если во фронтальной проекции лежит 4 кубика, а в боковой - 3, то мы можем выстроить 4 кубика так, что фронтальная проекция будет состоять из 4 кубиков, а боковая из 3. Если фигура имеет разрывы, то это никак не влияет на такое предположение. Пример для фронтальной проекции - 4(11101), боковой - 3(10101).

10000

00000

01100

00000

00001

Как видно, здесь фигура проецируется в 11101 и 10101. Теперь посчитаем максимум для данных проекций.
Если во фронтальной проекции на некоторой позиции стоит 1, то 1 могут быть заняты все клетки, кроме тех, которые соответствуют 0 в боковой проекции. Т.е. для одной единицы во фронтальной проекции получаем наибольшее количество блоков RB (кол-во единиц в боковой проекции), а так как у нас FB (кол-во единиц во фронтальной проекции) рядов, то максимальное кол-во блоков для слоя RB * FB. Чтобы посчитать максимальное количество блоков для всей фигуры достаточно просто сложить произведения RB на FB для всех слоев.
Технически это реализуется с помощью двух одномерных массивов, с номерами от 1 до n. В первом из них будет храниться количество элементов фронтальной и боковой проекции.


Задача g6_1056: Многоугольники (XV Всеукраинская олимпиада по информатике)

На плоскости задано такое множество из N многоугольников, что выполняются следующие условия:

1) никакие два многоугольника не имеют общих точек;
2) для каждого i-го многоугольника существует Pi многоугольников, внутри которых он находится, и N-1-Pi многоугольников, которые находятся внутри его, 0 < Pi < N-1.

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

Входные данные
Первая строка входного файла POLYGON.DAT содержит целое число N - количество многоугольников, 3 < N < 10000. Следующие N строк файла описывают N многоугольников. (i+1)-ая строка файла описывает i-ый многоугольник. Первое целое число Ci- количество вершин многоугольника, 3?Ci?20. Последующие Ci пар чисел - координаты вершин многоугольника в порядке его обхода. Координаты вершин - целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.

Пример входных данных
3
3 -2 1 8 9 12 1
3 7 5 6 3 7 4
4 4 3 7 7 9 3 1 2

Выходные данные
Единственная строка выходного файла POLYGON.SOL должна содержать N чисел: i-ое число строки должно быть Pi- количество многоугольников, внутри которых находится i-ый многоугольник.

Пример выходных данных
0 2 1

Решение g6_1056:
Когда я первый раз увидел эту задачу, то подумал что она геометрическая и огорчился (не люблю геометрические задачи, хуже них только задачи с графами). Но нет, нет геометрии в этой задаче.
Многоугольники не имеют общих точек. Очень важное условие.
Заведем массив, в который для каждого многоугольника запишем его крайнюю правую координату (можно записать любую другую "самую", но мы разберем случай с правой координатой). Это самая правая точка многоугольника. Естественно, что у самого большого многоугольника самая правая точка будет лежать правее самых правых точек всех остальных многоугольников. Если бы это было не так, то многоугольники имели бы точки пересечения, что противоречит условию.
Техническая реализация: Следует завести два массива, в один из которых записать координаты самых правых точек многоугольника (только координату по X, ту что отвечает за "правость"), а в другой - номера многоугольников. Затем отсортируем по убыванию массив правых координат с помощью быстрой сортировки (она есть в примерах А.Н. Никитина) вместе с элементами массива координат перемещая элементы массива номеров многоугольников. После того как массив отсортирован, заполним его элементы с правой координатой значениями, соответствующими номеру этого элемента - 1 (т.е. 0, 1, 2...). Теперь в этом массиве хранится число многоугольников, которые окружают данный многоугольник. Теперь с помощью другой процедуры быстрой сортировки отсортируем массив номеров по возрастанию, перемещая соответствующие элементы "правого" массива. Это делается для ускорения вывода, чтобы не искать каждый раз элемент в массиве заново.
Теперь просто идя по "правому" массиву от 1 до количества многоугольников выводим значения - это и есть количество окружающих многоугольников.

Задача g6_1057: Электронная почта (XIII Всеукраинская олимпиада по информатике)

Пользователь сети Интернет подписан на несколько разных списков рассылки, которые высылают ему по электронной почте сообщения на определенные темы. Для удобства пользователь создал себе набор папок, каждая из которых соответствует одной из тем. Перед тем, как читать сообщения он копирует их в соответствующую папку.
Почтовая программа, установленная на компьютере пользователя, позволяет за одну "операцию" переносить из "списка новых сообщений" в соответствующую папку:
- Одно сообщение из любого места списка
- Несколько сообщений, идущих в списке подряд, и относящихся к одной теме
Переносить можно не обязательно начиная с начала "списка новых сообщений". Пользователю необходимо перенести все новые сообщения в соответствующие им папки за наименьшее количество операций.
Пример. Пусть пользователь подписан на рассылки анекдотов, веселых историй, спортивных новостей и прогноза погоды. Пусть "список новых сообщений" при некотором вхождении в почтовую программу имел следующий вид: (Анекдоты, Спортивные новости, Прогноз погоды, Спортивные новости, Веселые истории, Веселые истории, Спортивные новости)

Список папок Список новых сообщений

1 Анекдоты 1 Анекдоты

2 Веселые истории 3 Спортивные новости

3 Спортивные новости 4 Прогноз погоды

4 Прогноз погоды 3 Спортивные новости

2 Веселые истории

2 Веселые истории

3 Спортивные новости

Переносить сообщения в папки он может следующим образом: сначала два сообщения на тему "Веселые истории". Тогда он получит следующий список: (Анекдоты, Спортивные новости, Прогноз погоды, Спортивные новости, Спортивные новости). Потом перенести сообщения о прогнозе погоды, после этого "Анекдоты", а потом, одновременно, все три сообщения о спортивных новостях. На это он потратит 4 "операции".
Задание: Напишите программу EMAIL которая будет вычислять минимальное количество "операций", с помощью которых можно перенести все новые сообщения в папки. Для удобства каждой теме присваивается номер.
Входные данные: Единственная строчка входного файла EMAIL.DAT содержит число N (0 < N < 200), отвечающее количеству новых сообщений и N целых чисел, которые соответствуют сообщениям, и являются номерами тем, которым эти сообщения принадлежат.

Пример входных данных
7 1 3 4 3 2 2 3

Выходные данные В первой строке выходного файла EMAIL.SOL должно находиться минимальное число операций для данных, приведенных во входном файле.

Пример выходных данных
4

Решение g6_1057:
Несмотря на жестокий насморк я продолжаю активно тренироваться :)
Итак, мы можем переносить несколько стоящих подряд сообщений за одно действие. Это единственное, что может уменьшить общее количество операций. Этим обстоятельством можно воспользоваться сразу при вводе данных. Например, если мы встречаем сообщение на ту же тему что и предыдущее, то не записываем его в массив. Технически это реализуется с помощью цикла while, который рабоет до тех пор, пока счетчик не достигнет значения, равного количеству сообщений. Если нам встретилось сообщение, такое же, как предыдущее, то уменьшим счетчик и количество сообщений на 1 (в итоге счетчик останется неизмененным).
Теперь нам следует создать массив указателей на следующий элемент с таким же номером. Каждый элемент должен ссылаться на такой же элемент, стоящий справа от него, или содержать 0, если такого элемента справа не существует.
Теперь начинается настоящая хитрость: эта задача решается методом динамического программирования очень красиво, так красиво, что я еще никогда не видел такого красивого решения этим часто используемым способом. Заведем массив размером 200*200. Координатой по горизонтали пусть будет номер левого элемента, а по вертикали - правого. В ячейке массива будет храниться значение, сколько операций необходимо осуществить, чтобы перетащить все сообщения от левого до правого.
Как же заполнять этот массив? Логично, что для переноски одного сообщения необходима ровно одна операция, т.е. главная диагональ будет заполнена 1. Также мы знаем, что в силу особенностей ввода информации у нас не может стоять подряд два сообщения с одной тематикой, т.е. на перетаскивание двух подряд идущих сообщений нам потребуется две операции.
А вот теперь самое интересное.
Если сообщений больше чем два, то следует рассматривать все гораздо хитрее. Допустим, что оказалось так, что правое и левое сообщение имеют одну и ту же тему, тогда:
Значение массива A[l, r] (здесь A - динамически подсчитываемый массив, l и r - левая и правая границы) равно A[l + 1, r - 1] + 1, т.е. мы можем растащить все сообщения между ними и они станут рядом и вытащатся за одну операцию! Но может оказаться, что мы можем растащить A[l, r] еще быстрее. Обратим внимание на наш массив указателей на следующий аналогичный элемент NEXT. А что если между этими одинаковыми элементами есть еще такие же (т.е. NEXT[l] R)? Тогда найдем все элементы x = NEXT[x] (первоначально x = l), пока x нее станет равно r. Тогда есть два варианта: если A[l, r] < A[l, x - 1] + A[x, r], то A[l, r] := A[l, x - 1] + A[x, r], т.е. может быть нам выгоднее растащить группу от x до r (элементы с номерами x и r равны, количество операций уже посчитано). Еще есть вариант, что нужно растащить группу, как две группы: от l до x и от x + 1 до r (значения также посчитаны). Мы будем изменять x, пока x не станет равно r.
Теперь рассмотри вариант, если сообщения с номерами l и r имеют разные темы. Растаскивание такого сообщения можно представить как A[l, r] = min(A[l + 1, r], A[l, r - 1]) + 1, т.е. мы перетаскиваем соседнюю группу сообщений и, затем, отдельно сообщение, которое в эту группу не входит. Но в промежутке от l до r могут встретиться сообщения, с такой же темой как у l. Это мы можем использовать. x = NEXT[x], первоначально x = l. Условие выхода из цикла - если NEXT[x] = 0, т.е. больше таких элементов не встречается, или NEXT[x] > r, т.е. эти элементы больше не встречаются на интервале [l, r]. A[l, r] = min(A[l, r], A[l + 1, x - 1] + A[x, r]) для каждого x. Т.е. мы пытаемся из группы, например 3, 4, 2, 3, 6, 7 вытащить сначала элементы 3, 4, 2, 3, а затем, отдельно, 6 и 7.
Технически это реализуется так: сначала заполняется главная диагональ массива A[l, l] единицами, затем A[l, l + 1] = 2 (два подряд разных сообщения), а затем запускается процедура динамического подсчета с параметрами (1, 3), (2, 4), (3, 5), ..., (1, 4), т.е. сначала проходяться все интервалы длиной 3, затем 4 и т.п. Окончательным ответом будет значение в ячейке A[1, n], т.е. левая граница 1, а правая - количество сообщений.

Задача g6_1058: Автобус (XIII Всеукраинская олимпиада по информатике)

Служебный автобус совершает один рейс по установленному маршруту и в случае наличия свободных мест подбирает рабочих, которые ожидают на остановках, и отвозит их на завод. Автобус также может ждать на остановке рабочих, которые еще не пришли. Известно время прихода каждого рабочего на свою остановку и время проезда автобуса от каждой остановки до следующей. Автобус приходит на первую остановку в нулевой момент времени. Продолжительность посадки рабочих в автобус считается нулевой.
Задание: Написать программу BUS, которая определит минимальное время, за которое автобус привезет максимально возможное количество рабочих.
Входные данные: Входной текстовый файл BUS.DAT в первой строке содержит количество остановок N и количество мест в автобусе M. Каждая i-я строчка из последующих N строчек содержит целое число - время движения от остановки _ к остановке i+1 (N+1-я остановка - завод), количество рабочих K, которые придут на i-ю остановку, и время прихода каждого рабочего на эту остановку в порядке прихода (1 <= M <= 2000, 1 <= N,K <= 200000).
Пример входных данных.
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Выходные данные: Единственная строка выходного текстового файла BUS.SOL должен содержать минимальное время, необходимое для перевозки максимального количества рабочих.
Пример выходных данных.
4

Решение g6_1058:
Мой насморк вроде бы прекратился (на спрее было написано, что надо брызгать 2 раза в каждую ноздрю 2 раза в день, а я брызгал по 6-8 раз 4-5 раз в день).
Теперь, собственно, решение. Сначала определим, что такое максимально возможное количество рабочих. Если общее количество рабочих больше вместимости автобуса, то это - объем автобуса, если же рабочих меньше чем вместимость автобуса - то это количество всех рабочих (в этом случае вместимости автобуса уместно присвоить значение, равное количеству людей).
Задачу надо решать с помощью двоичного поиска (бинарного поиска, дихотомии). А лучше с помощью двух двоичных поисков.
Когда мы считываем данные, следует определить время прихода последнего человека (т.е. то время, когда уже все люди будут на остановках) - это будет максимум в двоичном поиске. Минимум будет равен нулю. Если автобус должен задержаться перед остановкой, то он должен сделать это перед первой остановкой (действительно, если он подъедет к первой остановке, заберет людей, а потом будет ждать у второй остановки, то в это время на первую могут придти еще люди, а если ждать перед первой, то люди со второй никуда не денутся). Минимум и максимум у нас есть. Теперь берем задержку, равную x = (min + max) / 2. С помощью процедуры, которая будет описана ниже, вычисляем, сколько людей успеет придти до момента x на первую остановку, для второй остановки будет задержка, равная x + a[1], где a[1] - время следования от первой остановки до второй, для третьей задержка - x + a[1] + a[2] и т.д. Если количество севших в автобус на всех остановках больше либо равно вместимости автобуса, то надо заменить x на (min + x) / 2, если остались места в автобусе то x = (x + max) / 2. Условие выхода будет такое: если при некоторой задержке x автобус заполнен, а при задержке (x - 1) автобус не полон, то ответ x.
Теперь вторая дихотомия. Та самая, которая определяет, сколько людей успеет придти на определенную остановку до определенного момента. Здесь максимумом дихотомии будет количество людей на остановке, а минимумом - ноль. Выбираем среднего человека - если его время прихода меньше, чем задержка, то x = (x + max) / 2, если он не успеет придти, то x = (min + x) / 2. Здесь условие выхода такое: если человек успевает придти на остановку, а следующий за ним нет - то ответом будет номер человека. Отдельно нужно обрабатывать случай, если на автобус сядут все люди с остановки.

Задача g6_1059: Электронные часы (II Всероссийская командная олимпиада по информатике)

Циферблат новых электронных часов, установленных на главном здании офиса фирмы Macrohard, состоит из 4 прямоугольных панелей, каждая из которых состоит из 6 рядов по 5 лампочек в каждом. Первые две панели отображают цифры, из которых складываются часы, а следующие две - минуты. (Если сейчас меньше 10 часов, первая панель отображает 0).
К сожалению, лампочки, установленные на панелях, были произведены компанией Sveta.Net, которая известна своим принципом "раньше перегорит - больше спрос", вследствие чего на следующий день люди, проходя мимо офиса компании, видели лишь некоторое подобие цифр, поскольку некоторые лампочки больше не горели.
Петя живет в доме, стоящем прямо напротив офиса компании Macrohard. В первый день после установки часов он зарисовал у себя в блокноте, как выглядят все цифры на панелях (панели однотипные, поэтому одна и та же цифра на различных панелях выглядит одинаково). Теперь Петя хочет узнать, можно ли по текущему изображению на часах однозначно определить, сколько сейчас времени. Помогите ему!
Формат входных данных
При тестировании этой задачи в каталоге, который будет текущим, когда будет запущена Ваша программа, будет находиться два файла. Файл digits.txt содержит 6 строк по 50 символов в каждой. Он будет одинаковым для всех тестов и будет совпадать с приведенным в примере. Вы также можете найти этот файл в каталоге o:\common. Содержимое файла digits.txt задает правильное написание цифр на панелях (первый прямоугольник символов задает число 0, следующий - 1, и т. д. до 9). Не горящая лампочка обозначается символом "." (точка), а горящая - "#" (диез).
Входной файл input.txt содержит 6 строк по 20 символов в каждой - текущее изображение на часах. Первый прямоугольник задает первую панель, следующий - вторую, следующий - третью и последний - четвертую.
Формат выходных данных
Если можно точно определить время, которое сейчас отображается на часах, выведите это время в формате hh:mm. Если время нельзя определить однозначно, выведите AMBIGUITY. Если же в часах точно сломалось еще что-то, например центральный процессор, который управляет лампочками, выведите ERROR.
Примеры
digits.txt

..##.....#..##..####.#..#.####..###.####..##...##.

.#..#...##.#..#....#.#..#.#....#.......#.#..#.#..#

.#..#..#.#....#...#..#..#.###..###....#...##..#..#

.#..#....#...#.....#.####....#.#..#..#...#..#..###

.#..#....#..#......#....#.#..#.#..#..#...#..#....#

..##.....#.####.###.....#..##...##...#....##..###.


input.txt output.txt

..##..####.#..#.#### 23:45

....#....#..........

....#...#..#..#.###.

...#.....#.##......#

..#......#....#.#..#

.####..##.....#..#..


#.##.....#..##..#### ERROR

.#..#...##.#..#....#

.#.....#......#...#.

.#..#..............#

.#..#.......#......#

..##.....#.####.....


..##........##..#### AMBIGUITY

.#..#....#.#..#....#

.#............#...#.

.#..#..............#

.#..#.......#......#

..##.......####.....


Решение g6_1059: Предоставлено Андреем Станкевичем
Введем понятие "символ" как массив размера 6x5, в котором 1 соответствует горящей лампочке, а 0 - не горящей. Для двух символов A и B введем понятие их пересечения как массив C=A*B, где c[i][j] =a[i][j]*b[i][j]. Тогда верно следующее утверждение: чтобы символ A мог быть цифрой i, должно выполняться A*Di=A, где Di - символ, соответствующий каноническому написанию цифры i.
Помня также, что время лежит в диапазоне 00:00-23:59, получаем следующий алгоритм решения задачи: для каждого возможного времени проверить, может ли оно быть отображено сейчас на табло (для этого каждую цифру на табло надо сравнить с соответствующей канонической цифрой). После этого: если ровно одно время может быть отображено на табло, то это и есть ответ, если более чем одно, то ответ AMBIGUITY, в если ни одно время не подошло, то ответ ERROR.
Программа
Приведем процедуру проверки, что символ a может быть цифрой, содержащейся в символе b (в реализации для простоты не будем заменять . на 0, а # на 1, а оставим как есть):

type

tdigit = array [1..6, 1..5] of char;


function check(a, b: tdigit): boolean;

var

i, j: longint;

begin

check := false;

for i := 1 to 6 do

for j := 1 to 5 do

if (a[i][j] = '.') and (b[i][j] = '#') then

exit;

check := true;

end;

Теперь проверяем, какое время может быть на табло: часы и минуты, и выводим ответ:

for i := 0 to 23 do

begin

if can[1][i div 10] and can[2][i mod 10] then

begin

inc(ch);

hh := i;

end;

end;


cm := 0;

for i := 0 to 59 do

begin

if can[3][i div 10] and can[4][i mod 10] then

begin

inc(cm);

mm := i;

end;

end;

if (ch = 0) or (cm = 0) then

begin

writeln('ERROR');

end

else if (ch = 1) and (cm = 1) then

begin

writeln(hh div 10, hh mod 10, ':',

mm div 10, mm mod 10);

end else begin

writeln('AMBIGUITY');

end;


Задача g6_1060: Дождик (XIV Всероссийская олимпиада по информатике)

В НИИ метеорологии решили изучить процесс образования водоемов на различных рельефах местности во время дождя. Ввиду сложности реальной задачи была создана двумерная модель, в которой местность имеет только два измерения - высоту и длину. В этой модели рельеф местности можно представить как N-звенную ломаную c вершинами (x0, y0), ..., (xN, yN), где x0 < x1 < ... < xN и yi  yj, для любых i j. Слева в точке x0 и справа в точке xN рельеф ограничен вертикальными горами огромной высоты.
Если бы рельеф был горизонтальным, то после дождя вся местность покрылась бы слоем воды глубины H. Но поскольку рельеф - это ломаная, то вода стекает и скапливается в углублениях, образуя водоемы.
Требуется найти максимальную глубину в образовавшихся после дождя водоемах.

Входные данные
В первой строке файла rain.in расположены натуральное число N (1 <= N <= 100) и H - действительное число, заданное с тремя цифрами после десятичной точки (0 <= H <= 10 в 9 степени). В последующих N + 1 строках - по два целых числа xi, yi: -10000 <= xi, yi <= 10000 (0 <= i <= N).
Числа в строках разделены пробелами.

Выходные данные
Выходной файл rain.out должен содержать единственное число - искомую глубину с точностью до 4-х знаков после десятичной точки.

Пример
Входной файл rain.in
7 7.000
-5 10
-3 4
-1 6
1 -4
4 17
5 3
9 5
12 15
Выходной файл rain.out
15.8446

Решение g6_1060: предоставлено С.В. Густокашиным
Начнем с того, что добавим две крайних точки. Координата X первой точки совпадет с координатой x0, координата X последней - с координатой xN. Координаты Y дополнительных точек зададим заведомо больше возможной высоты слоя воды 100010000.
Запомним координаты Y и номера точек вершин и низин. Вершиной будем считать ту точку, для которых координаты Y соседних точек слева и справа меньше. Естественно за низину - ту, у которой координаты Y соседних точек слева и справа больше.
Да, крайние, искусственно добавленные точки, причислим к вершинам.
Таким образом, у каждой низины будет две соседних вершины. Рассчитаем "объем" (площадь) воды первоначально попадающей в низину как разность координат X соседних вершин умноженную на H.
При этом, не обращаем внимание на возможный переизбыток воды - наливаем "с горкой", потом разберемся с излишками.
Каждой вершине и низине поставим в соответствие "принадлежащие ей трапеции" и рассчитаем их площади. Координаты трапеций для низин начинаем с рассмотрения ближайших точек слева и справа. Естественно первая трапеция - вырожденная и представляет собой треугольник. Двигаемся до тех пор, перебирая координаты соседних точек слева и справа и рассчитывая площади трапеций, пока одна из точек не совпадет с координатой одной из вершин.
Координаты трапеций для вершин начинаем с рассмотрения ближайших точек слева и справа, координаты Y которых больше координаты вершины. Движемся от найденных точек влево и вправо до тех пор, пока одна из точек не совпадет с координатой одной из вершин.
После таких действий все рабочее поле должно быть разбито на трапеции, принадлежащие вершинам и низинам, и для каждой вершины и низины будет рассчитана ее площадь как сумма площадей принадлежащих ей трапеций.
А теперь закрутим бесконечный цикл "переливов" с двумя внутренними циклами просмотра низин.
Первый цикл назовем "перелив влево" с просмотром низин справа налево.
Если "объем" воды в низине больше ее собственного "объема" и координата Y вершины слева меньше координаты Y вершины справа, то убавляем "объем" воды, принадлежащей низине до ее собственного "объема", а излишек добавляем низине слева.
По окончании "перелива влево" запускаем цикл "перелива вправо" с "поглощением". Просмотр низин ведем слева направо. Условия перелива похожи, если "объем" воды в низине больше ее собственного "объема" и координата Y вершины справа меньше координаты Y вершины слева, то убавляем "объем" воды, принадлежащей низине до ее собственного "объема", а излишек добавляем низине справа. Если после перелива мы видим, что координата Y правой вершины меньше координаты Y следующей вершины справа, то производим "поглощение". Т.е. мы имеем случай, когда две низины с вершиной между ними зажаты между более высокими вершинами и обе низины полны.
Оставляем более глубокую низину, присваиваем ей "объем" "поглощаемой" вершины, а объем воды в преобразившейся низине будет составлять получившийся излишек при переливании. Набор трапеций "поглощенной" вершины также будет принадлежать теперь оставшейся низине. Устанавливаем флаг, что было "поглощение" чтобы после продолжить бесконечный цикл "переливов".
Если при очередном проходе не будет ни одного "поглощения", значит можно закончить бесконечный цикл "переливов" и приступать к определению самой глубокой из оставшихся низин.
Для каждой низины у нас имеется координата Y, "объем" воды и набор трапеций, принадлежащих низине. Для каждой трапеции, проверяем, залита ли она полностью и если да, то просто добавляем ее высоту к расчетной высоте воды в низине. Если трапеция залита не полностью, рассчитываем высоту воды исходя из ее "объема" в трапеции.
После просмотра всех оставшихся низин определяем самую глубокую низину.
При решении задачи возникла у меня небольшая проблема при расчете высоты воды между искусственными крайними вершинами, поскольку это вырожденная трапеция - прямоугольник. Выскочила ошибка "деление на ноль", но, я думаю, зная об этом, вы правильно решите вырожденное квадратное уравнение.
Разбор получился несколько затянутым, но задача того стоит, не обессудьте.
А теперь, самое интересное: вначале предполагалась другая задача, в которой координаты Y точек могут быть равны, а координаты X могут быть произвольны, т.е. возможны гроты и равнины. Это бы сильно усложнило задачу, но подождем олимпиаду следующего 2003 года. Спасибо за терпение.

Задача g6_1061: K-ичные числа (acm.timus.ru)

Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких, что их запись не содержит двух подряд идущих нулей.
Ограничения: 2 <= K <= 10; 1 <= N+K <= 18.

Входные данные.
Во входном файле INPUT.TXT содержатся числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Вывод.
Программа должна выдать в файл OUTPUT.TXT искомое число в десятичной записи.
Пример входного файла:
2
10
Пример выходного файла:
90

Решение g6_1061:
Эта задача на acm.timus.ru предлагается в 3 вариантах. В первом ограничение N+K <= 18, во втором 180, а в третьем 1800. Здесь будет изложено решение первого варианта этой задачи, т.к. главное здесь это понять метод решения, а сделать длинную арифметику несложно.
Для первого варианта в принципе возможен полный перебор, но существование 2 других задач, с такими жесткими условиями, говорит нам о том, что здесь его применять нельзя. Придется подумать... что, в общем-то, нам не свойственно...
Вспомним задачу #1043 Принцип компании. Если там представить газету как 1, а буклет как 0, то получим решение нашей задачи для частного случая, когда K = 2. Попробуем применить этот метод для произвольного K.
Последовательность из 0 элементов у нас одна. Из одного элемента - K. А вот над последовательностями из двух и более элементов придется призадуматься.
Мы получим корректную последовательность длиной t если к корректной последовательности длиной t - 1 допишем любую из K - 1 цифры (кроме нуля). Т.е.:
0, 1, 2 - последовательность из 1 элемента.
Для них корректны последовательности из двух элементов:
01, 02, 11, 12, 21, 22
Однако мы не учли, что последней цифрой может быть 0, но для этого необходимо, чтобы t-1 цифра не была нулем. Как же этого добиться?
Взглянем, что у нас получилось. У нас получились последовательности длиной t, у которых последняя цифра - не ноль. Их количество равно количеству последовательностей из t-1 элемента [f(t-1)] умножить на k-1.
Получается:
f(t) = (k-1)*f(t-1) + (k-1)*f(t-2)
К любой последовательности длины n-1 мы можем дописать любую из k-1 ненулевых цифр, отсюда (k-1)*f(t-1). К любой последовательности длины n-2 мы можем дописать любую ненулевую цифру и ноль, т.е. (k-1)*f(t-1)
Ну а числа Фибоначчи мы искали уже много раз, например в задаче #1025 Домино

Задача g6_1062: Черепаха (XIV Всероссийская олимпиада по информатике)

Домик черепахи расположен в начале прямой узкой грядки, на которой должны прорасти одуванчики - ее любимое лакомство. И вот черепахе приснился вещий сон. Из него она узнала, что наконец-то после полуночи начнут расти одуванчики. Ей даже приснилось, в какой момент времени и в какой точке грядки вырастет каждый одуванчик. Ровно в полночь черепаха выползла из домика, чтобы съесть все одуванчики и до следующей полуночи вернуться домой.
Черепаха может ползти со скоростью, не превосходящей величины vmax. Одуванчик она съедает, остановившись на время d. Если одуванчик начать есть, но не доесть до конца, то он засыхает, поэтому его надо съедать за один прием. Одуванчики прорастают тем позже, чем дальше они расположены от начала грядки. В одной точке не могут прорастать несколько одуванчиков, а также несколько одуванчиков не могут прорастать в один момент времени.
Требуется определить, в какой момент времени черепаха сможет вернуться домой, съев все одуванчики и затратив на путешествие наименьшее время.
Входные данные
В 1-й строке файла turtle.in находятся 2 целых числа, разделенные пробелом: vmax (в см/мин) и d (в минутах), 0 < vmax <= 200, 0 <= d <= 500.
Во 2-й строке находится число N - количество одуванчиков (в штуках). 0 <= N <= 1400 при d = 0, в противном случае 0 <= N <= 200.
В каждой из последующих N строк расположены: целое число xi - расстояние от одуванчика до начала грядки (в сантиметрах), 0 <= xi <= 32767, и через пробел ti - момент прорастания одуванчика (в формате hh:mm). Пары приведены в порядке возрастания расстояний.
Входные данные гарантируют, что черепаха может съесть все одуванчики и вернуться домой в течение суток.
Выходные данные
Файл turtle.out должен содержать момент времени возвращения черепахи домой (в формате hh:mm), округленный до целых минут в большую сторону.

Пример
Входной файл turtle.in
3 1
1
100 00:01
Выходной файл turtle.out
01:08

Примечания
1. В часе - 60 минут, в сутках - 24 часа.
2. Время в сутках изменяется от 00:00 до 23:59.
3. Частичные решения для случая d = 0 будут оцениваться.

Решение g6_1062:
Опять задачка со Всероссийской олимпиады 2002 года. И опять там я ее решил только наполовину :( эвристически. Кстати мое эвристическое решение получилось длиннее и запутанней правильного.
Теперь перейдем к изложению основной идеи решения.
Во-первых необходимо считать входные данные. Время прорастания я преобразовывал в минуты, а расстояние от начала грядки - как расстояние от предыдущего одуванчика до этого. Т.е. у меня от расстояния от начала до данного одуванчика отнималось расстояние от предыдущего одуванчика до начала грядки.
Ввод данных в этой задаче достаточно муторное дело - писал минут 10-15.
Теперь подумаем над алгоритмом, по которому черепаха должна есть одуванчики. Естественно, что по пути к последнему одуванчику она должна есть все, что уже проросли, потом съесть последний одуванчик, а затем возвращаться и есть все (они уже проросли раньше последнего). Но возникает одна проблема: а что если мы придем, а последний одуванчик еще не вырос? Надо ждать, причем ждать не у последнего одуванчика, а в самом начале грядки. Это объясняется тем, что, задержавшись в начале грядки, мы сможем съесть больше одуванчиков по пути туда и меньше оставить на обратный путь.
Задача решается дихотомией. Минимум - нулевая задержка, максимум - время прорастания последнего одуванчика - условие выхода - если пришли ровно к всходу последнего одуванчика или максимум минус минимум меньше 0.1 минуты (для верности). У нас будет переменная, отвечающая за задержку, значение которой будет равно (max + min) / 2 (обозначим эту переменную wait). Также у нас будет переменная, в которой храниться значение времени в данный момент (time). При входе в цикл считаем wait, а затем time := wait. Теперь идем по всем одуванчикам от первого до предпоследнего. К времени прибавляем время проползания от предыдущего одуванчика к следующему (time := time + x[i] / vmax). Если получилось, что время, в которое мы подползли к одуванчику больше либо равно времени прорастания этого одуванчика, то увеличиваем счетчик количества съеденных одуванчиков и к времени прибавляем d.
После того, как прошлись по всем одуванчикам, кроме последнего, прибавляем к общему времени, время, за которое черепаха проползет расстояние от предпоследнего до последнего одуванчика. Теперь, если время равно времени прорастания одуванчика - то на выход, если больше - то max := wait, если меньше - min := wait.
Теперь мы определили нужную задержку и нам известно время, затраченное на путь до последнего одуванчика. Также известно, что к этому времени он уже пророс. Чтобы получить итоговое время, надо к этому времени прибавить время на съедение оставшихся одуванчиков (мы знаем, сколько мы съели на пути туда) и время на обратную дорогу (просто разделить расстояние от начала до последнего одуванчика на скорость). Ответ готов. Осталось только преобразовать его к нужному формату.
Моя программа прошла все тесты, кроме одного. Там у жюри ответ получился 19:00, а у меня 19:01. Оказывается жюри округляло число по двум знакам после запятой, а различие пошло в третьем знаке. Моя программа верно посмотрела, что количество минут не целое и прибавило еще одну дополнительную минуту. А, оказывается, не надо было. Пришлось это обработать отдельно.

Задача g6_1063: Михаил Густокашин против бюрократии
Задача классическая. Формулировка: Михаил Густокашин.

Как я уже писал, с 1 сентября 2002 года я буду учиться в СУНЦ МГУ (школа-интернат им А.Н. Колмогорова, ФМШ 18). Для того, чтобы я был допущен к занятиям, мне необходимо предъявить справку по форме 086/У, на которой должна поставить свои подписи K врачей.
Все было бы хорошо, но вот некоторые врачи отказываются ставить подписи на справке до тех пор, пока на ней не распишется другой врач. Например, стоматолог отказался ставить мне подпись, пока я не принесу справку от психиатра, потому, что однажды его укусил один психически неуравновешенный мальчик, да так, что бедному врачу пришлось два месяца сидеть на больничном. Теперь он у всех своих пациентов требует справку об отсутствии психических расстройств. Много странностей у врачей...
Закончилось тем, что я составил список, какому врачу нужны какие справки. В первой строке моего списка (input.txt) содержится общее количество врачей (1 <= K <= 100). В следующих K строках описываются необходимые справки. Первое число (j) в i+1 строке входного файла означает, сколько справок нужно i-му врачу. Затем, в той же строке, содержится j чисел - номера врачей, чьи подписи надо предварительно поставить, чтобы получить подпись i-го врача.
Если подписи всех врачей собрать невозможно, то в выходной файл (output.txt) следует вывести "NO". Если же все справки собрать возможно, то в первой строке выходного файла должно содержаться "YES", а в следующих K строках - последовательность, в которой нужно получать справки.
Пример входного файла:
4
1 2
0
2 1 4
1 1
Пример выходного файла:
YES
2
1
4
3

Решение g6_1063:
Эта задача - классическая. Именно с нее я начал свое изучение теории графов (никогда их не знал). Связи удобно представить в виде ориентированного графа:




Логично, что кружочек, в который не входит стрелочек можно смело убрать (записав его в список обхода, предварительно). Этот врач ничего не требует. Вместе с кружочком уберем и стрелочки, которые ведут от него. Эту операцию будем повторять, до тех пор, пока совсем не останется кружочков (я добыл все автографы!) или пока в результате операции не будет удалено ни одного кружочка (где-то возник цикл), т.е. все подписи получить невозможно.
Требования врачей удобно хранить в двумерном массиве K * K (таблице смежности). Если элемент a[x, y] = 1 - значит врачу x требуется справка врача y, если a[x, y] = 0, то врачу x справка врача y не требуется. Первоначально просматриваем все строки и ищем строки, в которых совсем нет единиц. Допустим, мы нашли, что такой строкой будет строка x. Теперь просматриваем столбец, с номером x, и все единицы заменяем в нем на нули (необходимая подпись получена).


Задача g6_1064: Агенты (Польская олимпиада по информатике 2000)

Из-за участившихся раскрытий своих агентов, Комитет Государственной Безопасности Бутыляндии решил провести реформу, направленную на улучшение их деятельности. Первым делом необходимо обеспечить безопасность встреч агентов. Ваша программа должна помочь в решении этой проблемы. Вам дано описание путей в Бутыляндии и начальные положения двух агентов. Ваша программа должна ответить, возможно ли безопасная встреча этих агентов.
Чтобы быть в безопасности агенты должны соблюдать такие условия:
- Агенты двигаются в течение дня, и встречаются вечером,
- Агент должен изменять место пребывания каждый день,
- Агенты могут путешествовать только по дорогам, соединяющим города (в Бутыляндии, имеются односторонние дороги),
- Агент не может двигаться слишком быстро (это может выглядеть очень подозрительным) - в течение одного дня, он не может путешествовать дальше, чем в соседний город,
- Расстояние между двумя связанными городами настолько коротко, что агент, отправившись от одного города утром, достигнет другого вечером,
- Встречей называется такое состояние, когда два агента находятся в том же самом городе в тот же самый вечер.

Задача
Ваша программа должна
- Читать число городов и описания сети путей в Бутыляндии и стартовые положения агентов из входного файла AGE.IN,
- Проверять, возможна ли безопасная встреча, и если так, то, через сколько дней,
- Выводит результат в файл AGE.OUT.

Входные данные
В первой строке файла AGE.IN, имеются два целых числа n и m, разделенные пробелом, где 1 <= n <= 250, 0 <= m <= n * (n-1).
Во второй строке даны два целых числа a1 и a2, разделенные пробелом, 1 <= a1, a2 <= n и a1 a2. a1 и a2 стартовые положения агентов Номер 1 и Номер 2.
В m следующих строк даны пары чисел a и b, разделенные пробелом, 1 <= a, b <= n и a b. Эти числа означают, что имеется путь от города a к городу b.

Выходные данные:
Единственная строка файла AGE.OUT должна содержать:
- Одно положительное целое число, которое является минимальным временем (в днях) необходимым, чтобы устроить безопасную встречу двух агентов, если она возможна,
- Слово NIE (НЕ в Польском) - если такая встреча не возможна.

Пример
AGE.IN:
6 7
1 5
1 2
4 5
2 3
3 4
4 1
5 4
5 6
AGE.OUT
3

Решение g6_1064:
Во-первых, разберемся с входными данными. Естественно, что сеть дорог в Бутыляндии (в польском оригинале она называлась Byteland) представляет собой ориентированный граф, заданный списком ребер. Нам будет удобнее пользоваться таблицей смежности (двумерным массивом, который хранит в ячейке [x, y] 1 - если существует путь из x в y и 0 - в противном случае). Это делается на этапе чтения данных.
Заведем два одномерных булевских массива, с размером, равным количеству городов. Первый будет указывать, в каких городах может находиться первый агент, а второй - в каких может быть второй агент, в определенный день. Переменную, которая указывает, какой сегодня день, первоначально инициализируем нулем, а в массивах обозначим, что агенты могут находиться исключительно в начальных городах.
Теперь переходим к следующему дню. Здесь надо использовать два swap-массива, которые будут временно хранить информацию, в каких городах мы окажемся сегодня вечером. Для того, чтобы получить этот список городов, надо пройти по нашим булевским массивам и, если мы нашли, что мы можем находиться в городе x в день n, то в день n + 1 мы можем находиться в любом из городов, в который мы можем добраться из x. Занесем всю информацию об этих городах в swap-массивы, а затем заменим наши массивы на swap (наступил день n + 1). Если хоть один элемент и в первом и во втором массивах равен true (т.е. оба агента оказались в одном и том же городе), то выводим номер дня.
Гораздо сложнее все обстоит с ответом NIE. Во-первых, его надо давать в случае, если мы не можем оказаться ни в одном городе (т.е. все пути завели нас в тупик). Но возможно, что такой ситуации не будет, например, если агенты двигаются по кругу друг за другом. Здесь надо придумать какое-то другое условие выхода с ответом NIE. Самый простой вариант - поставить ограничение на количество дней, но его сложно определить. Например, если существует два кольца длиной 113 и 127 и один общий город соединяет их, то может понадобиться больше 14000 итераций для того, чтобы агенты встретились. Я не придумал эффективного способа. Разве что, поставить ограничение на количество итераций (n^2)/2. Работать это будет долго... Единственный способ улучшить такой вариант - уменьшить константу пропорциональности, т.е. выкинуть абсолютно все лишнее. Можно, конечно, поступить по другому - поставить ограничение не (n^2)/2, а n * 20, например, хотя есть шанс, что некоторые ответы будут не правильные, но по времени все должно уложиться.

Задача g6_1065: Игра в слова (II открытая Кировская командная олимпиада)

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

Напишите программу, помогающую играть в эту игру.

Входные данные
В первой строке входного файла записано выбранное для игры слово. В последующих строках задан "словарь" - множество слов, которые мы считаем осмысленными. Их количество не превышает 1000. Слово - это последовательность не более чем 255 маленьких латинских букв. Каждое слово записано в отдельной строке. Заканчивается словарь словом "ZZZZZZ" (состоящим из заглавных букв), которое мы не будем считать осмысленным. Слова в словаре, как это ни странно, не обязательно располагаются в алфавитном порядке.

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

Примеры входного и выходного файлов

C.IN

soundblaster
sound
sound
blaster
soundblaster
master
last
task
sos
test
bonus
done
ZZZZZZ

C.OUT

sound
sound
blaster
soundblaster
last
sos
bonus
done
ZZZZZZ

C.IN

windowsmustdie
summer
informatics
school
rules
olympiadisstarting
goodbymylovegoodby
exit
ZZZZZZ

C.OUT

ZZZZZZ

Решение g6_1065:
Мы уже решали подобную задачку (#1037 - Анаграммы).
Создадим два массива от a до z, в которых будем хранить, сколько раз встречается та или иная буква в слове. Первый массив отдадим на первое слово, а второй будем заполнять очередным проверяемым словом. Первоначально инициализируем первый массив нулями и пройдем по первому слову от начала до конца. Если в слове встретилась какая-то буква, то увеличим соответствующей ей элемент на 1.
Затем, заведем цикл repeat - until, условием выхода из которого будет прочтение строки ZZZZZZ. Если строка не равна ZZZZZZ, то инициализируем второй массив нулями, а затем также для всех букв этого слова будем увеличить соответствующие элементы второго массива. Теперь сравним все элементы от a до z в обоих массивах. Любой элемент первого массива должен быть не меньше элемента второго массива (иначе получилось бы, что мы использовали при составлении слова букву, которой нет в данном слове, или использовали больше букв, чем есть).


Задача g6_1066: Ездец (II открытая Кировская командная олимпиада)

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

"История Лицея", Москва, Мир, 2040 г.

Постановка задачи
Вам дан список заказов: время, когда заказ поступил, и номер столика, с которого он сделан (столики пронумерованы по часовой стрелке от 1 до N).

Ездец устроен следующим образом:
Вначале он находится напротив столика номер 1 в состоянии "свободен".
Когда поступает заказ, ездец переходит в состояние "обслуживание заказа". Он выбирает кратчайший из двух путей (по часовой или против часовой стрелки) от своего текущего положения до столика, который надо обслужить. На то, чтобы переместиться к соседнему столику, ездец тратит T1 секунд. (Таким образом, если, например, ему надо переместиться от 1-го столика к 5-му по часовой стрелке, то это займет 4*T1 секунд). Подъехав к нужному столику, он тратит еще T2 секунд на выдачу заказа. Затем он снова переходит в состояние "свободен" и остается у только что обслуженного столика.
Если какой-то заказ поступает в момент, когда ездец уже обслуживает другой заказ, то вновь поступивший заказ помещается в очередь и будет обслужен, как только ездец освободится. Если за время обслуживания заказа накопится несколько вновь поступивших заказов, то они будут выполняться в порядке очередности их поступления. Никакие два заказа не поступали одновременно.

Время ожидания (удовлетворения) заказа - это время между его поступлением и временем завершения его обслуживания. Среднее время ожидания - это сумма времен ожидания для всех заказов, деленная на количество заказов.
Входные данные
Во входном файле задано число N - количество столиков (1 < N < 1000), затем числа T1 и T2 (каждое из этих чисел - целое от 1 до 100).

Затем идет число M - количество заказов (1 < M < 10000), и, наконец, M пар чисел целых чисел - время поступления и номер столика очередного заказа. Время поступления заказа указано в секундах, оно положительно и не превышает 30000. Заказы указаны в порядке их поступления (т.е. в порядке возрастания времени заказа).

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

Примеры входного и выходного файлов
D.IN
10
2 11
6
10 1
21 1
22 7
23 2
200 2
201 1

D.OUT
22.333

Решение g6_1066:
Вообще-то достаточно простая задача. Будем считывать заказы по одному. У нас будет переменная, указывающая на настоящий момент времени, первоначально приравняем ее к нулю. Если время поступления заказа больше чем настоящий момент, то присваиваем настоящему моменту время поступления заказа (у робота не разработана система предсказания заказов). Если же настоящий момент больше времени заказа, то прибавляем к общему времени ожидания разность, между настоящим моментом и временем заказа (робот обслуживал не нас).
Теперь будем определять время, затраченное на собственно наше обслуживание. Сначала нам необходимо определить - какое расстояние меньше - по часовой или против часовой стрелки. Это уместно вынести в отдельную функцию, которая будет выбирать минимум между abs(a - b) [едем, не проезжая через первый столик] и ((n - a + b) mod n) [проезжаем мимо первого и последнего столиков]. Прибавим к настоящему моменту и времени ожидания минимум, умноженный на t1. Теперь просто добавим к времени ожидания и настоящему моменту t2.
Осталось только вывести результат: (время ожидания) / m

Задача g6_1067: Метро (Белорусская олимпиада по информатике 2002)

В некотором городе есть метро, состоящее из N (1 <= N <= 1000) станций и M линий, соединяющих их. Каждая линия обеспечивает проезд между какими-то двумя станциями в обе стороны. Между любой парой станций проведено не более одной линии. Сеть метро построена таким образом, чтобы с каждой станции можно было проехать на каждую (возможно, через промежуточные станции). Назовем это свойство связностью метро.
В связи с изобретением принципиально нового вида транспорта метро стало убыточным, и его работу решили прекратить. На заседании мэрии города было постановлено закрывать каждый год по одной станции, но так, чтобы связность метро каждый раз сохранялась. При закрытии какой-либо станции, линии, ведущие из этой станции в другие, естественно, тоже перестают функционировать.
Задание. По введенной информации о сети метро разработать какой-либо порядок закрытия станций, при котором метро всегда будет оставаться связным. Например, пусть метро выглядит так, как показано на рисунке. Тогда станции можно закрывать, например, в порядке 1, 2, 4, 3, 5. А порядок 3, 1, 2, 4, 5 - не подходит, так как после закрытия 3-й станции метро распадется на четыре не связных между собой части.




Ввод. Первая строка входного файла будет содержать числа N и M. В следующих M строках находится информация о линиях. Каждая из этих строк содержит через пробел числа Ai и Bi (Ai Bi) - две станции, которые соединяет i-я линия.
Вывод. Выходной файл должен состоять из N строк. Каждая строка должна содержать одно число - номер станции. Вывести станции нужно в порядке их закрытия.

Пример
input.txt
5 4
3 1
3 2
3 4
3 5
output.txt
1
2
4
3
5

Решение g6_1067:
Сначала я вспомнил самарское метро и решил, что эта задача очень похожа на #1063 - Михаил Густокашин против бюрократии. Но потом я вспомнил московское метро (кольцевую линию) и понял, что этот метод не пройдет. По крайней мере, не пройдет с теми входными данными, которые нам даны.
Ну и ладно. Придется решить задачу по-другому.
Воспользуемся поиском в глубину или в ширину на графе. Я пользовался поиском в глубину, т.к. время написание процедуры поиска в глубину меньше времени написания процедуры поиска в ширину. Естественно я использовал рекурсивную процедуру, а на выходе из нее, заносил номер вершины в специальный массив. Чтобы получить ответ, необходимо просто вывести этот массив с начала.
Как же это работает? Допустим, мы рассматриваем какую-то станцию, у которой в остовном дереве есть потомки. В силу порядка заполнения нашего массива, все ее потомки будут стоять перед ней, т.е. и удаляться раньше нее. С остальными станциями она будет иметь связь - например, через станцию №1 (если начинать обход с нее). После того, как все ее потомки будут удалены - можно спокойно удалять и ее - даже если кроме потомков в остовном дереве, она была связана с другими станциями, то в них существует другой путь (по маршрутам остовного дерева).
Сложность алгоритма, в зависимости от реализации, либо O(N2), либо O(M). А вот памяти он потребляет O(N2).

Задача g6_1068: Террористы (Украинские учебно-тренировочные сборы 2001. Оригинальное название "Игра")

В стране есть несколько аэропортов, и рейсы между ними. Можно долететь с одного аэропорта до другого, возможно с пересадками, но для любой пары аэропортов существует единственный маршрут перелета.
Два террориста играют в такую игру. Они делают ходы по очереди. Каждый ход состоит из таких операций. Игрок минирует аэропорт, выбирает рейс и улетает вместе с коллегой. После взлета он активирует взрывное устройство, в результате чего аэропорт взрывается и все рейсы до и из этого аэропорта отменяются. После приземления в другом аэропорту ход переходит к другому игроку. Проигрывает тот, кто не может сделать ход.
Задача
Напишите программу GAME которая по начальному списку рейсов и номеру аэропорта где в начале игры находятся террористы определит кто победит, если каждый игрок будет придерживаться оптимальной стратегии.
Входные данные
Первая строка входного текстового файла GAME.DAT содержит два целых: N - количество аэропортов (N <= 1000) и K - номер исходного аэропорта. Следующие N -1 строк содержат пары целых чисел - номера аэропортов, соединенных рейсом (все рейсы - двухсторонние и упоминаются только раз). В каждом аэропорту не более 20 рейсов.
Выходные данные
Единственная строка выходного текстового файла GAME.SOL должна содержать 0, если первый игрок проигрывает, или номер аэропорта, в который необходимо полететь, если первый игрок выигрывает. Если есть несколько "выигрышных" аэропортов, необходимо найти аэропорт с минимальным номером.
Пример входных данных
4 3
3 2
3 1
1 4
Пример выходных данных
2

Решение g6_1068:
Веселая задача! Во-первых, прочитаем первое условие: "для любой пары аэропортов существует единственный маршрут". Ясно, что структура данных, используемая в этой задаче - дерево. Его можно хранить, как динамический список сыновей, например, для каждой вершины указывая на левого сына и правого брата. Но структура данных - не самое главное в этой задаче, а самое главное - сама суть решения.
Теперь я приведу свой рисунок дерева для входных данных (ну не умею я рисовать!), а потом объясню, что означают цифры слева и справа от кружков:




Итак, перейдем к значению левой цифры: она означает четность вершины, т.е. расстояние от корня дерева, до этой вершины. Это понадобиться нам в некоторых случаях для определения того, какой игрок выиграл. Если вершина не имеет сыновей (т.е. лететь больше некуда), и ее четность равна 0 (ход первого игрока), то первый игрок, летя таким маршрутом, проигрывает; если же четность равна 1 и у вершины нет сыновей, то проигрывает второй игрок. Кстати, какой игрок выигрывает или проигрывает показывает цифра справа от кружка - если выигрывает первый игрок, то эта цифра равна 1, если проигрывает -1.
Теперь будем определять, выиграет или нет игрок в вершине, у которой есть сыновья. Если вершина имеет 0 четность (ход первого игрока), то, естественно, он должен выбрать среди сыновей такой маршрут, который обеспечивает ему выигрыш - т.е. если среди его сыновей есть сын с числом 1 справа, то первый игрок может выбрать выигрышный маршрут и этой вершине также присваивается значение 1. Если же четность вершины равна 1 (ходит второй игрок), то он должен стараться выбрать наихудший вариант для первого игрока, т.е. если у вершины есть сын с выигрышем -1, то и этой вершине присваивается -1.
Технически это реализуется с помощью рекурсивной процедуры и динамического массива. Если значения потомков не определены, то для них запускается рекурсивная процедура, если вершина не имеет потомков, то в динамический массив записывается выигрыш исходя из определенного нами правила. Если же значения всех потомков определены, то среди них выбирается наибольший или наименьший, соответственно четности вершины, и этот результат также записывается в массив.
Здесь было бы уместно применить альфа-бета отсечение, т.е. если при 0 четности мы нашли сына с выигрышем 1, то можно не искать других сыновей, однако нам надо найти наименьший номер аэропорта, в который надо полететь, а альфа-бета отсечение может "отсечь" этот вариант, так что придется обходиться без него.
Кстати, поиск номера выигрышного аэропорта надо осуществлять так: идем по всем аэропортам, начиная с наименьшего, и, если этот аэропорт имеет выигрыш 1 и не имеет сыновей, проверяем, все ли его предки имеют выигрыш 1 (для этого в списке надо хранить также указатель на предка). Если все предки имеют выигрыш 1, то выводим номер этого аэропорта. Поиск такого аэропорта можно организовать и по-другому.

Задача g6_1069: Школы (XIV Всеукраинская олимпиада по информатике)

С целью подготовки к проведению олимпиады по информатике мэр решил обеспечить надежным электроснабжением все школы города. Для этого необходимо провести линию электропередач от альтернативного источника электроэнергии "Майбуття" к одной из школ города (к какой неважно), а также соединить линиями электропередач некоторые школы между собой.
Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником "Майбуття", либо с одной из тех школ, которые имеют надежное электроснабжение.
Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения (стоимость схемы равняется сумме стоимостей соединений пар школ).
Задание
Напишите программу SCHOOLS, которая вычисляет стоимость двух наиболее экономных схем альтернативного электроснабжения школ.
Входные данные
В первой строке входного файла SCHOOLS.DAT находятся два натуральных числа, разделенных пробелом: N (3 <= N <= 100), количество школ в городе, и M - количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci - стоимость прокладки линии электроснабжения (1 <= Ci <= 300) от школы Ai до школы Bi (i = 1, 2, ..., N).
Пример входного файла
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
Выходные данные
В единственной строке выходного файла SCHOOLS.SOL должны содержаться два натуральных числа S1 и S2, разделенных пробелом - две наименьшие стоимости схем (S1 <= S2). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.
Пример выходного файла
110 121

Решение g6_1069:
Ясно, что мы имеем дело с графом, из которого нужно выделить некоторую компоненту, такую, что каждая вершина графа входит в эту компоненту. Сумма всех ребер этой компоненты должна быть наименьшей. Назовем эту компоненту остовным деревом минимального веса.
Существует два основных алгоритма нахождения остовного дерева минимального веса - алгоритм Прима (работает за O(n2), n - количество вершин в графе) и алгоритм Крускала (O(e*loge), e - количество ребер в графе). Первый алгоритм реализуется проще, поэтому задачу будем решать пользуясь им.
Цепляем электропитание к любой школе (это бесплатно, так как каждая школа должна быть элементом дерева, то стартовой можно выбрать любую, для определенности первую). Теперь нужно поговорить о структуре данных, хранящую связи между школами. Я использовал две таблицы смежности размером 100*100 (это даже в BP укладывается). Теперь перейдем к построению остовного дерева. Обозначим множество всех вершин буквой G, а множество вершин дерева - T. На каждом шаге к множеству T будем присоединять одну вершину из множества G/T (G исключая T), такую, что стоимость соединения этой вершины с T меньше, чем стоимость соединения любой другой вершины с множеством T. Для приведенных входных данных порядок включения вершин будет такой: 1, 2, 4, 5, 3.
Множество вершин T можно представить в виде одной вершины, т.е. завести для нее одномерный массив, хранящий стоимости соединения ее с вершинами, не входящими в T. Первоначально множество связей T будет совпадать с множеством связей первой школы, затем, выбираем из этого множества связь с наименьшим значением (самую дешевую линию) и добавляем к T вершину, на которую указывает эта связь. Теперь, если для какой-либо вершины из G/T стоимость проложения линии от добавленной вершины меньше, чем от T, то заменим стоимость проложения линии от T до этой вершины на стоимость проложения линии от этой вершины до вновь добавленной.
Может быть немножко путано, но я старался избежать теории, показав только практику.
Информацию о том, от какой вершины (кроме массива со стоимостями связей T надо хранить также массив, указывающей из какой вершины T исходит эта связь) до какой была проложена линия будем заносить во второю таблицу смежности.
После первого выполнения процедуры поиска мы получим первый вариант прокладки линий во второй таблице смежности. Теперь нам нужно найти второй вариант. Ясно, что второе остовное дерево должно отличаться от первого, т.е. не содержать хотя бы одного ребра, которое принадлежит второму остовному дереву. Эти мы и воспользуемся - будем по одному удалять ребра первого остовного дерева из данного графа и искать другое остовное минимального веса, не забывая после этого поиска восстанавливать ребро.

Задача g6_1070: Блокада (Всероссийская командная олимпиада среди школьников 2001)

Государство Флатландия представляет собой прямоугольник размером M * N, состоящий из единичных квадратиков. Флатландия разделена на K провинций (2 <= K <= 100). Каждая провинция представляет собой связное множество квадратиков, т.е. из каждой точки провинции можно дойти до любой другой ее точки, при этом разрешается переходить с квадратика на квадратик, только если они имеют общую сторону (общей вершины недостаточно). Во Флатландии нет точки, которая граничила бы более чем с тремя провинциями (т.е. четыре квадратика, имеющие общую вершину, не могут принадлежать четырем разным провинциям).
Каждая провинция имеет свой символ. Столица Флатландии находится в провинции, которой принадлежит символ A (заглавная латинская буква A). Провинция называется пограничной, если она содержит граничные квадратики. Провинция, в которой находится столица Флатландии, не является пограничной.
Король соседнего с Флатландией королевства Ректилания решил завоевать Флатландию. Для этого он хочет захватить столицу Флатландии. Однако он знает, что сил его армии недостаточно, чтобы сделать это сразу. Поэтому сначала он хочет окружить столичную провинцию, чтобы ослабить силы противника долгой блокадой, а потом захватить столицу.
Чтобы окружить провинцию, требуется захватить все провинции, с которыми она граничит. Две провинции граничат, если существует два квадратика, имеющие общую сторону, один из которых принадлежит первой из них, а другой - второй. Чтобы захватить провинцию, надо чтобы выполнялось одно из двух условий: либо она пограничная, либо граничит с какой-либо уже захваченной провинцией.
Чтобы сберечь силы своей армии, король Ректилании хочет установить блокаду столичной провинции, захватив как можно меньше провинций. Помогите ему выяснить, сколько провинций требуется захватить. Захватывать столичную провинцию нельзя, поскольку для этого сил армии Ректилании пока недостаточно.
Формат входных данных
Первая строка содержит M и N (3 <= M, N <= 200). Следующие M строк содержат N символов каждая и задают карту Флатландии. Символ, находящийся в i+1-й строке входного файла на j-м месте, представляет собой символ провинции, которой принадлежит квадратик (i, j). Все символы имеют ASCII-код больше 32 (пробела).
Формат выходных данных
Выведите в выходной файл единственное число - количество провинций, которые требуется захватить. Если установить блокаду невозможно, выведите "-1".
Примеры
input.txt
5 6
BBBBBZ
BCCCBZ
BCAbbZ
BDDDbZ
ЗЗЗЗЗZ
output.txt
4

Решение g6_1070:
Да... Первый новый разбор за 2 месяца. Но ничего, привезу компьтер в общагу - может быть ситуация проясниться, а сейчас - каникулы.
Представим связь между провинциями в виде двумерной таблицы смежности от chr(31) до chr(255), заполненной 255. Теперь эту таблицу надо заполнить. Если мы пишем на FP (а теперь мы пишем только на нем, т.к. теперь это официальный язык личной и командной олимпиад школьников), то проблем не возникает - загоняем все символы в массив char 200*200. Если мы все же пишем на BP, то заведем двумерный массив, [1..200, 1..2], где будем хранить предыдущую и нынешнюю строку. Тоже очень несложно реализуется. Условимся, что Флатландию полностью окружает провинция chr(31). Теперь будем устанавливать связи между провинциями. Пройдемся по всему массиву, в котором храниться карта Ректаландии и для каждой клеточки определим ее соседей. В таблице смежности обозначим, что существует связь между провинцией имеющей код клетки, в которой мы находимся и ее соседкой. Для граничных клеток (они легко определяются по координатам) установим, что они граничат с chr(31). Это можно реализовать по-другому, например, расширив карту на 1 в каждую сторону и предварительно заполнив chr(31) - меньше писанины, что архиважно, особенно на командных олимпиадах.
Теперь у нас есть таблица смежности. Найдем все провинции, с которыми граничит столица, и отметим их в булевском массиве. Теперь воспользуемся алгоритмом Флойда (пишется очень быстро, но работает медленнее чем Дейкстра, но в данном случае это неважно - главное побыстрее наколотить программу).

for k := chr(31) to chr(255) do

if k 'A' then for i := chr(31) to chr(255) do

for j := chr(31) to chr(255) do

if (a[i, j] 1) and (a[i, k] 0) and (a[k, j] 0)

then a[i, j] := a[i, k] + a[k, j];

Заметим, что через провинцию A мы не можем пройти к границе, т.к. мы не можем ее захватить.
Теперь пойдем по всем провинциям, которые граничат со столицей. Если для какой-либо из них расстояние до chr(255) равно 255, то выводим -1 - эта провинция окружена столичной. Если же такой ситуации не происходит, то из всех расстояний выберем наименьшее - оно и будет минимальным количеством провинций, которые необходимо захватить, чтобы добраться до провинций, окружающих столичную. Правда, в силу того, что мы считали chr(31) провинцией от этого результата надо отнять единицу. Теперь сложим количество провинций, окружающих столичную, с количеством провинций, которые необходимо захватить, чтобы добраться до них от границы. Это будет окончательный ответ.
Кстати, эту задачу также разбирал Андрей Станкевич - человек намного более опытный в олимпиадных задачах и обучении методам их решения, чем я. Можете поискать его вариант разбора на сайте neerc.ifmo.ru/school. Посмотрите комментарии к задачам Всероссийской командной олимпиады 2001.


Задача g6_1071: Форум (Всероссийская командная олимпиада среди школьников 2002)

Клуб Юных Хакеров организовал на своем сайте форум. Форум имеет следующую структуру: каждое сообщение либо начинает новую тему, либо является ответом на какое-либо предыдущее сообщение и принадлежит той же теме.
После нескольких месяцев использования своего форума юных хакеров заинтересовал вопрос - какая тема на их форуме наиболее популярна. Помогите им выяснить это.
Формат входных данных
Первая строка входного файла содержит целое число N - количество сообщений в форуме
(1 <= N <= 1000). Следующие строки содержат описание сообщений в хронологическом порядке.
Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк. Первая строка содержит число 0. Вторая строка содержит название темы. Длина названия не превышает 30 символов. Третья строка содержит текст сообщения.
Описание сообщения, которое является ответом на другое сообщение, состоит из двух строк. Первая строка содержит целое число - номер сообщения, ответом на которое оно является. Сообщения нумеруются, начиная с единицы. Ответ всегда появляется позже, чем сообщение, ответом на которое он является. Вторая строка содержит текст сообщения.
Длина всех сообщений не превышает 100 символов.
Формат выходных данных
Выведите в выходной файл название темы, к которой относится наибольшее количество сообщений. Если таких тем несколько, то выведите первую в хронологическом порядке.
Пример

forum.in
7
0
Олимпиада по информатике
Скоро третья командная олимпиада?
0
Новая компьютерная игра
Вышла новая крутая игра!
1
Она пройдет 24 ноября
1
В Санкт-Петербурге и Барнауле
2
Где найти?
4
Примет участие более 50 команд
6
Интересно, какие будут задачи

forum.out
Олимпиада по информатике

Решение g6_1071:
Каждую тему в форуме можно представить в виде дерева, т.е. первое сообщение - это корень дерева, остальные - ветви и листья. Нам необходимо найти дерево с максимальным количеством элементов и вывести тему, которая соответствуют корню этого дерева.
Я делал это таким методом: каждое дерево я преобразовывал в другое дерево, не имеющее ветвей. Т.е. ответ на какое-то сообщение, принадлежащее данной теме, делал ответом на первое сообщение в теме.



Такое преобразование делается очень просто: создаем массив, для каждого элемента содержащий номер его предка; если сообщение - начало новой темы (т.е. ответ на сообщение 0), то номер предка этого сообщения - его собственный номер, если же сообщение не является началом новой темы, то его номер предка равен номеру предка его отца. Т.е. на рисунке у сообщения 1 предок равен самому себе, у сообщения 2 отец - 1 сообщения, следовательно, предок 2 также 1, у 3 сообщения отец - 2 сообщение, его предок - 1, значит и предок 3 - 1 и т.д.
Теперь есть много способов подсчитать наиболее популярную тему, я делал это прямо по ходу преобразования деревьев. У меня был заведен массив, в котором содержалось количество элементов в дереве, корнем которого является элемент массива. Затем следует найти максимальный элемент массива (это также можно делать по ходу преобразований) и вывести соответствующую ему тему. Темы надо хранить в массиве строк с длиной 30 (он хорошо помещается в памяти), а сообщения вообще хранить не надо, а считывать их readln.

Задача g6_1072: Столица (Всероссийская командная олимпиада среди школьников 2002)

В некотором царстве, в некотором государстве было N городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |x1 - x2| + |y1 - y2|.
Император решил построить n+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.
Нелегкая задача выбрать место для столицы поручена Вам.
Формат входных данных
Первая строка входного файла содержит число N - количество городов (1 <= N <= 100). Следующие N строк содержат координаты городов - пары целых чисел, не превышающих 1000 по абсолютной величине.
Формат выходных данных
Выведите в выходной файл два целых числа - координаты точки, где следует построить столицу. Если решений несколько, выведите любое.
Примеры
capital.in
8
0 0
1 0
2 0
0 1
2 1
0 2
1 2
2 2
capital.out
1 1

capital.in
4
0 0
1 1
0 1
1 0
capital.out
0 2

Решение g6_1072:
Рассмотрим проекцию на ось x (координата y не влияет на расстояние по x, т.к. все дороги параллельны осям координат). Возьмем два крайних города (с наибольшей и наименьшей координатой). Если бы были только два этих города, то столицу можно было бы расположить в любой точке, между этими городами - суммарное расстояние до них равно расстоянию между городами. Если же столицу расположить вне отрезка, ограниченного двумя крайними городами, то суммарное расстояние будет больше расстояния между городами, а этого нам не надо.
Теперь рассмотрим пару предпоследних городов: для нее также должно выполняться это условие. Точно также оно должно выполняться для всех пар городов. Получается, что координата столицы по x должна лежать в отрезке между двумя средними городами (если городов нечетное количество, то столица должна быть в окрестностях среднего города). Т.е. нужно отсортировать координаты по x и выбрать за координату столицы средний элемент. Точно также нужно поступить и с y проекцией.
Мы знаем приблизительные координаты столицы (средние элементы отсортированных массив координат городов), попытаемся получить ее точные координаты. В клетке, которую мы выбрали, может находиться другой город, а столицу надо построить на свободном месте, так что этот вопрос надо как-то решать.
Это проблема решается небольшим перебором в окрестности этой точки, которая имеет заведомо большую площадь, чем могут занимать все города вместе взятые. Я использовал квадрат со стороной 23 и центром в точке с приблизительными координатами столицы. Мы должны перебрать все точки в этой окрестности и, если в некоторой точке нет города, посчитать сумму расстояний от нее до всех городов и выбрать среди всех точек такую, сумма расстояний для которой будет наименьший.
На олимпиаде мы так и не решили эту задачу, несмотря на то, что Андрей Шулятьев придумал правильный алгоритм, но я тогда смог разубедить его в правильности такого решения. Сила слова, что называется...

Задача g6_1073: Три города (Всероссийская командная олимпиада среди школьников 2002)

В одном государстве имеется N городов. Некоторые города соединены дорогами, причем для любых двух городов A и B выполняется следующее свойство: существует ровно один способ попасть из города A в город B если можно перемещаться только по дорогам и не разрешается проезжать по одной и той же дороге более одного раза.
Недавно президента этой страны заинтересовал вопрос: какие три города являются наиболее удаленными друг от друга. А именно, назовем взаимной удаленностью друг от друга трех городов A, B и C минимальное количество дорог, которое необходимо использовать, чтобы доехать от A до B, затем от B до C и затем от C до A (при этом разрешается использовать одну и ту же дорогу в различных путешествиях).
Требуется найти три города, для которых взаимная удаленность друг от друга будет максимальной.
Например, для пяти городов, соединенных дорогами так, как это показано на рисунке 1, три наиболее удаленных друг от друга города - это города 1, 2 и 5 (взаимная удаленность равна 2 + 3 + 3 = 8), а для городов на рисунке 2 - это любые три города, выбранные из множества {1, 2, 4, 5} (удаленность 2 + 2 + 2 = 6).





Формат входных данных
Первая строка входного файла содержит число N - количество городов (3 <= N <= 1000). Следующие N строк содержат описания городов. Описание i-го города сначала содержит Ki - количество городов, с которыми он соединен дорогами (1 <= Ki < N), а затем Ki чисел - номера городов, с которыми он соединен.
Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.
Формат выходных данных
Выведите в выходной файл три различных числа - номера трех наиболее удаленных друг от друга городов в произвольном порядке. Если решений несколько, выведите любое из них.
Примеры
three.in
5
1 3
1 3
3 1 2 4
2 3 5
1 4
three.out
1 2 5

three.in
5
1 3
1 3
4 1 2 4 5
1 3
1 3
three.out
1 2 4

Решение g6_1073:
Наверно, "Три города" - самая интересная задача командной олимпиады 2002. Перед тем как ее решать, придется подумать (это нам не свойственно, поэтому на олимпиаде мы ее, естественно, не решили).
Итак, необходимо найти расстояние между тремя наиболее удаленными городами. Вполне логичным представляется, что все три города должны быть крайними (т.е. быть соединенными только с одним городом), кроме случая, когда все города расположены в цепочку, но его мы рассмотрим отдельно.
Выберем произвольный город (назначим его первым городом) и будем считать его корнем нашего дерева. Определим расстояния от корня до всех вершин этого дерева. Та вершина, расстояние до которой будет максимально, будет вторым городом. Теперь надо найти третий город, это делается хитрым образом: для каждой вершины, в которую ведет только одна дорога, кроме корня дерева, пойдем рекурсивно вверх, к корню дерева, записывая в каждой вершине, какое максимальное расстояние до листа и номер этого листа.
Теперь пойдем от нашего второго города к корню, выполняя на каждой вершине (обозначим эту вершину за D, а наши три города за A, B и C) следующие операции: из всех детей выберем того, у которого не совпадает конечный лист и расстояние до его конечного листа максимально.





Вершина C, такая, что расстояние CD будет максимальным и будет третьим городом. Действительно, сумма расстояний AD и BD не зависит от D. А расстояние CD входит в сумму расстояний между тремя городами дважды. Т.е. расстояние между тремя городами равно AB * 2 + max(CD) * 2.
Для того чтобы найти лучший вариант, необходимо перебрать все возможные города, выбирая их за город A. На самом деле это вовсе не обязательно, т.к. все три города должны быть крайними городами, то выбирать за город A город, который соединен более чем с одним городом, нет смысла.
Теперь о тонкостях технической реализации. Во-первых, необходимо посчитать расстояние от корня дерева до всех узлов дерева. Я делал это рекурсивной функцией, т.к. городов не так уж много, а рекурсия пишется очень быстро. Во-вторых, следует подсчитать для каждого узла расстояние до наиболее далекого листа. Я также делал это рекурсивной функцией, которая запускалась для каждого листа, кроме корня дерева. Она шла к отцу узла (массив отцов строился на этапе подсчета расстояний от корня дерева) и, если для него расстояние до самого дальнего листа меньше, чем наименьшее расстояние, то записываем туда новое расстояние и в другой массив записываем, что конечный элемент (когда-нибудь он станет Ci) изменился, затем увеличиваем расстояние на 1 и переходим к отцу этого элемента.
После того, как рекурсивная функция запустится для всех листьев дерева, начнем распутывать все от вершины B. Перейдем к отцу вершины B и для всех его детей (кроме отца узла, ведь он тоже записан как потомок дерева) выберем среди таких, последний лист которых не равен B, тот расстояние для которого наибольшее. Последний лист этого элемента обозначим за C и запомним его, если DC больше максимального DC на данный момент.
Перейдем к отцу этого узла и т.д., пока не достигнем корня дерева. Если сумма расстояний между тремя городами (она равна AB * 2 + max(CD) * 2) больше максимальной суммы на данный момент, то запоминаем A, B и C.
Испробовав все A, мы найдем-таки лучшую тройку A, B, C, или получим, что C = 0. В таком случае, надо выбрать произвольное C не равное A и B - значит, все города лежат в цепочке.
Надеюсь, что что-нибудь понятно.

Задача g6_1074: Простые гири (?)

Имеются гири с массами: 1 г, 2 г, ..., N г (N <= 500000). Написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.
Входные данные:
Входной файл input.txt содержит число N.
Выходные данные
В выходном файле output.txt выводится список найденных пар. Все числа в выходном файле разделяются пробелами и (или) символами перевода строки.
input.txt
7
output.txt
1 6
7 4
5 2

Решение g6_1074:
Для решения этой задачи можно воспользоваться теоремой о том, что между натуральным n и 2 * n существует хотя бы одно простое число. Доказательства ее я не знаю, но оно нам не понадобится - информатика - великая наука :)
Итак, найдем наименьшее простое число M, лежащее между N и 2 * N. Естественно, его можно представить в виде суммы двух слагаемых из ряда чисел от 1 до N. Переберем и выведем все такие пары, следя за тем, чтобы числа в них не повторялись. Теперь мы можем найти оставшиеся пары, решив ту же самую задачу для числа N = M - N - 1, т.е. взяв за максимум первое неиспользованное число. Когда N станет равным нулю, то это будет означать, что все пары уже найдены.

Задача g6_1075: Folding (?)

Билл пытается компактно представить последовательность заглавных латинских букв от 'A' до 'Z', с учетом повторяющихся последовательностей в ней. Например, возможный способ представить последовательность AAAAAAAAAABABABCCD - есть 10(A)2(BA)B2(C)D. Билл ввел формальное понятие упакованной последовательности так:

 Последовательность, содержащая один символ из диапазона 'A'..'Z' считается упакованной последовательностью. Ее распаковка возвращает тот же символ.

 Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Причем, если результатом распаковки S является S', а Q - Q', то SQ распаковывается в S'Q'.

 Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное целое число, большее 1. Если S распаковывается в S', то X(S) распаковывается в S', повторенную X раз.

Согласно этому определению легко распаковать любую запакованную последовательность. На Билл более заинтересован в обратной операции. Он хочет запаковать данную последовательность так, чтобы результирующая запакованная последовательность содержала как можно меньше символов (включая цифры и скобки).
Input
Входной файл содержит одну строку, состоящую не менее, чем из одного и не более чем из 100 символов в диапазоне 'A'..'Z'. Output
Запишите в выходной файл одно число - длину кратчайшего из вариантов запаковки исходной последовательности. Sample input and output
folding.in
AAAAAAAAAABABABCCD
folding.out
12
folding.in
NERRCYESYESYESNEERCYESYESYES
folding.out
13

Решение g6_1075:
Для решения задачи надо воспользоваться динамическим программированием. Т.е. нам необходимо придумать, что и как мы будем хранить и как этим пользоваться.
Здесь логично завести двумерный массив, первый индекс будет означать позицию, с которой начинается сжимаемая подстрока, второй - длину подстроки.
Легко заметить, что последовательность, состоящую менее чем из 5 символов, сжать невозможно. Т.е. первые четыре столбца нашей матрицы мы можем смело заполнять количеством символов, т.к. эти строки сжать невозможно.
Теперь рассмотрим, как определить наименьшее количество символов в строке C[I, K]: здесь существует два варианта. Пусть K делится на H, тогда попытаемся разделить нашу подстроку на части длины H и проверим, не равны ли все эти части между собой. Если они равны, то в таком случае подстрока будет сжиматься в C[I, H] + 2{два символа уходят на открывающую и закрывающую скобки} + f(H) символов, где f(H) - количество символов в десятичной записи числа H. Перебрав все H, выберем вариант, при котором длина упакованной подстроки наименьшая.
Второй вариант представить нашу подстроку - это разбить ее на две подстроки всеми возможными способами. Для этого надо пустить цикл J от I до I + K - 1 разбиваю нашу строку на две подстроки от I до J и от J + 1 до I + K. Перебрав все J, выберем наименьшую сумму длин подстрок, на которые мы разбиваем текущую подстроку.
Теперь из двух вариантов представления выберем наименьший - он и будет результатом C[I, K]. Ответом будет значение C[1, length(s)]. Осталось только правильно организовать два цикла, а это совсем несложно.







Задача g6_1076: Фишки (15 Всероссийская олимпиада по информатике)

Авторы: А.П. Овсяников, Т.В. Овсянникова
Последовательность клеток занумерована числами от 1 до N. В каждой клетке стоит либо черная, либо белая фишка. Группой назовем набор подряд стоящих фишек одного цвета, ограниченный с обеих сторон фишками другого цвета или концами последовательности. Следует переместить фишки так, чтобы они образовали не более двух групп.
Перемещение фишек описывается с помощью плана обмена, в котором используются понятия операция обмена и шаг. Операция обмена меняет местами две соседние группы фишек. Шаг состоит не более чем из K одновременно выполняемых обменов. Обмены можно совершать одновременно только тогда, когда в них участвуют разные группы. После каждого шага группы одного цвета, оказавшиеся рядом, объединяются. План обменов содержит описания шагов, выполняемых последовательно.




Напишите программу, определяющую план обменов, с помощью которого за наименьшее число шагов получается последовательность, состоящая не более чем из двух групп.
Формат входных данных
В первой строке входного файла записаны числа N и K (1 <= N <= 100000 и 1 <= K <= 10000). Исходная расстановка фишек задается в последующих строках, содержащих N чисел (0 или 1), разделенных пробелами или переводами строк. При этом 0 соответствует черной фишке, 1 - белой.
Формат выходных данных
Выходной файл должен содержать описание шагов плана, по одному шагу на строке. Описание шага начинается с числа L - количества обменов на этом шаге. Затем для каждого обмена указывается минимальный номер клетки, в которой стоит фишка, участвующая в этом обмене. Последняя строка плана должна содержать одно число 0.
Примеры
fishes.in
9 3
1 0 0 1 1 0 1 1 0
fishes.out
2 1 6
1 1
0
fishes.in
3 1
1 1 0
fishes.out
0
Примечание
Требуется найти план, содержащий наименьшее число шагов, при этом общее число обменов может быть не минимальным.

Решение g6_1076:
Заметим, что количество фишек в одной группе не имеет никакого значения, т.к. за один обмен мы из 3 или 4 групп получаем 2. Получается, что нам нужно хранить количество фишек в группе только для того, чтобы правильно выводить позицию, с которой начинается группа, участвующая в обмене.
Необходимо завести массив A от одного до N (т.к. все группы могут состоять из одного символа) и хранить в нем позицию, с которой начинаются символы i-ой группы. Это сделать несложно - читаем последовательно символы последовательности и если символ не равен предыдущему, то сохраняем в A[i] позиция, на которой находиться данный символ (отсюда начинается новая группа) и увеличиваем i. Общее количество групп обозначим за M.
Теперь необходимо разработать алгоритм перестановки групп, чтобы добиться желаемого эффекта за наименьшее количество шагов. Будем выполнять действия до тех пор, пока количество групп не станет равным 2. Наша последовательность представляет собой последовательность групп вида 010101. Разобьем нашу последовательность на тройки и в каждой тройке произведем обмен первого элемента со вторым и в итоге, для данного примера, получим последовательность 101, а на следующем шаге 01.
Определим количество операций обмена, которые мы совершим на данном шаге: оно равно минимуму из K и количеством троек, на которые можно разбить нашу последовательность. Обозначим его за C. Теперь мы будем совершать операции обмена, меняя в каждой тройке первый и второй элементы. Эти обмены необходимо совершать только в последних C тройках нашей последовательности, оставляя первые Z = M - C * 3 элементов неизменными.
Займемся обменами элементов в последних C тройках. Пусть j - элемент, с которого начинается изменение последовательности, j = M - C * 3 + 1. Теперь, перебирая все i от C до 1, выводим все A[q], где q = M - i * 3 + 1 (начало первой группы в тройке), вывод такого число обозначает, что мы поменяли группу q с группой q + 1, это значит, что объединились группы q - 1 и q + 1, а также группы q и q + 2. Необходимо внести соответствующее изменение в массив: A[j] := (A[q + 2] - A[q + 1]) + A[q], где (A[q + 2] - A[q + 1]) - длина последовательности q + 1, которая теперь встала перед q. После этого необходимо увеличить j на 1. Отдельно рассматривается случай, когда q = 1: здесь вместо четырех участвуют три группы и поэтому менять следует не первую группу со второй, а вторую с третьей, т.е. предварительно увеличить j на 1.
Такой, казалось бы, сложный и запутанный способ решения задачи избавляет нас от использования списков или многократного присваивания массивов. Надеюсь, при внимательном прочтении и рисовании возможных вариантов и последовательности действий на бумаге все станет понятно.

Задача g6_1077: Квадраты 2

В одном квадратном государстве жили квадратные люди. И все остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной а метров, покупатель платил а2 квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок. Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это, безусловно, можно было сделать, приобретя участки размером 1*1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. "Так мне будет легче общаться с Квадратной Налоговой Инспекцией", - сказал он. Сделка состоялась.
Задание:
Напишите программу SQUARE, которая находит количество свидетельств, полученных жителем.
Входные данные:
Единственная строка входного файла SQUARE.DAT содержит целое положительное число N <= 60000 - число квадриков, которое было у жителя.
Выходные данные:
Единственная строка выходного файла SQUARE.SOL содержит число свидетельств, полученных в результате сделки.

SQUARE.DAT
344
SQUARE.SOL
3

Решение g6_1077:
Эта задача решается с помощью динамического программирования.
Сначала проверим, не является ли число полным квадратом. Если так, то сразу выводим "1" и заканчиваем. Если же не является, то придется потрудиться.
Заведем массив размером в 60000 элементов - в нем мы будем хранить количество участков для каждой площади. Пройдем его с 1 до N, если текущее число (i) - квадрат целого числа, то в соответствующий элемент массива записываем 1 и переходим к следующему. Если же это не так, то тут понадобиться еще один цикл (j) от 1, до тех пор, пока разность между i и j2 не станет меньше 1. Итак, мы можем узнать, сколько участков необходимо, чтобы скупить территорию i - j2; для того, чтобы скупить территорию площадью i, необходимо на один участок больше (этот участок со стороной j). Среди всех возможных j выберем минимальное количество участков для площади i и перейдем к следующему i. Этим мы полностью рассматриваем все варианты и выбираем наилучший (в этом несложно убедиться).

Задача g6_1078: Калькулятор (Командное соревнование школьников Свердловской области 2003)

автор: Денис Расковалов
Странные времена настали в Лощине Янтарной Росы. Все куда-то бегут, что-то покупают-продают, постоянно норовя обмануть друг друга. Нет былого спокойствия. Смутное время не обошло и Монастырь Светлой Луны: Никогда еще не было такого, чтобы обычный торговец пытался обмануть монахов, боязнь гнева Будды останавливала его. Но и этот страх померк перед страстью наживы.
Мудрый Настоятель подозревает, что один из поставщиков Монастыря нечист на руку. Известно, что при подсчете стоимости товара он использует Калькулятор. Этот Калькулятор умеет не так уж и много... Все что он умеет это:
1. ввести число 1
2. удвоить текущее число
3. поменять в текущем числе первую и последнюю цифры.
Калькулятор умеет работать лишь с целыми числами от 1 до 10000.
Обычно Торговец привозит в Монастырь товар, затем, пользуясь Калькулятором, подсчитывает стоимость товара, называет сумму Настоятелю, и Настоятель оплачивает товар. Настоятель хочет узнать, не обманывает ли его Торговец, называя сумму, которая не может быть получена с помощью Калькулятора. Помогите ему в этом.
Ввод. В файле находится единственное число k - сумма, названная Торговцем (1 <= k <= 10000)
Вывод. Выведите "YES", если сумма может быть получена с помощью Калькулятора, и "NO" в противном случае.

Пример input.txt #1
8042
Пример output.txt #1
YES
Пример input.txt #2
3
Пример output.txt #2
NO

Решение g6_1078:
На вход нам дается единственное число k, необходимо проверить, возможно ли получить его из числа 1 с помощью двух операций - умножения на 2 и обмена первой и последней цифр. Эта задача эквивалентна задаче о том, возможно ли из числа k получить число 1, с помощью операций - разделить на 2 и поменять местами первую и последнюю цифры числа.
Так мы и сделаем - напишем рекурсивную процедуру, которая состоит из трех условий:
Если текущее число 1, то выводим "YES" и прекращаем работу программы.
Если текущее число делится на 2, то запускаем рекурсивную процедуру, для числа, вдвое меньшего текущего.
Если после перестановки цифр число делится на 2, то запускаем рекурсивную процедуру для вдвое меньшего числа.
Здесь возникает вопрос: а не возникнет ли бесконечного цикла, т.е. мы переставляем цифры, получаем некоторое число, затем делим его на 2 и опять получаем первое число. Я не смог придумать, как проверить и отсечь это, кроме как создать массив от 1 до 10000 и проверять, не встречалось ли число ранее.
Для того чтобы переставить цифры, можно разбить число на части и собрать его заново, а можно перевести в строку и просто поменять местами первый и последний символы.

Задача g6_1079: Предсказание (Командное соревнование школьников Свердловской области 2003)

автор: Александр Сомов (подготовил Денис Расковалов)
Не секрет, что многие жители Лощины Янтарной Росы часто обращаются к монахам Монастыря с различными вопросами. Каждую весну жители окрестных деревень спрашивают Настоятеля, сколько мешков зерна они соберут осенью c одного посаженного весной мешка. Настоятелю надоело каждый раз изобретать ответ на этот вопрос, и он решил придумать алгоритм, который бы генерировал ответ (не подумайте, что он был просто шарлатаном, но нельзя же тревожить Будду по таким пустякам). Он решил, что будет отвечать по следующему правилу (такое уж хитрое правило никто не раскусит):
Факториалом числа n, n - натуральное, Настоятель называет число, определяемое по правилу: n! = 1, если n = 1
n! = n*(n - 1)!, еcли n > 1
Функция F(x), x >= 0 вычисляется по следующему правилу:
F(x) = x, если x <= 9
F(x) = F(S(x)), если x > 9
где S(x) - сумма цифр в десятичной записи числа x.
Правило это Настоятель применяет следующим образом: в год с номером n от рождения Будды мудрый Настоятель сообщает, что они соберут F(n!) мешков зерна с одного посаженного мешка весной. С каждым годом все трудней и трудней Настоятелю вычислять F(n!), ваша цель - помочь ему в этом.
Ввод. Единственное число n - номер года, 1 <= n < 200
Вывод. F(n!) - ответ Наставника
Пример input.txt #1
3
Пример output.txt #1
6
Пример input.txt #2
4
Пример output.txt #2
6

Решение g6_1079:
Заметим, что любой факториал числа, большего 5 делится на 9. Это следует из того, что он состоит из множителей 3 и 6, которые при умножении на другие числа дают число, кратное 9. Воспользуемся свойством делимости на 9: если число делится на 9, то и сумма его цифр делится на 9. Мы знаем, что наш факториал кратен 9 (при n > 5), т.е. и сумма его цифр кратна 9. Если сумма цифр больше 9, то снова подсчитаем сумму цифр уже этого числа, она также будет кратна 9. Т.е. конечным результатом всегда будет 9.
А первые 5 значений несложно рассчитать вручную: 1, 2, 6, 6, 3.

Задача g6_1080: Чайнворд (15 Всероссийская олимпиада по информатике 2003)

Автор: Михаил Климов.
Журналисты газеты "The Run Times" к каждому номеру готовят чайнворд. Чайнворд - это последовательность клеток, в которые читатель вписывает угаданные слова. При этом каждое следующее слово последовательности должно начинаться с той же буквы, которой заканчивается предыдущее, и эта буква записывается в одной клетке. Одно и то же слово в чайнворде может встречаться несколько раз. Количество клеток в чайнворде называется его длиной. Например, в чайнворд длины 9 можно вписать слова "set", "too" и "olymp" следующим образом: "setoolymp".
Из имеющегося списка слов журналисты должны составить чайнворд, а затем выделить в нем некоторые клетки так, чтобы из прочитанных последовательно слева направо букв в выделенных клетках образовывался лозунг спонсора газеты. Так, в приведенном выше примере чайнворд был составлен специально для лозунга "soly", который можно прочитать, если, например, выделить в чайнворде первую, четвертую, шестую и седьмую клетки.



Для экономии места в газете журналисты хотят составить чайнворд минимальной длины.
Напишите программу, которая по заданному списку английских слов и лозунгу составит такой чайнворд.
Входные данные
В первой строке входного файла записан лозунг спонсора, содержащий от одной до 250 букв. Во второй строке записано число N - количество слов, которые можно использовать при составлении чайнворда (1 <= N <= 1000). В последующих N строках перечисляются различных слова, каждое из которых содержит от двух до 10 букв.
Лозунг и все слова состоят только из строчных латинских букв. Ни одна из строк входного файла не содержит пробелов.
Выходные данные
В выходной файл выведите слова, из которых будет составлен чайнворд. Каждое слово должно быть выведено в отдельной строке. Порядок слов определяется порядком их расположения в чайнворде. Если решений несколько, выведите любое из них.
Если из заданных слов требуемый чайнворд составить невозможно, то выходной файл должен содержать только один символ - знак вопроса.
Примеры

kolonna-mchs-rossii-ostaetsya-zablokirovannoj-na-granice-serbii-i-kosovo-informacionnoe-agentstvo-ria-dagestan-respublikanskoe-informacionnoe-agentstvo-15122011.html
kolontituli-i-koloncifri-statya-iz-knigi-ili-drugogo-razovogo-izdaniya-35.html
koloskov-vi-hudozhestvennaya-literatura-rossijskaya-proza.html
kolpakidi-a-i-prohorov-d-p-imperiya-gru-ocherki-istorii-rossijskoj-voennoj-razvedki-stranica-10.html
koltanovskij-igor-aleksandrovich-abakumov-gorbunov-aleksandr-nikolaevich.html
kolumbiya-nastoyashee-issledovanie-provedeno-po-zakazu-ministerstva-po-antimonopolnoj-politike-i-podderzhke-predprinimatelstva.html
  • abstract.bystrickaya.ru/-1obshestvenno-politicheskaya-zhizn-v-sssr-v-19531964gg-nshrushev-posobie-dlya-podgotovki-k-edinomu-gosudarstvennomu-ekzamenu.html
  • occupation.bystrickaya.ru/metodika-prepodavaniya-osnov-vzaimozamenyaemosti-i-standartizacii-na-baze-vuza.html
  • reading.bystrickaya.ru/metodicheskie-rekomendacii-krasnoyarsk-2005-podgotovka-diplomnih-rabot-po-specialnosti-yurisprudenciya-metodicheskie-rekomendacii.html
  • exchangerate.bystrickaya.ru/ii-tri-mira-i-ih-otrazheniya-razlichie-sostoyanij-soznaniya-starogo-i-novogo-vremeni.html
  • control.bystrickaya.ru/bibliotechnij-fond-uchrezhdeniya-municipalnoe-obsheobrazovatelnoe-uchrezhdenie-gimnaziya-19-g-orla.html
  • testyi.bystrickaya.ru/84-stroitelstvo-i-priemka-v-ekspluataciyu-postanovlenie-gosgortehnadzora-rf-ot-18-marta-2003-g-n-9.html
  • vospitanie.bystrickaya.ru/zabelina-n-a-direktor-gbuk-g-moskvi-mgdb.html
  • vospitanie.bystrickaya.ru/zeleninaig-zam-direktora-po-nmr-mou-sosh-97-razvitie-kreativnih-kachestv-lichnosti-cherez-realizaciyu-licejskogo-komponenta-v-obrazovatelnom-processe.html
  • college.bystrickaya.ru/3-razrabotani-sushnostnie-i-tipologicheskie-harakteristiki-innovacionnih-uslug-opredelyayushih-innovacionno-orientirovannoe-razvitie-servisnoj-sferi.html
  • control.bystrickaya.ru/eposi-legendi-i-skazaniya-stranica-29.html
  • studies.bystrickaya.ru/bank-kak-subekt-privlecheniya-inostrannih-investicij-v-region-na-primere-kb-centr-invest-chast-10.html
  • abstract.bystrickaya.ru/23-po-sledam-skazki-o-care-saltane-atlantida.html
  • kontrolnaya.bystrickaya.ru/proishozhdenie-drevnerusskoj-zhivopisi.html
  • knigi.bystrickaya.ru/shiis-azastan-oblisini-aumatarin-damitu-badarlamasin-ske-asiru-turali-esep.html
  • crib.bystrickaya.ru/instrukciya-po-proektirovaniyu-i-montazhu-sistem-otopleniya-zdanij-iz-metalloplastikovih-trub-vsn-123-90-stranica-10.html
  • reading.bystrickaya.ru/metodicheskie-ukazaniya-dlya-slushatelej-kursa-professionalnoj-perepodgotovki-po-specialnosti-profpatologiya.html
  • notebook.bystrickaya.ru/kak-zhe-vse-taki-bit-schastlivim-specialnie-programmi-dlya-resheniya-zadach-v-takih-oblastyah-kak-sozdanie-garmonichnih-otnoshenij.html
  • write.bystrickaya.ru/globalizaciya-i-geopolitika-epohi-post-bipolyarnosti-politicheskaya-karta-mira-politicheskaya-karta-mira-kak-geopoliticheskoe.html
  • lecture.bystrickaya.ru/8razreshenie-sporov-i-raznoglasij-konkursnaya-dokumentaciya.html
  • student.bystrickaya.ru/22kriterii-ocenki-mezhdunarodnih-podhodov-programma-organizacii-obedinennih-nacij-po-okruzhayushej-srede-distr-general.html
  • ucheba.bystrickaya.ru/priblizitelnie-znacheniya-koefficientov-otrazheniya-sten-i-potolka-raschet-i-proektirovanie-iskusstvennogo-osvesheniya.html
  • spur.bystrickaya.ru/lekcii-po-marketingu-7.html
  • writing.bystrickaya.ru/gorkij-m-m-gorkij-pravda-bog-svobodnogo-cheloveka.html
  • kontrolnaya.bystrickaya.ru/programmi-v-kambodzhu-sezon-2011-klassicheskie-programmi-s-posesheniem-ankor-vata.html
  • holiday.bystrickaya.ru/obrazovatelnaya-programma-gosudarstvennogo-obsheobrazovatelnogo-uchrezhdeniya-srednej-obsheobrazovatelnoj-shkoli-604-s-uglublennim-izucheniem-predmetov-hudozhestvenno-esteticheskogo-cikla-stranica-6.html
  • knigi.bystrickaya.ru/situaciya-s-prirodnimi-pozharami-v-rossii-kontroliruemaya-soobshil-zubkov-informacionnoe-agentstvo-itar-tass-02082011.html
  • uchebnik.bystrickaya.ru/vneshneekonomicheskaya-deyatelnost-chast-6.html
  • education.bystrickaya.ru/3-trebovaniya-k-uchastnikam-i-usloviya-dopuska-o-provedenii-oblastnih-sorevnovanij-po-vidam-sporta-na-2010-god.html
  • abstract.bystrickaya.ru/24-kak-naladit-upravlenie-personalom-gorodskoj-administracii-vvedenie-v-predmet.html
  • laboratornaya.bystrickaya.ru/programma-vserossijskoj-nauchno-prakticheskoj-konferencii-1-2-marta-2006-goda-orgkomitet-konferencii.html
  • lecture.bystrickaya.ru/anglijskij-dlya-nashih-stranica-8.html
  • tests.bystrickaya.ru/kompleksnaya-programma-razvitiya-federalnogo-gosudarstvennogo-uchrezhdeniya-visshego-proffesionalnogo-obrazovaniya-moskovskogo-fiziko-tehnicheskogo-institututa-stranica-4.html
  • books.bystrickaya.ru/dobrenkov-v-i-kravchenko-a-i-metodi-sociologicheskogo-issledovaniya-uchebnik-dlya-vuzov-m-infra-m-2008.html
  • knowledge.bystrickaya.ru/nachalnik-otdela-kontrolya-obespecheniya-bezopasnosti-edinij-kvalifikacionnij-spravochnik.html
  • uchebnik.bystrickaya.ru/uchebno-metodicheskij-kompleks-disciplini-intellektualnie-informacionnie-sistemi-specialnost.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.