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

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


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

Un trunchi de con este un corp geometric obtinut prin sectionarea unui con obisnuit, cu un plan paralel cu baza si inlaturarea conului mic rezultat.
Se da un sir de trunchiuri de con, definite prin razele celor doua baze. Inaltimile nu au importanta.
Găsiti cel mai lung subsir format din suprapunerea unor trunchiuri de con, alese in ordinea din sirul dat, astfel incat oricare doua corpuri consecutive sa fie lipite perfect (bazele lipite sa fie de aceeasi raza). Un corp poate fi rotit pentru a se potrivi perfect peste baza de deasupra a corpului anterior.

Cerinţă

Scrieti un proram care sa determine lungimea maxima a subsirului construit din trunchiurile de con astfel incat conditia de lipire perfecta sa fie satisfacuta. Ordinea corpurilor din subsir trebuie sa fie aceeasi din sirul initial.

Date de intrare

Fisierul de intrare conuri.in contine pe prima linie un numar N reprezentand numarul de trunchiuri de con din sirul initial.
Urmatoarele N linii contin perechi de numere R1
R2, separate prin spatiu, reprezentand razele bazelor celor N trunchiuri de con.

Date de ieşire

Fisierul de iesire conuri.out va contine un singur numar reprezentand lungimea maxima a subsirului ce poate fi construit.

Restricţii

  • 1 <= N <= 100000
  • 1 <= R1, R2 <= 100000

Exemple

conuri.in conuri.out
5
1 5
2 4
1 2
3 4
4 1
3

Alex Palcuie
Robert Hasna
Andrei Vacaroiu
Universitatea din Bucuresti
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la InfoOltenia 2015: conjectura, copaci3, gropi1, wow
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, arbvalmax, procente, metrou
surse trimise | ajutor