Codeforces Beta Round 88 |
---|
Закончено |
В одной очень древней стране была популярна следующая игра. В игру играет два человека. Сначала первый игрок выписывает строку s1, состоящую ровно из девяти цифр и обозначающую число, не превосходящее a. Потом второй игрок, видя s1, выписывает строку s2, состоящую ровно из девяти цифр и обозначающую число, не превосходящее b. Здесь a и b — некоторые заданные константы, строки s1 и s2 игроки выбирают сами. Лидирующие нули в строках разрешаются.
Если число, задающееся конкатенацией (склейкой) строк s1 и s2, делится на mod, выигрывает второй игрок. Иначе — выигрывает первый игрок. Даны числа a, b, mod. Требуется определить, кто выиграет при оптимальной игре обоих. Если выиграет первый игрок, также требуется найти лексикографически минимальный выигрышный ход.
В первой строке заданы три целых числа a, b, mod (0 ≤ a, b ≤ 109, 1 ≤ mod ≤ 107).
Если выиграет первый игрок, выведите «1» и лексикографически минимальную строку, которую ему нужно выписать, чтобы победить. Если выиграет второй игрок, выведите одно число «2».
1 10 7
2
4 0 9
1 000000001
Лексикографическое сравнение строк реализует оператор < в современных языках программирования. Строка x лексикографически меньше строки y, если существует такое i (1 ≤ i ≤ 9), что xi < yi, а для любого j (1 ≤ j < i) xj = yj. Сравниваемые строки всегда имеют длину 9.
Название |
---|