e-olymp
Məsələlər

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

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

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

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

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

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

prb1446

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

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

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

Входные данные

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

  1. Строка S содержит от 2 до 100 символов включительно.
  2. Строка S может содержать только символы 'C' и '.'.
  3. Строка S содержит хотя бы одно вхождение символа 'C'.
  4. Строка S содержит хотя бы одно вхождение символа '.'.

Выходные данные

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
Sample 1
C.

Sample 2
.C

Sample 3
C.C.C

Sample 4
CC..CC..CC

Sample 5
.CC...C..CC.C
Çıxış verilənləri
Sample 1
DMITRY

Sample 2
IVAN

Sample 3
DMITRY

Sample 4
IVAN

Sample 5
DMITRY