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

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

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

Государственная антимонопольная служба возбудила расследование против крупной авиакомпании «Aero-float». Ей предъявлено обвинение в излишней неэкономности. Джонни было поручено проинспектировать «Aero-float» в целях обнаружения финансовых махинаций, но авиакомпания отказалась раскрывать полный список выполняемых ею прямых рейсов. После продолжительных переговоров руководство компании согласилось сообщить Джонни информацию о минимально возможной продолжительности перелёта между каждой парой городов, если использовать только прямые рейсы «Aero-float» и не учитывать время, затрачиваемое на пересадки.

Используя эту информацию, помогите Джонни установить: может ли компания «Aero-float» быть экономной или нет? Более формально, установите, существует ли набор рейсов, при котором длины кратчайших маршрутов именно такие, как было сообщено Джонни, и при котором компания является экономной?

Город N, в отличие от города M, расположен на склоне одного холма. Чистоту улиц этого города обеспечивает единственная поливальная машина. Бензин нынче дорог, поэтому движение муниципального транспорта «в гору» признано слишком расточительным.

Карта города представляет собой прямоугольник, разбитый на H × W клеток, где H и W — высота и ширина карты в клетках соответственно. Часть клеток заняты зданиями, остальные соответствуют улицам и площадям, которые и требуется помыть.

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

Помогите узнать экономному муниципалитету, какое максимальное количество свободных клеток поливальная машина сможет помыть, не поднимаясь при этом в гору? Определите также, какое минимально возможное расстояние ей при этом придётся преодолеть. Считается, что, перемещаясь в соседнюю по горизонтали или вертикали клетку, поливальная машина преодолевает одну единицу расстояния.

На Международной олимпиаде по информатике некоторые участники, конечно же, получают удовольствие именно от решения предложенных задач, но большинство — от полученных в новой стране впечатлений. Впечатления принято запечатлевать на фотоаппарат. Участник T решил подойти к процессу съёмок с научной (по его мнению) точки зрения. Он находится на круглой обзорной площадке и желает заснять сразу два интересных объекта, местоположение каждого из которых на земле мы будем описывать с помощью отрезка. T выбирает точку для съёмок внутри этой площадки так, чтобы суммарная площадь двух треугольников, образованных концами соответствующих отрезков и выбранной точкой на обзорной площадке была как можно больше.

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

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

Как и сегодня, за час до окончания олимпиады таблица результатов была «заморожена». Каково же было удивление участников, когда при подведении итогов выяснилось, что в окончательной таблице все команды расположились строго в обратном порядке (по отношению к порядку, зафиксированному «заморозкой»). Так как в окончательной таблице результатов посылки участников не отражены, вам предлагается определить, могло ли такое быть в принципе, или это результат технического сбоя системы.

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

Чтобы следить за прогрессом своего ученика, тренеру Влада приходится довольствоваться показаниями этого прибора. Каждый раз, когда Влад пробегает мимо тренера, сделав очередной круг по стадиону, тот записывает в блокнот показания секундомера в минутах. Фактически показания секундомера соответствуют целому числу минут, прошедших к определенному моменту времени. Причём, если секундомер показывает, например, 1, то это может обозначать и время ровно 2 минуты, так как 1.(9) = 2.

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