Heç Yerdə Pul
Nowhere şəhərində insanlar pullarını "sikkə və yuva" kimi istifadə edirlər. Burada 2 növ sikkə mövcuddur: ölçü1 və ölçü2. Ölçü2 sikkəsi, ölçü1-in qalınlığının iki qatıdır. İnsanlar sikkələrini yuvalarda saxlayır və onları pul kimi istifadə edirlər. Müxtəlif ölçülərdə yuvalar var. Ölçüsü n olan bir yuva, n ölçü1 sikkəsini tuta bilir. Yalnız tam dolu yuva qanuni pul sayılır. Hər dolu yuvanın dəyəri, içindəki sikkələrin yığılma yollarının müxtəlif sayıdır. Məsələn, ölçü-1 yuvada yalnız bir ölçü1 sikkəsi yığmağın bir yolu var. Ölçü-2 yuvada iki ölçü1 sikkəsi və ya bir ölçü2 sikkəsi yığmağın 2 yolu var. Ölçü-5 yuvada isə sikkələri yığmağın 8 yolu var, bunlar belədir: 1 1 1 1 1, 1 1 1 2, 1 1 2 1, 1 2 1 1, 2 1 1 1, 1 2 2, 2 1 2, 2 2 1. Beləliklə, ölçü-1, ölçü-2 və ölçü-5 dolu yuvanın dəyəri müvafiq olaraq 1, 2 və 8 (pul) vahididir.
Mr.Thinktwice bu şəhərdə bir baqqal dükanının sahibidir. O, müşahidə etdi ki, müştərilər, onlara uyğun formada pul qaytarışı edə bilən dükanlara üstünlük verirlər. Kiçik bir sorğudan sonra o, əksər müştərilərin dəyişiklik məbləğini aşağıdakı 2 sadə məhdudiyyətlərə uyğun almaq istədiklərini öyrəndi.
Yuvaların sayı minimum olmalıdır.
Hər bir yuvanın ölçüsü bir-birindən ən azı fərqli olmalıdır.
Bu o deməkdir ki, müştərilər eyni ölçüdə yuvalar istəmir və ölçülər çox yaxın olmadıqda bu fərqləri ayırd etmək daha asan olacaq.
Beləliklə, Mr.Thinktwice sizdən verilmiş dəyişiklik məbləği üçün yuxarıdakı məhdudiyyətlərə uyğun bir sıra yuva ölçüləri təqdim edə biləcək bir proqram yazmağınızı xahiş edir. Üstəlik, sıra azalan sırada sıralanmalıdır. Daha dəqiq desək, hər hansı bir dəyişiklik məbləği bu formul ilə yazıla bilər.
burada
X dəyişiklik məbləğidir.
n ümumi yuva sayıdır.
s_i i-ci yuvanın ölçüsüdür.
T yuva ölçüsündən sikkələrin yığılma yollarının sayına keçid edən bir funksiyadır.
və j ≫ k ≡ j ≥ k+2 olduqda
Məsələn:
Giriş verilənləri
Giriş standart girişdir və bir sıra tam ədədlərdən ibarətdir. Girişin hər sətri müsbət tam ədəd ilə təmsil olunan dəyişiklik məbləğidir və bu, 5000000000000000000 və ya 5×10^18-dən kiçik və ya bərabərdir. Giriş EOF (Faylın Sonu) ilə bitir.
Çıxış verilənləri
Hər dəyişiklik məbləği üçün 4 sətir çıxış məlumatı yaradın. Birinci sətir dəyişiklik məbləğinin özüdür. İkinci sətir yuva ölçülərinin (azalan sırada) ardıcıllığıdır və aralarında boşluq var. (Maksimum yuva ölçüsü 90-dan kiçik və ya bərabərdir.) Üçüncü sətir müvafiq yuva dəyərlərinin ardıcıllığıdır. Dördüncü sətir boş sətirdir.