олимпиадные задачи 2011-2012

[evgeniyvol]

помогите пожалуйста с решением.срочно!
1. ЕГЭ B1
Некоторое сигнальное устройство за одну секунду передает один из трех специальных сигналов. Какое количество различных сообщений можно передать при помощи этого устройства за N секунд?
Формат входных данных:
Задано одно натуральное число N (1 ≤ N ≤ 20).
Формат выходных данных:
Выведите количество сообщений.
Пример input.txt output.txt
1 3




2. Сейф
Вася был величайшим вором всех времен и народов. Однажды он решил ограбить банк. Чтобы открыть главный сейф, ему нужно вставить три определенных ключа в соответствующие замки сейфа. Только тогда дверь откроется.
Вася уже украл у директора связку ключей, в которой точно есть три нужных. Теперь он хочет оценить, сколько времени в худшем случае ему понадобится на открывание сейфа, если он успевает проверить одну комбинацию за одну секунду.
Формат входных данных:
Задано одно натуральное число N (3 ≤ N ≤ 104) —количество ключей в связке.
Формат выходных данных:
Выведите время в секундах.
Пример input.txt output.txt
2 6



3. Шашлыки
Вася с одноклассниками пошел на шашлыки. Ему поручили следить за мангалом. Через некоторое время он заметил, что шашлыки жарятся неравномерно. Поэтому он решил положить самые поджаристые шампура туда, где меньше жара и наоборот.
За один раз Вася может поменять местами два шампура. Так как они очень горячие, он хочет сделать минимальное количество перемещений. Помогите Васе подсчитать наименьшее количество перемещений шампуров учитывая, что он заранее выбрал какой шампур куда надо положить.
Формат входных данных:
В первой строке задано одно натуральное число N (1 ≤ N ≤ 105). Во второй строке через пробел записаны N различных чисел — номера позиций, куда нужно переместить соответствующие шампура. Все номера являются натуральными числами, не превосходящими N.
Формат выходных данных:
Выведите минимальное количество перемещений.
Пример input.txt output.txt
4
1 4 3 2 1
5
4 2 1 3 5 2



4. Лист в линию
На уроке русского языка Вася от скуки решил раскрасить тетрадный лист в линию, который представляет собой прямоугольник размером W×H. На нем нанесены горизонтальные и наклонные линии, разбивающие лист на кусочки. Вася решил каждый кусочек раскрасить в уникальный цвет. Какое количество различных цветов понадобится Васе?
Будем считать, что прямоугольник расположен в первой координатной четверти, причем левый нижний угол расположен в начале координат, а сторона длиной W параллельна оси абсцисс. Горизонтальные линии задаются ординатами точек пересечения прямых с осью OY, а наклонные — абсциссами точек пересечения прямых с осью OX. Наклонные линии составляют угол 45° с положительным направление оси OX (см. рисунок).

Формат входных данных:
В первой строке заданы четыре натуральных числа: W, H, N, M (1 ≤ W, H ≤ 105, 0 ≤ N < H, 0 ≤ M < W + H). Во второй строке записано N чисел — ординаты точек пересечения горизонтальных линий с осью OY. В третьей строке записано M абсцисс точек пересечения наклонных линий с осью OX. Гарантируется, что все линии проходят через прямоугольник (отсекают какую-то не пустую часть) и нет двух одинаковых линий. Все числа целые.
Формат выходных данных:
Выведите количество различных цветов.
Пример input.txt output.txt
6 4 2 1
1 3
1 6


5. Аэропорт
...Извержение вулкана Эйяфьядлайёкюдль в Исландии, сопровождающееся большим выбросом пепла в атмосферу, привело к отмене большинства авиарейсов в Северной Европе. С 12.00 полностью закрыто воздушное пространство Великобритании и Ирландии, с 10.00 — Норвегии. Также отменены все рейсы в северных областях Швеции и Финляндии. Возможно закрытие аэропортов и других стран, если их накроет облако пепла...

Как раз в это время Вася должен был лететь домой из Лондона, но его рейс оказался задержанным. Ему, как и многим другим пассажирам, пришлось ночевать в аэропорту в ожидании рейса. Вася решил лечь спать на одном или нескольких стульях. Для этого он хочет взять некоторое количество стульев так, чтобы всем оставшимся пассажирам досталось равное количество стульев. Помогите Васе определить, какое наименьшее количество стульев можно взять.
Формат входных данных:
Задано два натуральных числа N и M (1 ≤ M ≤ N ≤ 1 000 000 000) — число стульев и пассажиров, не включая Васю, соответственно.
Формат выходных данных:
Выведите сколько стульев надо взять Васе.
Пример input.txt output.txt
8 3 2

6. ЕГЭ В3
Найдите все основания систем счисления, в которых запись числа A оканчивается на 5.
Формат входных данных:
Задано одно натуральное число A (10 < A ≤ 109).
Формат выходных данных:
Выведите через пробел все основания в порядке возрастания.
Пример input.txt output.txt
27 11 22

[evgeniyvol]

7. Трасса Е95
Вася так и не дождался рейса на Санкт-Петербург. Так как спать на стульях — утомительное занятие, он купил машину и поехал на ней.
Один из участков пути проходит по всем известной трассе Е95. У нее есть несколько особенностей. Вскоре после открытия трассы, было решено ее продлить, в результате чего на ней появились километровые отметки с отрицательными числами. Другой отличительной особенностью этой трассы является то, что на ней заправки расставлены равномерно. Вася помнит, что он заправлялся на A-ом и B-ом километре этой трассы. Сейчас он проезжает мимо заправки на C-ом километре и хочет узнать, через сколько километров в худшем случае будет следующая заправка.
Формат входных данных:
Заданы три целых числа A, B и C, по модулю не превосходящие 109, причем A < B < C.
Формат выходных данных:
Выведите через сколько километров в худшем случае будет следующая заправка.
Пример input.txt output.txt
0 1 2 1
0 4 6 2



8. Новогодние игрушки
И вот Вася приехал в Санкт-Петербург. Проезжая мимо Зимнего дворца, он увидел забавную картину: толпы рабочих суетятся вокруг елок. Один из них объяснил Васе суть происходящего. Оказалось, что накануне город посетил высокопоставленный чиновник, которого неприятно удивила неравномерность украшения елок возле дворца. Он распорядился сделать так, чтобы каждая елка была украшена одинаковым количеством игрушек. Поскольку все игрушки уже использованы, то необходимо некоторые снять, а некоторые перевесить. Но никто не знает, успеют ли они выполнить работу до Нового года.
Вася решил помочь рассчитать, какое минимальное количество операций снятия и вешанья игрушек потребуется для выполнения распоряжения, но не справился. Помогите ему решить эту элементарную задачу.
Формат входных данных:
В первой строке задано одно натуральное число N (1 ≤ N ≤105) — количество елок. Во второй строке через пробел задано N неотрицательных целых чисел, не превосходящих 109 — количество игрушек на каждой елке.
Формат выходных данных:
Выведите количество операций, которое потребуется рабочим для выполнения распоряжения.
Пример input.txt output.txt
3
4 4 6 2
4
3 4 5 6 4

[Leshii]

Ууу как всё запущенно...
Мб сразу за тебя олимпиаду выиграть?)
Или чего там надо здать?)

[Nikita++]

Действительно запущено) Даже 10^5 у нас 105 и т.п. Помню эти задачки - с городского этапа олимпиады. Они ж элементарные) Ну только с 4 и 8 - подумать посидеть и то, это часа за 2-3 спокойно на 100 баллов написать можно. Если хочешь решение - показывай наработки.