0020. Делимость

Input file name:	divisibility.in
Output file name:	divisibility.out
Time limit:	2 s
Memory limit:	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

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

Discuss       Submit a solution