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

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


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

Se dă o tablă de şah cu n+1 linii (numerotate de sus în jos începând cu 1) şi 2n+1 coloane (numerotate de la stânga la dreapta începând cu 1). Pe prima linie pătratul din mijloc conţine 1 gram de fân, iar celelalte pătrate de pe prima linie nu conţin nimic. Începând cu linia a doua fiecare pătrat conţine o cantitate de fân obţinută prin adunarea cantităţilor de fân din cele 3 pătrate ale liniei anterioare cu care se învecinează (pe verticală şi diagonală). De exemplu dacă n=3 tabla are 4 linii, 7 coloane şi următoarea configuraţie.



Un cal pleacă de pe prima linie, de pe o coloană k≤n, sare din orice poziţie (i,j) în poziţia (i+1,j+2) atât timp cât este posibil şi mănâncă tot fânul din pătratele prin care trece. De exemplu, pentru n=3 şi k=2, pătratele prin care trece calul sunt marcate cu asterisc ( * )

Cerinţă

1. Cunoscând n şi k, să se calculeze cantitatea de fân de pe linia k a tablei.
2. Cunoscând n şi k, să se calculeze câte grame de fân mănâncă un cal care pleacă de pe prima linie, de pe coloana k.
Întrucât aceste numere pot fi mari, se cer doar resturile împărţirii la 100003 ale acestor numere.

Date de intrare

Fişierul de intrare 2sah.in va conţine pe prima linie un număr t cu valoarea 1 sau 2. Pe a doua linie a fişierului de intrare se găsesc două numere naturale n şi k separate printr-un spaţiu.
Dacă t=1 se va rezolva prima cerinţă, deci pentru valoarea n citită tabla are n+1 linii şi 2n+1 coloane, iar k reprezintă numărul liniei de pe care trebuie calculată cantitatea de fân.
Dacă t=2 se va rezolva a doua cerinţă, deci pentru valoarea n citită tabla are n+1 linii şi 2n+1 coloane, iar k reprezintă numărul coloanei din prima linie de unde pleacă calul.

Date de ieşire

Dacă t din fişierul de intrare este 1 se va rezolva doar prima cerinţă.
În acest caz fişierul de ieşire 2sah.out va conţine un singur număr reprezentând cantitatea totală de fân din toate pătratele situate pe tabla pe linia k (rezultatul trebuie afişat modulo 100003).
Dacă t din fişierul de intrare este 2 se va rezolva doar a doua cerinţă.
În acest caz fişierul de ieşire 2sah.out va conţine un singur număr reprezentând cantitatea totală de fân mâncată de un cal care pleacă de pe linia 1 şi coloana k (rezultatul trebuie afişat modulo 100003).

Restricţii

• 1 ≤ k ≤ n ≤ 1000000000 (un miliard)

Exemple

2sah.in2sah.outExplicaţii
1 3 2 3 t=1, deci se rezolvă prima cerinţă.
Pe linia a doua există 3 pătrate care conţin fiecare câte un gram de fân.(vezi desenul din enunţ)
2 3 2 2 t=2, deci se rezolvă doar a doua cerinţă.
Traseul calului este: (1,2) -> (2,4) -> (3,6) adică exact pătrăţelele marcate cu asterisc în desenul din enunţ. Prima poziţie nu conţine fân, iar celelalte două conţin câte un gram de fân. Deci calul mănâncă 2 grame de fân.

autor: Prof. Adrian Panaete
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la OJI 2015: panda, charlie, ech, lasere, dragoni, arc, defrag, dominant, pavare1, ordine, covor1, speciale, cuart
De acelaşi autor: butoane, risipa, mofocarburi, cover1, codarb, trifoi, albine2, nkd, transform, fractii2
Despre combinatorică: manevre, carti, bonuri, test, cub, nspecial, circuit, numere, cs, pluricex, parent, gray, siruri, anagrame, party, net, scaune, sir, monede, aztec, nrcuv2, perm, race, hanoig, red, grup, hperm, depou, grazing, pm, reteta2, playlist, young, pizza1, albine, caramele, teatru1, tub, robot1, sir23, soldati1, concurs1, comb, expresii, arbnr, cod1, munte, shgraf, desc, lex, munte1, maxperm, role, avere, vizibil, prime1, hexa, patrat, carti2, puncte2, pact, aranjari, numere5, borg, acolor, sg1, perfect, cifru2, bile4, pviz, culmi1, piramida1, trapez, frunze, sir7, logic, coduri, jetoane, kperms, tablite, secvpar, lego, permutari, binperm, multiplu1, operatii, fotbal, kbiti, jucarii, bradut, expozitie, parbit, kmax, petrecere, tango, rege, cd1, cifru3, kcons, bubblesort, hawaii, randomizare, kdist, reuniune, echipa, ghinion, cavaleri, camera616, covor, subm, grupuri, pavari, asfalt, adunscad, rotund, sport2, arbore1, lant1, module, nrperm, oneton, nrpomi, cover1, nrpal, probleme, optim, poly, vot1, sudoku1, flori2, xnumere, showroom, cntgcd, subsets, nkd, nrgraf, spion1, puteri, stiva1, permtr, relatii, matcnt, magic7, nmult, roua
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, zumzi, 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, matcnt, nmult
Despre exponenţiere logaritmică: ikebana, fibgcd, cover1, 2ndesc
surse trimise | ajutor