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

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


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

Harta unui continent poate fi văzută ca un dreptunghi având înălţimea de M unităţi, iar lăţimea de N unităţi. Colţul din stânga sus al hărţii are coordonatele (0,0), iar colţul din dreapta jos are coordonatele (M,N). Coordonatele oraşelor de pe hartă sunt întotdeauna numere întregi, adică sunt de forma (l,c) cu 0≤l≤M, reprezentând linia şi 0≤c≤N, reprezentând coloana. În unul din oraşele de pe hartă se găseşte un turist. El doreşte să pornească într-o expediţie deosebită. A decis să plece într-o anumită direcţie, şi să păstreze aceea direcţie pănă ajunge la marginea continentului (a hărţii) unde se încheie expediţia sa. Doreşte însă să aleagă acea direcţie care îl asigură că pe drumul său va trece prin cât mai multe oraşe.

Cerinţă

Dându-se dimensiunile hărţii, coordonatele oraşului în care se găseşte turistul şi coordonatele tuturor celorlalte oraşe de pe hartă, se cere să se determine numărul maxim de oraşe pe care le va vizita turistul.

Date de intrare

Pe prima linie a fişierului de intrare turist.in se găsesc numerele naturale M N separate printr-un spaţiu reprezentând dimensiunile hărţii. A doua linie a fişierului conţine două numere naturale l şi c separate printr-un spaţiu, reprezentând poziţia iniţială a turistului pe hartă. Linia a treia a fişierului conţine un număr natural k, reprezentând numărul de oraşele de pe hartă, diferite de oraşul în care se găseşte turistul.
Pe următoarele k linii se găsesc câte două numere naturale, separate printr-un spaţiu, reprezentând coordonatele câte unui oraş de pe hartă, altele decât cel în care se găseşte turistul.

Date de ieşire

Fişierul de ieşire turist.out va avea pe prima sa linie, un număr natural reprezentând numărul maxim de oraşe pe care le vizitează turistul.

Restricţii

1 ≤ M ≤ 1000
1 ≤ N ≤ 1000
1 ≤ k ≤ 2000

Exemple

turist.inturist.outExplicaţii
5 10 3 2 7 0 0 0 8 1 6 2 2 2 4 3 7 4 5 3 Datele de intrare corespund hărţii din figura următoare. Traseul ales este cel indicat de linia trasată.



autor: Prof. Carmen Popescu
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la OJI 2008: pluricex, concurs, piata, iepuri, numar
De acelaşi autor: light, sort, iepuras, pahare, arthur, pento, cod2, game, ambigram, jokes, trecere, paianjen, zumzi, cifru3, pamant, pixy, triburi, culori1, cifre5, arc
Despre divizibilitate: celule, cai, trei, ruleta, an, factori, perechi, anagrame, axa, perspic, scara, programs, iepuras2, fry, policefm, 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
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, 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
Despre sortare: harta, index, sort, concurs, baby, patrate2, repeat, bacan, toys, scor2, chimie2, politics, submat, scoici, ham, jokes, trecere, multiplu, paralel, tvshow, sirag1, tabara, munte, sport, puncte1, sume1, schi, granita, tren3, sant1, volei1, poze, maroco, dreptc, dist1, tir1, control, mosia, popas, reactivi, siruri1, coach, anag, matrice4, sume2, urgenta, basm, vot, balcon, joc14, cerc, k1, segm, calorii, ordonare, greutati, arctir, macheta, poligon4, centrala, robot4, lcdr, maxviz, sdmin, qtri, arme, flori1, parc1, mijloc, bile6, proiecte, patru, drept2, subsecvente, cursa1, eoliene, vintage, dreapta, riglef, rebus1, rascoala, zimeria, praslea, aperm, unudoi, gropi1, piscina, restaurare, cabana, culori3
Chestionare recomandate
surse trimise | ajutor