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

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


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

Consideram o tabla de sah infinita. O pozitie pe tabla de sah (un patratel) este identificata prin coordonatele sale, doua numere intregi x si y, reprezentand linia respectiv coloana pe care se afla patratelul respectiv. Patratul de coordonate (0,0) este undeva in centrul acestei table infinite, astfel ca pozitiile de pe tabla de sah pot avea atat coordonate pozitive, cat si coordonate negative.
Pe aceasta tabla de sah se afla N cai speciali. Un cal special face salturi in forma literei L (ca si un cal obisnuit), doar ca dimensiunea literei este diferita. Mai exact, la un salt, un cal special aflat in pozitia (x,y) se poate deplasa in una dintre urmatoarele 8 pozitii: (x-p, y-q), (x-p, y+q), (x+p,y-q), (x+p,y+q), (x-q,y-p), (x-q, y+p), (x+q,y-p),(x+q,y+p).
De exemplu, daca un cal special se afla pozitia (0,0), iar p=2, q=4, atunci poate sari intr-una dintre pozitiile (-4,-2), (-4,2), (-2,-4), (-2,4), (2,-4), (2,4), (4,-2), (4,2).

Cerinţă

Determinati numarul cailor care prin sarituri succesive pot ajunge din pozitia lor initiala in patratul de coordonate (0,0).

Date de intrare

Fisierul de intrare cai.in contine pe prima linie numerele naturale N, p si q, separate prin cate un spatiu. Pe fiecare dintre urmatoarele N linii se afla cate doua numere naturale x, y separate printr-un spatiu, reprezentand pozitiile initiale ale fiecarui cal.

Date de ieşire

Fisierul de iesire cai.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând numarul cailor care pot ajunge prin salturi succesive in patratul (0,0).

Restricţii

  • 3 <= N <= 30 000
  • 1 <= p, q <= 100
  • x si y sunt numere naturale strict pozitive de cel mult 50 de cifre
  • Pe tabla de sah pot fi oricati cai in aceeasi pozitie, in orice moment

Exemple

cai.in cai.out Explicaţii

5 2 4
3 1
4 8
12 12
1 1
4 2

3 Numai trei cai dintre cei cinci pot ajunge in origine. Calul din pozitia (4, 8) sare mai intai in (2, 4), apoi in (0,0). Traseul nu e unic.
Calul din
(12,12) sare in (10, 8), (6,6), (2,4), (0,0)
Calul din
(4,2) sare direct in (0,0).
Ceilalti doi cai nu pot ajunge in origine.

cai.in cai.out Explicaţii

3 1 2
3 1
2 2
4 3

3 Toti cei trei cai pot ajunge in origine:
(3,1) -> (1,2) -> (0,0)
(2,2) -> (0,1) -> (2,0) -> (1,-2) -> (0,0)
(4,3) -> (3,1) -> (1,2) -> (0,0)

prof. Dan Pracsiu
Grup Scolar "Stefan Procopiu" Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2008: celule, premii, scp, forum, vedete, film, finala, ab, nice, supertri, mod3, degrade, fractii, balanta, inginer, camp, ozn, hora, trei, rebus, sl, detinut, fbr, noroc, simetric, egal, manevre, connect3, gropi, nrcuv, ruleta, carti, pod, bonuri, tgv, fib, uscat, 2sir, atac, matrice2, zeratul, afise, an, dezbateri, test, miniasm, platforma, lac, vopsea, harta, nrbun2, barfa, nrbun, bunici, opmat, acop, tren, cub, picnic, cursa, rv, compus, comun, magic, votare, onu, tramvai, bipal, nspecial, retea, secvop
De acelaşi autor: rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, siruri3, acces, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj, dominant
Despre divizibilitate: celule, trei, ruleta, an, factori, perechi, anagrame, axa, perspic, scara, programs, iepuras2, fry, policefm, turist, kfactor, cuc, prime, sqr, evaluare, factk, div3, divizor, euclid, stop, matricea, mutare, viteza, ingerasi, prieteni, robinson, romeo, perechi1, sume1, fact, tzigla, cifru2, elfi, vraji, desen2, exponent, trapez, resturi, exp1, ron, spirala1, gardul, tort, poligon3, sume2, smith, biliard, printesa, secvente1, ultime4, padure, multiplu1, 235, iepurasi, numar3, cmmmc, randomizare, divizori, pitag, bileprime, pin, canguri, numar4, jocprim, covor, nivfractie, cmmdcsecv, ai, grupe2, numerus, sport2, fagure, grad2, sumdivprod, oak, sumprod, paisprezece, numere10, proddiv, puncte4, trifoi, cartier, alune, intersectii, divider, minm, numere11, prodnr, boltz, vistiernic, secvp, extraprime, divizori1, cumpanit, cntgcd, nrdiv, numere12, daruri, imprimanta, puteri, reflex, tg, sprime, diferenta, concurs4, vapoare, inventie, prime2
Chestionare recomandate
surse trimise | ajutor