Сотовая связь в деревне

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

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

 

Компания Дубки-телеком решила распространить свое влияние на близлежащие населенные пункты. Исследования показали, что все сколько-нибудь значимые поселения располагаются вдоль прямолинейного участка железной дороги Дубки-Березка.
Для обслуживания абонентов было решено установить K передатчиков. При работе сотовый телефон подключается к ближайшему передатчику. Исследования показали, что недовольство связью прямо пропорционально расстоянию от абонента до ближайшего передатчика. Таким образом, суммарное недовольство населенного пункта это произведение количества жителей в нем на недовольство каждого.
Требуется разработать программу, которая минимизирует максимальное недовольство среди населенных пунктов.

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

Входной файл содержит следующие три строки. Первая строка содержит число N (1 <= N <= 10000) - количество населенных пунктов и число K (1 <= К <= N) количество передатчиков. Вторая строка содержит N чисел P1, P2,..., PN, (0 <= Pi <= 10000), каждое из которых задает расстояние от Дубков до соответствующего населенного пункта. Третья строка содержит N чисел - количества жителей в каждом населенном пункте (натуральные числа, не превосходящие 100).

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

Выведите K чисел -- координаты оптимального расположения передатчиков в неубывающем порядке.

Пример

Ввод

2 1
1 2
1 1

Вывод

1.5

Честный дележ

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

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

 

В конце трудного рабочего дня три честных грабителя решили поделить выручку за день. В их распоряжении находятся N одинаковых алмазов. В соответствии с "кодексом грабителей" младшему грабителю должно достаться на один алмаз меньше, чем среднему по возрасту, а среднему - на один алмаз меньше, чем самому старшему. Возможен ли такой дележ? В случае положительного ответа найдите соответствующую тройку чисел.

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

В первой строке входного файла содержится целое число N (1 <= N <= 100).

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

В случае положительного ответа выведите через пробел тройку неотрицательных целых чисел A, B, C таких, что A+B+C=N и A+1=B, B+1=C. Если такой тройки не существует, выведите единственное число -1.

Пример

Ввод

Test #1
9

Test #2
7

Вывод

Test #1
2 3 4

Test #2
-1

Периметр Забора

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

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

 

Президент Берляндии решил увековечить свое имя в истории. Решено было построить Великий Берляндский Забор. Забор представляет собой последовательность вертикально расположенных досок. Каждая доска имеет ширину 1 метр. Всего в Заборе N досок, высота i-ой доски в Заборе равна Hi метров (i = 1..N). Главный конструктор сделал чертеж забора. Ваша задача найти периметр Великого Берляндского Забора на полученном чертеже.

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

В первой строке входного файла записано натуральное число N - количество досок в Заборе (1 <= N <= 1000). Во второй строке содержится последовательность N натуральных чисел H1, H2,..., HN, записанных через пробел. Hi обозначает высоту i-ой доски в Заборе. Все натуральные числа, не превосходящие 100.

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

Выведите искомый периметр в метрах.

Пример

Ввод

2
1 2

Вывод

8

Чертежник

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

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

 

Чертежник работает следующим образом. Карандаш ставится в точку (0, 0) координатной плоскости. При получении команды "L" чертежник передвигается влево на длину единичного орта, "R" - вправо, "U" - вверх, "D" - вниз. В результате выполнения последовательности команд на координатной плоскости окажется некоторый рисунок. При сравнивании рисунков их нельзя перемещать, вращать и т.д. Например, рисунки, соответствующие последовательностям команд "RULD" и "URDUDL", - равны. Рисунки же, соответствующие последовательностям команд "LU" и "UL", - различны. Вам дан набор последовательностей команд. Найдите, сколько различных рисунков соответствует данному набору.

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

В первой строке записано положительное целое число N (1 <= N <= 1000). Далее в N строках записаны непустые последовательности команд. Каждая последовательность команд задается строкой символов "L", "R", "U" и "D". Суммарная длина всех последовательностей не превосходит 10000.

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

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

Пример

Ввод

4
LU
RULD
UL
URDUDL

Вывод

3

Компакт-диски

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

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

 

Новый альбом популярной группы "Приплющенные" решено записать на двух дисках. В альбоме всего 4 песни. Продолжительность первой песни - A1 секунд, второй - A2 секунд, третьей - A3 секунд, четвертой - A4 секунд. Размер первого диска D1 секунд, а второго - D2 секунд. Промежуток между двумя песнями на диске не должен быть меньше 1 секунды. Никакая песня не должна разрываться, то есть каждая из четырех песен должна быть записана полностью на одном из двух дисках. На каждом диске должна быть записана хотя бы одна песня. Продюсер "Приплющенных" хочет знать, возможно ли записать все четыре песни на два диска таким образом.

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

Входной файл состоит из N (1 <= N <= 20) наборов входных данных. В первой строке входного файла записано натуральное число N, где N - количество наборов входных данных в файле. Далее идет 2N строк, по две строки на каждый набор входных данных. В первой строке каждой пары записана четверка натуральных чисел A1, A2, A3, A4 (1 <= Ai <= 1000, для всех i=1..4). Во второй строке пары записаны два натуральных числа D1, D2 (1 <= D1 <= 1000; 1 <= D2 <= 1000). Числа в строках разделяются пробелами.

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

Для каждого теста выведите ответ в отдельной строке. Выводите YES, если запись возможна и NO в противном случае.

Пример

Ввод

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

Вывод

YES
NO
NO
YES

Компрессия текста

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

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

 

Дана строка, состоящая из букв латинского алфавита. В целях ее компрессии разрешается любые ее подстроки, которые еще не подвергались сжатию, сжимать по следующему правилу. Строка A, состоящая из повторений некоторой строки B, записывается как символ "(", затем количество повторений, затем строка B, а затем символ ")". Например, строку ABABAB можно сжать, записав ее как (3AB). Ваша задача сжать заданную строку наилучшим образом, то есть таким образом, чтобы она стала как можно короче. Подстрокой называется последовательность идущих подряд символов строки. Регистр букв следует различать.

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

Во входном файле записана исходная строка. Длина строки не превосходит 100 символов.

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

Выведите данную строку в максимально сжатом виде. Напомним, что сжимать можно только еще не сжатые подстроки (например, сжатие (2(3AC)A) для строки ACACACAACACACA некорректно). Если решений несколько, то выведите любое из них.

Пример

Ввод

Test #1
AAAAAABABAB

Test #2
ABACABA

Вывод

Test #1
(5A)(3AB)

Test #2
ABACABA

Декомпрессия текста

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

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

 

Дана строка, состоящая из букв латинского алфавита. В целях ее компрессии разрешается любые ее подстроки сжимать по следующему правилу. Строка A, состоящая из повторений некоторой строки B, записывается как символ "(", затем количество повторений, затем строка B, и, наконец, символ ")". Например, строку ababab можно сжать, записав ее как (3ab). Подстрокой называется последовательность идущих подряд символов строки.
В данной задаче рассматривается правило сжатия, отличное от предыдущей задачи тем, что допускается повторное сжатие подстрок строки. Разумеется, можно сжимать лишь части, состоящие только из букв латинского алфавита. Например, строку acacacaacacaca можно сжать, записав ее в виде (2acacaca), и осуществить дальнейшую компрессию: (2(3ac)a).
Ваша задача осуществить обратное преобразование, то есть преобразовать строку из сжатого вида в несжатый.

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

Во входном файле записана строка в сжатом виде. Длина строки не превосходит 1000 символов.

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

Выведите результат декомпрессии строки. Гарантируется, что длина ответа не превосходит 10^5 символов. Заметим, что в результате декомпрессии длина строки может уменьшиться.

Пример

Ввод

(2(3AC)A)

Вывод

ACACACAACACACA