Задача 1A. Стартовая решетка

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Из-за несоответствия некоторых гоночных болидов регламенту на старт выходят лишь K ≤ N участников, при этом все они сохраняют свои стартовые позиции.

Правила публикации таблицы выглядят следующим образом:

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

Во первой строке входного файла содержатся числа K и M, в следующих 2*K строках для каждого гонщика указано имя, а затем стартовая позиция. Список отсортирован по возрастанию позиций.

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

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

Ограничения

1 ≤ N, M, K ≤ 100

Длина строки с именем гонщика не превосходит 100 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1
Michael Schumacher
1
######################
#  1 starting line   #
#--------------------#
# Michael Schumacher #
######################
2
5 2
racer1
1
racer2
2
racer3
3
racer4
4
racer5
5
###################
# 1 starting line #
#--------+--------#
# racer1 |        #
#        | racer2 #
#=================#
# 2 starting line #
#--------+--------#
# racer3 |        #
#        | racer4 #
#=================#
# 3 starting line #
#--------+--------#
# racer5 |        #
#        |        #
###################
3
3 3
a
1
b
21
driver
38
############################
#     1 starting line      #
#--------+--------+--------#
#   a    |        |        #
#        |        |        #
#        |        |        #
#==========================#
#     7 starting line      #
#--------+--------+--------#
#        |        |        #
#        |        |        #
#        |        |   b    #
#==========================#
#     13 starting line     #
#--------+--------+--------#
#        |        |        #
#        | driver |        #
#        |        |        #
############################

Задача 1D. Методом тряпки

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Школьники плохо написали контрольную работу по признакам делимости на k. Марфа Геннадьевна оставила их после уроков для работы над ошибками. Она написала на доске большое число N и сама на секунду задумалась. А делится ли её число на k?

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

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

В первом примере необходимо стереть цифры 7 и 6. Если стереть цифры 1, 4, 6, то полученное число 7 будет делиться на 7, но этот ответ не оптимален.

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

В третьем примере ничего нельзя поделать.

Система оценивания

Рекомендуется рассмотреть следующие частные случаи:

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

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

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

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

Ограничения

1 ≤ k ≤ 1000;

1 ≤ N ≤ 101000;

в записи числа N нет лидирующий нулей;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7
1746
14
2
3
106
6
3
10
256
IMPOSSIBLE

Задача 1G. Кусочно-линейная функция

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Вася хочет построить алгоритм рисования графиков функций вида y = k1|x + b1| + k2|x + b2| + ... + kn|x + bn|. Он понял, что это график кусочно-линейной функции, т.е. ось x можно разбить на интервалы ненулевой длины так, что на каждом из них график представляет из себя график линейной функции. А линейные функции алгоритм Васи рисовать уже умеет. Вася просит вас помочь ему определить, из каких линейных функций будет состоять его график.

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

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

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

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

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

Ограничения

1 ≤ n ≤ 1000.

|ki|, |bi| ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1 1
2
-1 -1
1 1
2
2
1 2 3 2
2
-4 -8
4 8
3
2
2 2 -2 2
1
0 0

Задача 1X. Поездка на каникулах

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:4 сек
Входной файл:trains.in   Ограничение памяти:256 Мб
Выходной файл:trains.out  

Условие

Железная дорога Флатландии представляет собой прямую, вдоль которой расположены N станций. Будем называть участок железной дороги от некоторой станции до следующей перегоном.

Поезд следует от станции 1 до станции N, делая остановку на каждой станции. В поезде K мест, пронумерованных от 1 до K. На поезд продаются билеты, каждый билет характеризуется тремя числами: S, T и A. Такой билет позволяет проехать от станции S до станции T на месте A.

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

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

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

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

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

Первая строка входного файла содержит числа N, M и K — количество станций, количество уже проданных билетов и количество мест в поезде. Последующие M строк содержат информацию о проданных билетах.

Каждая строка содержит три числа: si, ti и ai — номер станции, от которой куплен билет, номер станции, до которой куплен билет, и номер места, на которое куплен билет.

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

Далее идет строка, которая содержит число Q. Последующие Q строк содержат описания вариантов поездки. Каждая строка содержит два числа: fj, dj — номер станции, от которой Иван хочет поехать в этом варианте, и номер станции, до которой он хочет поехать.

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

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

Ограничения

2 ≤ N ≤ 200 000; 0 ≤ M ≤ 200 000, 1 ≤ K ≤ 200 000

1 ≤ si < ti ≤ N; 1 ≤ ai ≤ K

1 ≤ Q ≤ 200 000; 1 ≤ fj < dj ≤ N

Система оценки и описание подзадач

В этой задаче три подзадачи. Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 2, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 1 и 2.

Подзадача 1 (33 баллов)

N ≤ 100; M ≤ 100; K ≤ 100, Q = 1

Подзадача 2 (30 баллов)

N ≤ 200 000; M ≤ 200 000; K ≤ 200 000; Q = 1

Подзадача 3 (37 баллов)

N ≤ 200 000; M ≤ 200 000; K ≤ 200 000; Q ≤ 200 000

Получение информации о результатах окончательной проверки

По запросу сообщаются баллы за каждую подзадачу.

Пояснение к примеру

На перегоне от 2-й до 3-й станции все места заняты, поэтому проехать от 1-й до 5-й станции невозможно. От 3-й до 5-й станции можно проехать, используя два билета: от 3-й до 4-й станции на место 2 и от 4-й до 5-й на место 1. От 4-й до 5-й станции можно проехать, используя один билет на место 1.

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

Входной файл (trains.in) Выходной файл (trains.out)
1
5 4 3
1 4 1
2 5 3
2 3 2
4 5 2
3
1 5
3 5
4 5
-1
2
1

Задача 2A. ASCII в кубе

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

По данным целым числам W, H, D, W1, H1, D1 вывести ASCII-изображение параллелепипеда шириной W, высотой H и глубиной D, из которого удалён параллелепипед шириной W1, высотой H1 и глубиной D1. Удаление производится из угла, ближайшего к наблюдателю (ближний правый верхний угол). Параллелепипед состоит из кубиков размером 1x1x1. Каждый кубик выглядит так:

  +---+
 /   /|      
+---+ |      
|   | + 
|   |/ 
+---+
(используются символы '+', '-', '/', '|', соответственно ASCII 43, 45, 47, 124)

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

Входной файл содержит числа W H D W1 H1 D1

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

Выходной файл должен содержать ровно 3H + 2D + 1 строку, представляющую ASCII-изображение разности параллелепипедов. В начале первых 2D строк вместо пробелов должны стоять символы "точка" (ASCII 46).

Ограничения

1 ≤ W, H, D ≤ 40, 0 ≤ W1 < W, 0 ≤ H1 < H, 0 ≤ D1 < D.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 2 0 0 0
       
 ....+---+---+---+  
 .../   /   /   /|  
 ..+---+---+---+ |  
 ./   /   /   /| +  
 +---+---+---+ |/|  
 |   |   |   | + |  
 |   |   |   |/| +  
 +---+---+---+ |/   
 |   |   |   | +    
 |   |   |   |/     
 +---+---+---+    
  
2
3 3 3 2 1 2

 ......+---+---+---+
 ...../   /   /   /|
 ....+---+---+---+ |
 .../   /|   |   | +
 ..+---+ |   |   |/|
 ./   /| +---+---+ |
 +---+ |/   /   /| +
 |   | +---+---+ |/|
 |   |/   /   /| + |
 +---+---+---+ |/| +
 |   |   |   | + |/ 
 |   |   |   |/| +  
 +---+---+---+ |/ 
 |   |   |   | +  
 |   |   |   |/
 +---+---+---+
  

Задача 2D. Парное упражение

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Учитель построил перед собой класс из n учеников. Однако выяснилось, что ребята встали не по росту, а в некотором произвольном порядке. Не желая тратить время на перепостроение, учитель решил действовать по следующему алгоритму. Он находит в строю пару стоящих рядом учеников, рост которых отличается не более чем на k сантиметров и отправляет их выполнять упражнение. Это действие учитель повторяет до тех пор, пока такие пары существуют. Если таких пар нет, оставшиеся в строю ученики отправляются играть в волейбол.

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

В первом примере имеется 7 учеников. Учитель может вызвать учеников 2 и 3 (их рост 175 и 170, разница не превосходит k = 5), после чего они выйдут из строя, и останутся ученики с номерами 1, 4, 5, 6, 7. Вторую пару составляют ученики 1 и 4, имеющие нулевую разницу в росте (рост обоих равен 180). Ученики с номерами 5 и 7 имеют один и тот же рост 200, но учитель не может их вызвать, поскольку они стоят не рядом друг с другом. Если бы учитель вызвал сначала учеников 1 и 2, то оставшиеся ученики не смогли бы образовать ни одной пары.

Система оценивания

Рекомендуется рассмотреть следующие частные случаи:

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

Во начале входного файла записаны целые числа n и k. Далее следует n целых чисел hi. Число hi обозначает рост ученика, стоящего в строю i-ым.

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

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

Ограничения

1 ≤ n ≤ 500;

100 ≤ hi ≤ 300;

0 ≤ k ≤ 200;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 5
180 175 170 180 200 150 200
2
2 3
1 4
2
3 0
180 170 170 
1
2 3

Задача 2G. Кольцевая автодорога

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:road.in   Ограничение памяти:64 Мб
Выходной файл:road.out  

Условие

К 2110 году город Флэтбург, являясь одним из крупнейших городов мира, не имеет обходной автомагистрали, что является существенным препятствием для его развития как крупнейшего транспортного центра мирового значения. В связи с этим еще в 2065 году при разработке Генерального плана развития Флэтбурга была определена необходимость строительства кольцевой автомобильной дороги.

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

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

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

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

Входной файл содержит четыре строки. Каждая из них содержит по два целых числа: xi и yi — координаты места расположения достопримечательности. Первая строка описывает первую достопримечательность, вторая — вторую, третья — третью, четвертая — четвертую. Никакие две достопримечательности не находятся в одной точке.

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

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

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

Ограничения

100 ≤ xi, yi ≤ 100

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

Входной файл (road.in) Выходной файл (road.out)
1
0 0
0 1
1 0
2 2
7
1.5 0.5 1.14412281
2
0 0
0 1
1 0
1 1
Infinity
0.5 0.5 0.0

Задача 2X. Лягушка на деревьях (65 баллов)

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

Вдоль лесной тропинки растёт N деревьев высотой h1, h2, …, hN метров соответственно. Расстояние между соседними деревьями равно 1 метру.

Лягушка сидит на дереве с номером A и хочет попасть на дерево с номером B. Поскольку лазить по деревьям она не может, ей остаётся только перепрыгивать с одной вершины дерева на другую. При этом лягушка может развивать начальную скорость от 0 до v м/с, и прыгать под углом от 0 до α градусов.

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

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

Входной файл содержит числа N A B v α, за которыми следует N чисел h1 h2hN. Числа v и α — вещественные, остальные числа — целые.

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

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

Ограничения

1 ≤ A, BN ≤ 100, 1 ≤ hi ≤ 1000, 0.01 ≤ v ≤ 1000, 0.01 ≤ α ≤ 90.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1 2 10 80 
5 6
1

Задача 3A. Оригами

Автор:И. Бураго   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Складывание фигуры начинается с квадратного листа бумаги, лежащего на специальной (также квадратной) учебной доске для оригами. Доска размечена на n × n клеток, стороны которых параллельны её краям. Через все клетки доски проведены диагонали двух типов: пересекающие клетки сверху вниз слева направо (\) и справа налево (/). Две диагонали, соединяющие противоположные углы доски, называются главными.

Схема складывания фигуры состоит из последовательных указаний о сгибах. Каждый сгиб проходит вдоль одной из 4 n − 2 диагоналей доски, при этом бумага всегда загибается в сторону центра доски. Таким образом, для диагоналей, расположенных выше главной, возможен только сгиб вниз, для диагоналей, расположенных ниже главной, — только сгиб вверх. Сгиб, проходящий через главную диагональ, возможен как в одну, так и в другую сторону.

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

Ниже показан процесс складывания фигуры по схеме, приведённой в примере 2.

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

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

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

  1. Тип диагонали — символ '/' (ASCII 47) или '\' (ASCII 92).
  2. Направление сгиба листа — символ 'u' (ASCII 117) для сгиба вниз или 'l' (ASCII 108) для сгиба вверх; однозначно определяет положение относительно главной диагонали.
  3. Номер диагонали — целое число от 1 до n. Диагонали каждого типа, расположенные по одну сторону от главной, нумеруются по возрастанию от угла доски к главной диагонали.

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

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

Ограничения

1 ≤ n ≤ 100, 0 ≤ m ≤ 4 n − 2.

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
\u1/u3
~~^
~,#
,##
2
4 3
/l3\u2/u3
~~^~
~,#&gt;
,##~
#'~~

Задача 3D. Любители SMS

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

Расположение клавиш и координаты их центров показаны на приведённой схеме:

  1 2 3   (1; 1) (1; 2) (1; 3)
  4 5 6   (2; 1) (2; 2) (2; 3)
  7 8 9   (3; 1) (3; 2) (3; 3)
    0            (4; 2)
  
Во время набора сообщений пальцы не должны «скрещиваться», то есть палец левой руки не может оказаться правее пальца правой руки.

Одному члену жюри требуется набрать сообщение, состоящее из N символов. Помогите ему оценить минимальное время, которое для этого потребуется. Клавиша, которую нужно нажать, чтобы ввести i-й символ сообщения, задаётся изображённой на ней цифрой ai. В начальный момент времени палец левой руки находится на клавише 4, а палец правой руки — на клавише 6.

Рекомендуется рассмотреть частичные решения

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

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

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

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

Ограничения

1 ≤ N ≤ 105, 0 ≤ ai ≤ 9

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1 3 2 7
5
2
6
5 2 9 0 0 3
6.650281540

Задача 3G. Сухой фотограф

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

В некотором городе имеется достопримечательность - прямоугольная площадь размером X на Y метров, на которой работают N фонтанов. Турист желает посетить эту площадь и сделать несколько фотографий. Однако если при фотографировании находиться от какого-либо из фонтанов на расстоянии меньше R метров, фотоаппарат может быть поврежден брызгами воды. Помогите фотографу найти безопасную точку съёмки. Требуется по координатам фонтанов определить точку на площади, удалённую от каждого из них не менее чем на R метров, или определить, что такой точки не существует. Если таких точек более одной, вывести любую из них. Обратите внимание, что стоять в точности на границе окружности или прямоугольника разрешено.

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

В первой строке входного файла содержатся числа X Y N R, в каждой из следующих N строк - координаты xi yi i-го фонтана. Числа X Y R во входном файле — вещественные.

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

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

Ограничения

1 <= N <= 100, 1 <= X, Y, R <= 106.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
100 100 4 50
0 0
100 0
0 100
100 100
50 50

Задача 3X. Универсальный галактический гороскоп

Автор:С. Пак   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Летоисчисление на планетах галактического альянса ведется следующим образом: эпоха начинается с момента свершения События. Событие считается мгновенным, и с этого же момента начинается последовательное чередование знаков зодиака, которых P штук. Определенных имен у знаков нет, поэтому они обозначаются просто порядковыми номерами начиная с единицы.

Год состоит из M месяцев, каждый месяц состоит из D дней. Количество лет, месяцев и дней в записи даты означает количество полных прошедших, соответственно, лет, месяцев и дней. Событие имело место в нулевом дне нулевого месяца нулевого года (0.0.0), и, например, спустя два с половиной дня дата будет 2.0.0. Таким образом, если дата рождения галактического жителя 5.0.0, то есть через пять полных дней с момента События, то считается, что он родился уже в течение шестого дня.

Все P знаков зодиака распределены в точности равными периодами по K годам, причем период определенного знака зодиака не обязательно занимает целое количество дней.

Знак зодиака галактического жителя соответствует периоду, под знаком которого он родился. Необходимо по набору из N дат дней рождения галактических жителей определить их знаки зодиака. Если же житель родился в день, часть которого проходит под одним знаком зодиака, а вторая часть — под другим, то это невозможно достоверно сделать, и нужно вывести 0.

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

Входной файл содержит целые положительные числа N, M, D, K, P, после которых идут N дат дней рождения галактических жителей в формате DAYS.MONTHS.YEARS.

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

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

Ограничения

1 ≤ N, M, D, K, P ≤ 1000

0 ≤ DAYS < D; 0 ≤ MONTHS < M; 0 ≤ YEARS ≤ 999

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 2 2 1 4
0.0.0
1.0.0
0.1.0
1.1.0
0.0.1
1 2 3 4 1
2
3 2 5 1 3
4.0.133
1.1.77
3.1.44
2 0 3

Задача 4A. Гирлянда

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Ваша программа должна вывести в выходной файл изображение гирлянды. Гирлянда состоит из N звеньев, каждое из которых имеет вид ромба, состоящего из символов '#' (ASCII 35) для нечётных звеньев, либо '*' (ASCII 42) — для чётных звеньев. Размер i-го звена задаётся целым числом Ai. Каждая сторона ромба размером Ai состоит из Ai + 1 символа.

Гирлянда должна быть изображена на фоне прямоугольника, заполненного символами '.' (ASCII 46).

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

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

Во входном файле находится целое число N, за которым следует N чисел A1 AN — размеры звеньев.

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

Выходной файл должен содержать изображение гирлянды.

Ограничения

1 ≤ N ≤ 100, 1 ≤ Ai ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1
.#.
#.#
.#.
2
2 3 2
...#...
..#.#..
.#...#.
#.....#
.#...#.
..#*#..
..*#*..
.*...*.
..*.*..
...*...
3
3 1 1 2
..#..
.#*#.
.*#*.
.#*#.
#...#
.#.#.
..#..

Задача 4D. Домой на электричках

Автор:X командный чемпионат Санкт-Петербурга по программированию - V Открытая Кировская командная олимпиада   Ограничение времени:2 сек
Входной файл:a.in   Ограничение памяти:8 Мб
Выходной файл:a.out  

Условие

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

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

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

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

Во входном файле записаны сначала числа N и E. Затем записано число M, обозначающее число рейсов электричек. Далее идет описание M рейсов электрички. Описание каждого рейса электрички начинается с числа Ki — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

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

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

Ограничения

2 ≤ E ≤ N ≤ 1000, 1 ≤ M ≤ 100, 2 ≤ Ki ≤ N.

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

Входной файл (a.in) Выходной файл (a.out)
1
5 3
4
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
20

Задача 4G. Бармаглот под одеялом

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

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

Одеяло и Бармаглот имеют форму ломаных, заданных целочисленными координатами вершин (x1, y1), (x2, y2), … (xN, yN) для одеяла, (u1, v1), (u2, v2), … (uM, vM) для Бармаглота. При этом xi + 1 > xi и ui + 1 > ui для всех i.

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

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

Во входном файле расположены числа

N x1 y1 x1 y1xN yN

M u1 v1 u1 v1uM vM

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

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

Ограничения

3 ≤ M, N ≤ 100, 0 ≤ xi, yi, ui, vi ≤ 10000, x1 = u1, xN = uM.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 0 0 5 5 6 0
4 0 0 2 1 5 5 6 0
CRY

Задача 4X. Двойные тетради Чебурашки

Автор:C. Пак   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

У Чебурашки есть NS одинарных и ND двойных тетрадей. Все одинарные тетради имеют вес WS, а все двойные — вес WD. Чебурашка учится N дней в неделю. Он изучает M предметов, пронумерованных от 1 от M. Вес, который Чебурашке придётся перенести за один день, равен сумме весов всех тетрадей, которые он должен будет взять.

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

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

Во входном файле содержатся числа N M NS ND WS WD. Далее следует расписание, состоящее из N дней. Каждый день описывается одной строкой. В начале строки содержится Ki — число уроков в i-ый день, за которым следует Ki чисел — номера предметов. Все числа во входном файле целые.

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

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

Ограничения

0 ≤ N ≤ 6

0 ≤ M ≤ 10

0 ≤ WS, WD ≤ 109

0 ≤ K1 + K2 + … + KN ≤ 15

2 × ND + NS = M

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 4 0 2 2 2
2 1 2
2 3 4
2 1 2
2 3 4
8
2
4 4 2 1 0 2
2 1 2
2 3 4
2 1 2
2 3 4
4

Задача 5A. Кирпичная стена

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Изображение кирпичной стены состоит из Wh слоёв по Ww кирпичей в каждом. Изображение кирпича состоит из Bh строк по Bw символов в каждой. Все строки изображения кирпича начинаются с символа '|' (ASCII 124). Остальные символы в первых Bh − 1 строках изображения кирпича  — '.' (ASCII 46), а в последней строке — '_' (ASCII 95).

Изображения в слоях с чётными номерами циклически сдвинуты на Bw / 2 символов вправо. Всё изображение стены предваряется одной строкой, состоящей из Ww × Bw символов '_' (ASCII 95).

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

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

Входной файл содержит целые числа Bw Bh Ww Wh.

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

Выходной файл должен содержать Wh × Bh + 1 строк по Ww × Bw символов в каждой — изображение стены.

Ограничения

1 ≤ Bw, Bh, Ww, Wh ≤ 50, число Bw — чётное

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1 1 1
__
|_
2
4 2 5 3
____________________
|...|...|...|...|...
|___|___|___|___|___
..|...|...|...|...|.
__|___|___|___|___|_
|...|...|...|...|...
|___|___|___|___|___

Задача 5D. Круговая оборона

Автор:А. Кленин, Т. Чистяков   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Поскольку содержание армий — дорогостоящее занятие, Централия может постоянно поддерживать только N армий. К счастью, по той же причине её соседи, чья экономика менее стабильна, чем в Централии, могут в i-й год подготовить для завоевания Ai,k армий, где k = 0… 3 — номер соседа.

В Централии проживает могущественный колдун-экономист, который сумел предсказать количество враждебных армий на T лет вперёд. Вам поручена роль главнокомандующего армиями Централии с задачей распределения армий по границам таким образом, чтобы удобный для вторжения случай предоставился как можно позже. Задача осложняется тем, что за один год любая армия Централии может переместиться с той границы, которую она занимала в прошлом году, только на соседнюю границу, т.е. с k-й границы либо на границу (k + 1)mod 4, либо на границу (k + 3)mod 4.

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

Во входном файле находятся числа N T, за которыми следует T четвёрок чисел Ai,0 Ai,1 Ai,2 Ai,3 — количество армий, которые будут выставлены в i-м году каждым из соседних государств.

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

В выходном файле должно содержаться число Q — максимальное количество лет, в течение которого можно избежать вторжения (0 ≤ Q ≤ T), за которым следуют Q четвёрок чисел Bi,0 Bi,1 Bi,2 Bi,3 — количество армий, которые следует в i-м году расположить на каждой из границ (Bi,0 + Bi,1 + Bi,2 + Bi,3 = N). Расположение защищающихся армий в первом году может быть произвольным, а расположение в каждом следующем году должно учитывать ограничения на перемещение армий.

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

Ограничения

1 ≤ N ≤ 10, 1 ≤ T ≤ 1000, 0 ≤ Ai, j ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 2
0 4 0 0
2 1 1 0
2
0 4 0 0
2 1 1 0
2
4 2
0 4 0 0
2 0 1 1
1
0 4 0 0

Задача 5G. Фотограф и замок

Автор:A. Klenin   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Старинный замок имеет в плане форму выпуклого N-угольника. Замок находится внутри участка, имеющего форму выпуклого M-угольника, огороженного высоким забором (замок не соприкасается с забором). Фотограф желает сделать несколько фотографий замка таким образом, чтобы каждая из стен была видна хотя бы на одной фотографии. Позиция для съёмки определяется точкой, находящейся внутри участка, но снаружи замка. Считается, что стена видна из данной позиции, если отрезок, соединяющий её с любой точкой стены, не пересекает других стен. Позиция не может лежать на прямой, содержащей стену. Требуется определить минимальное количество позиций для фотографии, которое придется сделать фотографу.

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

Входной файл содержит числа N M x1 y1xN yN u1 w1uN wN, где xi yi - координаты вершин замка, ui vi - координаты вершин забора. Вершины перечислены в порядке обхода по часовой стрелке.

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

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

Ограничения

1 ≤ N, M ≤ 100. Все координаты представляют собой целые числа в диапазоне от 0 до 10000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 4
1 36  55 5  58 6  68 38  62 41  9 49  4 42
0 0  72 0
72 54  0 54
3

Задача 5X. Зельеварение

Автор:Н. Ляхута, М. Спорышев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

К сожалению, температура в комнате очень быстро стала некомфортной. И тут Вася подумал, почему бы не сделать температуру воздуха в комнате равной T0 + K, где T0 — температура в комнате до приготовления зелий. Он тут же вспомнил, что на уроках заклинаний он недавно научился заклинанию исчезновения! Заклинание позволяет ему безвозвратно уничтожить любой непрерывный отрезок подряд идущих колб вместе с их влиянием на температуру воздуха в комнате. Используя только это заклинание, Вася хочет сделать температуру в комнате желаемой.

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 2 ⋅ 103

107 ≤ K ≤ 107

104 ≤ ai ≤ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 0
1
1
2
5 1
1 2 3 -1 -1
4

Problem 6A. Advanced ASCII Cubes

Author:A. Klenin   Time limit:3 sec
Input file:input.txt   Memory limit:200 Mb
Output file:output.txt  

Statement

The table surface is divided into N by M square cells. Some cubes are stacked one upon another over the cells, forming towers. For each cell the number of cubes stacked over it is given in the matrix A.

Your program must output the view of the table in ASCII graphics, where each cube is represented as shown below:

  +---+
 /   /|      
+---+ |      
|   | + 
|   |/ 
+---+
(here the characters used are '+', '-', '/', '|', their ASCII codes are ASCII 43, 45, 47, 124)

The dot (ASCII 46) must be used as a background.

Input file format

Input file contains integers N M, followed by matrix A, row-by-row. The first row describes the cube tower furthest from the viewer, left to right, and the last row — nearest to the viewer.

Output file format

Output file must contain a string representation of the table view, with minimal number of lines required to show all cubes. Each line must contain a string of equal length, which is the minimal width required to show all cubes.

Constraints

1 ≤ N, M, Aij ≤ 50

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 4
1 1 1 1
1 2 1 1
1 1 1 1
........+---+..........
......+/   /|-+---+---+
...../+---+ |/   /   /|
....+-|   | +---+---+ |
.../  |   |/   /   /| +
..+---+---+---+---+ |/.
./   /   /   /   /| +..
+---+---+---+---+ |/...
|   |   |   |   | +....
|   |   |   |   |/.....
+---+---+---+---+......
2
3 5
2 2 1 2 2
2 2 1 1 2
3 2 1 2 2
......+---+---+...+---+---+
..+---+  /   /|../   /   /|
./   /|-+---+ |.+---+---+ |
+---+ |/   /| +-|  /   /| +
|   | +---+ |/+---+---+ |/|
|   |/   /| +/   /   /| + |
+---+---+ |/+---+---+ |/| +
|   |   | +-|   |   | + |/.
|   |   |/  |   |   |/| +..
+---+---+---+---+---+ |/...
|   |   |   |   |   | +....
|   |   |   |   |   |/.....
+---+---+---+---+---+......

Задача 6D. Плотность населения

Автор:Южно-Уральский открытый командный чемпионат   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

После проведения переписи населения Флатландии все данные были нанесены на карту. Прямоугольная карта Флатландии была разделена на клетки единичного размера. Число жителей в каждой клетке изменяется от 0 до 9.

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

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

В первой строке входного файла содержится три целых числа, разделенных пробелами — размеры Флатландии N, M и заданная плотность населения K. Далее следует N строк, каждая из которых содержит M цифр от 0 до 9 — карта распределения населения Флатландии.

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

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

Ограничения

1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ K ≤ 9

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 1
020
102
020
1 2 3 2

Задача 6G. Чебурашка и бильярд

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Затем Чебурашка установил бильярдный шарик внутрь рамки, в точку с координатами (x; y) и ударил по нему, в результате чего шарик начал двигаться с вектором скорости (Vx; Vy). Шарик движется без трения, т.е. скорость шарика не уменьшается со временем. При ударе об один бортик шарик отскакивает без потери скорости под углом, равным углу падения. Если шарик ударяется сразу о два бортика (т.е. попадает точно в угол), то вектор его скорости меняет направление на противоположное. Чебурашке интересно, какие координаты будет иметь шарик через время t, и он просит вас написать программу, отвечающую на этот вопрос.

Диаметр шарика пренебрежимо мал по сравнению с a.

Рекомендуется рассмотреть частичные решения

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

Во входном файле содержится целое число a, за которым следуют вещественные числа x y Vx Vy t, заданные с точностью 105

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

В выходном файле должно содержаться два числа — координаты (Xt; Yt) шарика через время t, выведенные с точностью не менее 103

Ограничения

1 ≤ a ≤ 103, 0 ≤ |Vx|, |Vy| ≤ 103, 0 ≤ t ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 0 0 0.01 0.01 300
1.000 1.000
2
5 2 1 -1 3 2
0.000 3.000
3
10 1 1 -200 -1000 6891.99971
1.058 1.290

Задача 6X. Реформа галактических вооруженных сил

Автор:С. Пак   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Программное обеспечение дроидов поддерживает разбиение дивизиона дроидов только на равные по количеству отряды. Например, дивизион из 6 дроидов может быть разбит на 1 отряд из 6 дроидов, 2 отряда из 3 дроидов, 3 отряда из 2 дроидов или 6 отрядов из 1 дроида.

Считается, что после объединения двух дивизионов, максимальную эффективность в бою имеет объединенный дивизион с наибольшим количеством отрядов. Например, максимально эффективный способ объединить два дивизиона, состоящие из из 6 и 4 дроидов — это разбить каждый на два отряда по 3 и 2 дроида, соответственно. Затем сформировать два увеличенных отряда по 5 дроидов. Новый объединенный дивизион будет состоять из 10 дроидов, состоящих в 2 отрядах.

Рассмотрим армию, состоящую из 4 дивизионов: 4 9 3 6. Возможные варианты разбиения дивизионов на равные по численности отряды: 1 дивизион: 1 по 4, 2 по 2, 4 по 1. 2 дивизион: 1 по 9, 3 по 3, 9 по 1. 3 дивизион: 1 по 3, 3 по 1. 4 дивизион: 1 по 6, 2 по 3, 6 по 1.

Соответственно, оптимальным решением будет объединение дивизионом 1 и 4 с разбиением на 2 отряда каждого, а также дивизионов 2 и 3 с разбиением на 3 отряда каждого. Общее количество отрядов в армии после объединения — 5.

Требуется данные 2 N дивизионов дроидов попарно объединить таким образом, чтобы общее количество отрядов в армии было максимальным.

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

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

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

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

Ограничения

1 ≤ N ≤ 10; 1 ≤ Di ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2 3 4
3
2
2
4 9 3 6
5
3
2
30 18 5 12
11

Задача 7A. Гистограмма

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

По данным целым числам a1, a2, …, aN требуется построить гистограмму. Гистограмма должна состоять из N столбцов, i-й столбец должен изображаться прямоугольником высотой ai и шириной в 3 символа. Столбцы должны быть:

Промежуток между столбцами, а также поля слева, справа и сверху гистограммы должны составлять один символ. В основании (нижней строке) гистограммы промежутки и поля должны изображаться символом '-' (ASCII 45), все остальные промежутки и поля — символом '.' (ASCII 46).

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

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

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

Выходной файл должен содержать max(ai) + 3 строк длиной 6 N + 1 символов каждая — изображение гистограммы.

Ограничения

1 ≤ N ≤ 100, 1 ≤ ai ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 6
.............
.......+---+.
.......|###|.
.......|###|.
.......|###|.
.......|###|.
.+---+.|###|.
.|###|.|###|.
-+---+-+---+-

Задача 7D. Домино (классика)

Автор:Фольклор   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Найти количество способов замостить домино 1 × 2 поле n × m.

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

Во входном файле содержатся числа n и m.

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

В выходной файл выведите ответ.

Ограничения

1 ≤ n ≤ 16;

1 ≤ m ≤ 10;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3
3

Задача 7G. Столкновение шариков

Автор:А. Кленин   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

По горизонтальной плоской поверхности катятся два шарика радиуса R метров каждый. В начальный момент времени шарики имеют координаты центров (x1, y1) и (x2, y2) метров, а также проекции скоростей на координатные оси (dx1, dy1) и (dx2, dy2) метров в секунду соответственно.

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

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

Входной файл содержит вещественные числа R x1 y1 dx1 dy1 x2 y2 dx2 dy2.

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

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

Ограничения

1 ≤ R ≤ 1000, 1000 ≤ x1, y1, dx1, dy1, x2, y2, dx2, dy2 ≤ 1000,

(x1 − x2)2 + (y1 − y2)2 > 4 R2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
0 0 10 0
50 0 -10 0
2.4

Задача 7X. Табуретки-2 (30 баллов)

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины. На табуреткоизготовительную фабрику поступило N ножек, имеющих слегка различающиеся длины L1, L2, … LN. Научно-исследовательский отдел фабрики обнаружил, что выпуск табуреток можно увеличить, если укорачивать некоторые ножки. При этом отпиленная часть выбрасывается.

Требуется определить минимальное количество распилов, необходимых для для изготовления N / 4 качественных табуреток.

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

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

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

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

Ограничения

1 ≤ N ≤ 10000, N mod 4 = 0, 1 ≤ Li ≤ 100.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8
18 16 17 17 16 17 17 19
2

0.225s 0.003s 87