Дедушка Леонида — мастер по плетению рыболовных сетей.
Для создания таких сетей требуется обладать должным талантом и терпением.
Настоящие мастера плели свои сети очень прочными, используя при этом ровно одну цельную верёвку.
Сеть представляет множество узлов, соединённых между собой рёбрами.
Будем считать, что сеть могла быть сплетена одной цельной верёвкой, если
существует непрерывный путь, проходящий через каждое ребро ровно по одному разу.
Путь должен начинаться и заканчиваться в узлах.
Леонид нашел на чердаке несколько рыболовных сетей своего дедушки.
Ему стало интересно, могли ли быть сплетены эти сети ровно из одной цельной верёвки.
Требуется определить, какие сети могли быть сплетены из одной цельной верёвки, а какие нет.
В качестве решения принимается текстовый файл, содержащий ответы к задаче в требуемом формате
(при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").
Формат входного файла
Рыболовные сети, найденные Леонидом, представлены на следующем рисунке:
Для каждой сети в новой строке выведите "Yes" или "No" (без кавычек) —
могла ли данная сеть быть сплетена ровно из одной верёвки.
На каждый тест должен быть дан ответ (иначе есть риск неверной проверки).
Если вы не знаете ответ на какой-то тест, то следует написать в выходном файле "?" (без кавычек).
Описание системы оценивания
Баллы начисляются пропорционально количеству правильных ответов в выходном файле.
По запросу сообщается количество набранных баллов.
Тесты
Баллы
Способ проверки
1-2
По 6 баллов за тест
Проверка осуществляется сразу после отправки решения
3-6
По 10 баллов за тест
Проверка осуществляется только после окончания олимпиады
7-10
По 12 баллов за тест
Проверка осуществляется только после окончания олимпиады
Примеры тестов
№
Входные данные
Выходные данные
1
Yes
No
Пояснение к примерам
Первая сеть могла быть сплетена следующим образом:
Куст трёхцветника в начале своего роста выглядит, как три ветки, направленные в разные стороны:
В начале очередного цикла цветения каждая ветка пускает два отростка в разные стороны.
При этом, ветка продолжает свой рост.
Отростки являются ветками, из которых в начале следующего цикла также начнут появляться новые отростки.
Каждая ветка даёт отростки ровно один раз.
После первого и второго циклов цветения трёхцветник примет следующий вид:
Юному садоводу стало интересно узнать количество веток у куста трёхцветника после N циклов цветения.
Требуется написать программу, которая считывает количество циклов цветения,
и вычисляет количество веток.
Формат входных данных
Первая строка содержит одно целое число N — количество циклов цветения.
Формат выходных данных
В единственной строке выведите ответ на задачу.
Ограничения
1 ≤ N ≤ 12
Описание системы оценивания
Баллы начисляются пропорционально количеству пройденных тестов.
По запросу сообщается количество набранных баллов.
Почтальон Пётр в течение Q дней собирается доставлять посылки для жителей 108 района.
Для удобства за один день он будет обслуживать только один конкретный дом.
В каждом доме ровно один подъезд и отсутствует лифт.
В i-й день Пётр будет доставлять посылки в дом, где Ni этажей.
Так совпало, что на каждый этаж каждого дома необходимо доставить ровно по одной посылке.
Почтальон хочет сделать работу как можно быстрее, поэтому берёт всегда как можно больше посылок, но не более чем Mi штук — тяжелые они, однако.
Пётр не привык выбирать, какие посылки доставлять в первую очередь, поэтому берёт их случайно.
Взяв посылки, он доставляет их в порядке возрастания этажей.
Например, если почтальон взял посылки для 2, 5 и 10 этажа, то сначала он доставит посылку на 2-й этаж, потом на 5-й, потом на 10-й.
После этого он возвращается в свой грузовик за новой партией.
И так до тех пор, пока не будут доставлены все посылки.
Подъёмом называется суммарное количество этажей, на которое необходимо подняться, доставляя посылки.
Например, если почтальон доставляет посылки на 1 и 3 этажи, а потом на 2, то сначала он поднимется на 1-й этаж, потом поднимется с 1-о этажа на 3-й, потом вернётся в грузовик за посылкой для 2-о этажа и доставит её.
Подъём в данном случае будет равен 1 + (3−1) + 2 = 5.
Разумеется, от порядка доставки зависит величина подъёма.
Для каждого дня Пётр хочет узнать минимальное и максимальное возможное значение подъёма при доставке посылок в этот день.
Разумеется, от порядка доставки зависит величина подъёма.
Для каждого дня Пётр хочет узнать минимальное и максимальное возможное значение подъёма при доставке посылок в этот день.
Требуется определить минимальное и максимальное возможное значение подъёма для каждого дня,
если известны количество этажей в доме и количество посылок, которые почтальон может унести.
В качестве решения принимается как программа, так и текстовый файл, содержащий ответы к задаче
в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").
Формат входного файла
Первая строка содержит целое число Q — количество рабочих дней у почтальона.
Далее следует Q строк, в каждой из которых записано по два целых числа Ni и Mi —
количество этажей в доме и количество посылок, которые почтальон может унести за один раз в i-й рабочий день.
Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты.
Этот файл можно скачать ЗДЕСЬ.
Второй пример соответствует тестам, которые будут оцениваться.
Формат выходного файла
Для каждого дня в отдельной строке выведите ответ на задачу.
Ответ должен состоять из двух целых чисел, записанных через пробел —
сначала минимальное значение подъёма в этот день, потом максимальное.
На каждый тест должен быть дан ответ (иначе есть риск неверной проверки).
Если вы не знаете ответ на какой-то тест, то следует написать в выходном файле "0 0" (без кавычек).
Ограничения
1 ≤ Q ≤ 15
1 ≤ Mi ≤ Ni ≤ 200
Описание системы оценивания
Баллы начисляются пропорционально количеству правильных ответов в выходном файле,
причем половина баллов начинается за минимальное значение подъёма, и половина — за максимальное.
По запросу сообщается количество набранных баллов.
Тесты
Баллы
Способ проверки
1-5
По 6 баллов за тест
Проверка осуществляется сразу после отправки решения
6-10
По 6 баллов за тест
Проверка осуществляется только после окончания олимпиады
11-15
По 8 баллов за тест
Проверка осуществляется только после окончания олимпиады
Пояснение к примерам
В первый день Пётр мог сначала доставить посылки на 2-й и 3-й этажи, а потом на 1-й.
Подъём составил бы 2 + (3−2) + 1 = 4.
Если же Пётр сначала доставлял посылки на 1-й и 2-й этажи, а потом на 3-й, то
подъём был бы равен 1 + (2−1) + 3 = 5.
В компании работает N человек.
Зарплата i-о сотрудника составляет ai бурлей.
Близится новый год, пора решать, кто из сотрудников получит премию.
Если на премию будет назначено k человек, то первый получит k бурлей, второй — k−1 бурлей и т.д.
Порядок получения премий совпадает с порядком сотрудников, в котором они перечислены.
Выплата премий не окажет большего влияния на капитал компании, если сумма всех премий не превышает сумму зарплат сотрудников, оставшихся без премии.
В тоже время, руководство компании хочет, чтобы как можно больше человек получили новогоднюю премию.
Помогите руководству компании определить максимальное количество человек, которым можно выплатить премию, так,
чтобы это не оказало большего влияния на капитал компании.
Требуется написать программу, которая считает количество сотрудников и их зарплаты,
и вычислит максимальное количество сотрудников, которые смогут получить премию.
Формат входных данных
Первая строка содержит одно целое число N — количество работников.
Далее следует N строк, в каждой из которых находится по одному целому числу ai —
зарплата i-го работника.
Формат выходных данных
В единственной строке выведите ответ на задачу —
максимальное количество сотрудников, которые смогут получить премию.
Ограничения
1 ≤ N ≤ 2 ⋅ 105
1 ≤ ai ≤ 106
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
N
1
20
1 ≤ N ≤ 102
2
15
1 ≤ N ≤ 103
1
3
15
1 ≤ N ≤ 104
1-2
4
20
1 ≤ N ≤ 105
1-3
5
30
1 ≤ N ≤ 2 ⋅ 105
1-4
Пояснение к примерам
В первом примере суммарная зарплата двух последних сотрудников равна 5.
Этого не хватит, чтобы выдать премию трём другим сотрудникам, так как их премия составит 6 = 3 + 2 + 1.
Долгое время мальчик Петя коллекционировал целые числа.
Сейчас в его коллекции уже N чисел.
Разумеется, Петя бережно относится к своей коллекции: не разбрасывает по квартире и хранит в некоторой последовательности.
Сегодня Петя решил, что хранить числа просто так не интересно, поэтому он хочет перемешать их и получить новую последовательность.
Неровностью последовательности называется сумма модулей разности почти соседних элементов.
Два элемента последовательности являются почти соседними, если их номера отличаются ровно на 2.
Например, почти соседними элементами будут числа на позициях 1 и 3, 2 и 4, 3 и 5 и т.д.
Петя уже очень хорошо знает математику, поэтому он смог написать формулу для подсчета неровности: ∑N−2i=1|ai − ai+2|.
Теперь Петя хочет узнать минимальное значение неровности, которое можно получить для его коллекции после перестановки элементов.
Вы должны ему с этим помочь.
Требуется написать программу, которая считает количество чисел в коллекции и сами числа,
и вычислит минимальное значение неровности коллекции после перестановки элементов.
Пояснение
Модулем числа называется его абсолютное значение.
Например, модулем числа 2 является 2, а модулем числа −3 является число 3.
Обозначается модуль как |x|.
Формат входных данных
Первая строка содержит одно целое число N — количество чисел в коллекции Пети.
Далее следует N строк, в каждой из которых находится по одному целому числу ai — коллекция.
Формат выходных данных
В единственной строке выведите ответ на задачу —
минимальное значение неровности коллекции после некоторой перестановки элементов.
Ограничения
1 ≤ N ≤ 105
1 ≤ ai ≤ 106
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
N
1
30
1 ≤ N ≤ 3
2
25
1 ≤ N ≤ 10
1
3
35
1 ≤ N ≤ 103
1-2
4
10
1 ≤ N ≤ 105
1-3
Пояснение к примерам
Обратите внимание, что первый и второй примеры относятся к первой подзадаче, а третий — ко второй.
В первом примере можно расположить коллекцию вот так: 3 1 2.
Тогда неровность будет равна |3 − 2| = 1.
Во втором примере нет ни одной пары почти соседних элементов.
