Задача A. Зимняя Симметрия ≡

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

Условие

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

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

Входной файл содержит число N, за которым следуют N четверок чисел x1, i, y1, i, x2, i, y2, i, описывающие i-тый отрезок. Все координаты — целые числа.

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

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

Ограничения

1 ≤ N ≤ 100 −10000 ≤ xi, yi ≤ 10000

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

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

Задача B. Сложные Ханойские Башни ≡

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

Условие

Согласно древней легенде в индийском городе Бенареса существует "Пирамида Браминов". Она состоит из N золотых колец разного диаметра и K алмазных стержней, на которые в день основания мира были надеты эти кольца. Жрецы храма должны непрерывно перекладывать кольца, соблюдая следующие правила:

1) Кольцо большего диаметра нельзя положить на кольцо меньшего диаметра

2) За один раз можно переместить только одно кольцо, являющиеся верхним на одном из стержней

Когда все кольца окажутся на K-том стержне по легенде произойдет конец света. Сначала все кольца лежат на 1-ом стержне. Так как жрецы хотят быстрее попасть на небо они просят вас написать программу, которая по числам N и K определит такой алгоритм перекладывания колец, что если К = 3, то число затраченных действий будет равно 2N-1, иначе число действий должно быть меньше чем минимум из чисел N3 и N2K.

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

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

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

Выходной файл должен содержать число M - количество перекладываний, за которым следует M пар чисел i j, которые обозначают, что верхний диск с i-того стержня должен быть перемещен на j-тый. Если решений несколько выведите любое из них. Если решений не существует выведите −1.

Ограничения

1 ≤ N ≤ 31, 2 ≤ K ≤ 33, M ≤ 215-1.

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

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

Задача C. Прикладная археология ≡

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

Условие

Недавно археологами была открыта неизвестная гробница фараона Тутанхамона К-того. Ими составлена карта (матрица размерности N × M), на которой символом "0"-обозначается пустое пространство, а символом "1"-стена гробницы.

Так как карта оказалась довольно большой и неудобной в транспортировке, археологи решили перевести ее в электронный вид, при этом было решено закодировать ее следующим образом: начиная с левого конца карты последовательности в 8 символов "0" или "1" кодируются в 1 байт (число от 0 до 255).

Вам необходимо написать программу, которая по числам N, M и закодированной карте определит, можно ли из клетки с координатами x1, y1 попасть в клетку с координатами x2, y2.

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

В первой строке входного файл содержатся числа N, M, x1, y1, x2, y2 за ними следуют M строк по N / 8 символов в каждой — карта гробницы. Гарантируется, что N кратно 8.

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

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

Ограничения

8 ≤ N ≤ 40000, 1 ≤ M ≤ 100, 0 ≤ x1,x2 ≤ N−1, 0 ≤ y1,y2 ≤ M−1

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
8 2 3 0 7 0
238
224
 
True
0.026s 0.003s 11