#1105
TG
Fie un număr natural N
. Spunem că (a, b, c)
este un triplet geometric limitat de N
, dacă a
, b
și c
sunt trei numere naturale astfel încât 1 ≤ a < b < c ≤ N
și \( b = \sqrt {a \cdot c} \).
Să se determine numărul tripletelor geometrice limitate de numărul natural N
.
ONI 2014, Clasa a IX-a
#1106
Progresie
Să se determine un șir strict crescător, cu lungimea N
, format din numere naturale nenule, \( 1 ≤ a_1 < a_2 < a_3 < … < a_N ≤ [2 \cdot N \cdot \sqrt{N}] \), cu proprietatea că oricare trei termeni distincți ai șirului nu sunt în progresie aritmetică, adică pentru oricare numere naturale i
, j
şi k
cu 1 ≤ i < j < k ≤ N
, este îndeplinită condiţia: \( a_i + a_j \neq 2 \cdot a_j \). Prin [x]
s-a notat partea întreagă a lui x
.
De exemplu, pentru N = 5
, cel mai mare termen al șirului va trebui să fie mai mic sau egal cu \( [2 \cdot 5 \cdot \sqrt{5} ] \), adică a
N
≤ 22
, deci o soluție este: 1, 2, 4, 5, 10
.
ONI 2014, Clasa a IX-a
#1206
Placa
Un gard este format din mai multe plăci dreptunghiulare. Fiecare placă este, la rândul ei, construită din NxM
cărămizi. Una dintre plăci ridică o problemă, deoarece este deteriorată. Placa este reprezentată pe hârtie cu ajutorul unei matrice cu N
linii și M
coloane, numerotate de la 1
la N
, respectiv de la 1
la M
. Matricea conține doar valori 0
și 1
, și respectă următoarele reguli:
1
indică prezența în aceea poziție a unei cărămizi, iar un element egal cu 0
indică absența ei;1
și linia N
conțin numai valori egale cu 1
, pentru că marginea de sus și cea de jos a plăcii este intactă;1
, situat în interiorul matricei, se poate ajunge pe linia 1
sau pe linia N
sau pe amândouă, mergând doar în sus sau doar în jos, parcurgând numai valorile egale cu 1
;1
).Se dorește modificarea plăcii și pentru aceasta se pot șterge din matrice maximum K
coloane alăturate. După ștergere se alipesc coloanele rămase și se deplasează pe verticală partea de sus a plăcii spre cea de jos, până când se va forma o coloană stabilă.
Să se determine înălțimea minimă Hmin
pe care o poate avea placa ștergând cel mult K
coloane alăturate. Identificați numărul minim de coloane alăturate care trebuie șterse pentru a obține înălțimea Hmin
.
ONI GIM 2014, Clasa a VII-a
#1186
Risc
Pentru a participa la un concert, n
persoane s-au așezat la coadă pe un singur rând în așteptarea deschiderii casei de bilete. Înălțimile celor n
persoane sunt toate distincte. Pe baza acestei informații cruciale, agenții de securitate au decis ca din motive de … securitate, ordinea persoanelor care așteaptă la coadă trebuie schimbată în funcție de înălțimile lor.
Astfel, agentii de pază vor alege, pe rând, câte o persoană și o vor trimite la sfârșitul rândului. După fiecare operație de tipul acesta, să-i spunem “de mutare”, rândul se restrânge, ocupându-se poziția rămasă liberă. Strategia agenților de pază este aceasta: la terminarea tuturor operațiilor de mutare, riscul minim de securitate se obține dacă toate persoanele aflate în dreapta persoanei celei mai înalte vor fi mai înalte decât cele aflate în stânga persoanei cele mai înalte. În plus, înalțimile persoanelor vor fi crescătoare până la poziția k
a persoanei celei mai înalte și descrescătoare după poziția k
.
Mai exact: dacă h[1]
, h[2]
, …, h[n]
sunt înălțimile persoanelor după finalizarea operațiilor de mutare, atunci: există o poziție k
, cu 1 ≤ k ≤ n
astfel încât h[1] < h[2] < ... h[k-1] < h[k] > h[k+1] > … > h[n-1] > h[n]
și în plus h[i] < h[j]
pentru oricare i < k
și k < j
.
Deoarece o asemenea logică este greu de combătut, iar agenții nu au aerul că vor să glumească, persoanele care așteaptă la coadă vor accepta toate mutările impuse de către aceștia.
Cunoscând numărul de persoane n
și înălțimile h[1]
, h[2]
, …, h[n]
ale acestora să se scrie un program care determină :
1. Poziția persoanei celei mai înalte în rândul inițial, în cazul în care nu sunt necesare operații de mutare.
2. Numărul minim de mutări necesare pentru ca rândul de persoane să prezinte un risc minim de securitate.
ONI 2015, Clasa a IX-a
#1188
Casa
În această poveste este vorba despre o casă cu mai multe camere. O cameră are forma unui pătrat de latură 1
. Dacă două camere au un perete comun, atunci se poate trece dintr-o cameră în alta. Casa nu are neapărat formă dreptunghiulară.
O asemenea casă poate fi descrisă în povestea noastră în două moduri:
0
şi 1
în care există N
valori egale cu 1
, ce corespund camerelor, iar prima linie, ultima linie, prima coloană şi ultima coloană au cel puţin un element egal cu 1
.N-1
perechi (a[i], b[i]) 1≤i<n
în care a[i]
din {1,2,…,i}
şi b[i]
din {N, S, E, V}
. Camerele vor fi numerotate de la 1
la n
. Perechea (a[i], b[i])
precizează poziţia camerei i+1
faţă de camera a[i]
: E
înseamnă la dreapta (est), N
deasupra (nord), V
la stânga (vest), S
dedesubt (sud). Observaţi că pentru prima cameră nu există nicio precizare!De exemplu, casa de mai sus poate fi descrisă de şirul (1 E) (2 E) (2 S) (3 S)
, adică a doua cameră e “lipită” la est de prima cameră, următoarea (a treia) la est de camera 2, a patra la sud de camera 2, iar ultima la sud de camera 3.
Cerința
ONI 2015, Clasa a IX-a
#1190
Sipet
Un arheolog a găsit un sipet interesant. După ce l-a deschis cu grijă, a constatat cu surprindere că sipetul conține bănuți de aur. Uitându-se mai atent a mai găsit ceva: un pergament ascuns într-un compartiment secret al sipetului, cu un text scris într-o limbă antică, pe care, din fericire, arheologul o cunoștea. Din text a reieșit că un grup de negustori foarte bogați a vrut să ascundă în mare secret averea breslei lor, formată din monede de aur, deoarece se prevestea un război cumplit. Negustorii știau că există șanse ca această comoară să fie găsită și confiscată de dușmani, deci s-au sfătuit cum e mai bine să procedeze, cum să ascundă comoara. Arheologul a reușit să deducă din text următoarele:
a) Cele N
monede, care formau averea breslei, au fost împărțite în maximum trei feluri de grămezi, formate din p1
, p2
și p3
bănuți, p1
, p2
și p3
fiind numere prime consecutive, p1<p2<p3
. Fiecare grămadă a fost pusă în întregime într-un sipet.
b) Este posibil să existe 0
(zero) grămezi formate din p1
sau p2
sau p3
monede, scopul fiind să se obțină o împărțire în care numărul monedelor rămase nedistribuite să fie minim, iar dacă există mai multe posibilități, se alege aceea pentru care numărul de grămezi este mai mare. Dacă există mai multe astfel de soluții, se consideră corectă oricare dintre ele.
c) Monedele care nu au putut fi distribuite conform regulilor stabilite, au fost donate bisericii.
Scrieți un program care determină numărul maxim S de sipete și numărul sipetelor cu p1, p2 respectiv p3 monede, precum și suma donată bisericii.
ONI 2015, Clasa a IX-a
#1226
Nebuni
Pe o tablă de şah cu N
linii şi N
coloane sunt plasaţi M
nebuni. După cum se ştie de la jocul de şah, nebunii atacă doar în diagonală.
O poziţie de pe tabla de şah este considerată sigură dacă nu este atacată de niciun nebun aflat pe tablă.
Scrieţi un program care să determine numărul de poziţii sigure de pe tabla de şah.
ONI GIM 2015, Baraj
#1228
SSK
Manole a învățat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A
cu N
linii și M
coloane. El numerotează liniile de la 1
la N
și coloanele de la 1
la M
. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A
. Șirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător.
Prin subtablou el înțelege o zonă dreptunghiulară din matricea A
, identificată prin colțul stânga-sus (x1,y1)
şi colţul dreapta-jos (x2,y2)
, elementele subtabloului fiind toate elementele A[i][j]
pentru care x1≤i≤x2
şi y1≤j≤y2
. Suma unui subtablou este suma tuturor elementelor sale.
ONI GIM 2015, Baraj
#2170
dreptc
n
puncte colorate dispuse în plan. Ele sunt identificate prin coordonatele lor întregi, pe axele OX
și OY
. Fiecare punct are asociat un număr natural între 1
și C
reprezentând codul culorii lui. Un dreptunghi se numește corect dacă îndeplinește simultan următoare condiții:
n
puncte date;OX
, OY
;Să se determine numărul maxim de dreptunghiuri corecte care se pot forma cu cele n
puncte din plan.
OJI 2007
#1962
Vecini Buni
Se consideră matricea A
ale cărei elemente pot avea doar valorile 0
sau 1
și în care numerotarea liniilor și numerotarea coloanelor începe de la 1
. Pentru un element oarecare al matricei, definim noţiunea de vecin ca fiind acele elementele din matrice aflate în imediata sa apropiere, pe una dintre direcțiile orizontală, verticală sau pe cele două diagonale. Un vecin bun al elementului A[i][j]
este un vecin care are aceeaşi valoare cu A[i][j]
.
Dându-se matricea A, să se determine numărul maxim de vecini buni pe care îi are unul dintre elementele matricei precum și numărul de elemente care au acest număr maxim de vecini buni.
OJI 2009, Clasa a VIII-a