Задача A. Наименьший общий делитель ≡

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

Условие

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

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

Входной файл содержит целые числа A B.

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

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

Ограничения

1 ≤ A, B ≤ 231 − 1

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

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

Задача B. Почти квадрат ≡

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

Условие

"Дети, нарисуйте в тетрадях квадрат" — сказала учительница. Вася поставил на листе бумаги четыре точки, соединил их с помощью линейки. Получился квадрат... ну, или во всяком случае какой-то четырёхугольник.

Васин сосед Петя согласился помочь исправить рисунок. За время, пока учительница подойдёт для проверки Васиной работы, Петя успеет стереть и перерисовать только одну вершину четырёхугольника.

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

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

Входной файл содержит вещественные числа x1 y1 x2 y2 x3 y3 x4 y4 — координаты вершин четырёхугольника, перечисленные в порядке обхода.

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

Выходной файл должен содержать числа M x y, где целое M — номер вершины, которую следует перенести (1 ≤ M ≤ 4), а вещественные (x, y) — её новые координаты, c абсолютной ошибкой не более 10 − 3. Если решения не существует, вывести единственное число 0 (ноль). Если существует несколько решений, вывести решение с наименьшим значением M.

Ограничения

 − 1000 ≤ x, y ≤ 1000

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
0.0 0.0  10.0 0.0  10.0 10.0  0.0 10.0
 
1 0.0 0.0
2 
0.0 0.0  9.5 0.0  10.0 10.0  0.0 10.0
 
2 10.0 0.0
3 
0.0 0.0  9.5 0.0  10.0 10.0  -0.1 10.0
 
0

Задача C. Плотники ≡

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

Условие

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

Затем плотники сложили бруски вместе, и заметили, что Васины дырки находятся на расстояниях a1, a2, …, aN см от начала бруска, а Петины — на расстояниях b1, b2, …, bN см от начала бруска.

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000

2 ≤ L ≤ 1000

1 ≤ ai, bi < L, ai < ai + 1, bi < bi + 1

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1 3
2 1
 
1 0
2 
2 5
3 4 3 4
 
0 0
3 
3 10
3 5 6
1 8 9
 
0 3
0.463s 0.011s 17