Задачи отборочных командных соревнований школьников 2012

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

Установим систему координат следующим образом. Центр диска имеет координаты `(0,0)`. Ось `Y` совпадает с Осевой дорогой. Пусть один город имеет координаты `(X_1,\ Y_1)`, а другой город – координаты `(X_2,\ Y_2)`. Тогда расстояние между городами, у которых `Y_1\ ≠\ Y_2`, вычисляется по формуле `|X_1|\ +\ |X_2|\ +\ |Y_1-Y_2|`, а расстояние между городами, у которых `Y_1\ =\ Y_2`, вычисляется по формуле `|X_1\ -\ X_2|`, где `|a|` означает абсолютное значение (модуль) числа `a`.

Напишите программу, определяющую расстояние, которое нужно пройти по дорогам, чтобы попасть из города с координатами `(X_1,\ Y_1)` в город с координатами `(X_2,\ Y_2)`.

Первая строка ввода содержит четыре целых числа `X_1`, `Y_1`, `X_2`, `Y_2` (`0\ ≤\ X_1^2+Y_1^2\ ≤\ 10^8`, `0\ ≤\ X_2^2+Y_2^2\ ≤\ 10^8`) – координаты двух городов.

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

10 15 -10 -5

40

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

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

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

Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 50`) – размеры карты. Далее следует `N` строк, содержащих по `M` символов. Символ '.' означает свободную от зданий клетку, а символ '#' – клетку, в которой находится одно здание. Гарантируется, что на карте есть хотя бы одно здание.

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

3 6
###.##
.###.#
.#..##

10
2 4

Примечание к примеру: через час после поджога дома в клетке (2,4) будет гореть 10 домов одновременно, и это зрелище можно будет наблюдать в течение получаса.

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

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

Первая строка ввода содержит два целых числа `N`, `M` (`0\ ≤\ N,\ M\ ≤\ 100000`), разделенных пробелом. Вторая строка ввода содержит `N` целых чисел – элементы первой последовательности, а третья строка содержит `M` целых чисел – элементы второй последовательности. Элементы каждой последовательности разделены пробелами. Все элементы последовательностей – целые числа, не превосходящие по абсолютной величине `10^9`.

Вывести одно целое число – минимальное количество операций.

2 4
1 2
-5 2 1 7

4

Трактир "Залатанный барабан" известен тем, что каждый вечер в нем происходит драка. Сначала эти драки возникали случайно, но затем превратились в командные соревнования между представителями трех рас – людьми, гномами и троллями. Каждый вечер в трактире происходит несколько поединков, сначала каждый человек из первой команды сражается с каждым гномом из второй команды, затем с каждым троллем из третьей команды, затем каждый гном сражается с каждым троллем. Участники соревнований из одной команды между собой не сражаются. Например, если в первой команде 5 человек, во второй 3 гнома, а в третьей 1 тролль, то будет проведено `5*3+5*1+3*1\ =\ 23` поединка. По правилам соревнований количество человек в первой команде должно быть больше или равно количеству гномов во второй команде, а количество гномов – больше или равно количеству троллей, так как в Анк-Морпорке живет очень много людей, много гномов и мало троллей.

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

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100\ 000`) – требуемое количество поединков.

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

23

23 1 0
11 1 1
7 2 1
5 3 1

В ходе поединка трактирщик Чарли записывает удары, выполненные каждым из участников, а по окончании выполняет подсчет баллов и определяет победителя. Участник, получивший большее количество баллов, становится победителем. Разные удары оцениваются в разное количество баллов. Удары Stroke и Blow дают один балл, удар Kick – два балла, а удар Jab – три балла. Чарли записывает только первую букву названия удара.

Напишите программу, которая определяет победителя поединка по записям Чарли.

Первая строка ввода содержит список ударов, выполненных первым участником. Вторая строка ввода – список ударов, выполненных вторым участником. Обе строки имеют длину от 0 до 100 букв и содержат только прописные латинские буквы B, J, K и S.

Вывести одно целое число – номер победившего участника поединка или 0, если у участников равное количество баллов.

KKBS
JKJ

2

Трактир "Залатанный барабан" весьма популярен среди искателей приключений, наемников, сорвиголов и негодяев. Искатели приключений всегда ходят большими кампаниями, так как убить дракона или гигантского монстра в одиночку практически невозможно. Рассказывая о своих подвигах одни герои (лгуны) всегда их приукрашивают, а другие (правдолюбы) говорят только правду. Нельзя верить ни одному числу, сказанному лгуном. Он может рассказать, как одним выстрелом из баллисты убил семь драконов, хотя всем известно, что драконы не летают стаями, и у них только одно уязвимое место на брюхе, в которое очень сложно попасть. Во время путешествий герои часто рассказывают друг другу истории и поэтому знают, сколько в их кампании лгунов и правдолюбцев. Трактирщик Чарли решил узнать, сколько лгунов в кампании, зашедшей в его трактир, так как кампания, в которой все лгуны, может удрать, не заплатив, или расплатиться фальшивой монетой. Но в результате, опросив всех героев и получив разные числа, Чарли не смог разобраться с этой проблемой.

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

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 100`) – количество человек в кампании. Во второй строке содержится `N` целых чисел в диапазоне от 0 до `N` – ответы искателей приключений на вопрос Чарли о количестве лгунов в их кампании.

В первой строке вывести одно число `K` – число вариантов количества лгунов. Во второй строке вывести `K` чисел – варианты количества лгунов в порядке возрастания. Если `K` равно 0, то вторая строка не выводится.

2
1 1

1
2

2
1 0

2
1 2

2
0 2

0

Во всех примерах количество лгунов может быть 0, 1 или 2.

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

В втором примере, если сказал правду герой, сказавший 0, то второй герой тоже должен был сказать 0. Следовательно, сказать правду мог только герой, назвавший число 1. Так же есть вариант когда оба героя лгут, не называя число 2.

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

`N` паломников после совместного путешествия к пирамидам Джелибейби сидят за круглым столом. Во время поездки они делали какие-то платежи как за себя, так и за других членов группы. У каждого есть некоторая сумма денег, оставшаяся после поездки, и каждый подсчитал, какая сумма должна получиться, если бы он платил только за себя. Вместо того, чтобы прямо передать деньги друг другу, паломники рассчитали среднее арифметическое `S` для  сумм, оставшихся у них после поездки, и пытаются перераспределить деньги нужным образом, используя только следующую операцию по передаче денег. Пусть у `i`-го человека текущая сумма денег равна `a_i`. Если `a_i\ >\ S`, то `i`-й человек должен передать соседу слева сумму `a_i\ -\ S` и такую же сумму соседу справа. Если `a_i\ <\ S`, то `i`-й человек должен забрать у сосед слева сумму `S\ -\ a_i` и такую же сумму у соседа справа.

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

В первой строке ввода содержится одно целое число `N` (`3\ ≤\ N\ ≤\ 1000`) – количество паломников. Во второй строке содержится `N` целых чисел `a_i` в диапазоне от 0 до 1000 – начальные суммы денег у паломников в порядке обхода стола по часовой стрелке. В третьей строке содержится `N` целых чисел `b_i` в диапазоне от 0 до 1000 – конечные суммы денег у паломников в том же порядке. Гарантируется, что сумма `a_i` равна сумме `b_i`.

Если перераспределение денег возможно, то в первой строке вывести сообщение YES, во второй строке вывести количество операций по передач денег, в третьей строке – номера паломников, которые должны выполнять передачу. Нумерация паломников начинается с 1. Можно вывести любой план выполнения операций, не обязательно самый кратчайший.

Если перераспределение денег невозможно, то в первой строке вывести сообщение NO.

3
1 2 3
3 1 2

YES
2
3 2

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

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

Первая строка ввода содержит три целых числа `A`, `B`, `C` (`1\ ≤\ A\ ≤\ B\ ≤\ C\ ≤\ 1000`, `A+B\ >\ C`) – размеры сторон треугольной столешницы. Вторая строка ввода содержит два целых числа `W`, `H` (`1\ ≤\ W,\ H\ ≤\ 1000`) – размеры прямоугольного проема в стене трактира.

В первой строке вывести сообщение YES, если столешницу можно пронести в проем, иначе вывести сообщение NO.

30 30 40
10 20

YES

30 30 40
10 19

NO

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

Напишите программу, которая определяет порядок подачи лодок для минимизации суммарного недогруза.

Первая строка ввода содержит два целых числа - количество типов лодок `N` (`2\ ≤\ N\ ≤\ 50`) и количество грузов в очереди `M` (`1\ ≤\ M\ ≤\ 100\ 000`). Вторая строка ввода содержит `N` различных целых чисел в порядке возрастания в диапазоне от 50 до 1000 – грузоподъемность каждого типа лодок. Третья строка ввода содержит M целых чисел в диапазоне от 50 до 1000  – веса желающих переправиться вместе с их грузом. Существует по крайней мере один тип лодки, которая может перевести любой груз из очереди.

Вывести в первой строке два целых числа – количество необходимых для переправы лодок `K` и минимальный суммарный недогруз `S`. Вторая строка должна содержать номера типов лодок в порядке их использования для перевозки. Если существует несколько вариантов, минимизирующих суммарный недогруз, то можно вывести любой из них.

2 5
300 500
200 200 200 200 200

3 300
1 2 2