суббота, 15 декабря 2012 г.

Задачи муниципального этапа олимпиады. Брянская область.


Благодарю свою коллегу Оксану Спасенникову, за присланные задачи!
Москва-сортировочная
Имя входного файла:
a.in
Имя выходного файла:
a.out
Максимальное время работы на одном тесте:
2 секунды
Максимальный объем используемой памяти:
64 мегабайта
 Тесты у меня

Ежедневно диспетчеру железнодорожной станции "Москва-Сортировочная" приходится переставлять вагоны во многих поездах, чтобы они шли в заданном порядке. Для этого диспетчер может расцепить пришедший на станцию состав в произвольных местах и переставить образовавшиеся сцепки из одного или нескольких вагонов в произвольном порядке. Порядок вагонов в одной сцепке менять нельзя, также нельзя развернуть всю сцепку так, чтобы последний вагон в сцепке оказался первым в ней.
Диспетчер просит вашей помощи в определении того, какое минимальное число соединений между вагонами необходимо расцепить, чтобы переставить вагоны в составе в требуемом порядке.
Формат входных данных
В первой строке входного файла содержится целое число N, (1£N£100). Во второй строке содержится перестановка натуральных чисел от 1 до N (то есть все натуральные числа от 1 до N в некотором порядке). Числа разделяются одним пробелом. Эта перестановка задает номера вагонов в приходящем на станцию составе. Требуется, чтобы в уходящем со станции составе вагоны шли в порядке их номеров.
Формат выходных данных
Программа должна записать в выходной файл единственное целое число, равное минимальному количеству соединений между вагонами, которое нужно расцепить в данном составе, чтобы их можно было переставить по порядку.
Примеры
a.in
a.out
4
3 1 2 4
2
5
5 4 3 2 1
4
2
1 2
0


Числа

Время на тест: 2 cекунды
Ограничения на память: 1 Mb.
Ввод-вывод осуществлять с клавиатуры

Во время урока алгебры Лина написала следующую таблицу на доске:
a
b
a2b
ab2
12
2
288
48
-1
-1
-1
-1
9
-3
-243
81




Лина выбрала целые числа a и b, 0<|a|<1000, 0<|b|<1000, a≥b, написала их в первый и второй столбцы, потом вычислила значение ab2, написала его в третий столбец и, наконец, вычислила ab2 и написала его в четвертый столбец. Вы можете считать, что Лина не сделала ошибок в вычислениях.
Петя стер некоторые из чисел в таблице и написал вместо них ноль.
a
b
a2b
ab2
12
0
288
0
-1
-1
-1
-1
0
0
0
81




 Ваша задача – написать программу, которая по строке из (модифицированной Петром) таблицы найдет начальные значения a, b, a2b и ab2. Если возможно более одного ответа, то нужно вывести ответ с минимальным значением a. Если таких ответов тоже несколько, то нужно выбрать из них ответ с минимальным значением b. И так далее.
Примеры
Ввод                           Вывод
12 0 288 0                   12 2 288 48
Ввод                           Вывод
0 0 0 81                      1 -9 -9 81


Загулявшие гости
Время на один тест – 1 сек
Ограничения на память: 1 Mb.

N гостей (1 £ N £ 30) засиделись на даче и боятся опоздать на последнюю электричку. У хозяина дачи, который остается на ночь, есть автомобиль, но в него могут сесть одновременно не более 4 человек, не считая шофера. Скорость движения автомобиля по лесной дороге – V км/час, скорость движения пешехода – U км/час, расстояние от дачи до железнодорожной станции – Z км, затратами времени на посадку-высадку пассажиров и разворот автомобиля можно пренебречь. За какое минимальное время все гости доберутся до станции?
Входные данные: текстовый файл GUESTS.IN содержит единственную строку со значениями величин N, V, U и Z, разделенными одним или несколькими пробелами. Все числа, кроме N – положительные, не превосходящие 100.
Выходные данные помещаются в текстовый файл GUESTS.OUT и содержат единственную строку с искомым значением времени, рассчитанным с точностью до 0.001.
Пример входных данных
8 30 5 15
Пример выходных данных
1.056

 Орехи

Время на тест– 5 секунд.
Ограничения на память– 32 МБ.

Имя входного файла:
input.txt
Имя выходного файла:
output.txt

Дима и Максим очень любят орехи. На этот раз они купили N орехов (2<=N<=1000000000) и, как обычно, занялись их дележом. Чтобы поделить орехи, они играют в следующую игру. Первым ходит Максим, а дальнейшие ходы совершаются по очереди. Самым первым ходом Максим может съесть любое количество орехов (но не все). Все остальные ходы делаются по правилам: игрок, который сейчас ходит, может съесть любое количество орехов, не превышающее:
А) количества орехов, которое было съедено на предыдущем ходу;
Б) удвоенного количества орехов, которое было съедено на предыдущем ходу.
Самый вкусный орех находится на самом дне кучки, в которую сложены все N орехов. Поэтому выигрывает игру тот игрок, который съест последний орех. Помогите Максиму выиграть в игру, если это возможно.
Ввод. Единственная строка входного файла содержит число N.
Вывод. Выведите сначала ответ для задачи A, а затем ответ для задачи Б. Ответ для каждой задачи выводится в следующем формате: если Максим может выиграть, то перечислите все его возможные первые ходы, которые ведут к победе, разделяя их пробелами, в порядке возрастания количества съедаемых орешков; если Максим не может выиграть, то выведите NO.
Пример.
input.txt                                                          output.txt
5                                                                     1
                                                                      NO



Автор: на