Почти счастливые числа

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Число называют счастливым, если оно состоит из 2*N цифр (лидирующие нули в числах не допускаются) и сумма первых N цифр равна сумме последних N цифр. Число называется почти счастливым, если из него можно получить счастливое число, заменив одну из его цифр на какую-либо другую. Например, числа 209440, 32, 8944 - почти счастливые, а 20944, 0, 209443, 9844, 1099 - нет. Необходимо найти количество почти счастливых чисел не меньших A и не больших B.

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

Во входном файле записаны целые числа A и B (0 <= A <= B <= 10^9).

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

Выведите ответ на задачу.

Пример

Ввод

1 99

Вывод

81

Вернуть долг

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Профессор Мурзов решил переехать из Бурляндии. Но, прежде чем переезжать, надо раздать долги. Профессор должен P буркристаллов попу Попову, O буркристаллов парикмахеру Паркину и S буркристаллов студенту Студневу. Расчет кристаллами очень простой: маленький кристалл - это один буркристалл, большой кристалл - это два буркристалла. Только одна проблема - нет объективного критерия для определения размера кристалла: большой он или маленький. Поэтому Мурзов попросил всех, кому он должен, оценить каждый из его кристаллов, т.е. сказать, большой это кристалл или маленький. Теперь перед ним стоит сложнейшая задача - распределить свои кристаллы так, чтобы отдать все долги. Возможно, кто-то получит больше, чем ему должны, но это не страшно - профессор не собирается возвращаться, а в других местах кристаллы не имеют никакой стоимости.

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

В первой строке записаны числа P, O и S (1 <= P, O, S <= 2 *10^5). Во второй строке записано число N - количество кристаллов у профессора (1 <= N <= 10^5). Далее идут N строк по 3 буквы без пробелов. Первая буква означает оценку этого кристалла Поповым, вторая - Паркиным, третья - Студневым. Буква 'B' означает, что кристалл оценен как большой, 'S' означает, что кристалл оценен как маленький.

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

Выведите в выходной файл N букв без разделителей - распределение кристаллов. Буква 'P' означает, что кристалл отдается Попову, 'O' - Паркину, 'S' - Студневу. Если решений несколько, выведите любое. Если невозможно распределить кристаллы, погасив долг, то выведите фразу "no solution".

Пример

Ввод

3 2 4
6
BBS
SSB
BBB
BBS
SSS
BBS

Вывод

OSPPSS

Шарики

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Для предстоящего праздника нужно как можно быстрее надуть M шариков. Для этого пригласили N добровольцев и арендовали аппарат для надувания шариков. В любой момент времени аппарат не может надувать более одного шарика. Было решено, что добровольцы будут работать на аппарате по одной минуте. Доброволец под номером i за одну минуту может надуть Ai шариков, после чего он должен отдохнуть не менее Bi минут. Необходимо найти минимальное время, за которое они могут надуть M шариков.

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

В первой строке записаны целые числа M и N (1 <= M <= 100, 1 <= N <= 10). Далее идут N строк по два целых числа Ai и Bi (0 <= Ai <= 10, 1 <= Bi <= 4).

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

В первую строку выведите T - минимальное время, за которое добровольцы могут надуть M шариков (в минутах).

Пример

Ввод

10 3
4 4
3 4
2 3

Вывод

5

Один лишний

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Задана последовательность N (2 <= N <= 10000) целых чисел a1, a2,..., an, где 0 <= ai < p, а p - заданное простое число (2 <= p < 1000).
Известно, что только N-1 чисел из всех ai (i = 1..N) образуют геометрическую прогрессию с натуральным знаменателем k, где 1 <= k < p (числа заданы в том порядке, в котором они идут в прогрессии).
Операция умножения выполняется по модулю p. Только одно число aj (1 <= j <= N) не входит в эту прогрессию.
Необходимо найти индекс j этого числа и знаменатель k. Если решений несколько, то необходимо вывести одно решение с наименьшим значением j.
Если при этом существует несколько различных знаменателей k, 1 <= k < p, то можно выбрать любой из них.
Гарантируется, что исходная последовательность ai (i = 1..N) не образует геометрическую прогрессию ни при каком знаменателе k, 1 <= k < p.

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

В первой строке записаны два целых числа - N и p. Во второй строке - числа a1, a2,...,an. Числа в строках разделены одним или несколькими пробелами.

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

Выведите j и k через пробел.

Пример

Ввод

5 11
1 3 9 7 5

Вывод

4 3

Улитка

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 640 KB.

ввод: input.txt
вывод: output.txt

 

Маленькая улитка живет на координатной прямой в точке A. Ровно в полдень она отправляется в точку B. В точке с какой координатой будет находиться улитка в час дня, если координата точки A равна XA, координата точки B - XB, а улитка за час проползает ровно одно деление координатной прямой?

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

В первой строке входного файла содержатся два целых числа XA, XB (-100<=XA<=100; -100<=XB<=100; XA не равно XB), записанные через пробел.

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

Выведите координату точки, в которой будет находиться улитка в час дня.

Пример

Ввод

Test #1
10 20

Test #2
20 10

Вывод

Test #1
11

Test #2
19

Пересечение отрезков

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 640 KB.

ввод: input.txt
вывод: output.txt

 

Даны два отрезка на координатной прямой. Определите, пересекаются ли они (то есть имеют ли они хотя бы одну общую точку). Первый отрезок имеет координаты [X11,X12], второй - [X21,X22]. Отрезки могут вырождаться в точки.

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

Входной файл содержит N наборов входных данных. В первой строке файла записано натуральное число N (1<=N<=10). Далее в N строках содержатся описания N наборов входных данных. Каждый набор представлен четырьмя целыми числами X11, X12, X21 и X22 (-10^9<=X11,X12,X21,X22<=10^9; X11<=X12; X21<=X22), записанными через пробел.

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

Выведите N строк. В каждой строке выведите слово YES или NO в зависимости от того, пересекаются ли отрезки в соответствующем наборе входных данных.

Пример

Ввод

2
0 1 0 2
0 1 2 3

Вывод

YES
NO