Учительница по программированию задала Вовочке задачу — отсортировать массив из N чисел от 1 до N по возрастанию :). Вовочка поступает так: он просматривает массив слева направо, и, если замечает два элемента, стоящих рядом, таких, что правый меньше левого, он меняет их местами. Так он поступает, пока массив не будет отсортирован. Но Вовочка — очень ленивый ученик. В какой-то момент ему надоело сортировать числа, и он решил посчитать, сколько ещё описанных выше обменов нужно сделать. Помогите ему.
В первой строке входного файла находится натуральное число N (1 ≤ N ≤ 1 000 000). Во второй строке через пробел находятся N различных целых чисел, каждое из которых не меньше 1 и не больше N.
Выведите одно число — искомое количество обменов. Так как ответ может быть очень большим и сложным, выведите его по очень простому модулю 2.
5
1 2 5 4 3
1
Город N, в отличие от города M, расположен на склоне одного холма. Чистоту улиц этого города обеспечивает единственная поливальная машина. Бензин нынче дорог, поэтому движение муниципального транспорта «в гору» признано слишком расточительным.
Карта города представляет собой прямоугольник, разбитый на H × W клеток, где H и W — высота и ширина карты в клетках соответственно. Часть клеток заняты зданиями, остальные соответствуют улицам и площадям, которые и требуется помыть.
Поливальная машина начинает свой путь в одной из клеток самого верхнего ряда, не занятой зданиями. Она может полить асфальт в текущей клетке и переместиться в любую из двух соседних клеток этого же ряда, не занятых зданиями. Объехать здания, не поднимаясь при этом в гору, невозможно. Поливальная машина также может переместиться в соседнюю по вертикали свободную клетку из нижнего ряда.
Помогите узнать экономному муниципалитету, какое максимальное количество свободных клеток поливальная машина сможет помыть, не поднимаясь при этом в гору? Определите также, какое минимально возможное расстояние ей при этом придётся преодолеть. Считается, что, перемещаясь в соседнюю по горизонтали или вертикали клетку, поливальная машина преодолевает одну единицу расстояния.
В первой строке входного файла находятся натуральные числа H и W — высота и ширина карты города (1 ≤ W ≤ 1 000, 1 ≤ H ≤ 1 000). В следующей строке расположено единственное натуральное число K — номер столбца клетки первой строки, в которой поливальная машина начинает движение (1 ≤ K ≤ W). Гарантируется, что эта клетка свободна от зданий.
Каждая из следующих H строк содержит W символов ‘|#|’ и ‘.’, означающих, соответственно, клетки со зданиями и без.
Выведите два целых числа — максимальную площадь в клетках, которую может обработать поливальная машина, и минимальное расстояние, которое ей для этого придётся преодолеть.
8 8
7
..#....#
##..#...
...#..#.
.##..#..
..#.#...
#.#.#...
#.#...##
##..####
21 23
На Международной олимпиаде по информатике некоторые участники, конечно же, получают удовольствие именно от решения предложенных задач, но большинство — от полученных в новой стране впечатлений. Впечатления принято запечатлевать на фотоаппарат. Участник T решил подойти к процессу съёмок с научной (по его мнению) точки зрения. Он находится на круглой обзорной площадке и желает заснять сразу два интересных объекта, местоположение каждого из которых на земле мы будем описывать с помощью отрезка. T выбирает точку для съёмок внутри этой площадки так, чтобы суммарная площадь двух треугольников, образованных концами соответствующих отрезков и выбранной точкой на обзорной площадке была как можно больше.
Помогите T с выбором такой точки. Возможность заснять сразу два объекта при этом анализировать не нужно, мы лишь действуем в рамках модели, сформулированной T. Если объекты загораживают друг друга, то этим также нужно пренебречь и считать площади независимо.
В первой строке входного файла находятся число T — количество тестов (1 ≤ T ≤ 105). Далее следуют описания тестов. В первой строке каждого описания содержится 4 числа x1, y1, x2, y2, характеризующие координаты концов первого отрезка. Во второй строке — x3, y3, x4, y4, описывающие второй отрезок. В третьей строке записаны три числа x0, y0, R — координаты центра круговой площадки и её радиус. Все числа целые, по модулю не превосходящие 1 000. Радиус положителен.
Гарантируется, что отрезки невырождены и не пересекаются с круговой площадкой. Также гарантируется, что они не имеют общих внутренних точек.
Для каждого теста выведите координаты точки внутри круга, удовлетворяющей условию задачи. Если таких точек несколько, то выведите любую из них. Координаты следует выводить с как можно бóльшим числом знаков после десятичной точки. Соответствующая сумма площадей должна отличаться от правильного ответа по абсолютной или относительной величине не больше чем на 10 - 6.
1
0 0 1 0
0 0 -1 0
0 2 1
0.0000000000 3.0000000000
Командная олимпиада, о которой идёт речь в этой задаче, проходила по тем же правилам, что и олимпиада, в которой вы сейчас участвуете. Возможно, за одним исключением: на ней было введено ограничение на суммарное число посылок от одной команды, которые можно было потратить как на одну задачу, так и распределить их по всем задачам некоторым образом.
Как и сегодня, за час до окончания олимпиады таблица результатов была «заморожена». Каково же было удивление участников, когда при подведении итогов выяснилось, что в окончательной таблице все команды расположились строго в обратном порядке (по отношению к порядку, зафиксированному «заморозкой»). Так как в окончательной таблице результатов посылки участников не отражены, вам предлагается определить, могло ли такое быть в принципе, или это результат технического сбоя системы.
Первая строка содержит три натуральных числа: N — количество команд, K — количество задач, L — лимит на суммарное число посылок по задачам (N ≤ 1000, K ≤ 12, K ≤ L ≤ 200).
Далее следуют N строк, описывающих саму таблицу на момент заморозки. i-я строка содержит название команды (строка из латинских символов и цифр длины не более 50) и K элементов, показывающих успех команды по каждой из задач. j-й элемент таблицы имеет вид * Wrong(Time), где:
* — знак ‘ + ’ или ‘ - ’, показывающий, решила ли команда задачу;
Wrong — количество неуспешных посылок по данной задаче;
Time — минута, на которой команда сдала задачу (0 ≤ Time ≤ 239); если данная задача ещё не была решена, Time = 0.
Команды упорядочены от первого места на момент заморозки к последнему. Напоминаем, что команды сортируются по числу решённых задач, а при равном количестве — по увеличению штрафного времени, которое складывается из времени сдачи задачи и общего количества неудачных попыток по решённым задачам, умноженного на 20. Продолжительность олимпиады — 5 часов.
Гарантируется, что ни одна команда не превысила лимит на число посылок и что никакие две команды не имеют одинаковый с точки зрения сортировки результат.
Если порядок команд теоретически мог измениться за последний час соревнований на обратный, то сначала выведите строку «Possible», а затем подробную таблицу окончательных результатов в формате, аналогичном таблице из входного файла (см. пример). Если соревнование так закончиться не могло, то выведите единственную строку «Impossible».
3 3 10
winner +2(235) +3(170) -2(0)
middle -2(0) +1(30) -0(0)
looser -1(0) +5(30) -0(0)
Possible
looser +1(240) +5(30) +0(240)
middle +5(241) +1(30) +0(240)
winner +2(235) +3(170) +2(240)
2 2 20
winner +10(1) +0(10)
looser -0(0) +1(1)
Impossible
Спортивный программист для достижения вершин своего мастерства должен быть натренирован в совершенно разных аспектах, в том числе и физически. Кто-то для этого садится на велосипед, кто-то ныряет в бассейн, а молодой программист Влад бегает по стадиону. Но из-за неаккуратного обращения с личными вещами его секундомер может измерять время только в минутах, без указания секунд и тем более их долей.
Чтобы следить за прогрессом своего ученика, тренеру Влада приходится довольствоваться показаниями этого прибора. Каждый раз, когда Влад пробегает мимо тренера, сделав очередной круг по стадиону, тот записывает в блокнот показания секундомера в минутах. Фактически показания секундомера соответствуют целому числу минут, прошедших к определенному моменту времени. Причём, если секундомер показывает, например, 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).