Задача A. Обход доски конем ≡

Условие

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

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

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

Ограничения

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

1 1

A1

1 2

No solution

3 4

A1 B3 C1 A2 B4 C2 A3 B1 C3 A4 B2 C4

Задача B. Два компьютера ≡

Условие

Имеется два компьютера с одинаковой производительностью и N программ, которые необходимо выполнить. Известно, что i-я программа требует для выполнения на любом из компьютеров T_i секунд. Программы можно выполнять в любом порядке, но прерывать однажды запущенную программу нельзя. Сразу после окончания одной программы можно запускать следующую.

Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.

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

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

Ограничения

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

5 7 10 3 5 6

16

Problem C. Hot-keys ≡

Statement

Input file format

Input file contains number of captions N followed by N lines with captions.

Output file format

Output file must contain N lines with the same captions as in input. In those captions which have hot-key assigned, leftmost occurrence of hot-key letter must be preceded with '&' (ASCII 38).

Constraints

1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and consist of small Latin letters.

Sample tests

3
yes
no
cancel

&yes
&no
&cancel

4
abc
bca
acb
aaaa

&abc
&bca
a&cb
aaaa

Задача D. Слово из кубиков ≡

Условие

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

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

Ограничения

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

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4

Problem E. Divide by Squares ≡

Statement

Divide by Squares is played on a rectangular grid. Some of the squares in the grid are numbered. The objective is to divide the grid into rectangular and square pieces such that each piece contains exactly one number, and that number represents the area of the rectangle (from Wikipedia).

On the pictures you can see a sample of the puzzle and its solution.

You are to write program that solves this puzzle.

Input file format

Output file format

Constraints

Sample tests

4 4 4
2 1 4
2 3 6
3 1 4
4 4 2

1 1 2 2
1 3 3 2
3 1 2 2
4 3 1 2

Задача F. Гаджет в кредит ≡

Условие

Студент Вася решил приобрести себе новый гаджет. Стипендия у Васи небольшая, а гаджет — дорогой, поэтому Вася решил купить гаджет в кредит.

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

• Первоначально сумма долга равна стоимости гаджета C.
• По истечении максимум N лет вся сумма долга должна быть выплачена
• Вася должен определить ежемесячный платеж M — целое число рублей, которое он будет выплачивать каждый месяц. Исключение может составлять последний платёж — оставшаяся на последний месяц сумма долга может оказаться меньше M.
• Каждый месяц после Васиного платежа оставшаяся сумма долга увеличивается на P процентов и округляется вверх до целого числа.

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

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

1. P = 0
2. C, P ≤ 10³

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

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

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

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

Ограничения

1 ≤ C ≤ 10⁹; 0 ≤ P ≤ 10⁹; 1 ≤ N ≤ 10⁴

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

1 0 1

1

1 124 12

8

1 1 12

2

Задача G. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

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

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

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

Входной файл содержит три целых числа: W, H, N

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

Problem H. Elliptical devastation ≡

Statement

Spaceship Behemoth was sent to conquer the Gamma Pisces star system.

System has N planets numbered from 1 to N. The planets may be considered stationary and located on one plane. Every planet is guarded by a military space station, with the orbit in the same plane.

Some of these stations rotate around their planets clockwise, others — counterclockwise. Station orbits are ellipses. They can intersect, but cannot touch. No orbit lies entirely inside of another.

Spaceship is so huge and strong that it can easily destroy any object it encounters. Too bad, but to make it so powerful, engineers had to limit its navigational and maneuvering capabilities. It can either orbit a planet on the same orbit as one of the stations or very rapidly accelerate and decelerate to jump from one orbit to another one. The trajectory of such jump is a straight line tangent to both source and destination orbits.

To destroy a space station the ship must enter its orbit with the rotation direction opposite to that of the station. If it encounters the station while on the orbit, the station will be immediately smashed to pieces. If it has to depart an orbit before reaching its prey, it leaves a nuclear proximity mine, which will finish the business for sure.

After the destruction, the orbit of the former station gets polluted by much debris dangerous even for our mighty ship. It still can safely travel across these already visited orbits, but cannot take them for later maneuvers.

Your program must plan an assault on Gamma Pisces, which will result in destruction of all of its military stations. Behemoth will emerge from the subspace on orbit of Gamma Pisces Prime (planet number 1) and start its mission there.

Input file format

Input file contains integer N — the number of planets, followed by N orbit descriptions. Each description consists of 5 integers x₁ y₁ x₂ y₂ c d, where (x₁, y₁) and (x₂, y₂) specify coordinates of ellipse foci, c is the length of semi-major axis and d equals 1 if station rotates clockwise and  − 1 if counterclockwise.

Output file format

Output file must contain N integers — planet numbers in order of visiting. If several solutions exist, output lexicographically minimal one. If the solution does not exist, output a single integer  − 1.

Constraints

Sample tests

2
-5 0 -5 0 1 1
5 0 5 0 1 -1

1 2

2
-1 0 -1 0 4 1
1 0 1 0 4 -1

-1

Задача I. Репликация ≡

Условие

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

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

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

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

• N ≤ 100

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

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

Ограничения

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

3 3
1 2
1 2
2 3

2
1
0

3 3
1 2
1 3
2 3

1
2
1

Задача J. Производство деталей ≡

Условие

Предприятие «Авто-2010» выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за p_i секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

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

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

Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.

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

Первая строка входного файла содержит число n — количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂… p_n, определяющих время изготовления каждой детали в секундах.

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

Известно, что не существует циклических зависимостей в производстве деталей.

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

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

Ограничения

1 ≤ n ≤ 100000, 1 ≤ p_i ≤ 10⁹

Сумма всех чисел k_i не превосходит 200000.

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

3
100 200 300
1 2
0
2 2 1

300 2
2 1

2
2 3
1 2
0

5 2
2 1

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

9 3
3 2 1

Задача K. КПК ≡

Условие

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

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

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

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

Ограничения

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

3 1
2 3

1
2 3
1
1 2

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

Условие

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

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

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

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

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

Во входном файле содержатся числа N M N_S N_D W_S W_D. Далее следует расписание, состоящее из N дней. Каждый день описывается одной строкой. В начале строки содержится K_i — число уроков в i-ый день, за которым следует K_i чисел — номера предметов. Все числа во входном файле целые.

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

Ограничения

0 ≤ N ≤ 6

0 ≤ M ≤ 10

0 ≤ W_S, W_D ≤ 10⁹

0 ≤ K₁ + K₂ + …  + K_N ≤ 15

2 × N_D + N_S = M

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

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

8

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

4