Fişierul intrare/ieşire:ikebana.in, ikebana.outSursăONI 2011, clasele 11-12
AutorZoltan SzaboAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.45 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ikebana

O florărie vrea să ajungă în Guinness book cu cel mai mare aranjament floral. Ei au la dispoziţie t tipuri de flori, dintre care patru tipuri sunt mai speciale: gerbera, orhideea, azaleea şi hortensia. Lucrătorii au hotărât să pună florile distanţate uniform pe mai multe rânduri, pe fiecare rând exact n flori. Nu vor exista două rânduri identice, dar toate rândurile vor respecta anumite cerinţe:

  • Ei au observat că hortensiile au o viaţă mult mai îndelungată, dacă se învecinează pe acelaşi rând cu o azalee şi cu o orhidee, indiferent dacă ordinea este azalee-hortensie-orhidee sau orhidee-hortensie-azalee.
  • Gerberele vor fi amplasate în aşa fel încât între oricare două gerbere să existe cel puţin p flori, tipul lor fiind oricare dar nu gerbera.

De exemplu dacă avem la dispoziţie t = 5 tipuri de flori: azalee (notate cu a), hortensii (notate cu h), orhidee (notate cu o), gerbere (notate cu g), şi begonii (notate cu b), între două gerbere se vor amplasa minim p = 3 flori, iar rândul va fi format din n = 6 flori, atunci următoarele aranjamente florale sunt corecte: "aoaaoo", "ahohag", "gbbbgo", "gbbbog", "bbbbbb".
Următoare aranjamente nu sunt însă corecte: "ohoaha" (hortensiile nu sunt între o orhidee şi o azalee), "gogbao" (cele două gerbere nu sunt despărţite de minim trei flori), "ahohah" (ultima hortensie nu se învecinează cu o orhidee).
Pentru n = 6, p = 3, t = 5, numărul diferitelor aranjamente florale este 2906.

Cerinţă

Cunoscând valorile lui n, p şi t, să se determine numărul liniilor distincte ce se pot obţine cu cerinţele de mai sus.

Date de intrare

Fişierul ikebana.in conţine pe un singur rând 3 numere naturale n, p şi t separate prin câte un spaţiu.

  • n – reprezintă numărul de flori de pe un rând;
  • p – numărul minim de flori ce trebuie să despartă două gerbere dintr-un rând;
  • t – numărul tipurilor de flori distincte ce stau la dispoziţia florăriei.

Date de ieşire

Fişierul ikebana.out va conţine pe unicul rând un singur număr: numărul de aranjări distincte modulo 666013.

Restricţii

  • 1 ≤ n ≤ 1.000.000.000
  • 3 ≤ p ≤ 20
  • 4 ≤ t ≤ 20

Exemplu

ikebana.inikebana.out
6 3 5
2906
ikebana.inikebana.out
10 6 8
620160

Explicaţie

În al doilea exemplu numărul aranjamentelor distincte este de 181775696, şi avem: 181775696 % 666013 = 620160

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content