Спортивный программист для достижения вершин своего мастерства должен быть натренирован в совершенно разных аспектах, в том числе и физически. Кто-то для этого садится на велосипед, кто-то ныряет в бассейн, а молодой программист Влад бегает по стадиону. Но из-за неаккуратного обращения с личными вещами его секундомер может измерять время только в минутах, без указания секунд и тем более их долей.
Чтобы следить за прогрессом своего ученика, тренеру Влада приходится довольствоваться показаниями этого прибора. Каждый раз, когда Влад пробегает мимо тренера, сделав очередной круг по стадиону, тот записывает в блокнот показания секундомера в минутах. Фактически показания секундомера соответствуют целому числу минут, прошедших к определенному моменту времени. Причём, если секундомер показывает, например, 1, то это может обозначать и время ровно 2 минуты, так как 1.(9) = 2.
На контрольной тренировке Влад бегал с постоянной скоростью, однако по записям тренера не так легко сказать, с какой именно. Кроме того, секундомер был, возможно, запущен до того как Влад начал бегать. Напишите программу, которая поможет тренеру определить за какое минимальное, а также максимальное возможное время Влад мог пробегать каждый круг.
В первой строке входного файла находится единственное натуральное число N — количество записей в блокноте тренера (2 ≤ N ≤ 105). В следующей строке находятся сами эти записи — разделённые пробелами целые числа a1, a2, ..., aN (0 ≤ a1 ≤ a2 ≤ ... ≤ aN ≤ 106). Здесь a1 соответствует времени, когда Влад пробежал мимо тренера в первый раз.
Выведите два неотрицательных вещественных числа, разделённых пробелом, — минимальное и максимальное возможное количество минут, за которое спортсмен пробегал один круг. Ваш ответ должен отличаться от правильного менее чем на 10 - 3.
Если ответа не существует, то есть Влад не мог бежать с постоянной скоростью так, чтобы записи тренера получились именно такими, в единственной строке выведите «No solution».
5
2 3 5 6 8
1.33333 1.66667
5
1 6 9 14 17
4 4
3
1 5 6
No solution
5
1 1 2 3 3
0.5 0.75
Во втором тесте время 4 соответствует показаниям секундомера 1.(9), 6.0, 9.(9), 14.0, 17.(9).
В четвёртом примере минимальное время соответствует показаниям секундомера 1.5, 1.(9), 2.5, 3.0, 3.5, а максимальное — показаниям 1.0, 1.75, 2.5, 3.25, 3.(9).
Максим и Лёша поехали на сборы в Петрозаводск. После тура они решили не ходить на дорешивание, а поиграть в шахматы. Игра проходит на бесконечной доске, и в какой-то момент у Максима осталось только две ладьи и король, а у Алексея — один король. А на бесконечной доске в такой ситуации победить затруднительно. Тогда Максим заменил своего короля на припасённую ещё одну ладью и ситуация изменилась.
Помогите Максиму поставить мат тремя ладьями на бесконечной доске.
Это интерактивная задача. При запуске решения на стандартный поток ввода поступают 8 чисел — координаты короля и трёх ладей на поле. Координаты не превосходят по модулю 100. Гарантируется, что в начальный момент никакие две фигуры не стоят на одной клетке, и король не находится под боем ни одной из ладей. Первый ход делает Максим.
На каждый ход Максима вводится ответный ход Алексея — перемещение короля dx, dy относительно текущей позиции (0 ≤ |dx|, |dy| ≤ 1). В случае, если |dx| = |dy| = 0, программа должна немедленно завершиться (это означает, что был поставлен мат, пат или сделан некорректный ход).
Для каждого хода выводите на стандартный поток вывода три числа — номер ладьи (1, 2 или 3) и перемещение ладьи lx, ly (|lx| + |ly| > 0;|lx|·|ly| = 0). Ход должен быть корректным, т. е. ладья не может пойти в занятую клетку, перепрыгнуть через другую фигуру. Перемещение ладьи не должно быть больше, чем на 1 000 клеток.
2 0 1 2 0 4 4 1
1 0
-1 -1
0 0
1 0 -1
2 3 0
3 -2 0
Вывод должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в С/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
Программа не должна делать более 40 ходов. Если после хода программы мат не поставлен, а король сделать ход не может, то считается, что тест не пройден.
Ладья может ходить на произвольное количество клеток по горизонтали или по вертикали. Король же может ходить в любую соседнюю клетку, которая не находится под боем ладьи, в том числе, он может «съесть» ладью, если клетка, в которой ладья стоит, не находится под боем другой ладьи. Обратите внимание, что в случае, если король съест ладью, то выигрыш станет невозможным, и тест не будет пройден.
Мат — ситуация в шахматах, когда король находится под ударом ладьи, а игрок не может сделать ни одного хода, чтобы его избежать. Пат — ситуация в шахматах, когда король не находится под ударом ладьи, но при этом игрок не может сделать ни одного хода.
Обратите внимание, что тестирующая система сообщает подробный протокол взаимодействия вашей программы и программы жюри. Гарантируется, что существует программа, которая на всех тестах жюри умеет ставить мат.
Пример ответа тестирующей системы для примера из условия.
Starting position: king on (2 0), rooks on (1 2) (0 4) (4 1)
Turn 1
Max moves 1st rook to (1 1)... OK.
Alex moved king to (3 0)
King on (3 0), rooks on (1 1) (0 4) (4 1)
Turn 2
Max moves 2nd rook to (3 4)... OK.
Alex moved king to (2 0)
King on (2 0), rooks on (1 1) (3 4) (4 1)
Turn 3
Max moves 3rd rook to (2 1)... OK.
It's nowhere for king to go :-(
Game over! Checkmate - Max wins!
Положение фигур по ходу игры.
В одном уездном городе Эн было решено построить собственное метро. Все силы города были мобилизованы на выкапывание станций и прокладку подземных путей дедовскими лопатами.
Вся эта история нас бы совершенно не интересовала, если бы однажды в мэрию города не пришло письмо из далёкой страны Емакира. Оказалось, что компания Alpep подозревает администрацию уездного города в нарушении их патента на jMetro и грозится возбудить против города Эн дело. Согласно патенту, jMetro — это метро, в котором:
Поскольку компания Alpep известна своими необоснованными обвинениями в нарушениях патентов, мэрия города хочет проверить правомочность заявления компании.
В первой строке заданы два числа N и M ( 1 ≤ N , M ≤ 2·10 5 ) — количество станций метро и перегонов между ними. Следующие M строк содержат описания перегонов: каждая из них содержит по два числа — номера станций, между которыми есть перегон. По каждому перегону составы могут ездить как в одну, так и в другую сторону. Между любыми двумя станциями существует не более одного перегона. Никакой перегон не соединяет станцию саму с собой.
Выведите « YES », если метро уездного города Эн нарушает патент jMetro, и « NO » в противном случае.
Первый пример соответствует рисунку из условия.
15 19 1 4 4 11 2 10 3 2 8 7 7 6 12 10 15 10 11 2 14 9 6 13 7 9 7 11 2 5 8 3 6 10 3 6 11 3 12 3
YES
5 4 2 1 2 3 2 5 2 4
NO