Задача A. Avengers and Shawarma

Автор:A. Usmanov. Translation: V. Toropov.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Разобравшись с инопланетным вторжением, Мстители решили перекусить шаурмой.

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

Халк крушит!, пока ожидает приготовления заказанной шаурмы.

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

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

В первой строке записано два целых числа N и M — количество шаурмы, заказанные Халком, и количество поваров, взявшихся за заказ гиганта.

Во второй строке записано два целых числа T и S — время приготовления первой шаурмы и разница во времени между приготовлением последующих.

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

Выведите одной целое число — время приготовления всего заказа Халка.

Ограничения

1 ≤ N, M, T ≤ 100

0 ≤ S ≤ 100

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

Стандартный вход Стандартный выход
1
5 2
10 5
45
2
13 4
4 1
22
3
10 1
5 0
50

Задача B. Bedtime thoughts

Автор:A. Usmanov. Translation and Illustrations: A. Logutova.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

Сегодня муж Анастасии подарил ей автомобиль. Девушке стало интересно, способен ли этот автомобиль осветить её комнату.

Окна комнаты Анастасии находятся на высоте H метров. Можно считать, что автомобиль осветил комнату, если освещена любая часть окна.

Свет от фар автомобиля образует сектор окружности. Дальность свечения от фар составляет L метров. Максимальный угол распространения света равен A градусов.

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

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

В первой строке записано три целых числа H, L и A.

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

Выведите "Yes" или "No" (без кавычек) — может ли автомобиль Анастасии осветить её комнату.

Ограничения

1 ≤ L, H ≤ 100

0 < A < 90

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

Стандартный вход Стандартный выход
1
25 50 30
Yes
2
25 45 30
No
3
9 10 89
Yes

Задача C. Casino

Автор:佳木斯大学, A. Usmanov. Translation: V. Toropov.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

Самому старшему из братьев родители дали больше всего денег. Второму по старшинству — на один меньше, чем первому. Третьему — на один меньше, чем второму и т.д. Анингак самый младший и ему досталось всего M долларов.

Братья собираются играть до тех пор, пока у каждого из них не останется денег. Причем, передавать деньги друг другу братья не собираются.

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

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

В первой строке записано два целых числа N и M — количество братьев и количество денег у Анингака.

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

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

Ограничения

0 ≤ N ≤ 40

1 ≤ M ≤ 1000

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

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

Во втором примере у Анингака есть 1 доллар, а у его брата — 2 доллара. Братья могут выбрать ставку в один доллар. Тогда в первом раунде Анингак истратит все свои деньги, а у брата хватит денег сыграть еще в одном раунде.

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

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

Задача D. Don't understarve

Автор:N. Grebenyuk, A. Usmanov. Translation: A. Logutova.   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Уилсон заблудился в пещере размером N × M клеток. Но у него есть карта, на которой приняты следующие обозначения:

'#' — непроходимая клетка (пропасть, стена);

'.' — свободная клетка;

'X' — червоточина, при переходе в эту клетку Уилсон равновероятно переместится в одну из других червоточин;

'S' — начальное положение Уилсона;

'F' — клетка, до которой нужно добраться (выход на поверхность).

Перемещение через червоточину — процесс рискованный, так как при этом очень сильно падает рассудок. А при низком рассудке могут начать нападать монстры.

Рассудка Уилсона хватит ровно на одно перемещение. Поэтому он хочет узнать вероятность выбраться из пещеры, используя при этом не более одной червоточины. Разумеется, Уилсон действует оптимально, то есть он старается максимизировать вероятность.

Уилсон может перемещаться в четырех возможных направлениях: вверх, вниз, вправо, влево.

Обратите внимание, что Уилсон не может наступить в червоточину при этом не переместившись.

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

В первой строке содержится два целых числа N и M — размеры пещеры.

Далее следует N строк по M символов — карта пещеры.

Гарантируется, что на карте всегда присутствует одна клетка 'S', как минимум одна клетка 'F', и как минимум две клетки 'X'.

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

Выведите ответ как обыкновенную несократимую дробь в виде двух целых чисел, разделённых пробелом (например, если ответ 50 / 74, нужно вывести "25 37").

Ограничения

2 ≤ N, M ≤ 1000

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

Стандартный вход Стандартный выход
1
2 2
XX
SF
1 1
2
4 4
#F.X
##X#
X#SX
###F
2 3
3
2 5
.F#S.
XXXXX
1 2
4
3 5
.F#S.
.#X#.
X..X#
0 1

Задача E. Encrypted phone

Автор:N. Grebenyuk, A. Usmanov. Translation: A. Logutova.   Ограничение времени:2 сек
Ввод / вывод:интерактивный   Ограничение памяти:256 Мб

Условие

Данная задача является интерактивной.

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

Чтобы разблокировать свой телефон, Алексей должен разгадать эту последовательность. Для этого он может задать учителю не более Q вопросов — делится ли i-ое число в последовательности (нумерация чисел от 1 до N) на число d.

Помогите Алексею вернуть доступ к телефону, он уже полностью раскаялся в своём поведении на уроке и больше так делать не будет.

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

Первая строка содержит одно целое число N — длина последовательности чисел.

Гарантируется, что числа в последовательности не изменяются в зависимости от вопросов Алексея.

Гарантируется, что последовательность чисел сгенерирована случайным образом.

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

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

Протокол взаимодействия

Для каждого теста жюри зафиксировало число Q — максимальное количество вопросов, которые можно задать учителю. Гарантируется, что Q вопросов достаточно, чтобы решить задачу. Это число не сообщается программе-решению. Если решение делает более Q вопросов, то на этом тесте оно получает в качестве результата тестирования "Wrong answer".

Чтобы задать вопрос программа-решение должна вывести строку вида "? i d", где i (1 ≤ i ≤ N) и d (1 ≤ d ≤ 5000) — целые числа. В ответ на вопрос программа жюри подаёт на вход программе-решению либо строку "Yes", либо строку "No", в зависимости от того, делится ли i-ое число в загаданной последовательности на число d.

Каждый вопрос и вывод ответа должен заканчиваться символом перевода строки \n, а также необходимо выполнить сброс буфера:

Язык C++ Pascal Java Python
Сброс буфера cout.flush() flush(output) System.out.flush() stdout.flush()

Ограничения

100 ≤ N ≤ 400

1 ≤ Xi ≤ 5000

Q = min(150 ⋅ N, 5 ⋅ 104)

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

Обратите внимание, что первый тест не подходит под ограничения задачи (N = 2).

Он сделан лишь для демонстрации протокола взаимодействия программы-решения и программы жюри.

При проверке первого теста Q = 2000.

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

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

Yes

No

Yes

No

No

Yes

Yes

Yes

Yes

Okay

? 1 3

? 1 5

? 1 7

? 1 11

? 1 13

? 1 4998

? 2 128

? 2 512

? 2 4096

! 4998 4096

Задача F. Factorio

Автор:A. Usmanov, L. Verkhovtsev. Translation: A. Logutova.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Астронавт Леонид потерпел крушение на отдалённой неизвестной планете, полной природных ресурсов. Корабль астронавта стал непригодным для путешествий после крушения. Поэтому Леонид был вынужден остаться на планете. Спустя много лет он добился небывалых успехов в освоении планеты — организовал завод по добыче и переработке железной руды.

Завод работает в несколько этапов:

1. N буров добывают руду. Скорость работы одного бура — UN кг/ч;

2. Руда попадает в печи для переплавки. Скорость работы одной печи — UK кг/ч;

3. Пластины из печей попадают в M станков для обработки. Скорость работы одного станка — UM кг/ч.

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

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

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

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

В первой строке записано две целых числа N и M — количество буров и станков.

Во второй строке записано три целых числа UN, UK и UM — скорости работы одного бура, одной печи и одного станка соответственно.

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

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

Если ответов несколько, то следует вывести минимальный.

Ограничения

1 ≤ N, M, UN, UK, UM ≤ 109

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

Рассмотрим подробнее первый пример. Зафиксируем время работы завода — T = 10 часов. Количество добытых ресурсов для разного количество печей представлено в таблице.

Количество печей Добыто руды, кг Переплавлено руды, кг Остаток руды, кг Обработано пластин, кг Остаток пластин, кг Избыток, кг
1100 307030070 + 0
2 604060040 + 0
3 9010702010 + 20
4 100070300 + 30

Для трёх и четырёх печей избыток одинаковый, значит достаточно построить лишь три печи.

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

Стандартный вход Стандартный выход
1
10 7
1 3 1
3
2
6 4
2 5 3
3
3
13 11
2 6 3
5

Задача G. Gandalf and Trolls

Автор:N. Grebenyuk, A. Usmanov. Translation: A. Logutova.   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Гэндальф Серый оказался окружён троллями в пещере. Изначально расстояние между волшебником и ближайшим троллем равно R метров. За каждую секунду тролли успевают пробежать T метров. В конце каждой секунды Гэндальф отбрасывает троллей назад магическим кольцом света на D метров.

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

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

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

Первая строка содержит четыре целых числа R, D, T, S.

Вторая строка содержит вещественное число P, заданное с точностью до 5 знаков после запятой.

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

Выведите единственное вещественное число — вероятность Гэндальфа Серого дожить до рассвета.

Ваш ответ будет считаться правильным, если его абсолютная погрешность не превосходит 10 − 5. А именно: пусть ваш ответ равен a, а ответ жюри — b. Тогда ваш ответ будет считаться правильным, если |a − b| ≤ 10 − 5.

Ограничения

1 ≤ R ≤ 50000

1 ≤ D, T ≤ 100

1 ≤ S ≤ 500

0 ≤ P ≤ 1

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

Стандартный вход Стандартный выход
1
10 10 10 1
1.0
0.00000
2
15 6 10 2
0.7
0.70000
3
7 1 2 3
0.0
1.00000
4
50000 100 100 500
0.0
0.00000
5
100 99 1 500
0.01
0.33301

Задача H. Hydrocarbons

Автор:N. Grebenyuk. Translation: A. Logutova, V. Toropov.   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Группа учёных изучала образец ванадиевого катализатора нового поколения. Он позволяет формировать самые разнообразные линейные углеводороды из газообразной смеси углерода и водорода.

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

Любая углеводородная цепочка, полученная в данном эксперименте, в полном виде строится по следующим правилам:

1. Сначала цепь изображается в виде линейной последовательности атомов углерода (помечаются символом 'C'). При этом связь между соседними углеродами может быть как одинарной (помечается как '-'), так и двойной (помечается '=').

2. Затем к каждому углероду присоединяются атомы водорода одинарными связями так, чтобы каждый углерод был четырехвалентен, то есть суммарно образовывал 4 связи (двойная связь считается за две связи):

 — у крайних атомов углерода (первый и последний) водороды присоединяются так, чтобы связи образовывали равные углы. То есть если водородов 2, то они будут связаны диагональными связями ('/', '\'), если 3, то связями вверх ('|'), вниз ('|') и вбок ('-').

 — у остальных углеродов: если имеется 1 водород, то он присоединяется связью вверх, если 2 водорода, то вверх и вниз.

В кратком виде же цепочка записывается как последовательность вида CHa1 CHa2...CHaN, где ai (2 ≤ ai ≤ 4) — количество атомов водорода при i-м углероде. Если количество атомов водорода равно 1, то оно не указывается. Если у углерода нет атомов водорода, то символ 'H' не указывается вообще.

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

Для полного понимания внимательно просмотрите примеры.

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

Первая строка содержит строку — краткую запись углеводородной цепи.

Гарантируется, что данная углеводородная цепь является корректной.

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

Выведите поле символов размером 5 × (3 + 2 ⋅ N), где N — количество углеродов в цепочке.

Все пробелы, незанятые символами связи или атомов, следует заполнить символами '.'.

Ограничения

1 ≤ N ≤ 10000

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

Стандартный вход Стандартный выход
1
CH4
..H..
..|..
H-C-H
..|..
..H..
2
CH2CH2
H.....H
.\.../.
..C=C..
./...\.
H.....H
3
CH3CH2CH2CH3
..H.H.H.H..
..|.|.|.|..
H-C-C-C-C-H
..|.|.|.|..
..H.H.H.H..
4
CH3CHCCH2
..H.H.....H
..|.|..../.
H-C-C=C=C..
..|......\.
..H.......H

0.697s 0.019s 29