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

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


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

Albinuţa Zumzi locuieşte într-un stup format din N celule de formă hexagonală. Cele N celule numerotate de la 1 la N sunt dispuse sub formă de spirală ca în figura alăturată.
Adică, celula din centrul stupului este numerotată cu 1. Plecând de la această celulă spre sud şi apoi în spirală, în sensul acelor de ceasornic, sunt numerotate celelalte celule.
Iniţial Zumzi se găseşte în celula din centru (cea numerotată cu 1), şi doreşte să ajungă, trecând din celulă în celulă, la celula cu numărul de ordine X, unde se găseşte prietenul ei. Zumzi se poate deplasa dintr-o celulă în oricare dintre celulele vecine, fără a părăsi însă stupul. Două celule sunt vecine dacă au o latură comună.
Unele celule ale stupului sunt ocupate de alte albine şi de aceea Zumzi nu poate să treacă prin ele.


Cerinţă

Problema vă cere să determinaţi câte variante are Zumzi ca după exact K paşi să ajungă la prietenul ei.

Date de intrare

Fişierul de intrare zumzi.in conţine pe prima sa linie valorile naturale N, M, K, X separate printr-un spaţiu, având următoarea semnificaţie:
- N - numărul total de celule din stup;
- M - numărul de celule din stup ocupate de alte albine
- K - numărul de paşi pe care îi are la dispoziţie Zumzi
- X - numărul de ordine a celulei în care se găseşte prietenul lui Zumzi.
Următoarea linie a fişierului de intrare conţine M numere naturale separate printr-un spaţiu reprezentând numerele de ordine ale celulelor ocupate din stup.

Date de ieşire

Fişierul text zumzi.out va conţine pe prima sa linie un singur număr natural reprezentând numărul de variante pe care le are zumzi la dispoziţie de a ajunge la prietenul ei.

Restricţii

1 <= M < N <= 300
X<>1
K<=100

Zumzi nu are posibilitatea de a părăsi stupul, iar în plus odată ajunsă la prietenul ei nu îl va mai părăsi.
Zumzi nu este o albină foarte inteligentă de aceea ea poate trece de mai multe ori printr-o celulă, cu exceptia celulei finale, in care se afla prietenul ei, celula in care va intra o singura data si nu o mai paraseste.

Exemple

zumzi.inzumzi.outExplicaţii
12 4 3 9 11 4 6 8 4 Variantele sunt:
1-2-10-9
1-3-2-9
1-3-10-9
1-7-2-9



12 4 4 2 11 4 6 8 9 Variantele sunt:
1-3-10-9-2
1-7-1-3-2
1-5-1-7-2

etc

autor: Prof. Carmen Popescu
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2006: borg, diamant, matrice1, petrom, ratina, vitale, acolor, cifru1, evo, part, trasee, bombo, cub2, prieteni2, sg1, fact, limbaj, panouri, pereti, sant1, adun, sport1, baschet1, mere3, roboti, tzigla, morse, powerpuff
De acelaşi autor: light, sort, iepuras, pahare, turist, arthur, pento, cod2, game, ambigram, jokes, trecere, paianjen, cifru3, pamant, pixy, triburi, culori1, cifre5, arc
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, 2ndesc, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre numere mari: fib, 2sir, test, sort, gray, siruri, vecini, div, sir2, nrcuv2, scor, hanoig, red, matrice3, pavaj, depou, pm, sqr, set, albine, teatru1, descfib, tub, m01, soldati1, euclid, mutare, munte1, bifo, banda10, sg1, cutii, numere7, trapez, patrate6, muguri, impozit, kbiti, m4, numar3, parbit, petrecere, randomizare, radical, ghinion, aliniere, sumb, cavaleri, camera616, numar4, pavari, asfalt, rotund, cos, risipa, xpn, dale, codpatrat, culori1, plus, minm, pomi, cifrab, subsets, doitrei, conjectura, ech, inventie
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor