Задача A. Марсианские кассы

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

Условие

Марсианские кассовые аппараты распечатывают коды товаров на чеках в виде строки, состоящей из цифр от '0' до '9' и заглавных латинских букв от 'A' до 'F'. Все коды имеют длину N символов.

Каждый символ выводится в виде матрицы размером 5 × 7 позиций, некоторые из которых закрашиваются при печати. Символы отделяются друг от друга вертикальным рядом неокрашенных позиций. Матрицы для всех используемых символов приведены ниже ('.' (точка) обозначает неокрашенную, а '#' — закрашенную позицию):

0
.###.
#...#
#..##
#.#.#
##..#
#...#
.###.
1
...##
..#.#
.#..#
#...#
....#
....#
....#
2
.###.
#...#
....#
...#.
..#..
.#...
#####
3
.###.
#...#
....#
.###.
....#
#...#
.###.
4
#...#
#...#
#...#
#...#
.####
....#
....#
5
#####
#....
#....
####.
....#
#...#
.###.
6
.###.
#...#
#....
####.
#...#
#...#
.###.
7
#####
....#
....#
...#.
..#..
.#...
#....
8
.###.
#...#
#...#
.###.
#...#
#...#
.###.
9
.###.
#...#
#...#
.####
....#
#...#
.###.
A
..#..
.#.#.
#...#
#...#
#####
#...#
#...#
B
####.
#...#
#...#
####.
#...#
#...#
####.
C
.###.
#...#
#....
#....
#....
#...#
.###.
D
###..
#..#.
#...#
#...#
#...#
#..#.
###..
E
#####
#....
#....
####.
#....
#....
#####
F
#####
#....
#....
####.
#....
#....
#....

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

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

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

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

Входной файл состоит из 7 строк по 6 × N − 1 символов каждая — изображение перекрывающихся товарных кодов.

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

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

Ограничения

1 ≤ N ≤ 40

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

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

Задача B. Рейтинг студента

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

Условие

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

Один студент получил N заданий утром дня с номером 1.

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

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

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

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

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

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

Если студент не сможет заработать ни одного балла, вывести единственное число 0.

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

Ограничения

1 ≤ N ≤ 1000; 1 ≤ Li, Di, Ri ≤ 1000

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

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

Задача C. Упаковка конфет

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

Условие

Кондитерская фабрика изготовила партию конфет N различных сортов. В партию входит ai конфет i-го сорта.

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

Требуется определить максимально возможное значение M. Например, если изготовлено 15, 19 и 55 конфет трёх разных сортов, то их следует упаковывать в обычные коробки по 4 штуки, после чего останутся конфеты для 3 коробок ассорти.

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

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

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

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

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

Ограничения

2 ≤ N ≤ 105; 1 ≤ ai ≤ 109

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

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

Задача D. Лестница и прямая

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

Условие

Бесконечная лестница на плоскости задана ломаной, состоящей из чередующихся горизонтальных отрезков длиной H и вертикальных отрезков длиной V. Точка (0, 0) является левой вершиной одного из горизонтальных и верхней вершиной одного из вертикальных отрезков.

Прямая на плоскости задана координатами двух различных точек на ней (x1, y1) и (x2, y2).

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

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

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

Входной файл содержит целые числа H V x1 y1 x2 y2.

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

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

Ограничения

1 ≤ H, V ≤ 109; 109 ≤ x1, y1, x2, y2 ≤ 109

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

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

0.054s 0.005s 13