Задача A. Новогодняя игра ≡

Условие

В Новогоднюю ночь Дед Мороз предложил Тимофею и Насте игру на сообразительность, прежде чем вручить подарки. В этой игре Дед Мороз произнесет два числа — a и b, и Тимофей должен записать все числа от a до b в возрастающем порядке. Затем Настя пронумерует каждую цифру в получившейся строке, чтобы подготовиться к вопросам.

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

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

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

В первой строке входных данных подается два числа - a и b (1 <  = a < b <  = 10⁵).

Во второй строке подается k (1 <  = k <  = 10⁵) - количество вопросов, которые задает Настя.

В следующих строках входных данных дается k запросов, состоящих из двух чисел l и r (1 <  = l < r <  =  длины строки), где l и r — индексы цифр.

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

Для каждого k_i запроса необходимо вывести единственный ответ - сумму цифр на отрезке от l до r.

Решения, работающие при b < 100 будут набирать не более 20 баллов.

Решения, работающие при b < 10³ будут набирать не более 40 баллов.

Решения, работающие при b < 10⁴ будут набирать не более 70 баллов.

Решения, работающие при b <  = 10⁵ будут набирать не более 100 баллов.

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

1 10
3
2 5
5 8
1 10

14
26
46

Задача B. Студсовет играет в настольный теннис ≡

Условие

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

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

Первый подающий обычно определяется жребием. Далее подающие чередуются каждые две подачи. Партия продолжается до достижения одним из игроков 11 очков. В случае равного счёта 10:10 подача переходит к другому игроку (команде) после каждого розыгрыша до тех пор, пока отрыв не составит два очка

По жребию самую первую подачу делает Данил. Гарантируется, что счёт таков, что игра продолжается.

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

Два целых неотрицательных числа d и s (0 <  = d,s <  = 10⁹), разделенных пробелом — счёт игры в текущий момент времени.

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

Строка name — имя игрока, который сейчас будет подавать.

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

0 0

Danil

0 1

Danil

1 1

Saveliy

2 1

Saveliy

3 1

Danil

10 10

Danil

10 11

Saveliy

Задача C. Конфеты ≡

Условие

Денис очень любит конфеты. Однажды его мама принесла домой пакет с n конфетами, и Денис хочет выкрасть k из них. На это у него есть m дней. Каждый день он может красть любое количество конфет (не больше k). Независимо от того, сколько конфет Денис украл, каждый вечер количество конфет в пакете изменяется на w_i (мама либо добавляет либо достает конфеты). Более того мама может заметить украденные конфеты с вероятностью P_i = x_i / n_i, где x_i — это количество украденных в этот день конфет, а n_i это количество конфет утром этого дня.

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

К вечеру m-го дня Денис в сумме должен выкрасть k конфет.

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

В одной строке n, k, m — целые положительные числа, разделенные пробелом: изначальное количество конфет, число конфет, что нужно выкрасть, и количество дней. k,w ≤ n. n,k,m,w < 10⁵.

Во второй строке идут m целых чисел w_i ≤ 10⁴.

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

Первым числом выведите h, количество дней, в которые Денис должен красть конфеты.

Затем h строк, в каждой по 2 числа: номер дня и количество конфет в этот день.

Строки должна быть упорядочена по дням.

Если существует несколько вариантов ответа, выведите тот, сумма дней которого минимальна, если и таких несколько, то выведите тот, где h минимально, а если и таких несколько, то минимизируйте первый день.

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

11 2 3
-1 2 1

1
3 2

Задача D. DOGE ≡

Условие

Возглавив DOGE, Милон Аск решил сократить финансирование дорожных сетей в стране А. В стране А n (1 <  = n <  = 10⁹) городов и n * (n − 1) / 2 дорог, таких, что между каждыми двумя городами есть прямая дорога. Сокращение финансирования, планируемое Аском, приведёт к тому, что k (1 <  = k <  = n * (n − 1) / 2) дорогами пользоваться будет невозможно. Список этих дорог не известен.

В стране Б тут же заявили, что теперь существуют города X и Y страны А, такие что из города X невозможно по дорогам (в том числе и через другие города/не напрямую) попасть в город Y. Известно, что стало на k дорог меньше, но неизвестно какие именно дороги стали недоступны.

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

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

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

Выведите: YES, если города не соединены.

Выведите: NO, если города соединены.

Выведите: unknown, если это неизвестно.

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

2 1

NO

2 0

YES

3 2

unknown

Задача E. Ёлочка вам нравится? ≡

Условие

У Пети есть любящая жена и не сильно любящая теща. Обе они попросили купить каждой по елке к новому году. А Петя, конечно же, забыл купить елку Теще. И вот, у Пети есть елка, то есть дерево, то есть связный граф без циклов. На ветках елки находятся гирлянды разной красоты - вершины графа. Красота всей елки равна сумме красот гирлянд на ней. Петя хочет разрезать елку, то есть удалить одно ребро в графе так, чтобы она разделилась на две елки. Но Петя знает, что теща и жена поссорятся, если получат елки, абсолютная разница красот которых больше чем k. Помогите Пете понять, может ли он разрезать елку так, чтобы никто не обиделся. Выведите Yes, если может, и No } иначе.

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

В первой строке дано три числа N, E и k - количество гирлянд и веток соответственно. 2 ≤ N ≤ 10⁵, 0 ≤ k ≤ 10⁹.

Во второй строке дано N чисел a_i - красота i − й гирлянды.  − 10⁹ ≤ a_i ≤ 10⁹.

В следующих E строках дано 2 числа a₁ и a₂, означающие, что гирлянды a₁ и a₂ соединены веткой.

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

Одной строчкой выведите Yes, если можно разрезать елку, так, чтобы выполнялось условие, и No, в ином случае.

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

3 2 2
1 2 3
1 2
1 3

Yes