Свежие олимпиадные задачи (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

[Леха]

Задача B. Строчка (60 баллов)

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

На день рождения родители подарили Васе набор кубиков, на которых написаны разные английские буквы. Он тут же начал выкладывать из кубиков разные слова, но все они ему не нравились. Наконец он понял, что ему нравятся слова-палиндромы, которые читаются справа налево так же, как и слева направо. Например, abba, bcb, k - палиндромы, а abaa, ab, acccb - нет. Теперь Вася хочет убрать некоторые кубики из последнего выложенного им слова так, чтобы остался палиндром. Причем на самом первом кубике Вася уже построил железную дорогу, поэтому он может убирать кубики только начиная с последнего и дальше по порядку. То есть, из слова abcde он сначала получит abcd, затем - abc, затем - ab, и, наконец, - a. Помогите Васе узнать, какой полиндром максимальной длинны он сможет получить из своего слова описанным образом!

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

Пример

strin.in
aba

string.out
aba

string.in
aaaba

string.out
aaa