eolymp
bolt
Try our new interface for solving problems
Məsələlər

Игра с монетами

Игра с монетами

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Для игры с монетами используется горизонтальная полоска, разделенная на N одинаковых квадратных клеток. Изначально в некоторых клетках доски есть монеты, а в некоторых - нет.

Два игрока - Дмитрий и Иван - начинают по очереди делать ходы, причем Дмитрий ходит первым. За один ход игрок может проделать следующие действия:

  1. Выбрать любую монету, справа от которой есть хотя бы одна свободная клетка.

  2. Переместить выбранную монету в любую из свободных клеток, находящихся справа от нее.

  3. Переместить ровно на одну клетку влево все монеты, которые находятся между позициями выбранной монеты до и после ее перемещения.

Пример хода проиллюстрирован на следующем рисунке:

Если обозначить монету символом 'C', а пустую клетку - символом '.', то состояние полоски можно описать как строку из N символов. Для примера выше состояние полоски до хода описывается строкой "C.CC...C..CC.C", а после хода - строкой "C.C...C..CC.CC".

Проигравшим считается тот игрок, который не смог сделать ход (т.е. к моменту хода этого игрока все монеты примыкают к правому краю полоски). Соответственно, игрок, сделавший самый последний ход - это победитель игры.

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

Giriş verilənləri

Строка S, описывающая состояние полоски до начала игры.

  1. Строка S содержит от 2 до 100 символов включительно.

  2. Строка S может содержать только символы 'C' и '.'.

  3. Строка S содержит хотя бы одно вхождение символа 'C'.

  4. Строка S содержит хотя бы одно вхождение символа '.'.

Çıxış verilənləri

Строка, равная "DMITRY", если победителем игры окажется Дмитрий, и равная "IVAN", если победителем игры станет Иван.

Nümunə

Giriş verilənləri #1
C.
Çıxış verilənləri #1
DMITRY