Nivelul concursului: Național
http://oni2016craiova.ro/ http://www.oni2016.ro/
Grupe
Clasa a V-a Clasa a VI-a Clasa VII-a Clasa VIII-a Clasa a IX-a Clasa a X-a Clasele XI-XII Juniori Seniori#1687
Omogene
Se consideră o matrice cu L
linii și C
coloane care memorează doar valori din mulțimea {0,1,2}
. O submatrice nevidă (formată din cel puțin o linie și cel puțin o coloană) a acestei matrice o numim omogenă dacă numărul valorilor de 0
este egal cu numărul de valori de 1
și egal cu numărul valorilor de 2
.
Să se determine câte submatrice nevide omogene există.
ONI 2016, clasa a IX-a
#1704
Cercetasi
Un grup de N
cercetași, numerotați de la 1
la N
, se află în tabără la munte. Pentru ei, organizatorii au pregătit N
scaune, de asemenea numerotate de la 1
la N
, așezate în cerc, astfel încât fiecare cercetaș să aibă locul său (locul cercetașului i
este pe scaunul i
, 1≤i≤N
).
Pentru desfășurarea următoarei activități, organizatorii au decis ca M
dintre cercetași să prezinte diferite exerciții. Numărul M
este egal cu cea mai mare putere a lui 2
cu proprietatea că numărul N
de cercetași aflați în tabără se poate scrie ca sumă de M
numere consecutive în mulțimea numerelor impare. Cei M
cercetași care vor prezenta sunt cei numerotați cu numerele impare consecutive a căror sumă este N
. De exemplu, dacă N=8
, atunci M
este 2
, iar exercițiile vor fi prezentate de cercetașii numerotați cu 3
, respectiv cu 5
.
Din joacă, micii cercetași s-au așezat pe scaune la întâmplare. Organizatorii au nevoie pentru a desfășura activitatea ca cel puțin cei M
cercetași care vor prezenta exercițiile să se afle pe locurile lor. Pentru aceasta, o parte dintre cercetași trebuie să-și schimbe locul și organizatorii invită micii cercetași să participe la jocul numit ”Mutare”. Acest joc se desfășoară astfel: unul dintre cercetașii care nu se află pe locul lor se ridică și merge în interiorul cercului. Cercetașul numerotat cu numărul scaunului rămas liber își va ocupa locul, iar locul ocupat de el anterior rămâne astfel liber. Jocul continuă până când scaunul cercetașului aflat în interiorul cercului se eliberează și el se așază pe locul său.
Fiind dat numărul N
, precum și ordinea în care s-au așezat cercetașii pe scaunele numerotate de la 1
la N
, scrieți un program care să determine:
M
de cercetaşi care vor prezenta exerciţii în cadrul activităţii;M
cercetaşi care vor prezenta exerciţiile, în ordine strict crescătoare;M
cercetași care vor prezenta exercițiile să se afle pe locurile lor.ONI 2016, clasa a VIII-a
#1696
Perechi2
Fie un şir a[1]
, a[2]
, …, a[n]
de numere naturale, unde n
este impar. Avem la dispoziţie o singură operaţie admisă şi anume: putem aduna la două poziţii diferite din şir o aceeaşi valoare naturală nenulă.
Cerințe:
ONI 2016, clasa a V-a
#2301
secv
Se consideră două numerele naturale K
și S
și un șir de N
numere naturale a[1]
, a[2]
,…, a[N]
. O secvenţă de lungime K
este un subşir format din K
elemente aflate pe poziţii consecutive în şir: a[i]
, a[i+1]
,.., a[i+k-1]
. Parcurgând șirul de la stânga la dreapta, începând cu primul element, se elimină prima secvență de lungime K
, cu suma elementelor strict mai mare decât numărul S
. În urma ștergerii șirul va avea N-K
elemente: a[1]
, a[2]
,…, a[N-K]
. Operația de ștergere continuă după aceleași reguli până când nu mai există secvențe care pot fi eliminate.
Să se scrie un program care citind numerele N
, K
, S
și cele N
elemente din șir rezolvă cerințele:
1) Determină numărul secvențelor care se vor elimina respectând condiția din enunț.
2) Considerând că în șirul citit nu sunt posibile eliminări de secvențe conform condiției din enunț, programul determină numărul de elemente a[i]
din șir cu proprietatea următoare: ștergerea lui a[i]
conduce la obținerea unui șir în care se mai poate elimina cel puțin o secvență de K
elemente cu sumă strict mai mare ca S
.
ONI GIM 2016, Baraj
#1695
Oglinda
Pentru un număr natural N
se consideră șirul a=(1,2,3...,N)
, deci a[i]=i
pentru orice i
, 1≤i≤N
.
Asupra acestui șir se pot aplica operații de două tipuri:
a) la operația de tipul 1 se specifică două valori i
și j
, cu 1≤i≤j≤N
. Efectul acestei operații asupra șirului este de oglindire a secvenței din șir care începe cu elementul de pe poziția i
și se termină cu cel de pe poziția j
. De exemplu, dacă în șirul a=(1,2,3,4,5,6,7)
se aplică operația 3 6
, atunci șirul devine a=(1,2,6,5,4,3,7)
. Iar în șirul a=(1,4,3,2,5,6,7)
, dacă se aplică operația 4 6
, atunci a=(1,4,3,6,5,2,7)
.
b) Operația de tipul 2 conține un indice i
, 1≤i≤N
, și cere să afișăm valoarea elementului care se află în acel moment pe poziția i
în șir.
Se consideră M
astfel de operații într-o ordine dată.
Scrieți un program care să determine și să afișeze rezultatul pentru fiecare operație de tipul 2.
ONI 2016, clasa a V-a
#1697
Cod1
Ionel și Georgel sunt colegi de clasă și doresc să facă schimb de fișiere prin email. Fiecare dintre ei își arhivează fișierele cu câte o parolă. Fiecare copil își construiește parola pe baza unui șir format din N
numere naturale.
Numerele din șir care se folosesc efectiv pentru construirea parolelor sunt doar cele divizibile cu numerele din mulțimea {2,3,4,5,6,7,8,9,10,11,12,13,14,15}
. Copiii numără câte din valorile din șir sunt divizibile cu fiecare din aceste numere.
Parola folosită de Ionel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea {2,3,4,5,6,7,8,9}
. Parola folosită de Georgel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea {10,11,12,13,14,15}
.
Scrieţi un program care citește șirul celor N
numere și determină:
ONI 2016, clasa a VI-a
#1706
Stele
2
, strict mai mică decât 2
26
, cu o literă a alfabetului, astfel: 2 0 |
2 1 |
2 2 |
2 3 |
2 4 |
2 5 |
2 6 |
2 7 |
2 8 |
2 9 |
2 10 |
2 11 |
2 12 |
a | b | c | d | e | f | g | h | i | j | k | l | m |
2 13 |
2 14 |
2 15 |
2 16 |
2 17 |
2 18 |
2 19 |
2 20 |
2 21 |
2 22 |
2 23 |
2 24 |
2 25 |
n | o | p | q | r | s | t | u | v | w | x | y | z |
2
; dacă o putere este folosită de mai multe ori în descompunerea numărului atunci ea va fi precedată în șir de numărul de utilizări.Un număr poate fi reprezentat astfel în mai multe moduri. De exemplu, pentru numărul 100
printre variantele de reprezentare avem:
100 = cfg = 22+25+26 = 4+32+64 = 100
100 = 2ab2cde2f = 2*20+21+2*22+23+24+2*25 = 2*1+2+2*4+8+16+2*32 = 100
100 = 16bcg = 16*21+22+26 = 16*2+4+64 = 100
Scrieți un program care rezolvă următoarele cerinţe:
s
numărul de stele dintr-o galaxie, determină o reprezentare codificată a acestui număr formată doar din litere mici distincte ordonate alfabetic;g
, reprezentând numărul de galaxii și g
numere în scriere codificată, reprezentând numărul de stele din fiecare galaxie, determină scrierea zecimală a numărului total de stele din cele g
galaxii.ONI 2016, clasa a VIII-a
#1709
Asort
Se consideră un număr natural par N
și șirul ordonat crescător X
format din primele N
numere naturale nenule:
X[1] = 1
, X[2] = 2
, …., X[N] = N
.
Pozițiile numerelor din șir se pot modifica doar conform regulii A
,după cum urmează:
X[1]
este număr impar, atunci se interschimbă X[1]
cu X[2]
, X[3]
cu X[4]
, …, X[N-1]
cu X[N]
;X[1]
este par atunci se interschimbă X[2]
cu X[3]
, X[4]
cu X[5]
, …, X[N-2]
cu X[N-1]
, iar X[N]
cu X[1]
.Aplicând de R
ori regula A
șirului X
se transformă șirul dat într-un șir “A sortat”.
Cunoscându-se numerele naturale N
, R
, K
și T
, scrieți un program care să determine:
1) Numărul situat pe poziția K
în șirul “ A
sortat” obținut prin aplicarea de R
ori a regulii “ A
” șirului X
.
2) Predecesorul și succesorul numărului T
în șirul “ A
sortat” .
ONI GIM 2016, Baraj
#1676
Elmer
În antrenamentul său intens pentru prinderea lui Daffy Duck, celebrul vânător Elmer Fudd a început să vâneze rațe în orașul său preferat, Craiova. Se știe că există N
rațe reprezentate prin puncte în planul de coordonate xOy
, având coordonatele (x,y)
și M
ziduri sub forma unor segmente verticale având un capăt pe axa Ox
și o anumită înălţime fiecare.
Vânătorul Elmer dorește să împuște cât mai multe rațe. El poate fi poziționat în orice punct de abscisă număr natural nenul, pe axa Ox
. O rață poate fi ochită de vânător dacă zidul nu blochează glonțul vânătorului, adică segmentul imaginar delimitat de rață și de vânător nu se intersectează cu nici un zid.
Să se afle numărul maxim de rațe care pot fi ochite de vânătorul Elmer.
ONI 2016, clasa a X-a
#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