Свежие олимпиадные задачи (10.12.2006) Опции

[Леха]

Задача А. Спор (100 баллов)

Ввод: с клавиатуры
Вывод: на экран
Ограничение по времени: 5 секунд
Ограничение по памяти: 64 мегабайта


Вася и Петя поспорили, можно ли с помощью монетки построить такую игру, чтобы вероятность выиграша была равна заданной дроби p/q. Разрешается кидать монету произвольное количество раз, и каждый раз монета выпадает любой из сторон с вероятностью равной 1/2. Эта последовательность записывается, и некоторые конечные последовательности объявляются выигрышными, а некоторые - проигрышными. При этом независимо от хода игры она должна закончиться не более чем за некоторое КОНЕЧНОЕ число бросаний, не зависящее от конкретной последовательности выпавших сторон.
Вам требуется написать программу, которая разрешит спор.

Формат входного файла
Заданы два целых числа p и q (0<=p<=q<=10^9, q<>0).
Формат выходного файла
Выведите YES, если такую игру можно построить, NO в противном случае (заглавными буквами).

Пример

Ввод
9 24
Вывод
YES


Ввод
1 3
Вывод
NO

Сообщение отредактировано: Леха - 10.12.2006 21:27

[Леха]

Задача С. n-мерные сундуки (150 баллов)

Имя входного файла: chest.in
Имя выходного файла: chest.out
Ограничение по времени: 10 секунд
Ограничение по памяти: 64 мегабайта

n-мерному котенку Мурзику посчастливилось найти тайник с сокровищем древних Тинков. Однако, сокровище оказалось упаковано в n крепких сундуков, занумерованных числами от 1 до n. Сундуки могут находиться внутри друг друга. Для каждого сундука существует уникальный ключ, который необходим, чтобы его открыть. Ключ может находиться внутри некоторого сундука, либо просто висеть на стене в тайнике. Сокровище находится в сундуке K.

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


Формат входного файла
Первая строчка входного файла содержит натуральное число [/b]n (1 < n < 1024). Во второй строке записаны n чисел a(i), определяющих положение сундуков. a(i) - номер сундука, внутри которого находится i-й сундук. Если i-й сундук не находится внутри другого, а просто стоит на полу в тайнике, то a(i) равно 0. В третьей строке аналогично описывается положение ключей. i-й сундук можно открыть только с помощью i-го ключа. Последняя строка входного файла содержит число K - номер сундука, где лежит сокровище.
Формат выходного файла
В первой строке выходного файла выведите M - минимальное количество сундуков, которые придется открыть Мурзику. Во второй строке выведите номера этих сундуков в том порядке, в котором он должен их открывать. Если оптимальных решений несколько, разрешается выводить любое.
Если Мурзик не сможет добраться до сокровища, выведите в выходной файл единственное слово IMPOSSIBLE (заглавными буквами).

Пример

chest.in
3
2 0 0
0 0 1
3

chest.out
3
2 1 3

chest.in
3
2 1 0
1 2 1
3

chest.out
IMPOSSIBLE