Codeforces Round 258 (Div. 2) |
---|
Закончено |
Завоевав золото и серебро в IOI 2014, Akshat и Malvika захотели немного развлечься. Сейчас они заняты игрой на сетке, составленной из n горизонтальных и m вертикальных палочек.
Точкой пересечения на сетке называется любая точка сетки, образованная пересечением одной из горизонтальных и одной из вертикальных палочек.
На сетке, показанной ниже, n = 3 и m = 3. Сетка образована n + m = 6 палочками (вертикальные палочки выделены зеленым цветом, а горизонтальные — красным цветом). На сетке есть n·m = 9 точек пересечения, которые пронумерованы от 1 до 9.
Правила игры очень простые. Игроки ходят по очереди. Akshat завоевал золото, поэтому он делает первый ход. На своем ходу игрок должен выбрать любую оставшуюся точку пересечения, а затем удалить из сетки все палочки, которые проходят через эту точку. Игрок проигрывает, если не может сделать ход (на сетке не осталось точек пересечения).
Предположим, что оба игрока играют оптимально. Кто победит в игре?
Первая строка содержит два целых числа через пробел, n и m (1 ≤ n, m ≤ 100).
Выведите "Akshat" или "Malvika" (без кавычек), в зависимости от того, кто победит при оптимальной игре.
2 2
Malvika
2 3
Malvika
3 3
Akshat
Пояснение к первому примеру:
Изначально сетка имеет 4 точки пересечения. На рисунке они пронумерованы от 1 до 4.
Если Akshat выберет точку пересечения 1, то он уберет две палочки 1 - 2 и 1 - 3, полученная сетка будет выглядеть вот так:
Так как осталась только одна точка пересечения (это 4), Malvika обязана выбрать ее и убрать две оставшихся палочки. После ее хода сетка будет пуста.
На пустой сетке Akshat не может сделать ход, поэтому он проиграет.
Так как все 4 точки пересечения сетки идентичны, Akshat проиграет, независимо от того, какую он выберет на первом ходу.
Название |
---|