Задача A. Дилемма счетовода ≡

Условие

В некотором царстве, в некотором государстве жил был царь. Очень этот царь любил математику, а еще оброк, который платили ему главные купцы: Аршинов, Вавилов, Лукин, Климов, Пименов, Федотов и Шевелёв. Каждый из них дает оброк в пушнине, самоцветах, тканях, жемчугах и товарах заморских.

Царский счетовод все пересчитывает в золото и аккуратно записывает. И продолжалось так из года в год, пока царь не решил все задачи, которые хотел и не добрался до оброка. Много думал и придумал свою задачу для счетовода: "А сосчитай-ка ты мне на сколько мер золота платит самый богатый купец больше, чем самый бедный, а иначе голова с плеч".

Помогите счетоводу справится с поставленной задачей.

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

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

Все числа положительные и не превосходят 255.

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

Выведите одно целое число — ответ на задачу.

Описание системы оценивания

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

По запросу сообщается количество набранных баллов за каждый тест.

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

10 10 10 10 10
1 1 2 3 5
8 13 21 34 36
20 20 20 20 20
5 5 5 5 5
1 2 4 8 16
3 9 27 62 10

100

249 21 19 131 243
64 172 241 145 43
168 132 108 140 136
203 60 250 225 184
148 163 198 247 134
43 154 216 154 25
19 127 68 180 198

330

Задача B. Спасательная операция ≡

Условие

Из-за столкновения Титаника с льдиной образовалась огромная дыра в борту судна. Данная авария не обошлась без жертв. Владимиру Ленину не хватило места в спасательной шлюпке, но остался спасательный круг радиуса R₁. Не долго думая Вова прыгнул в ледяную воду.

Спустя некоторое время Вова обнаружил, что он окружен со всех сторон льдинами. Известно, что Вова оказался в центре круглой полыньи радиуса R и центром в точке с координатами (x, y).

Во избежания обморожения, на помощь Владимиру выдвинулись спасатели. Для спасения утопающего, необходимо спустить спасательный челнок радиуса R₂. При спуске челнока он должен полностью поместиться в полынье и не должен пересекаться с спасательным кругом Владимира. Для того чтобы спасатели точно знали, где находится Вова, он не меняет своего местоположения и находится в точке с координатоми (x₁, y₁).

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

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

В первой строке записано три целых числа R, x, y — радиус территории и координаты ее центра.

Во второй строке три целых числа R₁, x₁, y₁ — радиус спасательного круга Ленина и его координаты.

В третьей строке записано одно целочисленное радиус спасательного челнока R₂.

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

Выведите "Yes", если Ленин будет спасён, или "No", если это невозможно.

Ограничения

1 ≤ R₁, R₂ ≤ R ≤ 1000

0 ≤ x, y ≤ 1000

0 ≤ x₁, y₁ ≤ 1000

Описание системы оценивания

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

По запросу сообщается количество набранных баллов за каждый тест.

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

40 2 0
13 2 0
7

Yes

20 0 0
12 1 1
13

No

20 0 0
5 15 0
15

Yes

Задача C. Тяжелая химия ≡

Условие

Никита — химик со стажем. Сегодня он купил себе весы с двумя чашами. Он собирается использовать их для взвешивания атомов различных химических элементов. Один атом может весить любое целое количество нанограммов от 1 до N.

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

Никите стало интересно, какое минимальное количество гирь ему необходимо купить, чтобы он смог взвесить атом любого химического элемента.

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

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

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

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

Ограничения

1 ≤ N ≤ 2 ⋅ 10⁹

Описание системы оценивания

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

По запросу сообщается количество набранных баллов за каждый тест.

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

В первом примере Никита может купить гири с весом 1, 1 и 4. Возможны и другие варианты весов, но купить менее трёх гирь не получится.

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

5

3

3

2

20

4

Задача D. Накопительная система ≡

Условие

У Пети есть N копилок. Изначально все копилки пусты. Мальчик может совершать два действия:

• 1 i m d — положить во все копилки следующее количество монет: max(0, m − d ⋅ |i−j|), где j — номер копилки, куда кладутся моменты. Проще говоря, в копилку i кладётся m монет, в копилки i−1 и i+1 — m − d монет, i+2 и i−2 — m − 2 ⋅ d и т.д. до нуля.
• 2 l r — узнать суммарное количество монет в копилках с номерами от l до r.

Сегодня Петя задумал выполнить Q действий. Помогите ему узнать ответ для каждого действия второго типа.

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

Первая строка содержит два целых числа N и Q — количество копилок и количество действий, которые Петя собирается совершить.

Далее следует Q строк, в каждой из которых записано одно действие в формате, описанном в условии задачи.

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

Для каждого действия второго типа выведите строку, содержащую одно целое число.

Ограничения

1 ≤ N, Q ≤ 10⁵

1 ≤ d ≤ m ≤ 10⁵

1 ≤ i, l, r ≤ N

Описание подзадач и системы оценивания

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

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

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

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

8 10
2 1 8
1 1 3 1
2 1 2
1 3 7 2
2 2 5
2 1 8
1 7 10 8
2 1 8
2 3 3
2 4 7

0
5
23
30
44
8
21

Задача E. Крестики-нолики ≡

Условие

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

Правила игры следующие: два игрока по очереди делают ходы на поле 3 × 3. Ход заключается в том, чтобы поставить в любую свободную клетку свой символ. Тот кто ходит первым ставит крестики, тот кто вторым — нолики. Выигрывает тот, кто первым сможет собрать в линию по вертикали, горизонтали или диагонали три своих символа. Если никто не смог этого сделать — объявляется ничья.

Преподаватель решил позволить Пете ходить первым, так как хочет эффектно рисовать на доске нолики, символизируя тем самым, что именно он думает о знаниях Пети по его предмету.

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

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

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

Чтобы сделать ход ваша программа должна вывести "x y", где x — номер строки, y — номер столбца, куда Петя совершает ход.

На каждый свой ход программа жюри может вывести следующее:

 — "win" — если ход вашей программы стал выигрышным для Пети;

 — "draw" — если преподаватель не может сделать ход и объявлена ничья;

 — в первой строке "go", а во второй строке "x y" — ход преподавателя в соответствующую клетку;

 — в первой строке "lose", а во второй строке "x y" — если соответствующий ход преподавателя приводит его к победе;

Если ваша программа получила "win" или "draw", то сразу же начинается новая партия, кроме случая, когда текущая партия была последней.

Если ваша программа получила "lose", то она должна немедленно завершиться. На данном тесте ваше решение получит вердикт "Wrong answer".

Если ваша программа попытается сделать ход в уже занятую клетку, то это приведёт к получению вердикта "Presentation error".

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

Ограничения

1 ≤ N ≤ 1000

1 ≤ x, y ≤ 3

Описание системы оценивания

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

По запросу сообщается количество набранных баллов за каждый тест.

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

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

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

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

2

go
1 2

go
3 1

go
2 1

win

go
2 2

go
1 3

go
3 2

go
1 1

draw

2 2


1 3


2 3


3 3

3 3


1 2


3 1


2 1


2 3