Задача A. Avengers and Shawarma ≡

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M, T ≤ 100

0 ≤ S ≤ 100

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

5 2
10 5

45

13 4
4 1

22

10 1
5 0

50

Задача B. Breaking digits ≡

Условие

Требуется написать программу, которая, получив целое число A в десятичной записи, разделит его цифры между двумя числами B и C таким образом, чтобы:

1. Каждая цифра числа A встречалась ровно один раз либо в B, любо в C.
2. Сумма B + C была максимально возможной.

Формат входного файла

Входной файл содержит единственное целое число A.

Формат выходного файла

Выходной файл должен содержать целые числа B и C. Если существует несколько решений, выведите любое из них.

Ограничения

10 ≤ A ≤ 10⁹

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

11

1
1

439

94
3

1000

100
0

Задача C. Casino ≡

Условие

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

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

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

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

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

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

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

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

Ограничения

0 ≤ N ≤ 40

1 ≤ M ≤ 1000

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

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

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

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

0 2

1

1 1

2

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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N, M ≤ 1000

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

2 2
XX
SF

1 1

4 4
#F.X
##X#
X#SX
###F

2 3

2 5
.F#S.
XXXXX

1 2

3 5
.F#S.
.#X#.
X..X#

0 1

Задача E. Edge of the knight ≡

Условие

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

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

Формат входного файла

В первой строке записано расположение первого коня в формате HW, где H — обозначение колонки (вертикали), W — обозначение строки (горизонтали).

Формат выходного файла

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

Ограничения

H ∈ (a, b, c, d, e, f, g, h)

1 ≤ W ≤ 8

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

Напомним, что фигура конь ходит буквой Г. То есть во время своего хода конь перемещается в одном из направлений (вертикальном или горизонтальном) на 1 одну клетку, а в другом направлении — на 2 клетки.

В первом примере второго коня можно поставить в клетки c1, g1, c3, g3, d4 и f4.

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

e2

6

f5

8

Задача F. Dreaming on a train ≡

Условие

Программист Вася каждый день ездит на работу и с работы на электричке.

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

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

Если Вася услышит название своей станции, то ни за что ее не проспит.

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

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

Формат входного файла

В первой строке входного файла даны целые числа N, M — общее количество станций и количество станций, которое Вася проспит.

Формат выходного файла

В выходной файл выведите единственное число — вероятность проспать объявление своей станции с точностью не менее 5 знаков после запятой.

Ограничения

1 ≤ M ≤ N ≤ 1000

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

2 1

0.5

3 1

0.25

Задача G. Factorio ≡

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M, U_N, U_K, U_M ≤ 10⁹

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

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

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

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

10 7
1 3 1

3

6 4
2 5 3

3

13 11
2 6 3

5

Задача H. Hydrocarbons ≡

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10000

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

CH4

..H..
..|..
H-C-H
..|..
..H..

CH2CH2

H.....H
.\.../.
..C=C..
./...\.
H.....H

CH3CH2CH2CH3

..H.H.H.H..
..|.|.|.|..
H-C-C-C-C-H
..|.|.|.|..
..H.H.H.H..

CH3CHCCH2

..H.H.....H
..|.|..../.
H-C-C=C=C..
..|......\.
..H.......H

Задача I. Encrypted phone ≡

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

100 ≤ N ≤ 400

1 ≤ X_i ≤ 5000

Q = min(150 ⋅ N, 5 ⋅ 10⁴)

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

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

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

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

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

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