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

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


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

Să considerăm o tablă de şah, formată din pătrate albe şi negre, plasate alternativ. Fiecare pătrat de pe tabla de şah are latura de L mm. Pătratul din colţul stânga-jos al tablei de şah este negru.
Vom considera un sistem cartezian de coordonate, cu originea plasată în colţul din stânga-jos al tablei. Astfel fiecare punct de pe tabla de şah poate fi identificat prin coordonatele sale carteziene (x, y), unitatea de măsură fiind mm.
Pe tabla de şah se află un greiere în punctul de coordonate (xg, yg). Greierele poate face salturi. La un salt el se va deplasa cu dx mm la dreapta şi dy mm în sus (adică din punctul de coordonate (x,y) va ajunge în punctul de coordonate (x+dx, y+dy)).

Cerinţă

Să se determine care este numărul minim de salturi pe care trebuie să le facă greierele până să ajungă în interiorul (nu şi pe bordura) unui pătrat de culoare albă (dacă acest lucru este posibil).

Date de intrare

Fişierul de intrare greiere.in conţine mai multe seturi de date de test, câte un set pe o linie. Un set de date de test constă din 5 numere naturale separate prin spaţii L xg yg dx dy, cu semnificaţia din enunţ. Fişierul se termină cu o linie pe care sunt scrise 5 valori 0 (acesta este ultimul set de date de test).

Date de ieşire

Fişierul de ieşire greiere.out va conţine câte o linie pentru fiecare set de date de test. Pe linia i va fi scris numărul minim de salturi pe care trebuie să le facă greierele până ajunge într-un pătrat alb pentru setul de date de pe linia i a fişierului de intrare. Dacă pentru setul de date respectiv nu există soluţie, în fişierul de ieşire se va scrie valoarea -1.

Restricţii

  • 0 <= L <= 1000
  • 0 <= xg, yg <= 100000
  • 0 <= dx, dy <= 2000
  • În fişierul de intrare există cel mult 100 de seturi de date de test.
  • Pentru setul de date 0 0 0 0 0 se va afişa în fişierul de iesire 0.

Exemple

greiere.in greiere.out
20 4 3 3 2
25 0 0 5 25
4 1 1 2 3
0 0 0 0 0

6
-1
3
0


prof. Emanuela Cerchez
Colegiul Naţional "Emil Racoviţă" Iaşi
emanuela.cerchez@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, stelar, atelier, secv9, ny, radical, arbgraf, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, stele, covor, subm, mess, secvnumber, cladire, ssmax, parcela, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre structura repetitiva: cifre1, super, schimb, jeton, descfib, taxe, romane, mobile, cuburi3, tzigla, morse, powerpuff, multimi, ucif, tabel, ocr, numere7, cifre2, piramida, vraji, reforma, cartonas, cabina, case, desen2, exponent, cifre3, concurs3, joc13, reactivi, vanatoare, submult, paranteze, tort, copaci1, ogorul, puncte3, efort, muzeu, smith, biliard, palc, prod3, fazanr, cadouri, bursa, meteo, prodmax, zar, tren4, lego, maraton1, cluburi, domino1, jump, alo, cifra1, case1, brazi, divizori, pitag, porumb, secv9, divk, rachete, pin, sumacifre, aritm, psp, triplu, triunghi3, cmmdcsecv, ssmax, ape, furnici1, domino2, acoperire1, ore, pegals, b2k, sumdivprod, subsecvmax, dale, bancomat, sume4, alice, porumb1, albine2, culegere, stele1, medalion, cifreco, meteo1, unupatru, xyz, vistiernic, chibrituri, bete1, greieri, interviu, prieten, prize, conturi, numere12, martisoare, piramide, pagini, punctul, tablita, pavare1, ordine, covor1, speciale, echer, numere13
Despre structura alternativa: cuburi3, multimi, ucif, tabel, ocr, numere7, cabina, exponent, cifre3, concurs3, joc13, reactivi, vanatoare, submult, visul, paranteze, copaci1, ogorul, muzeu, timer, triunghi1, piatra, numerus, ape, domino2, ore, pegals, alun, chibrituri, interviu
Software recomandat
surse trimise | ajutor