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