0020. Делимость

Имя входного файла:	divisibility.in
Имя выходного файла:	divisibility.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Дана строка с цифрами от 0 до 9. Используя эти цифры, нужно получить максимальное число, делящееся на 15. Цифры в этом числе не обязательно должны идти в том порядке, в котором они даны. Также, необязательно использовать все цифры. При этом, ведущие нули в получившемся числе запрещены.

Формат входного файла

В первой строке находится число n – длина строки (1 ≤ n ≤ 10⁶). Во второй строке находится строка s длины n с цифрами от 0 до 9.

Формат выходного файла

Выведите максимально возможное число, делящееся на 15, без ведущих нулей. Если такого числа получить нельзя, выведите в выходной файл "impossible" (без кавычек).

Пример:

divisibility.in	divisibility.out
5 02041	4200
2 15	15

Источник: Командное школьное первенство Республики Карелия по программированию, октябрь 2008.

Обсудить       Отправить решение



Версия для печати