Задача A. Марфа Геннадьевна в кустах ≡

Условие

Марфа Геннадьевна считает, что её соседка по даче, Элеонора Агафьевна, слишком любопытна и постоянно подглядывает за Марфой Геннадьевной из окна. Граница участков Марфы Геннадьевны и Элеоноры Агафьевны представляет собой отрезок длиной L см.

Марфа Геннадьевна решила загородить соседке обзор, засадив границу кустами. У Марфы Геннадьевны имеются семена N видов кустов. Известно, что кусты i-го вида вырастают до ширины в a_i см. При этом для нормального развития кустам i-го вида необходимо, чтобы расстояние между краями соседних кустов, а также от края куста до края границы участков было не менее b_i см.

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

Рекомендуется рассмотреть следующие частичные решения

• N = 1;
• N = 2;

Формат входного файла

Входной файл содержит целые числа N L, за которыми следует N пар целых чисел a_i b_i — ширина куста и минимальное расстояние для i-го вида.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 10³

2 ≤ L ≤ 10⁴

1 ≤ a_i, b_i ≤ 10⁴.

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

2 5
3 1
2 1

2

2 7
3 2
2 3

4

1 10
5 3

10

Задача B. Открытый подсчёт ≡

Условие

Юный робототехник Вася построил робота, который способен перемещаться по неограниченному клетчатому полю согласно заложенной в него программе. Робот занимает ровно одну клетку поля. Программа для робота состоит из последовательности команд, разделённых запятой. Каждая команда состоит из латинской буквы и натурального числа. Буква задаёт направление движения (U — на север, D — на юг, L — на запад, R — на восток), а число — количество клеток, на которое робот должен сдвинуться.

Требуется по данной программе определить количество различных клеток (считая начальную), которые посетит робот во время её выполнения. Например, при выполнении программы D3,U4 робот сдвинется на юг на 3 клетки, затем на север на 4. В сумме робот посетит 5 различных клеток (3 из них — по два раза каждую).

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

Формат входного файла

Первая строка входного файла содержит целое число N — количество программ. Последующие N строк содержат по одной программе каждая.

Формат выходного файла

Выходной файл должен содержать N целых чисел — количество различных клеток, посещённых роботом при выполнении каждой программы.

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

2
D100,L10
R1,L1,R1,L2

111
3

Задача C. Султан и мудрецы ≡

Условие

Однажды султан решил проверить знание математики у своих мудрецов.

Для этого он собрал N мудрецов, и потребовал от них назвать N различных натуральных чисел, дающих в сумме указанное число D.

Мудрецы начал выступать по очереди, i-й мудрец называл число a_i. И вот очередь дошла до N−1-го мудреца — Васи.

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

Рекомендуется рассмотреть следующие частичные решения

• N = 3;
• a_i ≤ 1000;

Формат входного файла

Входной файл содержит натуральные числа D N, за которыми следует N − 2 натуральных числа a_i — числа, названные мудрецами до Васи.

Формат выходного файла

Выходной файл должен содержать подходящее для Васи число, либо −1, если такого числа не существует.

Если решений несколько, выведите любое из них.

Ограничения

3 ≤ N ≤ 10⁵

1 ≤ D, a_i ≤ 10⁹, a_i ≠ a_j∀ i ≠ j

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

18 4
2 6

1

26 5
2 5 9

4

13 4
2 5

-1

Задача D. Парное упражение ≡

Условие

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

Учитель построил перед собой класс из n учеников. Однако выяснилось, что ребята встали не по росту, а в некотором произвольном порядке. Не желая тратить время на перепостроение, учитель решил действовать по следующему алгоритму. Он находит в строю пару стоящих рядом учеников, рост которых отличается не более чем на k сантиметров и отправляет их выполнять упражнение. Это действие учитель повторяет до тех пор, пока такие пары существуют. Если таких пар нет, оставшиеся в строю ученики отправляются играть в волейбол.

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

В первом примере имеется 7 учеников. Учитель может вызвать учеников 2 и 3 (их рост 175 и 170, разница не превосходит k = 5), после чего они выйдут из строя, и останутся ученики с номерами 1, 4, 5, 6, 7. Вторую пару составляют ученики 1 и 4, имеющие нулевую разницу в росте (рост обоих равен 180). Ученики с номерами 5 и 7 имеют один и тот же рост 200, но учитель не может их вызвать, поскольку они стоят не рядом друг с другом. Если бы учитель вызвал сначала учеников 1 и 2, то оставшиеся ученики не смогли бы образовать ни одной пары.

Система оценивания

Рекомендуется рассмотреть следующие частные случаи:

• n < 4;
• k = 0;

Формат входного файла

Во начале входного файла записаны целые числа n и k. Далее следует n целых чисел h_i. Число h_i обозначает рост ученика, стоящего в строю i-ым.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 500;

100 ≤ h_i ≤ 300;

0 ≤ k ≤ 200;

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

7 5
180 175 170 180 200 150 200

2
2 3
1 4

3 0
180 170 170 

1
2 3