Задача Kingdoms. В одному далекому казковому королівстві жив Вчений. Багато років він працював над можливістю подорожувати іншими казковими королівствами, що знаходяться в паралельних світах. Внаслідок проведених багаточисельних експериментів і завдяки щасливому випадку Вчений раптом виявив, що здійснити свою давню мрію можна за допомогою портального пристрою, зібраного з чарівних кристалів. Існує всього дев'ять різновидів таких кристалів, причому кристали кожного з дев'яти видів є в королівстві в достатній кількості. Для того, щоб потрапити в казкове королівство, яке знаходиться в паралельному світі номер N, треба послідовно (щільно один до одного вряд) з'єднати рівно N чарівних кристалів таким чином, щоб оптичне збільшення отриманого портального пристрою чисельно дорівнювало його електричному опору. Допоможіть Вченому визначити, скільки існує різних способів потрапити в паралельний світ номер N і яка мінімальна кількість чарівних кристалів кожного виду для цього знадобиться.
Величини оптичного збільшення та електричного опору кожного з дев'яти видів кристалів чисельно рівні їх номерам- від одного до дев'яти. Наприклад, оптичне збільшення всіх чарівних кристалів "номер шість" дорівнює шести й електричний опір їх також дорівнює шести. Подорожі відбуваються по черзі, кристали можна використовувати багато разів.
Технічні умови. Програма Kingdoms читає з пристрою стандартного введення натуральне число N(1<=N<=500). Програма виводить у одному рядку через пропуски спочатку шукане число - кількість різних способів потрапляння в паралельний світ із заданим номером, а далі дев'ять чисел - мінімальну кількість кристалів (у порядку збільшення номерів) для здійснення всіх почергових подорожей у паралельний світ номерN.
|
Приклад Введення 3 Виведення 6 1 1 1 0 0 0 0 0 0
|
Коментар до прикладу Можливі комбінації для N=3.
123 132 213 231 312 321
Оптичне збільшення: 1х2х3=6; Електричний опір: 1+2+3=6. |
|
Коментар для тих, хто не знає фізику. Оптичне збільшення послідовно сполучених кристалів дорівнює добутку оптичних збільшень кожного кристала. Електричний опір послідовно сполучених кристалів дорівнює сумі електричних опорів кожного кристала. |
|