Управление образования г. Якутска

Задача A. Часы с боем

Старинные часы бьют каждые полчаса. Причем в начале каждого часа они бьют столько раз, сколько сейчас часов (по 1 разу - в час ночи и в час дня, по 2 раза - в два часа ночи в два часа дня и т.д., в полночь и в полдень они бьют, соответственно, по 12 раз). И еще 1 раз они бьют в середине каждого часа.

Дан промежуток времени (известно, что прошло строго меньше 24 часов). Напишите программу, определяющую, сколько ударов сделали часы за это время.

Формат входных данных

В первой строке записан начальный момент времени, во второй строке - конечный. Моменты времени задаются двумя целыми числами, разделяющимися пробелом. Первое число задает часы (от 0 до 23), второе - минуты (от 1 до 59, при этом оно не равно 30).

Формат выходных данных

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

Примеры

5 20
10 25

45

10 25
5 20

135

5 2
5 21

0

Задача B. Выборы жрецов

В стране Олимпиадии снова выборы.

Страна состоит из маленьких графств. Графства объединяются в конфедерации. Каждая конфедерация раз в год выбирает себе покровителя - одного из 200 жрецов. Этот ритуал называется Великими Перевыборами Жрецов и выглядит так: конфедерации одновременно подают заявления (одно от конфедерации) в Совет Жрецов о том, кого они хотели бы видеть своим покровителем (если заявление не подано, то считают, что конфедерация хочет оставить себе того же покровителя). После этого все заявки удовлетворяются. Если несколько конфедераций выбирают одного и того же Жреца, то они навсегда объединяются в одну. Таким образом, каждый Жрец всегда является покровителем не более чем одной конфедерации. Требуется написать программу, позволяющую Совету Жрецов выяснить номер Жреца-покровителя каждого графства после Великих Перевыборов. В Совете все графства занумерованы (начиная с 1). Все Жрецы занумерованы числами от 1 до 200 (некоторые из них сейчас могут не быть ничьими покровителями).

Формат входных данных

Во входном файле записано число N - количество графств в стране (1≤N≤5000) - и далее для каждого графства записан номер Жреца-покровителя конфедерации, в которую оно входит (графства считаются по порядку их номеров). Затем указаны заявления от конфедераций. Сначала записано число M - количество поданных заявлений, а затем M пар чисел: первое число - номер текущего Жреца-покровителя, второе - номер желаемого Жреца-покровителя.

Все числа во входном файле разделяются пробелами и (или) символами перевода строки.

Формат выходных данных

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

Пример

7
1 1 5 3 1 5 1
2
5 1
1 3

3 3 1 3 3 1 3

Задача C. Представление чисел

Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B - максимален.

Формат входных данных

Во входном файле записано натуральное число N (2≤N≤10⁹)

Формат выходных данных

В выходной файл выведите два искомых числа A и B. Если решений несколько, выведите любое из них.

Примеры

15

5 10

16

8 8

Задача D. Гексагон

Поле для игры в новую игру "Гексагон" разбито на шестиугольники (см. рисунок). Игрок, стартуя из некоторого начального шестиугольника, сделал несколько ходов. Каждый ход заключается в перемещении фишки в соседний шестиугольник (имеющий с тем, где находилась фишка до начала хода, общую сторону) - тем самым, ход делается вдоль одного из направлений X, Y или Z (см. рисунок). Игрок записал все свои ходы, причем если фишка двигалась вдоль какого-либо направления несколько раз подряд, то в записи это обозначается указанием направления и количества ходов, которые были сделаны.

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

Формат входных данных

В первой строке входного файла записано число N - количество строк в записи перемещений фишки (1≤N≤100). Далее идет N строк с записью ходов: в каждой строке записана сначала большая буква X, Y или Z, задающая направление, затем пробел, и число, задающее количество ходов в данном направлении (число может быть и отрицательным, если игрок перемещал фишку параллельно оси, но в направлении, противоположном направлению оси). Все числа по модулю не превышают 200.

Формат выходных данных

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

Пример

4
Z -2
Y 3
Z 3
X -1

2
Y -2
Z -2

Задача E. Магия Копперфильда

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

1	2	...	N
N+1	N+2	...	2*N
:	:	...	:
N*(N-1)+1	N*(N-1)+2	...	N*N

Дэвид просит каждого зрителя поставить палец на левую верхнюю картинку (то есть в клетку номер 1), и Магия начинается: маг просит зрителей сдвинуть свой палец K1 раз в произвольном направлении (сдвигать палец разрешается только на соседнюю картинку по горизонтали или по вертикали, оставлять палец на месте запрещено, при этом если, допустим, Дэвид попросил сдвинуть палец 3 раза, то можно, например, сдвинуть палец на одну клетку вправо, затем - на одну клетку вниз, затем - на одну вверх). Затем со словами "Ваш палец не здесь" Дэвид убирает некоторые картинки, и - что удивительно, пальцы телезрителей действительно не указывают на те картинки, которые убирает Дэвид. Затем он просит сделать K2 ходов, и так далее (если Дэвид уже убрал какую-то картинку, то ходить через эту клетку нельзя). В конце, Дэвид убирает все картинки, кроме одной, и, улыбаясь, говорит: "Вы здесь" (аплодисменты).

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

Формат входных данных

Во входном файле записано одно число N - размер квадрата (2≤N≤100).

Формат выходных данных

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

K1	X1,1	X1,2	...	X1,m1
K2	X2,1	X2,2	...	X2,m2
...	...	...	...	...
Ke	Xe,1	Xe,2	...	Xe,me

где K_i - это число ходов, которые должны сделать телезрители, а X_i,1 ... X_i,mi - номера картинок, которые Дэвид должен убрать с экрана после этого. При этом все K_i должны удовлетворять условию 2N≤K_i≤10000 и все K_i должны быть различны. Каждая картинка (кроме той, которая останется) должна убираться ровно один раз. После каждой просьбы зрителей сделать K_i ходов, Дэвид должен убирать хотя бы одну картинку. Каждое K_i должно печататься в начале новой строки. Ситуаций, когда телезритель остался на клетке, у которой нет соседних, а его просят куда-нибудь ходить, возникать не должно.

Пример

3

8 4 6
13 9
10 7 1
7 8
11 3 5

Задача F. Кубическое уравнение

Напишите программу, которая будет искать все целые X, удовлетворяющие уравнению

AX³ + BX² + CX + D = 0,

где A, B, C, D - данные целые числа.

Формат входных данных

Во входном файле записаны четыре целых числа: A, B, C, D. Все числа по модулю не превышают 2*10⁹.

Формат выходных данных

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

Примеры

1 0 0 -27

1 3

0 1 2 3

0

Задача G. Скорая помощь

Бригада скорой помощи выехала по вызову в один из отделенных районов. К сожалению, когда диспетчер получил вызов, он успел записать только адрес дома и номер квартиры K₁, а затем связь прервалась. Однако он вспомнил, что по этому же адресу дома некоторое время назад скорая помощь выезжала в квартиру K₂, которая расположена в подъезда P₂ на этаже N₂. Известно, что в доме M этажей и количество квартир на каждой лестничной площадке одинаково. Напишите программу, которая вычилсяет номер подъезда P₁ и номер этажа N₁ квартиры K₁.

Формат входных данных

Во входном файле записаны пять положительных целых чисел K₁, M, K₂, P₂, N₂. Все числа не превосходят 1000.

Формат выходных данных

Выведите два чиса P₁ и N₁. Если входные данные не позволяют однозначно определить P₁ или N₁, вместо соответствующего числа напечатайте 0. Если входные данные противоречивы, напечатайте два числа -1 (минус один).

Примеры

89 20 41 1 11

2 3

11 1 1 1 1

0 1

3 2 2 2 1

-1 -1

Задача H. Функция A от строчки

Дана строка S, состоящая из N символов. Определим функцию A(i) от первых i символов этой сроки следующим образом:

A(i) = максимально возможному k, что равны следующие строки:

S[1]+S[2]+S[3]+...+S[k]
S[i]+S[i-1]+S[i-2]+...+S[i-k+1]

где S[i] - i-ый символ строки S, а знак + означает, что символы записываются в строчку непосредственно друг за другом.

Напишите программу, которая вычислит значения функции A для заданной строчки для всех возможных значений i от 1 до N.

Формат входных данных

В первой строке входного файла записано одно число N. 1≤N≤200000. Во второй строке записана строка длиной N символов, состоящая только из больших и/или маленьких латинских букв.

Формат выходных данных

В выходной файл выведите N чисел - значения функции A(1), A(2), ... A(N).

Пример

5
aabaa

1 2 0 1 5