Задача A. Трёхцветник ≡

Условие

Куст трёхцветника в начале своего роста выглядит, как три ветки, направленные в разные стороны:

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

После первого и второго циклов цветения трёхцветник примет следующий вид:

Юному садоводу стало интересно узнать количество веток у куста трёхцветника после N циклов цветения.

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

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

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

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

В единственной строке выведите ответ на задачу.

Ограничения

1 ≤ N ≤ 40

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

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

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

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

1

9

2

21

Задача B. Доставка почты ≡

Условие

Почтальон Пётр привёз посылки для жителей 108 дома. В этом доме всего один подъезд, N этажей и отсутствует лифт.

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

Пётр не привык выбирать, какие посылки доставлять в первую очередь, поэтому берёт их случайно. Взяв посылки, он доставляет их в порядке возрастания этажей. Например, если почтальон взял посылки для 2, 5 и 10 этажа, то сначала он доставит посылку на 2-й этаж, потом на 5-й, потом на 10-й. После этого он возвращается в свой грузовик за новой партией. И так до тех пор, пока не будут доставлены все посылки.

Подъёмом называется суммарное количество этажей, на которое необходимо подняться, доставляя посылки. Например, если почтальон доставляет посылки на 1 и 3 этажи, а потом на 2, то сначала он поднимется на 1-й этаж, потом поднимется с 1-о этажа на 3-й, потом вернётся в грузовик за посылкой для 2-о этажа и доставит её. Подъём в данном случае будет равен 1 + (3−1) + 2 = 5.

Разумеется, от порядка доставки зависит величина подъёма. Пётр хочет узнать минимальное или максимальное возможное значение подъёма.

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

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

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

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

Третья строка содержит одно целое число P. Если P = 1, то необходимо посчитать минимальное значение подъёма. Иначе P = 2 и необходимо посчитать максимальное значение подъёма.

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

В единственной строке выведите ответ на задачу.

Ограничения

1 ≤ M ≤ N ≤ 2 ⋅ 10⁹

1 ≤ P ≤ 2

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

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

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

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

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

Обратите внимание, что первый и третий примеры относится к первой подзадаче, а второй и четвёртый — к четвёртой.

В первом примере Пётр мог сначала доставить посылки на 2-й и 3-й этажи, а потом на 1-й. Подъём равен 2 + (3−2) + 1 = 4.

Во втором примере Пётр мог сначала доставить посылки на 1-й и 2-й этажи, а потом на 3-й. Подъём равен 1 + (2−1) + 3 = 5.

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

3
2
1

4

3
2
2

5

7
3
1

12

7
3
2

18

Задача C. Выдача премий ≡

Условие

В компании работает N человек. Зарплата i-о сотрудника составляет a_i бурлей.

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

Но назначение премии и её выплата не одно и тоже. Дело в том, что размер выплачиваемой премии не может превышать половину зарплаты. То есть, если у сотрудника зарплата 9 бурлей, а назначена премия в 100 бурлей, то он получит лишь 4 бурля (выплата не целого числа бурлей не осуществляется).

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

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

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

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

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

Далее следует N строк, в каждой из которых находится по одному целому числу a_i — зарплата i-го работника.

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

В единственной строке выведите ответ на задачу — максимальное количество сотрудников, которые смогут получить премию.

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ a_i ≤ 10⁶

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

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

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

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

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

В первом примере суммарная зарплата двух последних сотрудников равна 5. Этого не хватит, чтобы выдать премию трём другим сотрудникам, так как их премия составит 6 = 3 + 2 + 1.

Во втором примере суммарная зарплата двух последних сотрудников будет равна премии первых двух: 5 = 2 + 2 + 1, так как первый сотрудник не может получать премию больше, чем 5 / 2 = 2.

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

5
6
4
7
3
2

2

5
5
4
7
3
2

3

5 
1
2
1
1
1

4

Задача D. Рыболовная сеть ≡

Условие

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

Сеть представляет N узлов, соединённых между собой M рёбрами. Будем считать, что сеть могла быть сплетена одной цельной верёвкой, если существует непрерывный путь, проходящий через каждое ребро ровно по одному разу. Путь должен начинаться и заканчиваться в узлах.

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

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

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

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

Далее идёт M строк, в каждой из которых записано два целых числа u_i и v_i — номера узлов, между которыми проходит i-е ребро.

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

Обратите внимание, что у сети могут быть петли и кратные рёбра.

Пояснение

Петлёй называется ребро, соединяющее узел с самим собой.

Кратные ребра — два и более рёбер, соединяющих одну и ту же пару узлов.

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

В единственной строке выведите "Yes" или "No" (без кавычек) — могла ли данная сеть быть сплетена ровно из одной цельной верёвки.

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ M ≤ 2 ⋅ 10⁵

1 ≤ u_i, v_i ≤ N

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

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

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

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

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

Первая сеть могла быть сплетена следующим образом:

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

6 9
1 2
1 4
1 5
2 3
2 5
2 6
3 6
4 5
5 6

Yes

4 6
1 2
1 3
1 4
2 3
2 4
3 4

No

2 4
1 1
1 2
1 2
2 2

Yes

4 2
1 2
3 4

No

Задача E. Загадочная последовательность ≡

Условие

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

Долгое время мальчик Петя коллекционировал целые числа. Сейчас в его коллекции уже N чисел. Разумеется, Петя бережно относится к своей коллекции: не разбрасывает по квартире, и, более того, хранит её отсортированной по неубыванию.

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

Неровностью последовательности называется сумма модулей разности почти соседних элементов. Два элемента последовательности являются почти соседними, если их номера отличаются ровно на K. Например, если K = 2, тогда почти соседними элементами являются числа на позициях 1 и 3, 2 и 4, 3 и 5 и т.д.

Петя уже очень хорошо знает математику, поэтому он смог написать формулу для подсчета неровности: ∑N−Ki=1|a_i − a_i+K|. Теперь Петя хочет узнать минимальное значение неровности, которое можно получить для его коллекции после перестановки элементов. Вы должны ему с этим помочь.

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

Пояснение

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

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

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

Чтобы задать вопрос программа-решение должна вывести строку вида "? i j", где i и j (1 ≤ i, j ≤ N) — целые числа, номера чисел в последовательности. В ответ на вопрос программа жюри подаёт на вход программе-решению значение |a_i − a_j| — модуль разности соответствующих элементов последовательности.

Если программа-решение определила ответ на задачу, она должна вывести строку "! ans", где ans — ответ на задачу. После этого программа-решение должна завершиться.

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

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

Ограничения

1 ≤ N ≤ 10⁶

1 ≤ K ≤ 10³

1 ≤ a_i ≤ 10⁹

a₁ ≤ a₂ ≤ ... ≤ a_N−1 ≤ a_N

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

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

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

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

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

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

Обратите внимание, что первый и второй примеры относятся к первой подзадаче, а третий и четвёртый — ко второй.

В первом примере можно расположить первые четыре числа на четных позициях, а остальные числа — на нечетных.

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

В третьем примере исходная последовательность может быть следующей: 1 4 5 7 13. Расположить эти числа так, чтобы неровность была минимальна, можно несколькими способами. Например, 1 7 13 4 5. Тогда разница между почти соседними элементами равна: |1 − 4| + |7 − 5| = 3 + 2 = 5.

В четвёртом примере нет ни одной пары почти соседних элементов.

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

8 2

3

0

1

2

Ok

? 1 4

? 4 4

? 5 6

? 6 8

! 6

10 1

8

991

999

Ok

? 1 9

? 9 10

? 1 10

! 999

5 3

3

1

2

6

Ok

? 1 2

? 2 3

? 3 4

? 4 5

! 5

2 3

999999

999999

Ok

? 1 2

? 2 1

! 0