#1690
Undo
XORin este nemulțumit de problemele primite în prima zi de concurs de la Olimpiada Națională de Informatică și decide astfel să se implice în comisie. În scurt timp devine specialistul comisiei în generarea de teste formate din șiruri de numere. Din când în când el trebuie să adauge sau să șteargă elemente din șir. Câteodată el decide să readauge dintre elemente șterse anterior. Fie șirul de numere a=(a[1], a[2], … ,a[N])
și N
numărul de elemente din șir după fiecare operație.
Astfel el are de realizat următoarele operații pornind de la un șir vid:
x
;x
elemente din șir;x
elemente șterse. Dacă, de exemplu, în operația anterioară de ștergere a unui număr y
de elemente, am șters elementele a[N-y+1]
, a[N-y+2]
,…, a[N]
, iar acum urmează o operație de readăugare a x
elemente, vor fi adăugate în ordine elementele a[N-y+1]
, a[N-y+2]
,…, a[N-y+x]
la sfârșitul șirului.Din când în când XORin își pune următoarea întrebare: de câte ori există valoarea x
în șir?
ONI 2016, clasa a X-a
#1856
Taxe2
Într-o ţară în care corupţia este în floare şi economia la pământ, pentru a obţine toate aprobările necesare în scopul demarării unei afaceri, investitorul trebuie să treacă prin mai multe camere ale unei clădiri în care se află birouri.
Clădirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pătrat de dimensiune n•n
. Pentru a facilita accesul în birouri, toate camerele vecine au uşi între ele. În fiecare birou se află un funcţionar care pretinde o taxă de trecere prin cameră (taxă ce poate fi, pentru unele camere, egală cu 0
). Investitorul intră încrezător prin colţul din stânga-sus al clădirii (cum se vede de sus planul clădirii) şi doreşte să ajungă în colţul opus al clădirii, unde este ieşirea, plătind o taxă totală cât mai mică.
Ştiind că el are în buzunar S
euro şi că fiecare funcţionar îi ia taxa de cum intră în birou, se cere să se determine dacă el poate primi aprobările necesare şi, în caz afirmativ, care este suma maximă de bani care îi rămâne în buzunar la ieşirea din clădire.
OJI 2003
#4242
perle
Graniţa nu se trece uşor. Asta pentru că Balaurul Arhirel (mare pasionat de informatică) nu lasă pe nimeni să treacă decât după ce răspunde la nişte întrebări. În acea ţară există trei tipuri de perle normale (le vom nota cu 1
, 2
şi 3
) şi trei tipuri de perle magice (le vom nota cu A
, B
şi C
). Perlele magice sunt deosebite prin faptul că se pot transforma în alte perle (una sau mai multe, normale sau magice). Să se determine pentru fiecare şir de intrare dacă se poate obţine prin transformările de mai sus sau nu (alegând orice primă perlă magică, la fiecare şir).
OJI 2004, Clasa a X-a
#2390
rj
În ultima ecranizare a celebrei piese shakespeariene Romeo și Julieta trăiesc într-un oraș modern, comunică prin e-mail și chiar învață să programeze. Într-o secvență tulburătoare sunt prezentate frământările interioare ale celor doi eroi încercând fără succes să scrie un program care să determine un punct optim de întâlnire.
Ei au analizat harta orașului și au reprezentat-o sub forma unei matrice cu N
linii şi M
coloane, în matrice fiind marcate cu spațiu zonele prin care se poate trece (străzi lipsite de pericole) şi cu X
zonele prin care nu se poate trece. De asemenea, în matrice au marcat cu R
locul în care se află locuința lui Romeo, iar cu J
locul în care se află locuința Julietei. Ei se pot deplasa numai prin zonele care sunt marcate cu spaţiu, din poziţia curentă în oricare dintre cele 8
poziţii învecinate (pe orizontală, verticală sau diagonale).
Cum lui Romeo nu îi place să aştepte şi nici să se lase aşteptat n-ar fi tocmai bine, ei au hotărât că trebuie să aleagă un punct de întâlnire în care atât Romeo, cât şi Julieta să poată ajunge în acelaşi timp, plecând de acasă. Fiindcă la întâlniri amândoi vin într-un suflet, ei estimează timpul necesar pentru a ajunge la întâlnire prin numărul de elemente din matrice care constituie drumul cel mai scurt de acasă până la punctul de întâlnire. Şi cum probabil există mai multe puncte de întâlnire posibile, ei vor să îl aleagă pe cel în care timpul necesar pentru a ajunge la punctul de întâlnire este minim.
Scrieţi un program care să determine o poziţie pe hartă la care Romeo şi Julieta pot să ajungă în acelaşi timp. Dacă există mai multe soluţii, programul trebuie să determine o soluţie pentru care timpul este minim.
OJI 2004
#2429
matrice9
Fie A
o matrice dreptunghiulară de numere întregi cu N
linii numerotate de la 1
la N
şi M
coloane numerotate de la 1
la M
. În matricea A
oricare două elemente consecutive de pe aceeaşi linie sunt distincte.
Se defineşte un şir valid de numere întregi ca fiind fie un şir crescător, fie un şir descrescător, fie un şir crescător concatenat cu un şir descrescător, fie un şir descrescător concatenat cu unul crescător. Exemple de şiruri valide sunt: 1 2 3 7
, 8 5 2 1
, 3 5 6 2
, 4 1 5 6
.Se defineşte o submatrice a lui A
de coordonate (l1
, c1
, l2
, c2
) ca fiind matricea formată din toate elementele A(i,j)
, cu l1 ≤ i ≤ l2
şi c1 ≤ j ≤ c2
. O submatrice a lui A
este validă dacă liniile sale sunt şiruri valide.
Atenţie! O submatrice validă poate avea pe o linie un şir crescător de numere, pe a doua un şir descrescător, pe a treia un şir crescător concatenat cu unul descrescător etc. Deci, liniile unei submatrice valide nu trebuie să fie neapărat şiruri de acelaşi tip.
Aria unei submatrice este egală cu numărul de elemente din care este formată submatricea. Se cere să se găsească o submatrice validă a lui A
de arie maximă.
ONI 2006
#2249
panouri
Pe autostrada Soarele Estului sunt aşezate de-a lungul şoselei, la distanţe egale, panouri publicitare ale unor firme. Aceeaşi firmă, poate să aibă mai multe panouri publicitare şi fiecare panou poate să apară în mai multe locuri. Panourile se identifică prin numere naturale, numărul total de panouri fiind N
. Firma X Corporation are panouri de T
tipuri diferite. Firma a primit aprobarea construirii unui mare complex turistic în apropierea autostrăzii; de aceea, pentru alegerea locului, este interesată şi de următorul aspect: care este lungimea minimă de şosea, în care se pot întâlni, toate cele T
tipuri de panouri publicitare ale firmei, indiferent de ordinea acestora, şi indiferent dacă între ele se mai interpun sau nu panouri ale altor firme. Cunoscând N
– numărul total de panouri de la marginea autostrăzii şi ordinea amplasării lor, ca şi cele T
tipuri de panouri amplasate de firmă, determinaţi numărul minim de intervale dintre două panouri între care firma X Corporation îşi regăsește toate panourile sale.
ONI 2006
#2861
puncte4
Zăhărel a desenat pe o foaie de hârtie N
puncte în plan. Curios din fire, şi-a ales încă M
puncte pe axa OX
şi s-a întrebat pentru fiecare dintre cele M
puncte de pe axa Ox
care dintre cele N
puncte este cel mai apropiat (situat la distanță minimă). Se consideră că distanța dintre două puncte (x1, y1)
şi (x2, y2)
este (x1-x2)
2
+ (y1-y2)
2
. Scrieți un program pentru Zăhărel care să determine pentru fiecare dintre cele M
puncte de pe axa OX
, care este distanța la cel mai apropiat punct dintre cele N
desenate pe hârtie.
ONI 2007 Baraj
#3404
castel3
Înspăimântătorii tăi luptători au răpit-o pe Prinţesa Ghiocela şi au închis-o în castelul tău de pe vârful Muntelui Pleşuv. Deoarece eşti un geniu malefic, te-ai hotărât să îi oferi prinţesei iluzia unei şanse de evadare.
Castelul tău are forma unui caroiaj cu M
linii şi N
coloane. Cele M x N
celule ale castelului sunt numerotate de la 1
la M x N
în ordinea parcurgerii caroiajului pe linii de sus în jos, iar pe aceeaşi linie în ordinea coloanelor de la stânga la dreapta. În fiecare dintre celulele castelului ai pus câte o cheie, mai precis celula i
conţine cheia cu numărul i
. Evident, pentru a intra într-o cameră, prinţesa are nevoie de o anume cheie care permite deschiderea acesteia. Mai mult, dintr-o cameră prinţesa se poate deplasa într-un moment numai într-una dintre cele maximum patru camere adiacente pe orizontală şi verticală, doar dacă deţine cheia necesară deschiderii sale. Odată ce a intrat într-o cameră şi a obţinut o cheie, prinţesa o păstrează şi poate să o utilizeze ori de câte ori doreşte. Deşi eşti convins că prinţesa nu va scăpa din castel, eşti curios să afli câte dintre cele M x N
camere îi sunt accesibile. Date fiind dimensiunile castelului, camera în care se află iniţial prinţesa şi cheile necesare deschiderii fiecăreia dintre camere, află răspunsul la această întrebare presantă.
ONI 2007, clasa a X-a
#2649
reactii
Să considerăm o secvenţă de n
substanţe chimice \( s= s_{1}, s_{2},…,s_{n} \). Substanţele sunt numerotate distinct de la 1 la n şi fiecare substanţă apare în secvenţa s o singură dată. Determinaţi pentru o secvenţă dată de substanţe, dacă în urma reacţiilor ce se pot produce conform regulilor din enunţ rezultă o substanţă stabilă.
ONI 2009
#3564
copaci1
Se consideră n
copaci de diferite înălţimi, aflaţi în linie dreaptă la distanţe egale, numerotaţi de la 1
la n
. Pentru fiecare copac se cunoaşte înălţimea sa \( {H}_{i} \). Cum şi copacii simt nevoia să socializeze, fiecare dintre ei are prieteni printre ceilalţi copaci. Prietenii oricărui copac i
se pot afla atât la stânga, cât şi la dreapta sa. Relaţiile de prietenie sunt definite în felul următor: pentru fiecare copac i
considerăm un şir \( {d}_{1}, {d}_{2}, …, {d}_{x} \) reprezentând prietenii copacului i
situaţi în dreapta sa şi un şir \( {s}_{1}, {s}_{2}, …, {s}_{y} \) reprezentând prietenii copacului i
situaţi în stânga acestuia. Copacii din cele două şiruri corespunzătoare unui copac i
formează împreună lista prietenilor acestuia. Determinaţi în câte moduri se pot alege 3
copaci diferiţi dintre cei n
cu proprietatea că, oricum am alege 2
copaci dintre cei 3
, fie aceştia copacul A
şi copacul B
, atunci A
este prieten cu B
şi B
este prieten cu A
.
ONI 2012, Clasa a IX-a