Задача A. Археологи и курганы ≡

Условие

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

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

Формат входных данных

В первой строке подается число N – количество строк и столбцов поля с курганами.

Следующие N строк содержат по N целых чисел a_i, – высоты курганов.

Формат выходных данных

Выведите k строк по 2 целых числа через пробел i, j, 1 ≤ i, j ≤ N – индексы строк и столбцов соответственно, на пересечении которых находятся курганы наиболее значимых граждан (порядок вывода курганов значения не имеет). Если таких курганов нет, то выведите 0.

Ограничения

1 ≤ N ≤ 1500

−10⁹ ≤ a_i ≤ 10⁹

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

5
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 

0

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

1 2

Задача B. Космическое поселение ≡

Условие

Для освоения Марса требуется построить исследовательскую базу. База должна состоять из N одинаковых модулей.

Каждый модуль представляет собой жилой отсек, который в основании имеет форму прямоугольника размером A × B метров.

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

Модуль с защитным слоем, толщина которой равна D метрам, будет иметь в основании форму прямоугольника размером (A + 2 D) × (B + 2 D) метров.

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером W × H метров.

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

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

Пояснения к примеру

В первом примере можно установить дополнительный защитный слой толщиной 2 метра и разместить модули на поле, как показано на рисунке.

Во втором примере жилой отсек имеет в основании размер 5 × 5 метров, а поле — размер 6 × 6 метров.

Добавить дополнительный защитный слой к модулю нельзя.

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

Входной файл содержит пять разделенных пробелами целых чисел: N, A, B, W, H.

Гарантируется, что без дополнительного защитного слоя все модули можно разместить в поселении описанным образом.

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

Выходной файл должен содержать одно целое число: максимальную возможную толщину дополнительного защитного слоя.

Если дополнительный защитный слой установить не удастся, требуется вывести число 0.

Ограничения

1 ≤ N, A, B, W, H ≤ 10¹⁸

Система оценки и описание подзадач

Подзадача 1 (26 баллов)

1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (23 балла)

1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 10⁹.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 3 (24 балла)

1 ≤ N ≤ 10⁹; 1 ≤ A, B, W, H ≤ 10¹⁸.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (27 баллов)

1 ≤ N ≤ 10¹⁸; 1 ≤ A, B, W, H ≤ 10¹⁸.

В этой подзадаче 9 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

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

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

11 2 3 21 25

2

1 5 5 6 6

0

Задача C. Быстрая помощь ≡

Условие

В городе В случилась катастрофа: неожиданно наступила зима. Чтобы облегчить судьбу жителей В, из города М решено направить N самолётов с тёплой одеждой.

Самолёты имеют различную скорость, так что самолёт номер i затратит на полёт в точности a_i минут. Разгрузка любого самолёта в аэропорту В занимает L минут, после чего аэропорт готов к приёму следующего самолёта.

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

Самолёты могут взлетать в любом порядке, но не должны обгонять друг друга в воздухе, т. е. если самолёт 1 взлетел раньше самолёта 2, то и приземлиться он должен раньше.

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

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

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

Ограничения

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

2 10
8 5

25

Задача D. Черепаха в лабиринте ≡

Условие

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

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

Вам нужно написать программу для черепахи Тортилы.

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

В первой строке входного файла содержатся числа N M

В следующих далее N строчек по M символов содержится описание лабиринта:

• Точка '.'(ASCII 46) обозначает пустую клетку
• Решётка '#'(ASCII 35) обозначает стену, в такие клетки заползти нельзя

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

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

Ограничения

1 ≤ N, M ≤ 500

Гарантируется, что левый нижний и правый верхний углы лабиринта — пустые клетки

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

3 3
...
.#.
...

2

5 3
...
...
#..
.#.
...

6

2 10
........#.
..#.......

0

Задача H. Кубики ≡

Условие

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

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

Помогите Пете! Выясните, сколько кубиков может быть у Пети. Петя видит отражение всех кубиков в зеркале и часть кубиков, которая находится перед ним. Часть кубиков может быть позади Пети, их он не видит.

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

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

Ограничения

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

6 2
1 1 2 2 1 1

3 5 6