Текстовый редактор
Всемирно известная кампания разработала новый, упрощённый вариант своего популярного текстового редактора. В распоряжении пользователя есть всего 4 возможные операции, которые можно выполнять в текстовом редакторе (каждая операция выполняется одним нажатием на соотвествующую клавишу):
Напечатать в редакторе символ "А" - клавиша "А" (символ прибавлятся в конец текущей строки)
Выделить всю строку - клавиша "S" (select)
Скопировать все выделенные символы в буфер - клавиша "C" (copy)
Добавить содержимое буфера в конец текущей строки - клавиша "P" (paste), при этом вставка затирает выделенную строку.
Определить максимальное количество символов "А", которые можно напечатать в редакторе за N нажатий и указать последовательность операций, приводящих к этому результату.
Входные данные
Входными данными к задаче является целое число N (0 < N < 50).
Выходные данные
В стандартный поток вывода в первой строке вывести целое число - максимальное количество символов "А", которые можно напечатать в редакторе за N нажатий, а во вторую строку - последовательность операций, которые приводят к этому результату. Если такая последовательность не одна, то вывести ту, которая минимизирует количество символов в буфере обмена.
Примечание: Три рази нажимаем клавишу "А" - получаем строку AAA. Нажимаем клавишу "S" - выделяем все символы, нажимаем клавишу "С" - копируем их в буфер, нажимаем клавишу "Р" - вставляем вместо выделенной строки содержимое буфера, ещё два раза нажимаем клавишу "Р" - прибавляем содержимое буфера к текущей строке. Всего сделали 8 нажатий и получили строку из 9 символов "А".