XI Всеукраинская олимпиада по информатике

1. Часы

Жители планеты Олимпия любят летать в гости на другие планеты. Ученые планеты разработали часы, которые могут налаживаться для отсчета времени на любой планете. Эти часы состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

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

Входные данные. Входной текстовый ASCII-файл CLOCK.DAT содержит в единственной строке натуральны числа S, M, H, K (количество секунд в минуте, минут в часе, часов в сутках и общее количество шариков соответственно; S, M, H £ 60, S+M+H-2£ K£ 1000).

Выходные данные. Выходной текстовый ASCII-файл CLOCK.SOL должен содержать в единственной строке вычисленное Вашей программой количество суток.

Замечание. В тестах, которые будут применяться при проверке, использование длинной арифметики не предусматривается. Для представления количества суток советуем использовать типы данных extended в Pascal и long double в C.

Пример ввода и вывода.

2. Водопровод

Город состоит из N районов (1£ N£ 100). Каждый район имеет скважину для добычи воды. Каждые две скважины соединены между собой трубой. По каждой трубе вода может течь только в одном направлении. Вследствие энергетического кризиса в каждый момент времени работает только одна скважина. Поскольку система проектировалась без предусмотрения такого режима работы, некоторые районы города иногда остаются без воды.

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

Входные данные. В первой строке файла WATER.DAT находится число N - количество районов (скважин) в городе. В следующих N строках для каждой скважины указываются количество и номера скважин, из которых к ней поступает вода. Скважины имеют номера от 1 до N.

Выходные данные. В единственной строке файла WATER.SOL должно быть одно число - номер искомой скважины, если таковая существует, либо 0 в противном случае.

Пример ввода и вывода.

3. Охрана

Дано N (1£ N£ 100) пронумерованных объектов, которые охраняются и соединены K дорогами (1£ K£ 4950). Из любого объекта в любой можно проехать дорогами. Движение каждой дорогой возможно в оба направления. Необходимо разместить подразделение охраны так, чтобы наиболее удаленный объект достигался как можно быстрее.

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

Входные данные. Входной текстовый ASCII-файл POLICE.DAT в первой строке содержит натуральные числа N и K. В следующих K строках содержатся по три натуральных числа F, T, S (объекты с номерами F и T соединяет дорога длиной S километров, 1£ S£ 100; непосредственно между F и T может быть не более одной дороги).

Выходные данные. Выходной текстовый ASCII-файл POLICE.SOL должен содержать числа D, L, M, R (расстояние до наиболее удаленного пункта равно D, подразделение следует разместить в R километрах от объекта L на дороге до объекта M).

Пример ввода и вывода.