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

Пираты напали на торговую бригантину, и между кораблями началась дуэль. Первый выстрел пираты и торговцы делают в момент встречи кораблей, затем дуэль продолжается, пока один или оба корабля не потонут. Пушки пиратов стреляют через каждые `X` секунд, а пушки торговцев – через каждые `Y` секунд. Пиратская шхуна затонет после `A` выстрелов с бригантины, а бригантина — после `B` выстрелов пиратов.

Напишите программу, определяющую победителя этой дуэли.

Первая строка ввода содержит четыре целых числа `X,\ Y,\ A,\ B` (`1\ ≤\ X,\ Y,\ A,\ B\ ≤\ 100`) – скорострельность пушек и прочность кораблей.

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

20 20 10 5

1

20 10 11 6

0

Когда шхуна в результате неудачной дуэли затонула, пираты сели в шлюпку и отправились на ближайший остров, находящийся под углом `alpha` к направлению на восток (ось `X`). Движению мешает сильное океанское течение, текущее со скоростью `v` под углом `beta` к направлению на восток (см. рис.). Шлюпка пиратов плывёт со скоростью `w`.

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

Первая строка ввода содержит четыре целых числа – скорость шлюпки `w`, скорость течения `v`, направление на остров `alpha` в градусах, направление течения `beta` в градусах (`1\ ≤\ w,\ v\ ≤\ 100`, `0\ ≤\ \ alpha,\ beta\ ≤\ 359`).

Вывести одно число от 0 до 360 - направление движения шлюпки в градусах с точностью `10^{-6}`. Если сила течения так велика, что пираты не смогут добраться до острова, то вывести число `-1`.

10 5 30 60

15.522488

На остров прибыли `N` пиратов. С собой в шлюпке они привезли коробку с `K` крекерами. Уставшие пираты легли спать. Ночью проснулся один из пиратов, разделил крекеры на `N` равных кучек, а лишние крекеры, получившиеся при таком дележе, отдал мартышке. Затем пират съел крекеры из одной кучки, а остальные крекеры сложил обратно в коробку и снова лег спать. Через некоторое время проснулся второй пират, который поступил точно также. Так же сделали и все остальные пираты. Утром пираты проснулись, поделили поровну между собой оставшиеся крекеры, а лишние крекеры снова отдали мартышке.

Напишите программу, определяющую, сколько крекеров досталось мартышке.

Первая строка ввода содержит два целых числа – количество пиратов `N` (`2\ ≤\ N\ ≤\ 10`) и количество крекеров `K` (`100\ \ ≤\ \ K\ ≤\ 10^9`).

3 100

4

Пояснение к примеру: первый пират отдал мартышке 1 крекер, и в коробке осталось 66 крекеров, второй пират ничего мартышке не дал, а в коробке осталось 44 крекера, третий пират отдал мартышке 2 крекера, а в коробке утром было 28 крекеров, из которых 1 крекер получила мартышка.

После завтрака пираты развлекаются, играя в "пять чашек". Один из пиратов переворачивает вверх дном 5 чашек и кладет небольшой шарик под самую левую из них. Затем он начинает менять пары соседних чашек местами, не отрывая их от стола. Возможны четыре варианта обмена чашек, которые обозначены буквами A (обмен 1 и 2 чашки), B (2 и 3), С (3 и 4) и D (4 и 5). Другой пират пытается угадать, где находится шарик.

Напишите программу, определяющую местонахождение шарика после серии обменов.

Первая строка ввода содержит последовательность из букв A, B, C и D, длиной от 1 до 100 символов.

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

ABD

3

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

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

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤100`) — количество кусков пиццы. Каждая из следующих `N` строк содержит имя пирата, взявшего очередной кусок пиццы. Имя пирата содержит от 1 до 20 строчных латинских букв.

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

4
silver
silver
pew
silver

2

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

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

Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 1000`) – размеры острова. Далее следует `N` строк, содержащих по `M` символов N, S, W и E. Символ N означает, что пират при попадании на этот участок местности побежит на север (вверх), символ S – на юг (вниз), символ W – на запад (влево), символ E – на восток (вправо). Гарантируется, что символы на краях острова не ведут за пределы острова.

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

3 4
EEES
NEWS
NWWW

2

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

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

Первая строка ввода содержит одно целое числа – количество пробок и бутылок `N` (`1\ ≤\ N\ ≤\ 2000`). Далее программа должна выдавать запросы вида "? `i\ j`", где `i` – номер пробки, а `j` – номер бутылки (`1\ ≤\ i,\ j\ ≤\ N`). После вывода запроса программа должна сделать принудительную запись буфера вывода (в C++ это делает endl, в C нужно использовать fflush(stdout), в Pascal - flush(output)). На запрос программа получает строку, содержащую символ '<', если диаметр пробки `i` меньше диаметра горлышка бутылки `j`, или символ '>', если пробка больше, или символ '=', если пробка точно подходит. Программа может сделать не более `75000` запросов. Когда программа полностью определит соответствие между бутылками и пробками, она должна вывести строку, содержащую символ '!', после которого следует последовательность из `N` чисел от 1 до `N`, разделенных пробелами, и завершить работу. `i`-е число в этой последовательности указывает номер пробки для `i`-й бутылки.

2
<
=

? 1 1
? 2 1
! 2 1

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

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

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

11
.....XX...X
....XX...XX
...XX...XX.
...........
....XXX....
...........
.....X.....
....XX...X.
...XX...XX.
...X...XX..

3
2 6 8

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

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

Первая строка ввода содержит два целых числа – количество участников в командах `N` (`2\ ≤\ N\ ≤\ 20`) и предельную разницу в весе `D` (`1\ ≤\ D\ ≤\ 10000`). Далее следует две строки, содержащих по `N` чисел от 1 до 10000 – веса участников в первой и во второй команде.

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

3 100
160 155 100
95 100 105

1
1 3

Пояснение к примеру: также можно поменять 2-го участника из первой команды на 1-го или 2-го участника из второй.

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

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

Первая строка ввода содержит одно целое число — количество деревьев `N` (`3\ ≤\ N\ ≤\ 100000`). Далее следует `N` строк, содержащих по два целых числа в диапазоне от –10000 до 10000 — координаты деревьев. Нет деревьев с совпадающими координатами.

Вывести одно число — максимальное расстояние с относительной точностью `10^{-4}` (выведенный ответ должен отличаться от правильного не более на 0.01%).

4
1 1
1 -1
-1 -1
-1 1

1.41421356