.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » ikebana

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
ikebana


Timp maxim de execuţie / test:
1.4s
Memorie totala disponibilă / stivă:
32MB / 1MB

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 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 ≤ 1000000000
• 3 ≤ p ≤ 20
• 4 ≤ t ≤ 20

Exemple

ikebana.inikebana.outExplicaţii
6 3 5 2906 Numărul aranjamentelor distincte este de 2906
10 6 8 620160 Numărul aranjamentelor distincte este de 181775696, şi avem:
181775696 % 666013 = 620160

autor: Prof. Zoltan Szabo
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2011: sport2, macheta, butoane, acces, mxl, segmente, tsunami, tort1, ec, ape, poligon4, stalpi2, furnici1, telecab, posta, fotbal1, xmoto, radare, pamant, fagure, goe, papusa, taburet, joc17, mesaj3, zar1, joc16, talent, xy, arbore1, robot3, copii, hacker, terenuri3d, terenuri, expresie2, poteci, joc18
De acelaşi autor: balanta, bonuri, cub, magic, magic2, munte, euclid, banda, biliard, fractie1, fotbal, arctir, orientare, rege, fibo1, piatra, war, aritm, ssmax, sirmax, punctfix, domino2, lant1, parc1, cubulete, biperm, triunghi6, stiva1
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre exponenţiere logaritmică: fibgcd, cover1, 2sah
surse trimise | ajutor