Задача A. Определить век по году ≡

Условие

Когда Андрей учился в начальной школе, его учили определять, к какому веку относится заданный год. Теперь Андрей хорошо знает, что, например, 2001 год относится к XXI веку, а 2000 год — к XX веку.

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

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

Поэтому Андрей очень просит участников Весеннего турнира-2013 написать компьютерную программу, принимающую на вход номер года в десятичной системе счисления и выводящую номер века, к которому относится этот год, в римской системе счисления.

Формат входного файла

Входной файл содержит целое число Y — номер года.

Формат выходного файла

Требуется вывести в выходной файл номер века, к которому относится год Y, в римской системе счисления, используя заглавные буквы латинского алфавита I, V, X.

Ограничения

1 ≤ Y ≤ 3000.

Примеры тестов

2001

XXI

2000

XX

658

VII

2703

XXVIII

Задача B. Кто не списал? ≡

Условие

После контрольной работы по физике преподаватель заподозрил неладное. Все сданные студентами работы были одинаковы! Поразмыслив над этим феноменом, преподаватель определил его причину: один из студентов честно выполнил задание, а остальные у него списали.

Преподаватель решил зачесть работу только тому единственному студенту, который выполнил её самостоятельно. Чтобы определить этого студента, он пронумеровал всех студентов, писавших контрольную, числами от 1 до N, и задал каждому вопрос: "Чьё это решение?".

Каждый студент назвал номер студента, который является настоящим автором работы.

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

Напишите программу, которая по этим данным определит самостоятельного студента.

Формат входного файла

Входной файл содержит два целых числа N M, за которыми следует N целых чисел a_i от 1 до N — номер самостоятельного студента по утверждению i-го студента.

Формат выходного файла

Выходной файл должен содержать единственное число — номер самостоятельного студента. Если самостоятельного студента однозначно определить невозможно, вывести −1.

Ограничения

1 ≤ N ≤ 100000 0 ≤ M ≤ 100000

Примеры тестов

2 1
1 1

-1

2 0
2 2

1

Задача C. Государство ≡

Условие

Жили-были в одномерном пространстве два правителя одного государства — два брата. Государство их было маленьким, всего одна клетка. (Всё одномерное пространство разделено на клетки.)

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

Поэтому братья придумали такую игру: посылать по очереди войска либо влево, либо вправо в любую клетку, смежную с их государством, но только не в клетку Бабы Яги. А у какого брата не останется хода, тот и выиграл. А когда они в игру наиграются, тогда и вместе пойдут на Бабу Ягу.

Схема территории показана на рисунке. В начальный момент времени государство занимает клетку с номером N+1, и братьям доступны для завоевания ещё 2 N клеток. Баба Яга занимает клетку с номером k.

Кто победит в игре при оптимальной игре игроков? Начинает игру игрок с номером 1.

Формат входного файла

Входной файл содержит целые числа N k.

Формат выходного файла

Выходной файл должен содержать число 1, если победит первый игрок, и число 2, если победит второй игрок.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ k ≤ N.

Примеры тестов

1 1

2

2 2

1

Задача D. Марфа Геннадьевна и напёрстки ≡

Условие

Этим летом Марфа Геннадьевна побывала в Турции. Там она участвовала в усложнённой игре в напёрстки. Правила игры таковы. У ведущего есть три напёрстка, под каждым из которых находится шарик, то есть всего есть три шарика: маленький, средний и большой. Ведущий может несколько раз менять местами соседние напёрстки, после чего игроку предлагается отгадать, под каким напёрстком какой шарик находится.

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

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

Формат входного файла

Первая и вторая строки входного файла содержат по 3 целых числа от 1 до 3. Число 1 означает маленький шарик, 2 — средний, 3 — большой. В каждой строке все числа различны.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — ответ в задаче.

Примеры тестов

1 2 3
3 2 1

3

2 1 3
2 1 3

0

3 1 2
3 2 1

1

Задача E. Y-хромосома ≡

Условие

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

На Марсе есть квадратное световое табло, разделённое на N × N квадратиков. Каждый квадратик может либо светиться, либо не светиться. Требуется, чтобы на табло появилась буква Y в виде русской буквы У.

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

Сколько существует способов изобразить букву Y на табло N × N? Буквы, отличающиеся размерами и/или местом, либо положением второй (маленькой) диагонали, считаются различными.

Формат входного файла

Входной файл содержит единственное целое число N.

Формат выходного файла

Выходной файл должен содержать целое число — количество способов.

Ограничения

3 ≤ N ≤ 100

Примеры тестов

3

1

4

6

5

20

Задача F. Комбинированная эстафета ≡

Условие

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

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

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

Формат входного файла

Входной файл состоит из четырёх строк по четыре числа в каждой. j-ое число в i-ой строке (обозначим его t_ij) означает время, за которое i-ый спортсмен проходит дистанцию j-ым стилем. Каждое из чисел t_ij задано не более чем с двумя знаками после десятичной точки.

Формат выходного файла

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

Ограничения

0 ≤ t_ij ≤ 120

Примеры тестов

49.61 55.47 61.97 53.33
53    59.5  66.5  57.5
56    63    70    61
59.5  67.5  75    65

3 2 4 1 

Задача G. Средняя скорость ≡

Условие

Коля каждый день ездит из дома до кампуса ДВФУ на острове Русском. Он заинтересовался, с какой средней скоростью он едет? Средняя скорость — это отношение общего пройденного пути к общему времени.

Коля разбил весь путь следования на N равных по длине участков и измерил среднюю скорость на каждом из них. Даны числа v₁, …, v_N — средние скорости на каждом участке. Требуется найти среднюю скорость на всём пути следования.

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел v_i.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100

1 ≤ v_i ≤ 100

Примеры тестов

2
40 60

48.0000

3
16 12 24

16.0000

4
40 10 20 30

19.2000

Задача H. Рисунки инопланетян ≡

Условие

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

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

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

Формат входного файла

Входной файл содержит единственное целое число N.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — количество дней, когда все рисунки состоят из одинаковых геометрических фигур.

Ограничения

Примеры тестов

3

1

18

2

25

3

Задача I. Марфа Геннадьевна ест яйца ≡

Условие

У Марфы Геннадьевны есть любимая курица, которую она назвала Марфой. В определённые дни Марфа давала по яйцу, и Марфа Геннадьевна в тот же день съедала его. Марфа Геннадьевна записывала, в какие дни Марфа давала яйцо.

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

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

Формат входного файла

Входной файл содержит целое число N.

Далее следуют N целых чисел a_i — номера дней, в которые Марфа Геннадьевна съедала яйцо.

Формат выходного файла

Требуется вывести в выходной файл слово GOOD, если Марфа Геннадьевна съедала не более двух яиц в неделю, и слово BAD, если найдётся хотя бы один промежуток из семи подряд идущих дней, в который она съедала более двух яиц.

Ограничения

1 ≤ N ≤ 100

1 ≤ a₁ < a₂ < … < a_N ≤ 1000

Примеры тестов

3
1 7 8

GOOD

5
1 7 9 12 17

BAD

Задача J. Во саду ли, в огороде ≡

Условие

Во саду ли, в огороде бегала собачка.

Огород, по которому бегает собачка, представляет собой квадрат размером N × N метров.

Разумеется, это не первая среди собак, бегавших по этому огороду, и каждая из них хотя бы раз закапывала в нем косточки. Поэтому в разных местах огорода присутствует вкусный запах разной интенсивности. Огород разделён на N² квадратиков, в квадратике с координатами (i, j) интенсивность запаха равняется a_i,j.

Квадратик с координатами (1, 1) расположен в левом верхнем углу огорода. Первая координата откладывается по горизонтали, вторая — по вертикали.

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

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

Формат входного файла

Входной файл содержит целые числа N i₀ j₀.

Далее следуют N² целых чисел a_i,j.

Формат выходного файла

Выходной файл должен содержать пары целых чисел — траекторию собаки.

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

Ограничения

2 ≤ N ≤ 100

0 ≤ a_i,j ≤ 100

1 ≤ i₀, j₀ ≤ N

Примеры тестов

3 2 2
5 0 3
2 1 1
2 3 4

2 2
2 3
3 3