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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ Y ≤ 3000.

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

2001

XXI

2000

XX

658

VII

2703

XXVIII

Задача B. Девушки-программисты ≡

Условие

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

Перед чемпионатом производится формирование команд: участники выбирают, с кем они будут в одной команде.

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

У жюри есть мешок с N шариками. На шариках написаны числа от 1 до N.

Всего участников N (причём N кратно трём), среди них M девушек.

Жюри достаёт из мешка 3 шарика (считаем, что все возможные тройки шариков равновероятны). Участники с соответствующими номерами в списке объединяются в команду.

Итак, требуется для каждого k = 0, 1, 2, 3 вычислить вероятность p_k случайного события, состоящего в том, что в этой команде будет k девушек.

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

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

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

Требуется вывести в выходной файл 4 вещественных числа: p₀, p₁, p₂, p₃ — с точностью до 5 знаков после десятичной точки.

Ограничения

1 ≤ M ≤ N ≤ 100.

N делится на 3.

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

3 1

0.00000 1.00000 0.00000 0.00000

3 2

0.00000 0.00000 1.00000 0.00000

6 4

0.00000 0.20000 0.60000 0.20000

6 2

0.20000 0.60000 0.20000 0.00000

Задача C. Марфа Геннадьевна и социальная сеть ≡

Условие

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

Деревенский программист-самоучка Иван Никанорович создал социальную сеть ДN ("Деревня Network") специально для жителей деревень, и деревенские жители стали регистрироваться в этой социальной сети.

Как и в остальных социальных сетях, в социальной сети ДN у каждого пользователя есть так называемый "список друзей", и пользователи могут отправлять друг другу сообщения.

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

Однажды утром Марфа Геннадьевна отправила всем пользователям сети ДN из "списка её друзей" ссылку на интересный сайт. Вечером все эти пользователи получили сообщение.

Затем информация распространялась по сети ДN следующим образом.

1. Сообщения отправляются только утром, а получаются только вечером.
2. Если пользователь B получил информацию от пользователя A, то утром следующего дня пользователь B разошлёт эту информацию всем пользователям из "списка его друзей", от которых он не получал эту информацию и которым он не отправлял эту информацию.

Отметим, что социальная сеть ДN устроена таким образом, что если пользователь B находится в "списке друзей" пользователя A, то и пользователь A находится в "списке друзей" пользователя B. Никакой пользователь не может находиться в своём же "списке друзей".

Требуется определить, сколько раз каждый пользователь социальной сети ДN получит информацию (ссылку на сайт с кулинарными рецептами).

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

Первая строка входного файла содержит целое число N — количество пользователей социальной сети ДN.

Далее для каждого пользователя во входном файле записана следующая информация. Сначала идёт целое число k_i — количество пользователей в "списке друзей" пользователя i, за которым следуют k_i различных целых чисел от 1 до N — номера пользователей из списка друзей i-го пользователя.

Марфа Геннадьевна — это пользователь с номером 1.

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

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

Ограничения

1 ≤ N ≤ 100.

0 ≤ k_i < N.

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

3
2  2 3
1  1
1  1

0 1 1

3
2  2 3
2  3 1
2  1 2

0 2 2

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

0 1 1 1 2 0

Задача D. Пересадка ≡

Условие

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

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

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

Входной файл содержит целое число N — количество автобусов, за которым следует N целых чисел a_i — номера маршрутов. Гарантируется, что существует хотя бы два автобуса с разными маршрутами.

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

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

Ограничения

2 ≤ N ≤ 10⁵, 1 ≤ a_i ≤ 10⁹.

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

5
23 17 17 2 23

3

3
54 54 7

1

Задача E. Перетягивание канатов ≡

Условие

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

Дети обратились к самому умному ученику в классе, Васе, с просьбой поделить их на две команды и выбрать судью.

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

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

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

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

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

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

Ограничения

3 ≤ N ≤ 30.

0 ≤ a_i ≤ 10⁷.

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

3
1 2 3
    

1

3
1 10 10
    

0

Задача F. Lode Runner возвращается ≡

Условие

Компания-разработчик компьютерных игр решила выпустить обновлённую версии классической аркадной игры Lode Runner.

Игра проходит в лабиринте, состоящем из горизонтальных платформ, соединённых лестницами. Лабиринт изображается в виде поля шириной W и высотой H клеток, каждая клетка которого содержит один из символов "." (ASCII 46) — свободное место, "X" (ASCII 88) — платформа и "#" (ASCII 35) — лестница.

По правилам игры, все платформы должны быть строго горизонтальными и не соприкасаться друг с другом (т.е. два символа "X" могут соседствовать только по горизонтали). Каждая лестница должна быть строго вертикальной и соединять две платформы (т.е. представлять собой вертикальную полосу из символов "#", над верхним и под нижним символом которой находятся символы "X"). Лестницы могут соприкасаться друг с другом, находясь на соседних вертикалях.

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

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

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

Требуется написать программу которая по данному описанию уровня игры строит уровень, соответствующий правилам и получающийся из данного минимально возможным количеством замен символов "." и "#" друг на друга.

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

Первая строка входного файла содержит целые числа W H. Следующие H строк содержат по W символов каждая — описание уровня.

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

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

Ограничения

1 ≤ W, H ≤ 1000

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

6 4
.XX.X.
......
#.#...
XXXXX.

.XX.X.
..#.#.
..#.#.
XXXXX.

Задача G. Сложение вещественных чисел - 1 ≡

Условие

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

Требуется по данным записям чисел a и b определить позиции десятичных точек в них, которые приведут к выполнению равенства a + b = c.

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

Входной файл состоит из трёх строк, содержащих десятичные записи чисел a, b и c соответственно. Все числа состоят из цифр от 0 до 9, в записи числа c присутствует ровно один символ "." (ASCII 46). Записи чисел a и b не начинаются и не заканчиваются на цифру 0.

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

Выходной файл должен содержать два целых числа P_a P_b — позиции точек в первом и втором числе соответственно. Если существует несколько решений, выведите решение с минимальным значением P_a. Гарантируется, что хотя бы одно решение существует, и что позиция десятичной точки в каждом из чисел a и b находится в диапазоне от 1 до (длина числа + 1).

Ограничения

0 < a, b ≤ 10¹⁰⁰⁰⁰⁰

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

12345
6789
680.1345

2 4

111
111
122.1

3 4