Mr. Битл II (Mr. Битл наносит ответный удар)

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

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

 

Сад имеет форму прямоугольной таблицы NxM клеток. В левой верхней клетке (1,1) живет жук по имени Mr. Битл. Он решил навестить свою кузину, которая живет в правой нижней клетке (N,M). Жук умеет передвигаться по полю только вправо и вниз. На каждой клетке поля растет от 0 до 9 (включительно) цветов, кроме того, некоторые клетки "добрые" садоводы обработали ядом, смертельным для жуков. На ядовитых клетках цветов быть не может. Требуется узнать, какое наибольшее количество цветов Mr. Битл сможет набрать по пути к кузине. В клетках (1,1) и (N,M) как цветов, так и яда нет.

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

В первой строке записаны два числа N и M (1<=N<=80, 1<=M<=80, N+M>2) - количества строк и столбцов таблицы соответственно. Далее в N строках записано по M символов, описывающих сад. Если в строке номер P (из этих N) в позиции Q стоит цифра, то в соответствующей клетке поля растет такое количество цветов. Если в этой клетке стоит символ "*", значит в клетке яд.

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

Если безопасный путь существует, то выведите в первой строке неотрицательное число - наибольшее количество цветов, собранных по пути. Если безопасного пути к кузине не существует, выведите фразу "SEE YOU LATER". Не забывайте, что Mr. Битл ходит только вправо или вниз.

Пример

Ввод

3 5
0044*
300*7
00100

Вывод

5

Короткая запись

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

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

 

Преподаватель Оптимизаторов А.С. не любит длинных чисел чисел. Для этого он записывает числа в виде суммы нескольких (возможно одного) слагаемых. Каждое слагаемое имеет вид либо "N", либо "N^2", либо "N^3". Ваша задача найти длину кратчайшей записи числа M. Так как Оптимизаторов А.С. не любит больших чисел, он хочет, что бы все N (в слагаемых) были меньше 10.

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

Во входном файле записано целое число M (1<=M<=15000).

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

Выведите длину кратчайшей записи.

Пример

Ввод

Тест 1
10

Тест 2
1000

Вывод

Тест 1
3

Тест 2
13

О компьютерах

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

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

 

В одном университете жили-были веселые студенты и злобные лаборанты. Веселые студенты любили играть в Quake по сети. Чтобы помешать студентам играть в Quake, злобные лаборанты отсоединили все компьютеры от сети, поставили на длинный стол в ряд и прибили их к столу девятидюймовыми гвоздями. Но веселые студенты не сдались. Они решили соединить компьютеры проводами (коаксиальным кабелем) так, чтобы каждый компьютер был соединен хотя бы с одним соседним. Один метр провода стоит 1 бурль. Студенты измерили расстояния между соседними компьютерами в метрах и поместили их в файл input.txt. Все расстояния оказались целочисленными. Требуется написать программу, которая по данным расстояниям между компьютерами определяет минимальную сумму длин проводов, необходимых для требуемого соединения компьютеров.

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

В первой строке входного файла содержится число компьютеров N (2<=N<=25000). В последующих строках файла содержатся N-1 целых положительных чисел - расстояния между соседними компьютерами в метрах, по одному числу в каждой строке. То есть в строке номер K содержится растояние между (K-1)-ым и K-ым компьютером. Расстояние между первым и последним компьютером не превосходит 10^6.

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

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

Пример

Ввод

6
2
2
3
2
2

Вывод

7

Уравнение

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

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

 

Даны два целых числа A, B. Ваша задача найти количество корней уравнения Ax = B.

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

Во входном файле содержатся целые числа A, B (-1000 <= A,B <= 1000), записанные через пробел.

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

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

Пример

Ввод

1 1

Вывод

1

Мелодия

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

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

 

Цифровая клавиатура телефона "Berlphone i750" является прямоугольником размером N х M (N строк по M кнопок). Кнопки пронумерованы слева направо, сверху вниз (возможно, некоторые кнопки будут иметь номера больше 9).
В Интернете мелодии для телефонов этой серии предлагаются в виде строк. Каждая строка - последовательность символов, каждый из которых является командой. Символы "L", "R", "U", "D" обозначают сдвиг на одну клавишу влево, вправо, вверх, вниз соответственно. Символ "P" обозначает нажатие текущей клавиши. Других символов в строке нет. Если текущая клавиша находится на краю клавиатуры, а в соответствии с программой надо переместиться за край, то перемещение происходит по циклу. Например, если текущая клавиша "6", то команда "D" сделает текущей клавишу "3". Выполнение команд начинается с клавиши "1".
Ваша задача по данной строке команд вывести номера нажимаемых клавиш в порядке их нажатия.

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

В первой строке содержится пара натуральных чисел N, M (1 <= N,M <= 10) - размеры клавиатуры.
Во второй строке содержится последовательность символов длиной не более 100 символов - данная строка команд.

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

Выведите номера нажимаемых клавиш. Каждый номер выводите на отдельной строке.

Пример

Ввод

2 3
RPRP

Вывод

2
3

Правильные числа

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

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

 

Число называется правильным, если оно является квадратом целого числа, и у него первая и последняя цифры совпадают. Например, числа 0, 1, 4, 9, 121, 484 и т.д. - правильные числа. Найдите количество правильных чисел в отрезке [A, B].

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

В первой строке файла записаны целые числа A и B (0 <= A,B <= 10^16) через пробел.

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

Выведите количество правильных чисел в отрезке [A, B].

Пример

Ввод

0 500

Вывод

6

Бильярд

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

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

 

Стол для игры в берляндский бильярд представляет из себя прямоугольник размером N х M. Введем систему координат так, что начало координат совпадает с левым нижним углом стола, оси параллельны сторонам, а правый верхний угол имеет координаты (N, M). В точке (X, Y) находится шар (для данной модели размерами шара пренебрегаем, то есть считаем его материальной точкой). Известно, что (X, Y) не лежит на границе стола. Ваша задача указать точку (X0, Y0) на границе стола такую, что если игрок ударит в ее направлении, то забьет шар точно в угол, но перед этим шар четырежды отразится от всех сторон стола (от каждой по разу, в любом порядке). Шар отражается всегда таким образом, что угол падения равен углу отражения. При попадании точно в угол шар падает в лузу и прекращает движение.

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

Во входном файле в первой строке записана пара натуральных чисел N, M (2 <= N,M <= 1000). Во второй строке записана пара натуральных чисел (X, Y) (1 <= X <= N-1; 1 <= Y <= M-1).

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

В первой строке выведите слово "YES" если решение существует или "NO" в противном случае. Если решение существует, то во второй строке выведите пару чисел (X0, Y0) через пробел с точностью 6 знаков после запятой. Если решений несколько, выведите любое из них.

Пример

Ввод

5 3
3 1

Вывод

YES
5.000000 2.333333

Сумматор

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

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

 

Мальчики Петя и Вася играют в игру "Сумматор". У Пети имеется N (1 _ N _ 200) карточек с числами от 1 до 10000. У Васи есть неограниченное количество карточек со знаками '+' и '-'. Мальчики поочередно кладут карточки в линию, начиная с Пети. Когда у Пети заканчиваются карточки, считают результат полученного выражения. Если результат оказывается равным 0, то победил Вася. В противном случае победил Петя.
Вам необходимо составить программу, которая играет за Петю наилучшим образом, т.е. выигрывает всегда, когда это возможно.

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

Во входном файле в первой строке находится число N. Во второй строке записаны N чисел - числа, записанные на Петиных карточках. В третьей строке записано число K (1 <= K <= 1000) - количество предложенных вариантов игры Васи. Далее идет K строк по N-1 символу '+' или '-' - ходы Васи.

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

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

Пример

Ввод

3
1 2 3
4
++
+-
-+
--

Вывод

2 3 1
2 3 1
2 1 3
2 1 3

Пояснение

Предполагается, что когда Петя делает очередной ход, он не знает, как дальше будет играть Вася. Поэтому, если в двух вариантах игры первые P ходов Васи совпадают, то первые P+1 хода Пети тоже должны совпадать.

Управление памятью

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

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

 

Проблема выделения и распределения памяти ЭВМ - одна из центральных проблем современной кибернетики. Данная модель памяти ЭВМ состоит из N ячеек, пронумерованных числами от 1 до N. В нашей модели программы могут запрашивать пустые ячейки памяти для работы и могут освобождать их. Команда <ID>:=GET_EMPTY запрашивает у операционной системы номер пустой ячейки для того, что бы поместить в нее данные (найденная ячейка становится занятой). Номер пустой ячейки помещается в <ID>, <ID> - последовательность заглавных латинских букв и цифр, длинной не более 4 символов. Команда CLEAR(<ID>) освобождает ячейку с номером, записанным в <ID>. Вам дана последовательность описанных выше инструкций. Ваша задача - для каждой инструкции <ID>:=GET_EMPTY выдать значение <ID>. Гарантируется, что записанная последовательность инструкций может быть выполнена для данного размера памяти, а также правильность программы (не вызывается CLEAR на незанятую ячейку).

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

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

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

Для каждой команды <ID>:=GET_EMPTY выведите в выходной файл номер найденной пустой ячейки. Если таких ячеек несколько - выдайте любую.

Пример

Ввод

3 7
A:=GET_EMPTY
B:=GET_EMPTY
C:=GET_EMPTY
CLEAR(C)
C:=GET_EMPTY
CLEAR(B)
B:=GET_EMPTY

Вывод

1
2
3
3
2

Снова скобки

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

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

 

Имеется правильное арифметическое выражение, содержащее скобки и операторы +, -, *, /, и переменные. Длина выражения не превосходит 250 символов. Каждая переменная - последовательность больших или малых латинских букв. Ваша задача удалить все лишние скобки.
Пара скобок называется лишней, если их удаление не меняет значение выражение для любых допустимых значений переменных.
Например, "a+(b/c)" может быть уменьшенно до "a+b/c", но "a-(b-c)" не может быть заменено на "a-b+c".

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

В первой строке входного файла записано количество выражений (до 10000 включительно). Далее записаны сами выражения по одному в строке. Гарантируется, что в выражении пробелы не встречаются.

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

Для каждого выражения выведите его без лишних скобок.

Пример

Ввод

Пример #1
8
(a+(b*c))
((a+b)*c)
(a*(b*c))
(a*(b/c)*d)
((a/(b/c))/d)
((x))
(a+b)-(c-d)-(e/f)
(a+b)+(c-d)-(e+f)

Пример #2
1
(m/(p*w)*(((w-p))/b*l*(g*(((v-(f)+l))))))*c+((j/(d)/w))/((((q)-r*e)))+(((n*s)+m)*(v-k))*((y))*h-(v-q)-(f)-f/(k*(g-((q)/j+a)*a)-g)-s-(e)*e/((o)-y/c)-o+h-((l)-((((((((((r-(((i))+((z)+l-r)))))))))))))

Вывод

Пример #1
a+b*c
(a+b)*c
a*b*c
a*b/c*d
a/(b/c)/d
x
a+b-(c-d)-e/f
a+b+c-d-(e+f)

Пример #2
m/(p*w)*(w-p)/b*l*g*(v-f+l)*c+j/d/w/(q-r*e)+(n*s+m)*(v-k)*y*h-(v-q)-f-f/(k*(g-(q/j+a)*a)-g)-s-e*e/(o-y/c)-o+h-(l-(r-(i+z+l-r)))

Домашнее чтение

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

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

 

Школьнику Васе на уроке литературы задали на дом прочесть N страниц учебника. Он заметил, что за час успевает прочесть K страниц текста. Ваша задача узнать, сколько всего часов (как полных, так и не полных) школьник будет выполнять домашнее задание по литературе.

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

Во входном файле содержатся целые числа N, K (1 <= N,K <= 1000), записанные через пробел.

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

Выведите в выходной файл количество часов, необходимых для выполнения домашнего задания.

Пример

Ввод

10 3

Вывод

4

Числа I

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

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

 

На доске была записана последовательность натуральных чисел A1, A2,..., AN. Некто выписал в тетрадь другую последовательность B1 = A1, B2 = A1+A2,..., BN = A1+A2 +... +AN, а затем стер числа A1, A2,..., AN с доски и записал вместо них числа B1, B2,..., BN в произвольном порядке. Ваша задача найти первоначальную последовательность A1, A2,..., AN.

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

В первой строке записано натуральное число N (1 <= N <= 1000). Во второй строке записаны все члены последовательности B1, B2,..., BN в произвольном порядке через пробел (1 <= Bi <= 10^9 для всех 1 <= i <= N).

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

Выведите N чисел A1, A2,..., AN через пробел.

Пример

Ввод

3
3 6 1

Вывод

1 2 3

Сбор яблок

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

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

 

Петя и Катя хотят собрать яблоки с яблони в саду. Для этого Петя залез на яблоню и заметил, что если он начнет трясти яблоню, то первое яблоко упадет через A1 секунд после начала тряски, второе через A2 секунд после начала и т.д. вплоть до N-го яблока, которое упадет через AN секунд. В момент начала тряски яблони Катя стоит в точке с координатами (X, Y). Она поняла, что первое яблоко упадет в точку с координатами (X1, Y1), второе в точку с координатами (X2, Y2) и т.д. вплоть до яблока N, которое упадет в точку с координатами (XN, YN). Известно, что Катя бегает со скоростью 10 м/с. Если Катя в момент падения яблока не находится прямо в точке падения, то поймать его она не может и яблоко безвозвратно разбивается. Ваша задача узнать, какое наибольшее количество яблок M могут собрать Петя с Катей и номера этих яблок. Система координат введена на плоскости поверхности земли таким образом, что длина каждого орта равна 1 м.

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

В первой строке входного файла записаны целые числа N, X, Y (1 <= N <= 1000; -10000 <= X,Y <= 10000) через пробел. Далее в N строках содержится информация о яблоках. Каждая (K + 1)-я строка содержит три целых числа XK, YK, AK (-10000 <= XK,YK <= 10000; 1 <= AK <= 100000, K=1, 2,..., N), записанные через пробел.

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

В первой строке выведите целое число M - наибольшее количество яблок, которые могут собрать Петя с Катей. Во второй строке выведите номера этих яблок через пробел. Номера выводите в порядке возрастания.

Пример

Ввод

4 -10 0
0 0 1
10 10 2
10 0 3
10 -10 4

Вывод

3
1 3 4