Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Kingdoms

Задача Kingdoms. В одному далекому казковому королівстві жив Вчений. Багато років він працював над можливістю подорожувати іншими казковими королівствами, що знаходяться в паралельних світах. Внаслідок проведених багаточисельних експериментів і завдяки щасливому випадку Вчений раптом виявив, що здійснити свою давню мрію можна за допомогою портального пристрою, зібраного з чарівних кристалів. Існує всього дев'ять різновидів таких кристалів, причому кристали кожного з дев'яти видів є в королівстві в достатній кількості. Для того, щоб потрапити в казкове королівство, яке знаходиться в паралельному світі номер 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.

Коментар для тих, хто не знає фізику. Оптичне збільшення послідовно сполучених кристалів дорівнює добутку оптичних збільшень кожного кристала. Електричний опір послідовно сполучених кристалів дорівнює сумі електричних опорів кожного кристала.

 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"