Батарейки для роботов

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

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

 

В одной фирме работает N роботов. Про каждого робота известно Xi - наименьшее количество энергии, необходимое роботу в день, и Ci - дневная прибыль робота, если он будет работать (1 <= i <= N). Однажды в фирму на день задержали поставку энергетических батарей, которые вставляются в роботов. В робота может быть вставлена только одна батарея, вставлять в роботы батареи с энергией меньше Xi запрещено. На складе имеется M частично израсходованных батарей. Про каждую батарею известно количество оставшейся в ней энергии Bi (1 <= i <= M). Вам необходимо по имеющейся информации вычислить S - максимальную прибыль, которую фирма может получить в этот день.

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

В первой строке входного файла записана пара натуральных чисел N, M (1 <= N <= 10000; 1 <= M <= 100000) через пробел. Далее идут N строк с числами Xi и Ci (1 <= Xi <= 10^9; 1 <= Ci <= 200000 для 1 <= i <= N) - описание роботов. Затем идут M строк с числами Bi (0 <= Bi <= 10^9 для 1 <= i <= M) - описание батарей.

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

В выходной файл нужно вывести S.

Пример

Ввод

4 3
1 2
1 3
2 4
3 1
2
3
2

Вывод

9

Реформа

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

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

 

В Берляндии грядет пора реформ. Будет реформировано все, даже календарь. Теперь в календаре будет N (1<=N<=60000) месяцев. Все месяцы делятся на два вида - короткие и длинные (у нас коротких ровно 5 - февраль, апрель, июнь, сентябрь и ноябрь). Коротких месяцев будет M (0<=M<=N). Президент обеспокоен следующей проблемой: он хочет, чтобы короткие и длинные месяцы в году чередовались как можно равномернее. Придворный математик дал следующее определение.
Порядок месяцев равномерный, если для любого K (1<=K<=N) верен факт: количество коротких месяцев в любых K подряд идущих месяцах отличается не более чем на один.
Стоит заметить, что месяцы чередуются циклически, то есть для K=2 допустим набор декабрь, январь.

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

Во входном файле записаны целые N, M через пробел.

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

Выведите последовательность N символов. Символ "0" обозначает короткий месяц, а символ "1" - длинный. Порядок должен соответствовать искомому. Если равномерного порядка для данных N, M не существует, выведите фразу "No solution".

Пример

Ввод

12 5

Вывод

101010110101

Умный робот

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

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

 

Дан лабиринт N x N клеток. Некоторые его клетки непроходимы. Требуется обойти все его проходимые клетки роботом. Робот понимает команды L - передвинуться влево, R - вправо, T - вверх, B - вниз. Если робота просят передвинуться на непроходимую клетку или за пределы лабиринта, он игнорирует команду. Проблема в том, что неизвестно в какой клетке изначально стоит робот.

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

В первой строке входного файла записано целое число N (1<=N<=20). Далее идет N строк по N символов - описание лабиринта сверху вниз слева направо. Символ "." означает проходимую клетку, "x" или "X" - непроходимую.

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

В выходной файл необходимо вывести программу для робота, по которой он обойдет весь лабиринт. Если не существует такой программы, необходимо вывести слово "IMPOSSIBLE". Размер выходного файла не должен превышать 10000 байт.

Пример

Ввод

3
x.x
...
xx.

Вывод

BRRBTLLRT

Задача первая

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

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

 

Пусть дано множество простых чисел S={p1...pk}. Рассмотрим те числа, все простые делители которых принадлежат S. Из этих чисел вам требуется найти N-ое по величине (считается, что единица им не принадлежит).

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

В первой строке входного файла содержится число K (1 <= K <= 1000) и число N (1 <= N <= 1000000). Во второй - последовательность p1...pk.

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

Выходной файл должен содержать искомое число.

Пример

Ввод

3 4
2 3 5

Вывод

5

Пояснение

Гарантируется, что ответы на тесты принадлежат диапазону 0..10^18 и все данные простые числа принадлежат отрезку [2..2^31-1].

Считай слова

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

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

 

Каждую непустую последовательность символов 0 и 1 будем называть бинарным словом. Вам дано равенство двух бинарных слов, например: 1bad1 = acbe. Каждая буква суть переменная, про которую известна ее длина (то есть количество символов, которое эта переменная заменяет). Одинаковыми буквами обозначаются одинаковые переменные. Например, если a, b, c, d, e - переменные c длинами 4, 2, 4, 4, 2, тогда данное равенство имеет 16 решений.
Ваша задача для данного равенства посчитать количество его решений.
Одна переменная может встретиться в слове более одного раза.

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

В первой строке записано число натуральное X (1 <= X <= 5) - количество тестов в файле. Каждый тест состоит из 6 строк:
· Число K (0 <= K <= 26) - количество различных переменных в равенстве (предполагаем, что переменные - маленькие латинские буквы от "a" до K-ой буквы алфавита;
· L1, L2,..., LK - длины переменных;
· Длина левой части равенства;
· Левая часть равенства;
· Длина правой части равенства;
· Правая часть равенства.
Количество цифр плюс сумма длин всех вхождений всех переменных с каждой стороны равенства не превосходит 10000.

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

Выведите X строк. В каждой строке ответ для соответствующего теста.

Пример

Ввод

1
5
4 2 4 4 2
5
1bad1
4
acbe

Вывод

16

Оптимальная упаковка

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

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

 

Продукция фабрики поставляется на склад в виде цилиндров одинакового радиуса и высотой 2^K для некоторого целого неотрицательного K. Число K называется размером цилиндра. На складе находится N цилиндрических коробок с готовой продукцией. Про каждую коробку известен ее размер и стоимость. Директор фабрики считает, что более дешевый товар стоит продавать раньше.
На фабрику приехала машина с Q ящиками, каждый из которых тоже цилиндр с радиусом чуть большим, чем радиус коробки (то есть они ровно входят в контейнеры). Упаковка коробок в контейнеры - плотная, если сумма длин коробок в контейнере равна длине контейнера (то есть он заполнен полностью). Длина каждого контейнера тоже 2^K. Проверьте, возможно ли плотно упаковать все контейнеры продукцией со склада, и если да, то выведите наименьшую суммарную стоимость упакованного товара.

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

В первой строке содержится число N (1 <= N <= 10000) - количество коробок на складе. Далее в N строках описаны единицы товара (они же коробки, при правильном взгляде на вещи) парами целых чисел K (размер коробки, показатель степени длины) и стоимость P (0 <= K <= 1000, 0 <= P <= 10000).
Далее записано число Q - количество типов контейнеров на складе и в Q строках описаны эти типы парами чисел K и P (0 <= K <= 1000), где K - размер контейнера, показатель степени длины и P -- количество контейнеров данного типа. Суммарное количество контейнеров не превосходит 5000.

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

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

Пример

Ввод

5
1 3
1 2
3 5
2 1
1 4
2
1 1
2 1

Вывод

3

Пояснение

Пояснение: первый контейнер заполняется второй коробкой, а второй - четвертой.