#113621

ABCD-код

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2014, Задача A ]

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

Вася не помнит код, но у него есть несколько вариантов. Кроме того, Васе почему-то запомнился факт, что квадрат числа, составленного из первых двух цифр кода, в сумме с квадратом числа, состоящего из последних двух цифр кода, имеет при делении на семь остаток один. То есть, если код представляет собой «ABCD», где «A», «B», «C», «D» — некоторые цифры, тогда $AB^2 \ + \ CD^2$ имеет остаток 1 при делении на 7. Например, код 2843, является одним из возможных кодов, поскольку $28^2 \ + \ 43^2 \ = \ 2633 \ = \ 376 \ · \ 7 \ + \ 1$, а 8243 — нет, поскольку \(82^2 \ + \ 43^2 \ = \ 8573 \ = \ 1224 \ · \ 7 \ + \ 5.

У Васи есть несколько вариантов того, каким может быть код. Помогите ему определить, какие из вариантов могут быть кодом от входа в Петин двор.

Входные данные

В первой строке входного файла находится число \)t$ ($1 \le t \le 10 000$) — число вариантов кода, которые помнит Вася. В следующих $t\( строках содержится по четыре цифры — варианты кода.

Выходные данные

В выходной файл выведите \)t$ строк. В $i$-й строке выведите «YES», если $i$-й код может быть кодом для входа в Петин двор, иначе выведите «NO».

Примеры

Входные данные

Выходные данные

YES
NO
YES

#113622

Шахматы

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2014, Задача B ]

Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске $8 \times 8$ ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму. Васина доска состоит из $n$ столбцов, $i$-й из которых содержит $a_i$ клеток. Нижние клетки всех столбцов образуют один горизонтальный ряд, причем длины столбцов упорядочены слева направо по невозрастанию. На рисунке ниже приведен пример доски, в которой три столбца, содержащих 5, 2 и 1 клетку, соответственно.

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

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

Входные данные

В первой строке входного файла задано целое число $n$ — количество столбцов доски ($1 \le n \le 1000$). Следующая строка содержит $n$ чисел $a_1, a_2, \dots , a_n$ — количество клеток в столбцах ($1 \le a_i \le 1000, a_1 \ge a_2 \ge \dots \ge a_n$).

Выходные данные

В первой строке выведите число $k$ — минимальное число ладей, которое можно расставить на доске так, чтобы каждую клетку доски била хотя бы одна ладья. Следующие $k$ строк должны содержать описание позиций ладей, по одной на каждой строке. Позиция ладьи задается двумя числами: номером столбца, в котором стоит ладья, и номером клетки в столбце. Столбцы нумеруются, начиная с 1, слева направо, клетки в столбцах нумеруются снизу вверх, также начиная с 1.

Если подходящих расстановок несколько, можно вывести любую.

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

Для приведенных входных данных возможна и следующая расстановка:

Примеры

Входные данные

3
5 2 1

Выходные данные

2
1 1
2 2

#113623

Завоевание

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2014, Задача C ]

Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из $n$ городов его королевства. Петир выяснил, что в $i$-м городе ищут работу $a_i$ воинов, которых он может завербовать в свою армию.

Исходно в армии Лорда нет ни одного воина. Чтобы воин вошел в армию, Петир может заплатить этому воину. Для вербовки одного воина из $i$-го города, необходимо заплатить ему $c_i$ золотых монет. При этом воины из больших городов ценят свою работу дороже, поэтому если для $i$-го и $j$-го города выполнено $a_i < a_j$, то $c_i \le c_j$.

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

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

Входные данные

В первой строке входного файла находится целое число $n$ ($1 \le n \le 1000$) — количество городов, в которых Лорд Петир намерен набирать себе воинов. В следующих n строках входного файла находится по два целых числа $a_i$ и $c_i$ ($1 \le a_i \le 100, 1 \le c_i \le 10 000$) — количество воинов в $i$-м городе и число монет, которое необходимо заплатить одному воину в этом городе, чтобы он присоединился к армии. Для всех пар $i$ и $j$ выполнено условие, что если $a_i < a_j$, то $c_i \le c_j$.

Выходные данные

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

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

В приведенном примере Лорду необходимо действовать следующим образом. Сначала он платит 2 монеты воину из второго города, и 3 монеты воину из третьего города, чтобы они присоединились к его армии.

Теперь в армии Лорда 2 воина, а в городах осталось 1, 1 и 3 воина, соответственно. Воины из первого и второго городов бесплатно присоединяются к армии Лорда Петира, в его армии становится 4 воина, после чего и оставшиеся 3 воина из третьего города бесплатно присоединяются к его армии.

Примеры

Входные данные

Выходные данные

#113624

Дюны

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2014, Задача D ]

Географ Григорий Георгиевич исследует образование песчаных дюн. Он выбрал очень длинную дюну и разбил его на огромное число участков, которые пронумеровал от $1$ до $10^9$.

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

Порыв ветра номер $i$ имел силу $x_i$ и действовал на участки с $l_i$-го по $r_i$-й. В результате этого порыва высота участка номер $l_i$ увеличилась на $x_i$, высота участка номер $l_i \ + \ 1$ уменьшилась на $x_i$, следующего — снова увеличилась на $x_i$, и так далее до участка номер $r_i$, включительно.

Зная всю информацию о всех $n$ порывах ветра, Григорий Георгиевич хочет узнать установившуюся в итоге высоту некоторых интересующих его $m$ участков. Помогите ему.

Входные данные

В первой строке входного файла содержатся два натуральных числа $n$ и $m$ ($1 \le n, m \le 1000$) — количество порывов ветра и количество участков, итоговая высота которых интересует Григория Георгиевича.

В каждой из следующих n строк содержится описание очередного порыва ветра — три целых числа $l_i, \ r_i, \ x_i (1 \le l_i \le r_i \le 10^9; 1 \le x_i \le 1000$).

В каждой из следующих $m$ строк содержится целое число $q_i$ ($1 \le q_i \le 10^9$) — номер участка, для которого требуется узнать его итоговую высоту. Номера участков приведены в возрастающем порядке.

Выходные данные

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

Примеры

Входные данные

Выходные данные

#113625

Игра

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2014, Задача E ]

На уроке физкультуры первоклассники Петя и Вася играют в увлекательную игру. Перед ребятами в ряд стоит $n$ столбиков разной высоты. У мальчиков есть $m$ колец, которые они по очереди кидают на столбики, причем если на столбике уже есть кольцо, то кидать кольцо на этот столбик нельзя. Петя кидает первым.

Ребята выяснили, что Петя может закинуть кольцо на столбик только, если высота этого столбика не меньше $l_1$ и не больше $r_1$. На слишком высокий или слишком низкий столбик он закинуть кольцо не может. Зато, если столбик имеет подходящую высоту, бросок гарантированно заканчивается успехом. Аналогично, Вася может закинуть кольцо только на столбики с высотой не меньше $l_2$ и не больше $r_2$ и гарантированно закидывает кольцо на любой такой столбик.

Физрук Андрей Сергеевич обещал поставить пятерку тому из ребят, кто по итогам игры закинет больше колец на столбики. Помогите ребятам выяснить, кто из них выиграет при оптимальной игре.

Входные данные

В первой строке входного файла находятся два целых числа $n$ и $m$ — количество столбиков и колец, соответственно ($1 \le m \le n \le 10^5$). Следующие две строки содержат числа $l_1, \ r_1 \ и \ l_2, \ r_2$ — минимальную и максимальную высоту столбиков, на которые могут кидать колечки Петя и Вася, соответственно ($1 \le l_1 \le r_1 \le 10^9 , 1 \le l_2 \le r_2 \le 10^9$ ). В последней строке содержится $n$ чисел, описывающих высоту столбиков, высота каждого столбика является целым положительным числом и не превышает $10^9$.

Выходные данные

В выходной файл выведите «Petya», если выиграет Петя, «Vasya», если выиграет Вася, или «Draw», если при оптимальной игре оба мальчика закинут на столбики равное число колец.

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

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

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

В третьем примере Петя первым ходом закидывает кольцо на один из двух доступных ему столбиков, а Вася вторым ходом закидывает кольцо на второй из этих столбиков. Теперь у Пети нет столбиков, на который он может закинуть кольцо, он кидает третье кольцо, но не попадает. Вася же закидывает последнее кольцо на любой из столбиков высоты 3 или 4.

Примеры

Входные данные

Выходные данные

Petya

Входные данные

Выходные данные

Draw

Входные данные

Выходные данные

Vasya