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

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


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

Oraşul Julietei este de formă pătrată şi are străzi doar pe direcţiile Nord-Sud şi Est-Vest, toate la distanţe egale şi numite ca în desen: strada verticală 0, 1, 2, 3,…, respectiv strada orizontală 0, 1, 2, 3… . Julieta locuieşte la intersecţia străzilor: verticală x şi orizontală y (pozitia (x,y)). Romeo se află în colţul de Sud-Vest al oraşului (poziţia (0,0)) şi doreşte să ajungă la Julieta, nu ştim exact de ce, dar este treaba lui. Peste toate necazurile cunoscute ale bietului băiat, mai apar şi altele:
- oraşul urcă în pantă spre Nord, ceea ce îngreunează mersul în acea direcţie;
- nu poate merge decât spre Nord sau spre Est, pentru că dacă “ea” l-ar vedea mergând spre Vest sau spre Sud, atunci ar crede că el se îndepărtează definitiv de ea.
Numim segment elementar distanţa dintre două străzi paralele alăturate.
Dacă Romeo merge spre Est, atunci el consumă 1J (J=joule=o unitate de energie) pentru fiecare segment elementar parcurs. Din cauza pantei, dacă merge spre Nord k segmente elementare consecutive, consumă (1+2+3+…+k) J.
Romeo vrea să ajungă la Julieta (mergând în condiţiile de mai sus) cu un consum minim de energie.



De exemplu: dacă datele sunt: x=4 şi y=3, atunci desenul alăturat prezintă un drum posibil (dar nu cu consum minim de energie). În desen, avem un prim segment elementar orizontal (consum=1J), apoi spre Nord două segmente elementare (consum: 1+2 = 3J). Urmează 3 segmente spre Est (consum: 1+1+1 = 3J) şi ultima porţiune de un segment vertical (consum: 1J). Total consum energie: 1+3+3+1=8J.

Cerinţă

Scrieţi un program care citeşte x şi y şi care afişează numărul minim de J consumaţi pentru tot drumul de la poziţia (0,0) la poziţia (x,y), mergând doar în direcţiile precizate.

Date de intrare

Fişierul de intrare romeo.in conţine numerele x şi y pe prima linie, separate de un spaţiu.

Date de ieşire

Fişierul de ieşire romeo.out conţine o singură linie cu numărul de J consumaţi pentru distanţa totală parcursă din poziţia de plecare până în cea finală.

Restricţii

x şi y sunt numere naturale;
0<=x,y<=40000
Fiecare linie din fişierul de intrare şi din fişierul de ieşire se încheie cu marcaj de sfârşit de linie.

Exemple

romeo.inromeo.outExplicaţii
3 2 5


Datele de intrare indică un oraş ca în desen. Un drum posibil (el nu este unic) este dat de linia îngroşată. Primul segment vertical consumă 1J, porţiunea orizontală 3J şi ultimul segment vertical (cel din dreapta), încă 1J, deci vom afişa numărul 5, care reprezintă 1J+3J+1J=5J.

autor: Prof. Dan Grigoriu
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2005: baschet, ingerasi, numar1, prieteni, robinson, aritma, cezar, cuburi2, joc8, bifo, joc9, pal, seceta, antena, avere, joc11, paianjen, suma2, vizibil, masina3, csir, lsort, patrat, ziduri, anticip, bsir, evantai, galax, spion, texan
De acelaşi autor: lacuri, robinson, sir4, gardul, gaina, cub3
Despre divizibilitate: celule, cai, 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, 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 matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre sisteme de ecuatii liniare: xor, bcolor, magic4, butoane, mofocarburi, gxor
Chestionare recomandate
surse trimise | ajutor