#1776

Головоломка

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2005, Задача G ]

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

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

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

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

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

Входные данные

Первая строка входного файла содержит число \(k\) – количество карт (1 ≤ \(k\) ≤ 10).

Затем следуют \(k\) блоков, которые описывают карты. Первая строка каждого блока содержит два целых числа \(n_i\) и \(m_i\) (2 ≤ \(n_i\) ≤ 50, 1 ≤ \(m_i\) ≤ 1500), они задают количество позиций и количество отрезков на \(i\)-й карте, соответственно. Будем считать, что позиции пронумерованы числами от 1 до \(n_i\), причем начальная позиция имеет номер 1, а конечная – номер \(n_i\). В следующих \(m_i\) строках находятся пары номеров позиций, соединенных соответствующим отрезком.

Выходные данные

В случае, если существует последовательность ходов, после которой фишки на каждой карте одновременно окажутся в конечных состояниях, выведите в выходной файл минимальную длину такой последовательности. Если такой последовательности не существует, выведите слово «Impossible».

Примеры

Входные данные

Выходные данные

#1777

Экспериментатор

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2005, Задача H ]

На старости лет один профессор загорелся идеей исследования на прочность транзисторов «КД521(2)». К сожалению, ему не удалось привлечь на помощь никого из коллег, поэтому проводить измерения придется самостоятельно. Но это не пугает профессора.

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

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

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

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

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

Изначально профессор находится на первом этаже, и у него имеется m транзисторов. В доме, в котором живет профессор, n этажей.

Найдите минимальное число этажей, которое профессору в худшем случае придется подниматься вверх по лестнице во время проведения экспериментов.

Входные данные

Во входном файле заданы два целых числа – высота дома \(n\) (2 ≤ \(n\) ≤ 50) и количество транзисторов \(m\) (1 ≤ \(m\) ≤ 10).

Выходные данные

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

Примеры

Входные данные

2 1

Выходные данные

Входные данные

3 1

Выходные данные

#1778

Перевод времени

Темы: [Дата и время]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2005, Задача I ]

Как известно, с целью экономии электроэнергии многие страны используют переход на так называемое летнее время. Перевод времени осуществляется два раза в год – весной и осенью. Весной осуществляется переход на летнее время: часы переводятся на один час вперед. Осенью летнее время отменяется и часы переводятся на один час назад.

Перевод времени осуществляется ночью. При переходе на летнее время через минуту после 01:59 сразу наступает 03:00. При отмене летнего времени час с 02:00 по 02:59 повторяется два раза. А именно, в день перевода, когда первый раз после 02:59 должно стать 03:00, вместо этого снова становится 02:00.

Как одному из разработчиков новой операционной системы «Mocrosoft Widows 2006», вам поручено написать фрагмент ядра операционной системы, который будет осуществлять автоматический перевод системных часов на летнее время и обратно.

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

Входные данные

Первая строка входного файла содержит целое число m – количество минут, которое прошло от начала текущих суток, до первого момента времени, который следует вывести. Гарантируется, что оно неотрицательно и строго меньше числа минут в текущих сутках.

На второй строке находятся два целых числа \(d_1\) и \(d_2\), которые указывают, какой перевод времени осуществляется в текущие и в следующие сутки. Значение 1 означает, что осуществляется переход на летнее время, -1 означает, что осуществляется отмена летнего времени, а 0 означает, что перевода времени не осуществляется.

На третьей строке записано число \(k\) – количество отсчетов времени, которое ваша программа должна вывести (1 ≤ \(k\) ≤ 600).

Выходные данные

Выходной файл должен состоять из \(k\) строк, \(i\)-я из которых должна содержать показания часов через (\(i\)-1) минут после начального момента времени. Выводите время в формате «hh:mm».

Примеры

Входные данные

118
1 0
4

Выходные данные

Входные данные

190
-1 0
1

Выходные данные

02:10

Входные данные

0
-1 0
3

Выходные данные

00:00
00:01
00:02

Входные данные

1438
0 1
4

Выходные данные

#1779

Стена

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2005, Задача J ]

Фирма «Kel-Morian Productions» разрабатывают искусственный интеллект для новой автоматизированной модели промышленного робота SCV-2. На данном этапе создается робот для строительства и ремонта стен, составленных из стандартных строительных блоков.

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

Рисунок 1

Первая модель робота может выполнять ровно одно элементарное действие – взять верхний блок в некотором столбике и положить его на соседний столбик. При этом создавать новый столбик, ставя блок рядом с краем стены, не разрешается.

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

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

Рисунок 2

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

Входные данные

В первой строке входного файла записано целое число \(n\) (1 ≤ \(n\) ≤ 1000) – количество вертикальных рядов, из которых состоит стена. Вторая строка содержит числа \(a_1\), \(a_2\), …, \(_n\), где \(a_i\) задает количество блоков в \(i\)-м столбике (1 ≤ \(a_i\) ≤ \(10^6\)).

Выходные данные

В выходной файл выведите единственное целое число – минимальное количество перемещений блоков, необходимое для выравнивания стены.

Примеры

Входные данные

7
2 3 3 4 2 3 4

Выходные данные

#1780

Атака инопланетян

Темы: [Бинарный поиск]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2006, Задача A ]

На город Энск нападает флот инопланетян. Флот состоит из n космических кораблей, каждый из которых имеет форму равнобедренного прямоугольного треугольника.

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

Флот инопланетян прилетел с северо-востока, и застыл в таком положении, что все оси кораблей направлены строго на юго-запад.

Единственный способ нанести урон инопланетной армии – это пустить из некоторой точки поверхности Земли лазерный луч вертикально вверх. Пущенный так луч прожигает насквозь все вражеские корабли, через которые он проходит (даже те, которые он задевает по границе). Но этот выстрел повредит инопланетянам только в случае, если все n кораблей будут при этом поражены.

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

Помогите военным определить площадь территории, на которой можно поставить лазер.

Входные данные

В первой строке входного файла содержится целое число \(n\) – количество инопланетных кораблей (1 ≤ \(n\) ≤ 100).

В каждой из следующих n строк описывается положение очередного корабля. Описание состоит из трех целых чисел \(x_i\), \(y_i\) и \(s_i\), где \(x_i\) и \(y_i\) – координаты носа, а \(s_i\) – размер корабля. Поскольку корабль имеет форму равнобедренного прямоугольного треугольника, размером корабля военные решили называть длину катета.

Размеры кораблей – положительные числа, не превышающие 1 000. Координаты носов кораблей не превышают по абсолютной величине \(10^5\).

Выходные данные

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

Примеры

Входные данные

Выходные данные

4.500