Задача A. Лабиринт ≡

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

Условие

Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.

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

Во первой строке входного файла содержатся числа N, x0, y0, x1, y1. Далее следуют N строк по N символов в каждой — описание лабиринта.

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

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

Ограничения

0 ≤ N ≤ 100

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4 1 1 4 1
..#.
..#.
..#.
....
 
9

Задача B. Марсианское ДНК ≡

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

Условие

Марсианское ДНК состоит из последовательности пяти нуклеиновых кислот, обозначенных a, b, c, d, e соответственно. Известно что в ДНК не могут встречаться последовательности cd, ce, ed, ee. Ваша задача по заданной цепочке ДНК определить является ли она марсианской или нет.

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

Во входном файле содержится цепочка ДНК в описанной кодировке.

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

В выходном файле должно содержаться "TRUE", если ДНК марсианское и "FALSE" в противном случае.

Ограничения

В строке не более 10000 символов.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
ababab
 
TRUE

Задача C. Матрешки ≡

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

Условие

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

За один такт автомат может взять две матрешки и вложить меньшую в большую, причем если в матрешках уже содержаться другие матрешки, то они все вкладываются в самую большую, при этом номера матрешек остаются прежними. Если матрешка уже вложена в другую, то автомат упаковывает ту матрешку в которую она вложена. Программа автомата состоит из чисел N, K и следующих за ними K пар чисел ai, bi — номера матрешек, которые автомат упакует за i-тый такт.

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

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

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

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

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

Ограничения

0 ≤ N, K ≤ 100000

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

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

1 1 1 4

Задача D. НОД и числа Фибоначчи ≡

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

Условие

k-тым числом Фибоначчи называется k-тый член последовательности Fk = Fk−1 + Fk−2 , F0 = 0 , F1 = 1

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

Во входном файле находятся два числа n и k

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

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

Ограничения

1 ≤ n, k ≤ 100

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

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

Задача E. НОК ≡

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

Условие

Наименьшим общим кратным двух чисел a и b называется наименьшее положительное из чисел, которые делятся на a и на b

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

Во входном файле находятся два числа a и b

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

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

Ограничения

1 ≤ a*b ≤ 1012

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
5 8
 
40

Задача F. Отрезки ≡

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

Условие

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

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

Во входном файле находятся восемь чисел x0, y0, x1, y1, x2, y2, x3, y3 — координаты первого и второго отрезка соответственно

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

В выходном файле должно содержаться "PO" "PROTIV" или "SOVPALI" в зависимомти от того как повернут первый отрезок относительно второго

Ограничения

Все числа по модулю не превосходят 10000

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

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

Задача G. Сортировка подсчетом ≡

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

Условие

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

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

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

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

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

Ограничения

0 ≤ N ≤ 100000, все числа находятся в диапазоне от 1 до 100000

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4
2 1
3 2 
2 3
3 4
 
1 3 2 4
0.315s 0.025s 23