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

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


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Strada principala a orasului Bitland este un dreptunghi cu vârfurile în punctele (0, 0), (0, 2), (N, 2), (N, 0), acoperit 2xN cu dale cu latura 1m.

       
       

Noaptea în Bitland a viscolit, ca urmare unele dintre dale sunt acoperite cu zapada.
Masina pentru curatarea drumurilor are o lama cu lungimea 1 m. Initial masina este amplasata astfel încât extremitatile lamei au coordonatele (K, 0) si (K, 1). Intr-o secunda masina se deplaseaza cu exact 1 m, curatind zapada de pe intreaga dala parcursa. Daca este necesar, masina se poate deplasa si lateral (mai exact lama poate ajunge din pozitia (K,0)-(K,1) in pozitia (K,1)-(K,2) sau invers). Deplasarea in laterala se realizeaza instantaneu.

Cerinta
Scrieti un program care sa determine numarul minim de secunde necesare pentru curatarea zapezii de pe strada principala.

Date de intrare
Fisierul de intrare zapada.in contine pe prima linie doua numere naturale N K separate prin spatiu, cu semnificatia din enunt. Urmatoarele N linii contin câte 2 numere din multimea {0, 1} separate prin cate un spatiu (primul numar de pe linia i+1 este 1 daca patratelul cu coltul stanga-jos (i,0) este acoperit cu zapada si 0 in caz contrar; al doilea numar este 1 daca patratelul cu coltul stanga-jos (i,1) este acoperit cu zapada si 0 in caz contrar).

Date de iesire
Fisierul de iesire zapada.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul minim de secunde necesare pentru deszapezirea strazii principale.

Restrictii si precizari
1 <= N <= 1000
0 <= K <= N

În timpul lucrului masina nu poate parasi strada.
Pozitia finala a masinii poate fi oricare.

Exemplu

zapada.in zapada.out zapada.in zapada.out

4 0
0 0
1 1
0 0
0 1

6 4 0
0 0
0 1
0 0
1 1
5

prof. Sergiu Corlat
Liceul Moldo-Turc Chisinau
Contact:scorlat@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2007: perechi, teanc, index, light, copaci, teren, pizza, grupe, cod, ecran, drum, soldati, factura, palma, decript, lbd, aven, cs, h, trenuri, sort, spam, complex, parent, holo, tren2, gray, siruri, arce, pasi, cifre, mgo, firma, joc, cartonase, vikingi, anagrame, balbe, vecini, balaur, tribile, conflicte, criptmat, mesaj, maxim, magic3, desen, plimbare, cutie, patrate, party, vagoane, robot, astre, trains, numere2, friends, tricouri, furtuna, net, baby, scaune, 3d, axa, bile2, vmem, pahare, termen, sablon, cuvinte, excursie, hd, pajura, pc, sir, cadere, pioni
De acelaşi autor: nice, fib, atac, mere, ff, patrate, astre, baby, pendul, unu, dragon, placi, druid, bete, comori, ploaia, lot, arcas, factk, robot1, kalah, cetati, palc, expo, porumb, universitate, safeu, capra, zuma, gsm, megascoala
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, 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, zumzi, 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
surse trimise | ajutor