Задачи личных соревнований по спортивному программированию 2014

Хоттабыч отправил Женьку в королевство Бенэм и забыл отменяющее заклинание. Пришлось Вольке и Хоттабычу лететь в спасательную экспедицию на ковре-самолете. По пути им удалось связаться с Женькой и договориться, что он выложит на поляне `N` костров по кругу на равном расстоянии друг от друга и зажжет три из них, проинформировав таким образом о своем точном местонахождении и текущей обстановке на земле. Так как ковер-самолет может подлететь к поляне с любой стороны, то комбинации из 3 костров, переходящие друг в друга при повороте и зеркальном отражении, считаются одинаковыми. У разных сигналов должны отличаться расстояния между кострами.

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

Первая строка ввода содержит одно целое число `N` (`3\ ≤\ N\ ≤\ 1\ 000\ 000`) – количество вершин `N`-угольника.

В первой строке вывести одно число – количество различных сигналов.

6

3

В благодарность за свое освобождение джинн Гассан Абдуррахман ибн Хоттаб подарил Вольке караван верблюдов, груженных золотом. При подсчете выяснилось, что в сундуках может быть разное количество золотых монет. Женька, хорошо разбирающийся в математике, предположил, что количество монет в `i`-м сундуке можно задать как значение некоторого полинома от индекса `i`.

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

Первая строка ввода содержит одно целое число `N` (`3\ ≤\ N\ ≤\ 40`) – количество сундуков, в которых подсчитали количество монет. Во второй строке содержатся `N` целых чисел от 1 до 10000 – количество монет в сундуках.

В первой строке вывести одно число – предполагаемое количество монет в `(N+1)`-м сундуке. Допустимо, что число будет отрицательным.

4
1001 1004 1009 1016

1025

Хоттабычу так понравилось эскимо, что он забрал у продавщицы весь поднос с товаром. Он угостил Вольку и Женьку, а остальные – съел сам. Никто не считал, сколько было порций на подносе, но известно, что прямоугольные упаковки эскимо лежали на подносе в один слой, рядами, параллельными сторонам прямоугольного подноса, при этом все упаковки были ориентированы в одном направлении (но неизвестно — вдоль или поперек подноса).

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

Первая строка ввода содержит четыре целых числа `a`, `b`, `W` и `H` (`3\ ≤\ a\ ≤\ b\ ≤\ 20`, `20\ ≤\ W\ ≤\ H\ ≤\ 120`), разделенных пробелами – размеры упаковки эскимо и размеры подноса.

Вывести в первой строке одно целое число – максимально возможное количество порций эскимо, съеденных Хоттабычем.

5 12 44 75

46

На футбольном матче Хоттабыч стал подыгрывать команде «Шайба». Игроки команды «Зубило» не могли сдвинуться с места, а игроки другой команды волшебным образом перелетали с места на место. Но колдовство джинна не отличалось высокой точностью и могло переместить футболистов «Шайбы» только в точки с целыми координатами. Поэтому, если между двумя игроками «Зубило» не было точек с целыми координатами, они могли передать пас друг другу. С другой стороны, футболисты команды «Зубило» не могли пнуть мяч более чем на `D` метров.

Мяч попал к одному из игроков команды «Зубило». Напишите программу, которая определит, сможет ли команда «Зубило» забить гол. Для этого игрокам «Зубило» нужно попасть мячом в точку с координатами (0,0), которая находится внутри ворот команды «Шайба».

Первая строка ввода содержит два целых числа – количество игроков `N` (`1\ ≤\ N\ ≤\ 11`) в команде «Зубило» и максимальное расстояние `D` (`1\ ≤\ D\ ≤\ 100`), на которое игроки «Зубило» могут передать пас. Далее следует `N` строк, каждая строка содержит два целых числа `X_i`, `Y_i` (`1\ ≤\ X_i\ ≤\ 100`, `-35\ ≤\ "Yi"\ ≤\ 35`) – координаты `i`-го игрока «Зубило». Нет игроков с совпадающими координатами. В начальный момент времени мяч находится у 1-го игрока.

Вывести сообщение YES, если команда «Зубило» может забить гол, или NO, в противном случае.

2 5
2 0
4 1

YES

2 4
2 0
4 1

NO

Заметив, что Хоттабыч помогает команде «Шайба», Волька выхватил у одного из болельщиков стакан с боржомом и выплеснул на бороду джинна. Предположим, что в бороде Хоттабыча растут волоски разного типа и для управления перемещением нужен определенный набор волосков.

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

Первая строка ввода содержит последовательность длиной от 1 до 100000 из строчных латинских букв – перечисление типов волосков в бороде Хоттабыча слева направо. Каждая буква соответствует некоторому типу волоска. Вторая строка ввода содержит последовательность длиной от 1 до 1000 из строчных латинских букв – набор волосков для управления перемещением. Порядок букв в этом наборе является несущественным, важно только количество.

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

acdabbcbaxc
bca

4 5

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

Ввод содержит 8 строк по 8 символов, описывающих начальную позицию. Символ '.' означает пустую клетку, прописные латинские буквы K, Q, R, B, N, P обозначают короля, ферзя, ладью, слона, коня и пешку белых соответственно. Строчные латинские буквы k и n обозначают короля и коня черных соответственно. Символ '@' обозначает желаемую позицию короля. Символы K, k, n и '@' встречаются во входных данных ровно один раз, символы Q, R, B, N, P – не более 3 раз. 8-я строка ввода соответствует первой горизонтали шахматной доски. В начальной позиции король черных может находиться под шахом.

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

........
...k.@..
........
........
B.....n.
........
....Q...
...K....

4

........
..k..@..
........
........
......n.
........
...RR...
...K....

-1

"Ладога" вошла в полосу густых туманов. На палубе было неинтересно, сыро, в каютах – скучно. Поэтому все кресла и диваны в кают-компании были заняты экскурсантами. Одни играли в шахматы, другие – в шашки, третьи читали. Хоттабыч, Волька и Женька играли в игру «Контакт». Правила этой игры следующие. Один игрок (ведущий) загадывает секретное слово и говорит остальным игрокам первую букву этого слова. Каждый раунд кто-то из игроков, исключая ведущего, придумывает слово, начинающееся с открытых к этому моменту букв. Количество букв в этом слове должно быть больше, чем количество открытых букв секретного слова. Игрок дает описание этого слова, не называя его. Если ведущий по описанию в течении некоторого времени угадывает это слово, то раунд проигран. Если есть другой игрок, который угадает слово по описанию, то раунд выигран, и ведущий должен сказать следующую букву в слове. Слова повторно использовать нельзя. Если угадывающий игрок дает описание для секретного слова, то игра заканчивается. Также игра заканчивается, если открыты все буквы секретного слова.

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

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

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10000`) – количество слов. Далее следует `N` строк, каждая из которых содержит слово из строчных латинских букв длиной от 2 до 100 после которого через пробел записана одна цифра 0 или 1. Цифра 0 означает, что Хоттабыч не сможет назвать слово по его описанию, 1 – что сможет. Все слова начинаются с одной и той же буквы.

Вывести одно целое число – минимальное количество раундов игры в худшем случае.

7
cheater 1
cheburashka 0
centurion 0
centaur 1
center 1
celebration 1
cell 1

4

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

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

Первая строка ввода содержит два целых числа – текущая цена товара `P` (`2\ ≤\ P\ <\ 10^9`) и количество недель `K` (`1\ ≤\ K\ ≤\ 50`).

Вывести одно целое число – цену товара через `K` недель.

225 2

63

Омар Юсуф, брат Хоттабыча, в настоящее время работает в качестве спутника Земли. Иногда Хоттабыч связывается по радио с ним, чтобы поздравить с днем рождения или с Новым годом. Так как ультракороткие волны распространяются только в пределах прямой видимости, для Хоттабыча важно знать, когда возможен сеанс связи.

Напишите программу, которая определяет, возможно ли установить радиосвязь при следующих условиях. На самом краю земного диска радиуса `R` находится Хоттабыч. Омар вращается вокруг диска на расстоянии `2R` от центра диска. Угол между векторами, направленными из центра диска на текущие положения Хоттабыча и Омара, равен `A`. Радиосвязь возможна только в случае, если Омар находится выше касательной к диску в той точке, где находится Хоттабыч.

Первая строка ввода содержит одно целое число – угол `A` (`-180\ <\ A\ ≤\ 180`).

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

25

YES

-100

NO

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

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

Первая строка ввода содержит два целых числа в диапазоне от 1 до 999 – начальные координаты Вольки. Вторая строка ввода содержит одно целое число `N` (`3\ ≤\ N\ ≤\ 5`) – количество углов многоугольника. Третья строка ввода содержит `2N`  целых чисел в диапазоне от 0 до 1000 – координаты углов выпуклого многоугольника в порядке обхода против часовой стрелки. Координаты Вольки находятся строго внутри многоугольника.

Первая строка вывода должна содержать одно число – минимальное расстояние с точностью `10^-6`.

20 5
4
0 0 25 0 25 15 0 15

36.055513