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

Биллу повезло: он нашел книгу заклинаний, из которой узнал, что можно увеличить свое состояние в несколько раз. Волшебную фразу можно повторять многократно: после каждого заклинания состояние увеличивается в `K` раз. Но книга предупреждала: если состояние станет больше или равно одного миллиарда, то все деньги "испарятся".

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

В первой строке входного файла содержатся два целых числа, разделенных пробелом – первоначальная сумма у Билла `X` (`1\ ≤\ X\ ≤\ 10^7`) и коэффициент увеличения `K` (`2\ ≤\ K\ ≤\ 1000`).

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

1 10

8

Робот находится в левом верхнем углу прямоугольной площадки, разделенной на клетки. Площадка имеет размеры `N`x`M` клеток. Для управления роботом используются команды движения и команды рисования. Команда движения '<' заставляет робота сдвинуться на клетку слева, '>'  – на клетку справа, '^' – на клетку выше, 'v' (латинская строчная v) – на клетку ниже. Команды, которые могут вывести робота за пределы площадки, игнорируются. Команды рисования '0', '1', …, '9' заставляют робота нарисовать соответствующую цифру в текущей клетке. Если там уже была нарисована цифра, она заменяется на новую.

Напишите программу, моделирующую поведение робота.

В первой строке входного файла содержатся два целых числа, разделенных пробелом – размеры площадки `N` (`1\ ≤\ N\ ≤\ 10`) и `M` (`1\ ≤\ M\ ≤\ 10`). Во второй строке (длиной не более 200 символов) содержится программа для робота, состоящая только из цифр и символов <, >, ^, v.

В выходной файл вывести `N` строк по `M` символов – изображение площадки после выполнение программы. Пустые клетки выводятся символом '.'. Первоначально площадка чиста.

2 3
>1v2<3

.1.
32.

В часовой мастерской есть `K` часов с боем. Все часы начинают бить одновременно в момент, когда минутная стрелка доходит до числа 12, но с разными интервалами между ударами (интервал между ударами `i`-ых часов равен `a_i` секунд). Совпадающие по времени удары воспринимаются как один.

Напишите программу, которая по количеству прозвучавших ударов и длительностям интервалов между ударами определит время суток. В сутках не более 1000 часов (мастерская может находиться не на Земле).

В первой строке входного файла содержатся два целых числа, разделенных пробелом – количество часов `K` (`1\ ≤\ K\ ≤\ 1000`) и количество прозвучавших ударов `M` (`1\ ≤\ M\ <\ 10^6`). Во второй строке `K` целых чисел, разделенных пробелами – длительности интервалов между ударами `i`-ых часов `a_i` (`1\ ≤\ a_i\ ≤\ 1000`, `1\ ≤\ i\ ≤\ K`).

В выходной файл вывести одно целое число – время суток, соответствующее числу ударов.

3 4
1 2 2

3

Чтобы разбить кокос, обезьяны обычно забираются на крышу `N`-этажного дома и бросают кокос вниз. Однажды одна смышленая обезьяна, которой надоело постоянно подниматься на крышу, решила выяснить самый низкий этаж, при бросании с которого кокос разбивается. Обезьяна может подняться на любой этаж с 1-го по `N`-й (крыша считается `(N+1)`-м этажом) и бросить кокос в окно. Если кокос при падении не разбивается, обезьяна может использовать его для экспериментов снова. Всего у обезьяны для опытов приготовлено `K` кокосов. Обезьяна должна выяснить номер искомого этажа, использовав не более `K` кокосов. Также обезьяна хочет найти этаж за минимальное число бросков, так как она может нести только один кокос и для каждого броска ей приходится спускаться вниз на землю за приготовленным для опытов кокосом или за ранее брошенным, но неразбившимся кокосом.

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

В первой строке входного файла содержатся два целых числа, разделенных пробелом – количество этажей в доме `N` (`1\ ≤\ N\ ≤\ 10\ 000`) и число кокосов `K` (`1\ ≤\ K\ ≤\ 100`).

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

10 2

4

Антигравитационный аппарат позволяет двигаться по прямой, перелетая над любыми препятствиями. Но чем выше он летит над землей, тем больше расходует энергии. У аппарата есть только два режима движения, которые нельзя совмещать  – подъем-спуск и горизонтальный полет. Для полета на расстояние `r` на высоте `h` расход энергии составляет `(A*sqrt(h)\ +\ B)*r`. Снижение или увеличение высоты на `d` метров требует расхода `C*|d|` единиц энергии.

Напишите программу, которая рассчитает минимум энергии, требуемый для полета в городских условиях. Точка старта и точка финиша расположены на земле (`h\ =\ 0`) и вне зданий. Можно считать, что аппарат имеет точечные размеры и может летать вплотную к зданиям и к земле.

В первой строке входного файла содержатся пять целых числа, разделенных пробелом – количество зданий `N` (`0\ ≤\ N\ ≤\ 100`), расстояние до точки назначения `X` (`0\ <\ X\ ≤\ 10^6`) и коэффициенты `A`, `B` и `C` (в диапазоне от 0 до 1000). Далее следует `N` строк, содержащих по три положительных целых числа `L_i`, `R_i`, `H_i` (`R_{i-1}\ ≤\ L_i\ <\ R_i\ <\ X`, `0\ <\ H_i\ ≤\ 1000`), разделенных пробелами – описание зданий на линии полета: координаты левой и правой стены и высота.

В первой строке выходного файла вывести одно целое число – минимальное количество затраченной энергии на поездку, округленное до ближайшего целого.

2 100 2 1 10
20 40 50
50 60 25

1583