eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Замок у вигляді міні-гри

Замок у вигляді міні-гри

У багатьох комп'ютерних іграх злам замків реалізується у вигляді міні-ігр. У своїй грі Полікарп хоче використати наступну міні-гру. На екрані написано три цілих невід'ємних числа: \textbf{a}, \textbf{b}, \textbf{c}. Також є три кнопки "\textbf{a}", "\textbf{b}", "\textbf{c}". \begin{itemize} \item Кнопка "\textbf{a}": додає до числа \textbf{a} одиницю, а від чисел \textbf{b} та \textbf{c} віднімає одиницю. Цю кнопку можна натиснути, лише якщо числа \textbf{b} та \textbf{c} строго більші нуля. \item Кнопка "\textbf{b}": додає до числа \textbf{b} одиницю, а від чисел \textbf{a} та \textbf{c} віднімає одиницю. Цю кнопку можна натиснути, лише якщо числа \textbf{a} та \textbf{c} строго більші нуля. \item Кнопка "\textbf{c}": додає до числа \textbf{c} одиницю, а від чисел \textbf{a} та \textbf{b} віднімає одиницю. Цю кнопку можна натиснути, лише якщо числа \textbf{a} та \textbf{b} строго більші нуля. \end{itemize} Замок вважається відкритим, якщо після деякої (можливо, порожньої) послідовності натиснень на кнопки сума чисел \textbf{a}, \textbf{b} та \textbf{c} дорівнює одиниці. Ваша задача полягає у тому, щоб по числам на екрані сказати, яка мінімальну кількість натиснень знадобиться, щоб відкрити замок, або визнасити, що це неможливо. Якщо замок можна відкрити, потрібно вивести довільний оптимальний спосіб це зробити. \InputFile У першому рядку задано три цілих невід'ємних числа: \textbf{a}, \textbf{b}, \textbf{c} (\textbf{0} ≤ \textbf{a}, \textbf{b}, \textbf{c} ≤ \textbf{10^9}, \textbf{1} ≤ \textbf{a + b + c} ≤ \textbf{10^9}) --- числа, які на початку написані на екрані. \OutputFile У першому рядку виведіть єдине ціле число --- мінімальну кількість натиснень, потрвбну для відкриття замка. Якщо відкрити замок неможливо, виведіть \textbf{-1}. Якщо замок відкрити можна, у другому рядку виведіть довільний оптимальний спосіб зробити це --- рядок, який складається з символів "\textbf{a}", "\textbf{b}", "\textbf{c}", "\textbf{\]}", "\textbf{\[}" та цифр. Рядок повинен задовольняти граматиці (з початковим символом \textbf{answer}): \textbf{character ::= a | b | c;} \textbf{sequence ::= character | character sequence;} \textbf{block ::= character | number \[ sequence \];} \textbf{answer ::= block | block answer;} Тут \textbf{number} (\textbf{1} ≤ \textbf{numbe}r < \textbf{10^10}) --- ціле додатне число, записане без лідируючих нулів. Зверніть увагу, що рядок, яки задовольняє граматиці, не містить пропусків. Виведений рядок повинен позначати послідовність натиснкнь у оптимальній відповіді. Блок \textbf{character} \textbf{відповідає }натисненню на відповідну кнопку, блок \textbf{number \[ sequence \]} відповідає повторенню \textbf{number} разів послідовності натиснень \textbf{sequence}. Дивіться тестові приклади для кращого розуміння.
Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
1 1 0
Вихідні дані #1
1
c
Джерело Зимова школа Харків 2013, День 6 - Г.Агапова та І.Фефера