Инопланетяне с планеты Пандора уже много лет исследуют землян. Для этого на Землю внедрено множество агентов-пандорианцев. Так как среднестатический пандорианец примерно в 20 раз меньше среднестатичестического землянина, для перемещения по планете они используют специальных роботов, внешне неотличимых от жителей Земли. Внутри этих роботов с комфортом располагается команда агентов-исследователей.
Сегодня команда, управляющая роботом «Геннадий», получает свой гонорар. Команда состоит из двух пандорианцев, Джейка и Джейка, которые в данный момент исследуют жителей России. Гонорар исследователи получают один на двоих наличными в обыкновенном российском банке.
Джейк и Джейк должны получить сегодня K рублей. Смогут ли они разделить полученные монеты и купюры на двоих так, чтобы гонорар оказался поделен поровну, вне зависимости от того, какими именно монетами и купюрами им решат выдать K рублей в банке?
Напишите программу, которая поможет Джейку и Джейку ответить на этот вопрос.
На вход подается число K — сумма, которую получат Джейк и Джейк ( 1 ≤ K ≤ 100 000 ).
Выведите «YES», если вне зависимости от того, какими именно монетами и купюрами будет выдана нужная сумма, их можно будет поделить поровну, и «NO» — в противном случае. Действие происходит в России, поэтому для выдачи нужной суммы могут быть использованы купюры и монеты следующих номиналов: 1 , 2 , 5 , 10 , 50 , 100 , 500 , 1000 и 5000 рублей.
Тесты к этой задаче состоят из шести групп. За каждую группу баллы начисляются только при прохождении всех тестов группы.
-
Тесты 1–3. Тесты из условия, оцениваемые в ноль баллов.
-
Тесты 4–9. В тестах этой группы
K
< 10
. Эта группа оценивается в 20 баллов,
-
Тесты 10–18. В тестах этой группы
10 ≤
K
< 100
. Эта группа оценивается в 20 баллов.
-
Тесты 19–29. В тестах этой группы
100 ≤
K
< 1000
. Эта группа оценивается в 20 баллов.
-
Тесты 30–42. В тестах этой группы
1000 ≤
K
< 10 000
. Эта группа оценивается в 20 баллов.
-
Тесты 43–51. В тестах этой группы
10 000 ≤
K
≤ 100 000
. Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы
offline,
т. е. после окончания тура.
Тестирование на тестах каждой группы производится вне зависимости от прохождения всех тестов из предыдущих групп.
7
NO
24
YES
10
NO
Кроме Земли, пандорианцы уже много тысячелетий исследуют и другие планеты. Большой интерес для них в прошлом представляла планета Арракис. К сожалению, с началом исследований на Земле финансирование исследований на Арракисе было существенно урезано, и местным агентам-исследователям пришлось искать дополнительные источники дохода.
К счастью, пандорианцы очень хорошо разбираются в финансовых вопросах. Им не составило труда проанализировать политические, экономические и психологические тенденции, а также некоторые другие факторы, не имеющих названий на земных языках и на основе этих данных точно предсказать изменение стоимости воды на Арракисе на ближайший год. Как известно, вода на этой планете является главной ценностью после золота, на которое эту воду можно купить.
Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить \(\frac{10}{4}=2.5\) литра воды, а продать они эту воду смогут за \(2.5 \times 6=15\) золотых слитков. Таким образом, прибыль пандорианцев составила бы \(15-10=5\) золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды!
В первой строке задано целое число 2 ≤ N ≤ 100 000 — количество дней в году на планете Арракис.
Во второй строке заданы N целых положительных чисел a i ( 1 ≤ i ≤ N , 1 ≤ a i ≤ 5000 ), задающих стоимость воды на Арракисе в день i .
Выведите два целых числа: первое число — номер дня, в который стоит купить воду, второе число — номер дня, в который следует воду продать. Дни нумеруются с единицы. Если оптимальных пар дней для покупки/продажи несколько, то выведите любую из них.
Выведите два нуля, если покупка и продажа воды по указанной схеме не принесет пандорианцам прибыли.
6 10 3 5 3 11 9
2 5
4 5 5 5 5
0 0
Инопланетяне с планеты Пандора продолжают изучать жителей Земли. В этот раз они хотят проверить, влияет ли цвет глаз землянина на его зрение. Запланированное исследование состоит из серии экспериментов, для каждого из которых требуется двое землян с глазами одинакового цвета.
В поисках материала для исследования пандорианцы на своей летающей научной базе прибыли на обыкновенный курортный пляж, до отказа забитый греющимися на солнце туристами. Туристы занимают все доступное место на пляже, образуя, таким образом, прямоугольник размером N × M человек. По пляжу они не перемещаются. То есть, каждый турист однозначно задается своими координатами в этом прямоугольнике: номером ряда, в котором он лежит, и номером в этом ряду.
Научная база пандорианцев оборудована двумя специальными антигравитационными лучами, предназначенными для подъема грузов на базу и для их спуска на поверхность близлежащей планеты. Чтобы база не потеряла равновесия, оба луча следует использовать одновременно. Таким образом, пандорианцы могут либо поднять двух произвольных туристов с пляжа на базу, либо опустить двух туристов обратно на пляж. Исследование должно проходить следующим образом. Оператор антигравитационного луча выбирает на пляже двоих туристов и поднимает их на базу. После этого специальная аппаратура определяет цвет глаз каждого из них. Если полученные цвета совпадают, ученые уводят эту пару туристов для проведения очередного эксперимента, и на пляж они больше не возвращаются. Если же они не совпадают, оператор опускает этих туристов обратно на их места на пляже, после чего процесс повторяется.
Обычно такие исследования не вызывали никаких трудностей, но в этот раз ученые заявили оператору, что после завершения исследования на пляже не должно остаться ни одного землянина. Помогите оператору выбирать туристов в таком порядке, чтобы это требование оказалось выполненным. Гарантируется, что это возможно, то есть туристов можно разбить на пары так, чтобы цвет глаз в каждой паре совпадал.
Это интерактивная задача. В процессе тестирования программа-решение будет взаимодействовать с использованием стандартных потоков ввода/вывода с программой-интерактором, сообщающей в ответ на координаты двух очередных выбранных туристов цвета их глаз.
В первой строке заданы два числа: N и M — размеры прямоугольника, который туристы образуют своими телами, где N — это количество рядов, а M — количество человек в одном ряду пляжа. Гарантируется, что туристов на пляже четное число.
Затем программа-решение начинает взаимодействие с программой-интерактором в соответствии со следующим протоколом:
-
Программа-решение выводит в стандартный поток вывода одну строчку, описывающую, каких туристов оператор поднимает с пляжа в этот раз. Строчка должна содержать четыре целых числа
x
1
,
y
1
,
x
2
,
y
2
, где
x
1
— номер ряда, в котором лежит первый турист,
y
1
— его номер в этом ряду, а
x
2
и
y
2
— координаты второго туриста, заданные аналогично. Ряды нумеруются сверху вниз, начиная с
1
, туристы в них — слева направо, начиная с
1
.
Вывод должен завершаться переводом строки и сбросом буфера потока вывода.
Для последнего используйте
- flush(output) в паскале или Delphi;
- fflush(stdout) или cout.flush() в С/C++;
- sys.stdout.flush() в Python;
- Console.out.flush() в Visual Basic.
- После этого программа должна считать из стандартного потока ввода ответ программы-интерактора. Ответ состоит из двух натуральных чисел, не превышающих 200 000 — цвета глаз первого и второго туриста соответственно. Отправка туристов обратно на пляж или на исследование в соответствии с этими данными происходит автоматически. Если их забирают ученые, больше эти земляне на пляж не возвращаются. Их места на пляже остаются пустыми до конца исследования.
- Программа-решение должна завершить работу, когда на пляже не останется ни одного туриста. Гарантируется, что организовать выбор туристов так, чтобы это условие оказалось выполненным, всегда возможно. Количество запросов не должно превышать 262 144.
Тесты к этой задаче состоят из пяти групп.
-
Тест 1. Тест из условия, оценивается в ноль баллов.
-
Тесты 2–7. В тестах этой группы глаза у всех туристов одного цвета,
1 ≤
N
,
M
≤ 50
. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
-
Тесты 8–13. В тестах этой группы
1 ≤
N
,
M
≤ 50
. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
-
Тесты 14-17. В тестах этой группы
1 ≤
N
,
M
≤ 200
. Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы
offline,
т. е. после окончания тура. Тесты в этой группе оцениваются
независимо.
-
Тесты 18-21. В тестах этой группы
1 ≤
N
,
M
≤ 500
. Эта группа оценивается в 20 баллов. Решение будет тестироваться на тестах этой группы
offline,
т. е. после окончания тура. Тесты в этой группе оцениваются
независимо.
Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
Правильный пример на картинке.
После своего первого контакта с землянами обитатели планеты Пандора решили всё-таки перенять часть земных технологий. В частности, они предприняли попытку приспособить к особенностям своей планеты систему железнодорожного сообщения.
Построенная пандорианцами железная дорога представляет собой прямой отрезок, проходящий в непосредственной близости от N красивейших водопадов. Паровозик, который планируется запустить по этой дороге, будет без остановок проезжать весь маршрут, преодолевая участки между водопадами за строго определённое время.
Так как жители Пандоры очень трепетно относятся к красотам своей природы, они не хотят упускать ни малейшей возможности полюбоваться водопадами, искрящимися в дневном свете. Грамотно составлять расписания пандорианцы ещё не научились, и теперь они обратились за помощью к вам, участникам олимпиады по программированию.
Помогите обитателям Пандоры определить, в какое время дня паровозик должен проехать рядом с первым водопадом, чтобы пассажиры смогли увидеть все водопады на пути в дневное время, при этом не обязательно в один и тот же день. Водопад виден лишь в момент проезда паровозика мимо него, но, как известно, пандорианские водопады настолько впечатляющие, что и за мгновение можно сполна насладиться любым из них.
В первой строке через пробел вводятся два натуральных числа: количество часов в одних сутках ( H ) и минут в одном часу ( M ) на Пандоре ( 1 ≤ H , M ≤ 500 ).
Следующая строка содержит четыре целых числа, описывающих время начала ( H s , M s ) и конца ( H f , M f ) светового дня ( 0 ≤ H s , H f < H ; 0 ≤ M s , M f < M ). При этом либо H s < H f , либо H s = H f и M s < M f (гарантируется, что день начинается раньше, чем заканчивается). Если паровозик проезжает мимо водопада ровно в H s часов M s минут или ровно в H f часов M f минут, то считается, что он проехал мимо водопада днём.
Третья строка содержит одно натуральное число N — количество водопадов, рядом с которыми проезжает паровозик ( 1 ≤ N ≤ 100 000 ).
В следующих N - 1 строках вводятся по 2 целых числа H i и M i , описывающих продолжительность временных интервалов для проезда между соседними водопадами: H 1 , M 1 — время в пути между первым и вторым водопадами, H 2 , M 2 — между вторым и третьим и так далее. Гарантируется, что время, затрачиваемое на дорогу между любыми двумя соседними водопадами, строго положительно, не превосходит одних пандорианских суток и записано корректно: 0 ≤ H i ≤ H , 0 ≤ M i < M .
Если составить подходящее расписание невозможно, то в качестве ответа выведите одно слово « Impossible » (без кавычек). Иначе выведите два числа H 0 и M 0 , разделённые пробелом, описывающие любое подходящее время проезда паровозика рядом с первым водопадом.
Тесты к этой задаче состоят из четырех групп.
-
Тесты 1–2. Тесты из условия, оцениваемые в ноль баллов.
-
Тесты 3–17. В тестах этой группы
H
= 24
,
M
= 60
и
N
≤ 1000
. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
-
Тесты 18–38. В тестах этой группы
H
≤ 80
,
M
≤ 100
,
N
≤ 100000
. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо.
Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
24 60 8 0 22 0 6 6 0 21 0 19 0 12 0 10 0
12 0
24 60 8 17 20 10 2 11 59
Impossible
Как известно, знаменитые египетские пирамиды были построены инопланетянами. Именно они послужили толчком к развитию цивилизации на Земле. Но мало кто знает, что этими инопланетянами был пандорианцы. Теперь они хотят повторить свой успех на планете Макемаке.
Для постройки пирамид на Макемаке были завезены и расставлены в ряд N каменных блоков различных типов. Всего существует 9 типов блоков. Тип блока определяется его размером: самые большие блоки имеют тип 9 , а самые маленькие — 1 . Правильная пирамида должна состоять из поставленных друг на друга блоков, причем сверху обязательно должен быть блок типа 1 , а каждый блок должен стоять на блоке следующего по величине типа.
Конечно, пирамиды строят не сами пандорианцы, а местное население Макемаке. Пандорианцы лишь руководят строительным процессом, указывая, какой блок нужно двигать. Особенности анатомии макемакеанцев позволяют им поднять один блок и поставить его на первый встреченный справа блок или стопку блоков. Как только очередная пирамида оказывается достроенной (то есть на ней сверху оказывается блок типа 1 ), она вывозится из ряда блоков и устанавливается на специально подготовленную для нее площадку.
Разработайте стратегию постройки пирамид, при которой неиспользованных блоков останется как можно меньше.
В первой строке задано целое число N — количество завезенных блоков ( 1 ≤ N ≤ 100 000 ).
Во второй строке даны N целых чисел от 1 до 9 — типы блоков в том порядке, в котором они стоят в ряду, перечисленные слева направо.
Выведите минимально возможное число неиспользованных блоков.
Во втором примере можно построить только две пирамиды высотой 1.
В третьем примере можно из стоящих в середине блоков 1 2 построить пирамиду высотой 2, а из оставшихся блоков — пирамиду высотой 5.
Тесты к этой задаче состоят из трёх групп.
-
Тесты 1–3. Тесты из условия, оцениваются в ноль баллов.
-
Тесты 4–18. В тестах этой группы
1 ≤
N
≤ 2000
. Тесты в этой группе оцениваются
независимо.
Каждый успешно пройденный тест оценивается в 4 балла.
-
Тесты 19–28. В тестах этой группы
1 ≤
N
≤ 100 000
. Решение будет тестироваться на тестах этой группы
offline,
т. е. после окончания тура. Тесты в этой группе оцениваются
независимо.
Каждый успешно пройденный тест оценивается в 4 балла.
3 3 1 2
1
4 2 1 3 1
2
7 1 2 3 1 2 4 5
0