Задача 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. Радиостанция ≡

Условие

Во время исследования поверхности планеты Каппа-2 у отряда, в который входил курсант О’Денил, сломалась радиостанция! Для того, чтобы станция снова заработала, нужно заново настроить генератор несущей частоты. Курсант О’Денил знает, что несущая частота имеет вид двоичной последовательности d = 1010101010101… (последовательность может оканчиваться как на 0, так и на 1) и находится в диапазоне [a,b], где a и b - целые числа и a < b. Отряду нужно определить, можно ли настроить радиостанцию заново.

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

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

Единственная строка содержит два целых числа a и b, разделенные пробелом.

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

Выведите одно число - наибольшее число d (a ≤ d ≤ b), имеющее вид искомой последовательности. Если в диапазоне нет такой последовательности, то выведите 0.

Ограничения

1 ≤ a < b ≤ 10⁹

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

8 15

10

1 9

5

16 32

21

15 20

0

Задача C. Десант ≡

Условие

Курсант О’Денил, успешно прошедший теоретический курс в военной академии, был направлен для прохождения боевой практики на борт действующего корабля ВКФ Земной Федерации в звании третьего лейтенанта. Его корабль был направлен к звездной системе Каппа для высадки научной экспедиции.

По прибытии в систему кораблю требовалось обеспечить высадку исследовательского десанта на планету Каппа-2. Капитан корабля Мелисса Старк вызвала нашего героя для постановки следующей боевой задачи: обеспечить должное наведение десантной капсулы для достижения заданной точки.

О’Денил сразу же вспомнил, что для лучшего результата требуется установить угол наведения относительно борта корабля так, чтобы отрезок, соединяющий центр борта корабля и поверхность планеты был перпендикулярен к поверхности планеты. Для проведения данной операции наводчику выдавались координаты x₀, y₀ передней и x₁, y₁ задней части палубы корабля. Расчет проводится в плоскости орбиты корабля. Центр окружности, описывающей планету, размещается в начале координат (0,0).

Лейтенант просит Вас рассчитать угол, под которым будет проведен запуск десантной капсулы. Запуск будет проведен с центра корабля. Направление отсчета координат ведется от задней палубы к передней. За 0 градусов принимается угол, при котором капсула будет запущена параллельно кораблю.

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

В первой строке через пробел подаются четыре целых числа x₀, y₀, x₁, y₁ – координаты передней и задней палуб корабля.

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

В единственной строке выведите вещественное число z, 0 ≤ z ≤ 180 с точностью до двух знаков после запятой - угол в градусах, под которым с корабля проведен запуск десантной капсулы.

Ограничения

1 ≤ x₀, y₀, x₁, y₁ ≤ 10⁹

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

4010 3000 3990 3000

36.869897645844

Задача D. Полеты в космосе ≡

Условие

Экспедиция, в которую входит лейтенант О'Денил, собирается отправиться в далекую звездную систему F из системы S. Но ограничения на количество топлива в корабле не позволяют лететь напрямую по назначению, так что приходится делать дозаправки в других системах не реже, чем через T лет. Чтобы максимально быстро преодолевать межзвездные расстояния, половину пути корабль летит равноускоренно с ускорением a = 1св.год / год², а вторую половину равнозамедленно с тем же ускорением, что позволяет останавливаться вовремя. Дозаправки, по сравнению с перелетами, происходят моментально. Кроме того, из-за космических опасностей возможны перелёты только по заданным переходам.

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

Примечания:

Если корабль начал движение с нулевой начальной скоростью, то расстояние, пройденное им за время t с ускорением a, следует считать по формуле at²2.

Световой год - расстояние, которое свет проходит в вакууме за один год.

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

В первой строке вводится целое число T – максимальное время перелета между системами в годах.

Во второй строке вводится 3 целых числа: количество известных звездных систем N, номер начальной звездной системы S и номер конечной F (S ≠ F).

В третьей строке вводится количество безопасных переходов между различными соседними системами M. Остальные M строк содержат описания переходов в виде трех целых чисел a_i, b_i, l_i, где a_i и b_i - номера систем, а l_i - расстояние между системами в световых годах 1 ≤ l_i ≤ 10⁹.

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

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

Ограничения

1 ≤ a_i,b_i ≤ N

1 ≤ i ≤ M

2 ≤ N ≤ 50

1 ≤ S, F ≤ N

1 ≤ M ≤ N ⋅ (N − 1)2

1 ≤ l_i ≤ 10⁹

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

7
5 1 5
5
2 1 9
2 3 7
1 4 2
2 3 13
3 5 4

15.2915026221292

200
7 1 5
12
1 4 10403
1 5 14444
1 7 4
2 3 7609
3 4 233
3 5 3393
4 2 5278
4 5 8023
5 6 2781
6 2 3303
7 3 997
7 6 5664

183.649540649073

Задача E. Шифр ≡

Условие

Отряд под командованием лейтенанта О’Денила нашел странный текст, который состоит из n пар целых неотрицательных чисел a, b с одинаковым количеством разрядов. Лейтенант понял, что текст зашифрован и передал его в штаб.

В штабе дешифровщики поняли, что для расшифровки текста необходимо, чтобы пары были отсортированы следующим образом: первые числа a - по возрастанию, а вторые b - по убыванию в случаях, где первые числа соответствующих пар равны т.е. там, где

a_i = a_j, i ≠ j, i, j = 1,2,3,…,n

Помогите дешифровщикам получить зашифрованную последовательность, написав программу-дешифратор, сортирующие пары чисел указанным способом.

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

В первой строке подается единственное целое число n - количество пар чисел в последовательности.

В следующих n строках приводится n пар целых чисел a, b - перечень пар чисел для расшифровки.

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

Выведите n строк, в каждой из которых записана пара целых чисел a, b - искомую последовательность.

Ограничения

2 ≤ n ≤ 10³

 − 10⁹ ≤ a, b ≤ 10⁹

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

3
1123 1325
6356 3731
6356 3738

1123 1325
6356 3738
6356 3731