Задачи 2 лиги личного первенства областной олимпиады школьников по информатике 2003

Напишите программу, которая моделирует калькулятор, т.е. вводит последовательность нажатых клавиш и выводит результаты расчетов. Моделируемый калькулятор умеет работать только с целыми числами, которые по абсолютному значению меньше чем `10^10`. Калькулятор может выполнять только три арифметических действия: сложение, вычитание и умножение. Кроме клавиш +, - и *, на калькуляторе есть клавиша = и клавиши с цифрами от 0 до 9.

При включении на дисплее калькулятора появляется 0.

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

Перед нажатием клавиши с арифметической операцией можно ввести первый операнд с помощью цифровых клавиш. Если первый операнд операции не был введен, то им становится число на дисплее в момент нажатия клавиши с арифметической операцией. Нажатие следующей клавиши с арифметической операцией после ввода второго операнда приводит к выполнению предыдущей арифметической операции (операции, которые были уже выполнены при нажатии клавиши =, не являются предыдущими); результат вычислений появляется на дисплее и становится первым операндом выбранной арифметической операции. Если нажать несколько арифметических клавиш подряд без ввода второго операнда, то используется только последняя нажатая арифметическая операция.

Если при вычислениях получается число, которое по абсолютному значению больше или равно `10^10`, то на дисплее появляется сообщение ERROR. Любые арифметические действия с ERROR в качестве операнда приводят к результату ERROR.

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

Во входном файле содержится одна строка длиной от 1 до 250 символов, содержащая последовательность нажатых клавиш после включения калькулятора. Строка содержит только символы +, -, *, = и цифры от 0 до 9.

В выходной файл вывести результаты вычислений, появляющиеся на экране после нажатия клавиши =. Каждый результат нужно выводить на отдельной строке.

2+2*2=-6==

8
2
-4

В длинном коридоре находится `N` дверей, первоначально закрытых. Первый человек проходит по коридору и открывает каждую вторую дверь. Второй человек проходит и открывает каждую третью дверь, если она была закрыта, или закрывает ее, если она была открыта. Третий человек делает то же самое с каждой четвертой дверью. `K`-й человек – с каждой `(K+1)`-й дверью. Сколько дверей окажется открытыми после того, как по коридору пройдут `M` человек?

Во входном файле содержится две строки. В первой строке содержится целое число `N` – число дверей в коридоре (`2\ ≤\ N\ ≤\ 1000`). Во второй строке содержится целое число `M` – число проходивших людей (`0\ <\ M\ <\ N`).

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

6
4

3

Крестьянин, возвращаясь с ярмарки, увидел на мосту странную картину. Какой-то человек сначала считал деньги в кошельке, затем бросал в реку несколько монеток, бежал на другой конец моста, снова считал деньги в кошельке, и опять бросал несколько монеток и шел на другой конец моста. Наконец, пересчитав свои деньги, он явно обрадовался и отправился в дальнейший путь.

- Что ты делал? Зачем ты бросал деньги в воду? – спросил крестьянин, догнав странного человека.

Видя, что свой секрет скрыть не удастся, человек рассказал, что мост волшебный, что, если бросить с моста ровно 29 копеек, то, как только перейдешь мост, количество рублей в оставшейся сумме денег превращаются в новой сумме в количество копеек, а копейки – в рубли, что, перейдя мост несколько раз, можно получить сумму, намного большую первоначальной.

- Самое важное – вовремя остановиться, – сказал человек и ушёл.

Крестьянин задумался, достал кошелек и пересчитал свои деньги. У него было 46 рублей 47 копеек. "29 копеек – не деньги, дай-ка попробую". После первого прохода у него получилось 18р.46к., после второго прохода – 17р.18к., а после третьего – 89р.16к. "Ух-ты! А еще больше можно получить?" – обрадовался крестьянин. После четвертого прохода у него стало 87р.88к., после пятого – 59р.87к., после шестого – 58р.59к., после седьмого – 30р.58к., после восьмого – 29р.30к., после девятого – 1р.29к., а после десятого осталась 1 копейка.

"Эх, дурачина, надо было после третьего раза остановиться!" – расстроился крестьянин.

Напишите программу, которая по начальной сумме денег у крестьянина определит оптимальное число проходов по мосту для получения наибольшей конечной суммы.

Во входном файле в первой строке содержится целое число `M` – количество копеек, которые нужно бросать с моста (`1\ ≤\ M\ ≤\ 50`). Во второй строке содержатся два целых числа `R` и `K` через пробел – начальная сумма денег у крестьянина, выраженная в рублях и копейках (`0\ ≤\ R\ ≤\ 99`, `0\ ≤\ K\ ≤\ 99`).

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

29
46 47

3

Юный энтомолог изучает уровень интеллекта кузнечика, используя специальный полигон. Прямоугольный полигон был разделен на клетки размером 10x10 см и в каждой клетке был поставлен столбик из кубиков. Столбик может содержать от 0 до 9 кубиков. Все кубики имеют размер стороны 10 см.

Кузнечик прыгает по следующим правилам. Кузнечик может прыгать только в направлениях, параллельных стенам полигона. Перед прыжком он становится точно в центр верхней грани столбика из кубиков и прыгает вертикально вверх на 20 см. Затем он планирует, используя крылья, в выбранном направлении, теряя по 10 см высоты на 10 см горизонтального полета. В любой момент он также может сложить крылья и спикировать вертикально вниз, как показано на рис. 1. Кузнечик не может пробивать кубики, поэтому, чтобы попасть с левого столбика на правый на рис. 2, ему потребуется два прыжка. Кузнечик не может также покинуть полигон.

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

Во входном файле в первой строке содержатся два целых числа `N` и `M` через пробел – размеры полигона в клетках (`1\ <\ N\ ≤\ 100`, `1\ <\ M\ ≤\ 100`). Во второй строке содержатся два целых числа `X_1` и `Y_1` через пробел – координаты начальной клетки (`1\ ≤\ X_1\ ≤\ N`, `1\ ≤\ Y_1\ ≤\ M`). В третьей строке содержатся два целых числа `X_2` и `Y_2` через пробел – координаты конечной клетки (`1\ ≤\ X_2\ ≤\ N`, `1\ ≤\ Y_2\ ≤\ M`). Далее следует `M` строк, содержащих по `N` целых чисел от 0 до 9, разделенных пробелами – высота столбика из кубиков в соответствующей клетке на полигоне. Первое число первой строки соответствует координате `(1,1)`, а последнее число последней строки – координате `(N,M)`.

В выходной файл в первой строке вывести целое число `K` – минимальное количество прыжков, которое потребуется кузнечику, чтобы добраться от начальной клетки до конечной. Если добраться до конечной клетки невозможно, то вывести сообщение "IMPOSSIBLE" без кавычек.

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

7