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

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


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

Într-un parc de distracţii s-a introdus un joc nou: tir cu arcul. Participanţii trebuie să ţintească de la o anumită distanţă baloane fixate pe un şir de stâlpi de diferite înălţimi egal distanţaţi unul de altul. Dacă un balon este spart, stâlpul care l-a susţinut se va elimina, iar stâlpii rămaşi se vor repune la distanţe egale. Dacă un arcaş reuşeşte prin acest procedeu ca trei baloane consecutive în şir să fie pe o aceeaşi dreaptă, atunci el va câştiga un premiu consistent.
În exemplul de mai jos din două lovituri se poate obţine premiul:



Patronul a mizat pe faptul că vizitatorii vor fi începători în folosirea arcului sau, chiar dacă ar şti să ţintească bine, nu vor avea o strategie bună pentru eliminarea stâlpilor corespunzători.
Dar când a apărut primul arcaş care era şi profesionist şi deştept, casieria s-a golit. De atunci patronul s-a hotărât serios să pună stâlpii într-o ordine care să nu permită obţinerea premiului.

Cerinţă

Cunoscând numărul n al stâlpilor şi înălţimile lor h1, h2, ..., hn, să se determine, dacă este posibil, o aranjare a lor, astfel încât să fie imposibilă aducerea a trei baloane pe o dreaptă.

Date de intrare

Fişierul arctir.in conţine pe prima linie numărul n al stâlpilor. Următoarea linie conţine n numere naturale separate prin câte un spaţiu, reprezentând şirul înălţimilor stâlpilor h1, h2, ..., hn.

Date de ieşire

Fişierul arctir.out conţine o singură linie pe care se găsesc înălţimile stâlpilor în ordinea din aranjarea determinată conform cerinţelor, separate prin câte un spaţiu, sau numărul -1 dacă nu există o astfel de aranjare.

Restricţii

0 < n ≤ 5000
0 < hi ≤ 10 000 000, 1≤i≤n
• Diferenţa dintre înălţimea maximă şi înălţimea minimă dintre doi stâlpi nu depăşeşte 30000.
• Baloanele sunt punctiforme.
• Pot exista mai multe soluţii, orice soluţie corectă se acceptă.

Exemple

arctir.inarctir.outExplicaţii
6 2 4 4 3 6 3 4 4 2 3 6 3 Oricum am vrea să eliminăm elemente interioare, nu vom obţine trei numere care să corespundă a trei baloane pe o dreaptă.

autor: Prof. Zoltan Szabo
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Finala .campion 2010: expo, mine, popic, guess, orientare, activ, secvbiti
De acelaşi autor: balanta, bonuri, cub, magic, magic2, munte, euclid, banda, biliard, fractie1, fotbal, orientare, rege, fibo1, piatra, war, aritm, ssmax, sirmax, ikebana, punctfix, domino2, lant1, parc1, cubulete, biperm, triunghi6, stiva1
Despre sortare: harta, index, sort, concurs, baby, patrate2, repeat, turist, 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, 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
Despre Inducţie matematică: 2sir, h, gray, poligon, patrate1, set, descfib, suma1, mutare, sir1, prieteni1, excursie1, galax, prieteni2, peg, perfect, borcane, regine, comoara2, domino, partitie, acoperire1, xpn
Despre generare: taste, pluricex, balbe, magic3, formule, grup, zmeu, nr01, reteta2, playlist, pizza1, caramele, caini, tvshow, adevar, prime1, hexa, premii1, carti2, bile4, hof, matrx, cubinvers, guess, minmax, stele, tablou1, adunscad, sumprod, prisme, operatii1, expeval, triburi1, optim, patru, genab, dineu, cumpanit, nkd, relatii, wb
surse trimise | ajutor