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

Условие

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

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

.###.
#...#
#..##
#.#.#
##..#
#...#
.###.

...##
..#.#
.#..#
#...#
....#
....#
....#

.###.
#...#
....#
...#.
..#..
.#...
#####

.###.
#...#
....#
.###.
....#
#...#
.###.

#...#
#...#
#...#
#...#
.####
....#
....#

#####
#....
#....
####.
....#
#...#
.###.

.###.
#...#
#....
####.
#...#
#...#
.###.

#####
....#
....#
...#.
..#..
.#...
#....

.###.
#...#
#...#
.###.
#...#
#...#
.###.

.###.
#...#
#...#
.####
....#
#...#
.###.

..#..
.#.#.
#...#
#...#
#####
#...#
#...#

####.
#...#
#...#
####.
#...#
#...#
####.

.###.
#...#
#....
#....
#....
#...#
.###.

###..
#..#.
#...#
#...#
#...#
#..#.
###..

#####
#....
#....
####.
#....
#....
#####

#####
#....
#....
####.
#....
#....
#....

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

• N = 1

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

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

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

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

Ограничения

1 ≤ N ≤ 40

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

.###..#####
#...#.#...#
#...#.#...#
.####.####.
....#.#...#
#...#.#...#
.###..####.

9B
9F

.###..#####
#...#.#...#
#...###...#
.####.####.
....#.#...#
#...###...#
.###..####.

IMPOSSIBLE

#####...#..
#####...#..
#####...#..
#####...#..
#####...#..
#####...#..
#####...#..

IMPOSSIBLE

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

Условие

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

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

• Студенту потребуется ровно L_i дней, чтобы выполнить задание с номером i.
• Если студент берётся за какое-либо задание, то он ни на что не будет отвлекаться, пока его не выполнит.
• Начав работать над заданием в день с номером x, студент закончит и сдаст его в день с номером x + L_i − 1. Силы взяться за новое задание будут у него только на следующий день.
• Задание с номером i не будет принято, если оно будет сдано позже, чем в день с номером D_i.
• Рейтинг студента увеличится на R_i баллов после сдачи задания с номером i.

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

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

• N ≤ 2
• L₁ = L₂ = …  = L_N = 1
• D₁ = D₂ = …  = D_N

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000; 1 ≤ L_i, D_i, R_i ≤ 1000

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

5
7 8 6
2 2 1
5 8 4
3 9 3
2 5 1

7
3 1
4 6

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

Условие

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

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

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

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

• N = 2

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

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

Ограничения

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

2 
4 9

5

3
7 7 7

7

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

Условие

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

Прямая на плоскости задана координатами двух различных точек на ней (x₁, y₁) и (x₂, y₂).

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

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

• x₁ = x₂
• y₁ = y₂

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

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

Ограничения

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

2 2 0 0 5 0

-1

2 2 0 1 5 1

1