Гра з проміжками
Обмеження: 2 сек., 256 МіБ
Зеник і Марічка мають \(n\) камінців, розташованих у ряд. На \(i\)-ому камінцеві написано число \(a_i\).
Зеник і Марічка грають у гру. Вони ходять по черзі. Марічка ходить першою. На кожному ході гравець бере деякий непорожній послідовний проміжок камінців.
Наприклад, у нас є ряд із камінцями [4, 7, 2, 5, 9]. Гравець може вибрати взяти камінці із числами 2 й 5. Після ходу новий ряд матиме вигляд [4, 7, 9].
Гра завершується, коли всі камінці взяті.
Коли гравець бере камінець із числом \(x\), він отримує \(n^x\) штрафних балів. Гравець із меншою кількістю штрафних балів є переможцем гри.
Визначте, хто виграє, якщо обоє гравців грають оптимально.
Вхідні дані
Перший рядок містить ціле число \(n\) — кількість камінців.
Другий рядок містить \(n\) цілих чисел \(a_i\) — числа, записані на камінцях.
Вихідні дані
Виведіть Zenyk
, якщо виграє Зеник,
Marichka
, якщо виграє Марічка, або Draw
, якщо
гра закінчиться внічию.
Обмеження
\(1 \le n \le 10^5\),
\(0 \le a_i \le 10^9\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 4 4 7 1 | Marichka |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
2 7 7 | Draw |
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|