PY06-15. Tangalar bilan to‘lash

Do‘konda 1, 2 va 5 so‘mlik tangalar bilan to‘lash mumkin (har biridan istalgancha). n so‘mni necha xil usulda to‘lash mumkin?

Tangalar tartibi ahamiyatsiz: 2 + 1 va 1 + 2 — bitta usul. Faqat har tangadan nechtadan olingani muhim. n = 0 uchun bitta usul bor — hech narsa bermaslik.

Kirish ma’lumotlari

Bitta butun son n.

Chiqish ma’lumotlari

Usullar soni.

Cheklovlar

0 ≤ n ≤ 10⁶

n = 5: 5; 2+2+1; 2+1+1+1; 1+1+1+1+1 — 4 usul. n = 6: 5+1; 2+2+2; 2+2+1+1; 2+1+1+1+1; 1·6 — 5 usul.