#3390
turnuri2
Renumitul arhitect Prăbuşilă doreşte să construiască unul din cele mai interesante turnuri de pe planetă. Acest turn, în mod cu totul deosebit, va avea etaje de diverse lăţimi, între 1
şi 100
, numere întregi. Prăbuşilă s-a hotărât deja ce dimensiune va avea fiecare din etajele turnului, dar nu şi cum să le aşeze pe orizontală. El ar dori mai întâi să ştie câte variante are.
ONI 2004 clasele XI-XII
#2544
materom
Scrieţi un program care să determine în conformitate cu decizia directorului, diferenţa în modul dintre suma punctajelor de la limba română ale elevilor din echipa LNA şi suma punctajelor la matematică ale elevilor din echipă, precum şi suma tuturor punctajelor elevilor din echipa LNA.
ONI 2004, clasa a X-a
#2426
cuvinte8
Balaurul Arhirel se decide să înveţe biologie, aşa că doreşte să cumpere manualul de clasa a X-a. Din păcate, acesta nu se mai găsește pe piaţă, dar Balaurul reuşeşte să găsească o copie la un prieten. După ce începe să citească, Balaurul Arhirel observă că există greşeli în copia prietenului, iar într-un impuls de energie, se hotărăşte să corecteze manualul. El are la dispoziţie un dicţionar de M
cuvinte dintre care trebuie să extragă variante pentru cuvântul greşit. Asupra cuvântului greşit balaurul poate să facă următoarele schimbări în așa fel încât acesta să ajungă la o variantă din dicționar:
– poate șterge o literă;
– poate insera o literă;
– poate schimba o literă în altă literă.
Totuși, Balaurul Arhirel este leneş, aşa că nu doreşte să opereze mai mult de K
schimbări în cuvântul greșit pentru a-l aduce la o formă corectă (existentă în dicționar).
Ajutaţi-l pe Balaurul Arhirel să afle care dintre cuvintele din dicţionar ar putea fi variante ale cuvântului greşit.
ONI 2004 clasa a X-a
#2428
sortari
Balaurului Arhirel nu îi plac prea mult şirurile care nu sunt ordonate. Din acest motiv, nu poate să suporte permutările de N
elemente, aşa că se decide să le sorteze şi pentru asta inventează o metodă proprie de sortare.
El ia iniţial un şir S
care reprezintă o permutare de ordin N
. Caută în şirul S
cel mai mic (min
) şi cel mai mare element (max
). Să considerăm că min
se află în şirul S
pe poziţia pmin
, iar max
pe poziţia pmax
. Să notăm cu x
minimul dintre pmin
şi pmax
, iar cu y
maximul dintre pmin
şi pmax
. Şirul S
a fost astfel partiționat în alte trei şiruri, S1
, S2
, S3
care pot avea fiecare zero elemente, un element sau mai multe elemente. Şirul S1
începe la prima poziţie din şir şi se termină la poziţia x-1
. Şirul S2
începe la poziţia x+1
şi se termină la poziţia y-1
. Şirul S3
începe la poziţia y+1
şi se termină la ultima poziţie din şir.
Balaurul Arhirel mută valoarea min
la capătul din stânga al lui S
, iar valoarea max
la capătul din dreapta al şirului S
şi reia sortarea pentru fiecare din şirurile S1
, S2
, S3
.
Evident, această metodă nu va funcţiona întotdeauna pentru sortarea unei permutări.
Spre exemplu, pentru şirul S = (3 4 1 6 5 2)
, se găseşte min = 1
şi max = 6
, iar S1 = (3 4)
, S2 = ()
, S3 = (5 2)
. Se mută min
şi max
la capetele lui S
: S = (1 3 4 5 2 6)
şi se procedează la sortarea pe rând a şirurilor S1
, S2
, S3
. S1
este sortat, S2
nu are elemente, iar S3
va deveni S3 = (2 5)
. În final, S = (1 3 4 2 5 6)
.
Ajutaţi-l pe Balaurul Arhirel să afle câte dintre permutările de N
elemente pot fi sortate prin metoda sa.
ONI 2004 clasa a X-a
#2675
scara1
Domnul G are de urcat o scară cu n
trepte. În mod normal, la fiecare pas pe care îl face, el urcă o treaptă. Pe k
dintre aceste trepte se află câte o sticlă cu un număr oarecare de decilitri de apă, fie acesta x
. Dacă bea toată apa dintr-o astfel de sticlă, forța și mobilitatea lui G cresc, astfel încât, la următorul pas el poate urca până la x
trepte, după care, dacă nu bea din nou ceva, revine la “normal”. Sticlele cu apă nu costă nimic. Cantitatea de apă conținută de aceste sticle poate să difere de la o treaptă la alta.
Pe j
trepte se află câte o sticlă cu băutura energizantă. Şi pentru aceste sticle, cantitatea de băutură energizantă poate să difere de la o treaptă la alta. Să presupunem că într-una dintre aceste sticle avem y
decilitri de băutură energizantă. Dacă bea q
(q ≤ y
) decilitri dintr-o astfel de sticlă, la următorul pas G poate urca până la 2q
trepte, după care şi în acest caz, dacă nu bea din nou ceva, el revine la “normal”. Însă băutura energizantă costă: pentru o cantitate de q
decilitri consumaţi, G trebuie să plătească q
lei grei.
Pot exista trepte pe care nu se află nici un pahar, dar şi trepte pe care se află atât o sticlă cu apă cât şi una cu băutură energizantă. În astfel de situaţii, nu are rost ca G să bea ambele băuturi deoarece efectul lor nu se cumulează; el poate alege să bea una dintre cele două băuturi sau poate să nu bea nimic.
Determinaţi p
, numărul minim de paşi pe care trebuie să îi facă G pentru a urca scara, precum şi suma minimă pe care trebuie să o cheltuiască G pentru a urca scara în p
paşi.
OJI 2005, clasele XI-XII
#1747
Lacusta
Se consideră o matrice dreptunghiulară cu m
linii şi n
coloane, cu valori naturale. Traversăm matricea pornind de la colţul stânga-sus la colţul dreapta-jos. O traversare constă din mai multe deplasări. La fiecare deplasare se execută un salt pe orizontală şi un pas pe verticală. Scrieţi un program care să determine suma minimă care se poate obţine pentru o astfel de traversare.
OJI 2005, clasa a X-a
#3581
agitatie
O firmă producătoare de software organizează un interviu pentru ocuparea unui post de programator, la care s-au prezentat N
candidaţi. Aceştia sunt ordonaţi în funcţie de momentul la care şi-au trimis CV-ul şi numerotaţi cu numere consecutive de la 1
la N
. Fiecărui candidat i-a fost realizat în prealabil un profil psihologic şi i s-a determinat nivelul de agitaţie provocat de interviul care urmează să aibă loc, precum şi un sens (crescător sau descrescător) de modificare a acestui nivel. Astfel, la ora la care s-a anunţat începerea interviului (pe care o vom considera momentul 0
), fiecare candidat are un nivel de agitaţie iniţial. Pentru fiecare unitate de timp după momentul 0
şi până în momentul în care candidatul este invitat pentru interviu (până atunci el trebuind să aştepte), nivelul său de agitaţie se modifică cu 1
: pentru o parte din candidaţi nivelul creşte cu 1
unitate, iar pentru ceilalţi nivelul scade cu 1
unitate. Dacă nivelul de agitaţie a unui candidat ajunge la 0
, din acel moment, pentru fiecare unitate de timp următoare, nivelul de agitaţie va creşte cu 1
(se schimbă sensul de modificare a nivelului de agitaţie).
Să se scrie un program care să determine suma totală minimă a nivelelor de agitaţie a candidaţilor la sfârşitul interviului dacă aceștia sunt împărțiți optimal în grupuri.
ONI 2007, Clasa a IX-a
#3582
sotron1
Pe asfalt este desenat cu cretă un şotron, caroiaj format din n*n
căsuţe având aceleaşi dimensiuni (câte n
căsuţe pe fiecare din cele n
rânduri).
În fiecare căsuţă este scris câte un număr întreg din intervalul [-100, 100]
. Fiecare jucător are câte o piatră pe care o aruncă într-o căsuţă a şotronului, şi sărind într-un picior, împinge piatra din căsuţă în căsuţă, pe un anumit traseu astfel încât punctajul obţinut din suma numerelor de pe traseul parcurs să fie cât mai mare.
Numerele din căsuţele şotronului sunt scrise cu două culori albastru şi alb, astfel încât să nu existe două căsuţe alăturate (pe cele patru direcţii Nord
, Est
, Sud
, Vest
) având numere scrise cu aceeaşi culoare. Întotdeauna, prima căsuţă din primul rând al şotronului are înscris un număr de culoare albastră.
Se stabilesc apoi, următoarele reguli ale jocului:
Nord
;Est
;Să se scrie un program care să determine cel mai mare punctaj care se poate obţine jucând şotron după regulile stabilite.
ONI 2007, Clasa a IX-a
#2431
cover
Se consideră N
intervale închise, având extremităţile numere naturale cuprinse între 1
şi L
. Fiecare număr natural i
din intervalul [1, L]
are asociată o pondere c[i]
. Numim acoperire o mulţime de numere naturale cuprinse între 1
şi L
cu proprietatea că fiecare interval conţine cel puţin un element al mulţimii. Costul unei acoperiri este egal cu suma ponderilor numerelor din acoperire.
Pentru un set de intervale dat să se determine costul minim al unei acoperiri.
ONI 2007 Baraj
#2862
stiva2
Să considerăm o stivă, inițial vidă. Putem efectua următoarele operații:
push(X)
– se introduce în stivă litera X
(evident, în vârful stivei);
pop
– se extrage litera aflată la vârful stivei (operația pop se execută atunci când stiva este nevidă);
top
– se afișează litera aflată la vârful stivei (operația top se execută atunci când stiva este nevidă).
O secvență de operații este considerată corectă dacă:
- inițial stiva este vidă;
- se execută o serie de operații push
, pop
, top
, fără a executa pop
sau top
când stiva este vidă;
- la final stiva este vidă.
Utilizând secvențe corecte de operații, putem afișa diferite șiruri de caractere.
Dat fiind un șir format din litere mari, să se determine numărul minim de operații dintr-o secvență corecte care afișează șirul dat.
ONI 2008 Baraj