Задача A. Воробьянинов и афиши

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

"С утра по Васюкам ходил высокий худой старик в золотом пенсне и в коротких, очень грязных, испачканных клеевыми красками сапогах. Он наклеивал на стены рукописные афиши." (И.Ильф, Е.Петров. "Двенадцать стульев").

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

Формат входных данных

Единственная строка входного файла содержит три натуральных числа: n — количество домов на улице, a и b — выбранные Воробьяниновым числа.

Формат выходных данных

Выведите одно неотрицательное целое число — количество расклеенных афиш.

Ограничения

1 ≤ n, a, b ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере на улице 10 домов. Ипполит Матвеевич первым проходом расклеил пять афиш на дома, номера которых делятся на 2, то есть на дома с номерами 2, 4, 6, 8, 10. Вторым проходом он расклеил две афиши на дома, номера которых делятся на 3, то есть на дома с номерами 3 и 9. Дом номер 6 он пропустил — на нем афиша уже висит. Всего наклеено 7 афиш.

Во втором примере Воробьянинов не наклеит ни одной афиши.

Примеры тестов

Стандартный вход Стандартный выход
1
10 2 3
7
2
8 10 27
0

Задача B. Клуб четырех коней

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

"— И в самом деле, — сказали васюкинцы, — почему бы не переименовать нашу секцию в клуб четырех коней?" (И.Ильф, Е.Петров. "Двенадцать стульев").

Но одной смены названия мало - нужна хорошая эмблема. Единогласно было принято решение, что на ней будет изображена шахматная доска размером n × m, на которой будут располагаться четыре коня: два белых и два черных, причем каждый конь должен атаковать обоих своих противников. Помогите васюкинским любителям и посчитайте количество всех возможных различных эмблем для клуба.

Напомним, что шахматный конь атакует все поля, которые расположены на 2 клетки в одном направлении и одну клетку в сторону, образуя букву «Г».

Формат входных данных

Единственная строка входного файла содержит два натуральных числа, записанных через пробел: n и m.

Формат выходных данных

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

Ограничения

1 ≤ n, m ≤ 106

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В первом примере на доске 4 × 4 возможно нарисовать 8 различных эмблем.

Примеры тестов

Стандартный вход Стандартный выход
1
4 4
8
2
10 8
416

Задача C. Дворец шахматной мысли

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

Дворец шахматной мысли имеет высоту n этажей. На каждом этаже с номером k имеется ⌊ nk (n деленное на k, округленное вниз до целой части) комнат. Комнаты выровнены по левой границе и пронумерованы. Из первой комнаты каждого этажа можно перейти к лифтам.

Два шахматиста хотят как можно скорее встретится за шахматной доской. Первый из них сейчас находится на этаже k1 в комнате номер m1, второй - на этаже k2 в комнате номер m2. Чтобы им не мешали проходящие мимо люди, шахматисты договорились встретится в самой дальней комнате (то есть в комнате с наибольшим номером) на некотором этаже.

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

Формат входных данных

Единственная строка входного файла содержит семь натуральных чисел: n - количество этажей дворца, k1, m1 - местоположение первого шахматиста, k2, m2 - местоположение второго шахматиста, t1, t2 - время перемещения шахматистов между соседними комнатами и этажами. Гарантируется непротиворечивость входных данных.

Формат выходных данных

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

Ограничения

1 ≤ n, k1, m1, k2, m2 ≤ 109

1 ≤ t1, t2 ≤ 103

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере оба игрока уже находятся в самой дальней комнате этажа.

Во втором примере имеется девятиэтажный дворец. Первый игрок находится на первом этаже в шестой комнате, второй - на девятом этаже в первой комнате. От одной комнаты до другой они перемещаются за пять секунд, спускаются и поднимаются на лифте за одну секунду. Быстрее всего им встретиться на пятом этаже. До последней комнаты этого этажа первый шахматист будет добираться 39 секунд, второй - значительно быстрее (14 секунд). Соответственно, игра начнется через 39 секунд.

Примеры тестов

Стандартный вход Стандартный выход
1
9 3 3 3 3 1 1
3 0
2
9 1 6 9 1 5 1
5 39

Задача D. Два чемпиона мира

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

— Это он! — закричал одноглазый. — Ура! Ура! Ура! Я узнаю великого философа-шахматиста, старичину Ласкера. Только он один во всем мире носит такие зеленые носочки.

Хозе-Рауль Капабланка-и-Граупера снова поморщился." (И.Ильф, Е.Петров. "Двенадцать стульев").

Ласкер и Капабланка (второй и третий чемпионы мира по шахматам) сыграли между собой n партий. За победу выигравший получал 1 очко, за ничью оба соперника получали по 0,5 очка. В результате Капабланка всего набрал k очков, причем никакие две игры подряд не завершались с одним исходом. Укажите количество способов сыграть таким образом n партий.

Формат входных данных

Единственная строка входного файла содержит натуральное число n - количество сыгранных партий и число k - количество набранных очков Капабланкой. Число k либо целое, либо дробное с десятичной дробной частью равной 0,5.

Формат выходных данных

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

Ограничения

1 ≤ n ≤ 32

0 ≤ k ≤ 32

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере сыграно 4 партии, Капабланка набрал 2,5 очка. Укажем все шесть способов сделать это (указаны набранные Капабланкой очки в каждой партии):

1) 0 1 0,5 1

2) 0,5 1 0 1

3) 1 0 1 0,5

4) 1 0 0,5 1

5) 1 0,5 0 1

6) 1 0,5 1 0

Во втором примере Капабланка не мог проиграть две игры подряд.

Примеры тестов

Стандартный вход Стандартный выход
1
4 2.5
6
2
2 0
0

Задача E. Все билеты проданы

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

— Ну, как? — тихо спросил гроссмейстер.

— Входных тридцать и для игры — двадцать, — ответил администратор.

— Шестнадцать рублей. Слабо, слабо!

Через час в кассе было тридцать пять рублей. Публика волновалась в зале." (И.Ильф, Е.Петров. "Двенадцать стульев").

По количеству проданных билетов и собранным средствам определите стоимость билетов за вход и за право сыграть с гроссмейстером.

Формат входных данных

Первая строка входного файла содержит два неотрицательных целых числа a1 - количество проданных билетов за вход и b1 - количество проданных билетов за игру, а также число s1 - собранные за проданные билеты деньги. Число s1 указано в формате с десятичной точкой, после которой следует ровно две десятичных цифры (r.kk). Число до точки соответствует количеству собранных рублей, после - копеек. Первая строка соответствует состоянию кассы в некоторый момент времени после продажи хотя бы одного билета и до продажи последнего билета. Во второй строке в том же формате указаны количества проданных билетов и собранная сумма на момент закрытия кассы - a2, b2 и s2. Гарантируется непротиворечивость входных данных.

Формат выходных данных

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

Ограничения

0 ≤ a1 ≤ a2 ≤ 106

0 ≤ b1 ≤ b2 ≤ 106

0 ≤ r ≤ 109

00 ≤ kk ≤ 99

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Примеры тестов

Стандартный вход Стандартный выход
1
30 20 16.00
100 30 35.00
0.20
0.50
2
0 1 16.00
0 2 32.00
-1
16.00

Задача F. Игра с ладьями

Автор:Математические игры (Петров Н.Н), Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

Бендер и одноглазый любитель играют в следующую игру. На доске находится n ладей. Игроки ходят по очереди, первым ходит Остап. За один ход игрок может убрать с доски не менее одной и не более половины всех оставшихся ладей. Например, если сейчас на доске 8 ладей, забрать можно от 1 до 4 ладей. Проигрывает тот, после чьего хода останется последняя ладья. Кто выиграет при правильной игре?

Формат входных данных

Единственная строка входного файла содержит одно натуральное число: n - начальное количество ладей на доске.

Формат выходных данных

Выведите победителя - одно слово 'Bender' или 'One-eyed' (без кавычек).

Ограничения

2 ≤ n ≤ 109

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере Бендер вынужден забрать одну ладью. На доске останется последняя ладья - Остап проиграл.

Во втором примере первым ходом Бендер заберет три ладьи, на доске останется пять. Независимо от хода противника (тот заберет одну или две фигуры), Остап сможет оставить ему после своего второго хода две ладьи на доске и выиграть.

Примеры тестов

Стандартный вход Стандартный выход
1
2
One-eyed
2
8
Bender

Задача G. Путь к спасению

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

— Вот я вас сейчас, сволочей! — гаркнул он храбрецам-разведчикам, бросаясь с пятой площадки. Испуганные пластуны ухнули, переваливаясь за перила, и покатились куда-то в темноту бугров и склонов. Путь был свободен.

— Держите гроссмейстера! — катилось сверху. " (И.Ильф, Е.Петров. "Двенадцать стульев").

Остап бежит вниз по лестнице, на некоторых площадках которой его поджидают рассерженные шахматисты. У сына турецкоподданого есть показатель агрессивности, начальный уровень которой равен a. Если этот показатель не меньше количества k васюкинцев на площадке, то он может потратить k единиц агрессивности и преодолеть площадку без повреждений. В противном случае (или если Остапу не хочется уменьшать агрессивность), он получает от шахматистов k тумаков, а его агрессивность увеличивается на ⌊ k2 (k пополам, округленное вниз до целой части).

Определите наименьшее число тумаков, которое может получить на лестнице великий комбинатор.

Формат входных данных

Первая строка входного файла содержит два неотрицательных целых числа a - начальное состояние агрессивности и n - количество площадок, на которых Остапа поджидают противники. Во второй строке даны n натуральных чисел ki - количество шахматистов на каждой такой площадке.

Формат выходных данных

Выведите одно натуральное число - ответ на задачу.

Ограничения

0 ≤ a ≤ 100

1 ≤ n ≤ 100

1 ≤ ki ≤ 10

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

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

На первой площадке Остап не тратит агрессивность и получает первый тумак. Его агрессивность при этом не меняется (⌊ 12⌋  = 0) и по-прежнему равна 5.

На второй площадке Остап снова не тратит агрессивность и получает еще три тумака (всего 4). Его агрессивность при этом увеличивается на 1 (⌊ 32⌋  = 1) и становится равна 6.

На третьей площадке Остап пугает противников и не получает новых тумаков (всего 4). Его агрессивность уменьшается на 2 и становится равна 4.

На четвертой площадке Остап не тратит агрессивность и получает еще четыре тумака (всего 8). Его агрессивность при этом увеличивается на 2 (⌊ 42⌋  = 2) и опять становится равна 6.

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

Примеры тестов

Стандартный вход Стандартный выход
1
5 6
1 3 2 4 1 5
8

Задача H. В поисках равновесия

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

"— Осторожней, — пискнул одноглазый капитан.

Но было уже поздно. Слишком много любителей скопилось на правом борту васюкинского дредноута. Переменив центр тяжести, барка не стала колебаться и в полном соответствии с законами физики перевернулась." (И.Ильф, Е.Петров. "Двенадцать стульев").

После ряда экспериментов, изрядно промокшие шахматные любители поняли, что:

1) количество гребцов в барке должно быть одинаковым по обоим бортам.

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

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

Формат входных данных

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

Формат выходных данных

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

Ограничения

2 ≤ n ≤ 20

1 ≤ ai ≤ 106

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В первом примере всего два шахматиста. Разница их весов не может быть улучшена.

Во втором примере шестерых людей можно разделить на две группы с равными весами 50 + 50 + 100 и 80 + 60 + 60.

Примеры тестов

Стандартный вход Стандартный выход
1
2
70 80
10
2
6
50 80 60 50 100 60
0

Задача I. Конец большой игры

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

"Остап описал вокруг потерпевших крушение круг.

— Вы же понимаете, васюкинские индивидуумы, что я мог бы вас поодиночке утопить, но я дарую вам жизнь. Живите, граждане! Только, ради создателя, не играйте в шахматы! Едем, Ипполит Матвеевич, дальше!" (И.Ильф, Е.Петров. "Двенадцать стульев").

По данному английскому слову определите - 'Yes' или 'No'.

Формат входных данных

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

Формат выходных данных

Выведете 'Yes' или 'No' (без кавычек).

Ограничения

1 ≤ len(s) ≤ 20.

Система оценки и описание подзадач

Баллы за задачу начисляются только в случае, если все тесты успешно пройдены.

Примеры тестов

Стандартный вход Стандартный выход
1
football
Yes

1.065s 0.030s 37