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

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


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

Balaurul Arhirel este pus în faţa unei mari dileme. Fără să vrea, a ajuns în munţii României şi trebuie să parcurgă un traseu de-a lungul căruia să viziteze N cabane. El poate porni de la orice cabană, dar trebuie să treacă pe la fiecare cabană exact o dată.
Cabanele sunt numerotate de la 1 la N, iar fiecare se află la o înălţime egală cu indicele său exprimat în metri. Deplasarea între oricare două cabane se face în linie dreaptă (creşte sau scade constant). Problema este că Balaurul nu poate urca sau coborî mai mult de K metri între oricare două cabane consecutive de pe traseu, deci traseul trebuie să fie bine ales.
Norocul Balaurului este că există multe posibilităţi. Ghinionul vostru este că Balaurul ştie câte posibilităţi sunt şi vrea să vadă dacă şi voi ştiţi.

Cerinţă

Pentru valorile N şi K date, determinaţi numărul de posibilităţi de a vizita fiecare dintre cele N cabane exact o dată, astfel încât diferenţa de nivel (în valoare absolută) dintre oricare două cabane vizitate consecutiv să fie de maxim K metri. Rezultatul trebuie să fie dat modulo 30103 (restul împărţirii la 30103).

Date de intrare

Fişierul de intrare cabane.in va conţine pe prima linie valorile N şi K separate printr-un spaţiu.

Date de ieşire

Fişierul de ieşire cabane.out va conţine o singură linie pe care va fi scris numărul total de posibilităţi modulo 30103.

Restricţii

• K ≤ N ≤ 200
• 1 ≤ K ≤ 6

Exemple

cabane.incabane.outExplicaţii
4 2 12 Din cele 24 de trasee posibile 12 sunt valide:
1 2 3 4, 1 2 4 3, 1 3 2 4, 1 3 4 2,
2 1 3 4, 2 4 3 1, 3 1 2 4, 3 2 4 1,
4 2 1 3, 4 2 3 1, 4 3 1 2, 4 3 2 1

Iar celelalte 12 nu sunt. De exemplu 2 1 4 3 nu e valid pentru că între cabana 1 şi cabana 4 este o diferenţă de 3 metri.

autor: Marius Andrei
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot SB 2005: culmi1, drumuri, munte2, piramida1, tj, trapez
De acelaşi autor: conflicte, cadere, leaves, na, distanta, ivv, aparitii, tabara1, stop, hanoi, logn, cuburi1, viteza, masina3, anticip, spp, regine, comoara2, perle, cuvinte1, sortari, triti
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, 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, ikebana, 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 graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
surse trimise | ajutor