#1055
Compar
Ana şi Bogdan au inventat jocul “Compar”. Ana scrie pe tablă o secvenţă formată din N
numere naturale distincte cuprinse între 1
şi N
, apoi compară fiecare două numere învecinate din secvenţă scriind între ele semnul <
sau semnul >
, după caz.
De exemplu, dacă secvenţa de pe tablă este 6 4 2 1 3 5
, după compararea elementelor învecinate şi inserarea semnelor în secvenţă, Ana obţine:
6>4>2>1<3<5
După aceea Ana şterge cele N
elemente ale secvenţei şi păstrează numai semnele, astfel:
>>><<
La final, Ana îi arată lui Bogdan şirul semnelor şi îi cere să reconstituie secvenţa de numere naturale scrisă iniţial pe tablă.
Cunoscând şirul semnelor construit de Ana, scrieţi un program care să îl ajute pe Bogdan să reconstituie secvenţa de numere naturale distincte scrisă iniţial pe tablă.
OJI 2013, Clasa a VII-a
#1057
MaxP
Considerăm un şir de numere a
1
, a
2
, …, a
N
. O secvenţă nevidă în acest şir este de forma a
i
, a
i+1
, …, a
j
, unde i ≤ j
. De exemplu, pentru N=4
şi şirul 2 3 4 3
, secvenţele nevide sunt: 2
, 2 3
, 2 3 4
, 2 3 4 3
, 3
, 3 4
, 3 4 3
, 4
, 4 3
, 3
. Definim puterea unui element a
i
ca fiind numărul de secvenţe care-l conţin pe a
i
şi în care a
i
este strict mai mare decât celelalte elemente ale fiecăreia dintre respectivele secvenţe. Astfel în şirul 2 3 4 3
puterea elementului a
1
este 1
(fiind maxim doar în secvenţa formată din el însuşi), a elementului a
2
este 2
(a
2
fiind maxim în secvenţele 2 3
şi 3
), a elementului a
3
este 6
(fiind maxim în secvenţele 2 3 4
, 2 3 4 3
, 3 4
, 3 4 3
, 4
şi 4 3
), iar a elementului a
este 1
.
Scrieţi un program care determină puterea cea mai mare a unui element din şirul dat, precum şi numărul de elemente din şir care au cea mai mare putere.
OJI 2013, Clasa a VIII-a
#1040
Clepsidru
O clepsidră este un dispozitiv folosit pentru a măsura timpul. Clepsidra este alcătuită din două incinte de sticlă, conectate printr-un tub fin. Una dintre incinte este umplută cu nisip, acesta scurgându-se în cea de-a doua incintă, cu o viteză constantă. Clepsidra poate fi întoarsă, pentru a măsura o altă perioadă de timp.
Arheologii au descoperit un dispozitiv, pe care l-au denumit clepsidru, format din n
clepsidre identice, suprapuse, numerotate de la 1
la n
, prin care nisipul poate circula de la o clepsidră la alta datorită forţei gravitaţionale.
Studiind acest obiect, arheologii au constatat că :
1
, când clepsidrele sunt în ordinea 1
, 2
,…, n
cu clepsidra n
aşezată pe sol, cât şi în poziţia 2
, când clepsidrele sunt în ordinea n
, n-1
,…, 1
cu clepsidra 1
aşezată pe sol;1
bob de nisip/secundă, pentru toate clepsidrele, indiferent de poziţie;Arheologii studiază comportarea clepsidrului realizând două experimente diferite, după cum urmează:
a) Se aşează clepsidrul în poziţia 1
, se introduc în incinta de sus a clepsidrei 1
un număr b
de boabe de nisip şi se determină după câte secunde vor ajunge toate boabele de nisip în incinta de jos a ultimei clepsidre;
b) Se aşează clepsidrul în poziţia 1
, se introduc în incinta de sus a clepsidrei 1
un număr b
de boabe de nisip, apoi se aşează clepsidrul în k
stări consecutive, o stare fiind caracterizată de valorile s
i
şi p
i
, 1 ≤ i ≤ k
, ce reprezintă numărul de secunde, respectiv poziţia, în care este menţinut nemişcat clepsidrul, iar la final se determină numărul de boabe de nisip din incintele fiecărei clepsidre.
Spre exemplu, dacă clepsidrul este format din n=2
clepsidre, iar în incinta de sus a primei clepsidre se introduc b=3
boabe de nisip, la primul experiment se va obţine valoarea 4
.
La al doilea experiment se aşează clepsidrul în k=2
stări, caracterizate prin s
1
=3
, p
1
=1
; s
2
=1
, p
2
=2
.
Numărul de boabe de nisip din clepsidre va evolua ca în figura alăturată.
Să se scrie un program care citeşte valorile n
şi b
, precum şi valorile k
, s
i
, p
i
, 1 ≤ i ≤ k
, şi calculează valorile obţinute de arheologi la realizarea celor două experimente.
OJI 2013, clasa a IX-a
#1027
Cool
Se consideră un șir A
format din N
elemente naturale nenule. Numim secvență de lungime K
a șirului A
orice succesiune de elemente consecutive din șir de forma A
i
, A
i+1
,…, A
i+K-1
.
O secvență o numim secvență cool dacă elementele care o compun sunt distincte și pot fi rearanjate astfel încât să alcătuiască o secvență continuă de numere consecutive.
De exemplu, considerând șirul A=(3,1,6,8,4,5,6,7,4,3,4)
, atunci secvența (8,4,5,6,7)
este o secvență cool deoarece conține elemente distincte ce pot fi rearanjate astfel încât să alcătuiască șirul de numere consecutive 4,5,6,7,8,
pe când secvențele (4,3,4), (6,7,4,3)
nu sunt considerate secvențe cool.
Fiind dat un şir de N
numere naturale nenule se cer următoarele:
1. Pentru o valoare dată K
să se verifice dacă secvența A
1
, A
2
,…, A
K
este secvență cool. Dacă secvența este cool, atunci se va afișa cea mai mare valoare ce aparține secvenței. Dacă secvența nu este cool, atunci se va afișa numărul elementelor distincte din secvența A
1
, A
2
,…, A
K
, adică numărul elementelor care apar o singură dată.
2. Lungimea maximă a unei secvențe cool și numărul secvențelor cool de lungime maximă.
OJI 2014, Clasa a IX-a
#1046
Munte
Se consideră un şir x
1
, x
2
,…, x
n
format din n
numere naturale distincte. O secvenţă de număr maxim de elemente vecine în şir, de forma x
i
, x
i+1
,…, x
k-1
, x
k
, x
k+1
,…, x
j
(1≤i<k<j≤n
) cu proprietatea că x
i
< x
i+1
< ...< x
k-1
< x
k
> x
k+1
> ... > x
j
, se numeşte munte cu vârful x
k
. Două secvenţe munte au maxim un element comun în şir. O secvenţă munte are cel puţin 3
elemente. Un exemplu de şir format cu valorile 3 4 6 8
nu conţine nicio secvenţă munte, iar unul format cu valorile 3 4 8 1 2 5 0
conţine 2
secvenţe munte: 3 4 8 1
şi 1 2 5 0
.
După determinarea tuturor secvenţelor munte şi a vârfurilor acestora, se elimină din şir vârfurile secvenţelor munte şi procedura continuă repetat cu determinarea noilor secvenţe munte şi a vârfurilor lor din şirul nou obţinut. Procedura se opreşte în momentul în care în şir nu mai există nicio secvenţă munte.
Scrieţi un program care citeşte numerele n
, x
1
, x
2
, …, x
n
şi apoi determină:
a) numărul de secvenţe munte din şirul iniţial;
b) numărul total de secvenţe munte obţinute pornind de la şirul iniţial până la cel care nu mai conţine nicio secvenţă munte;
c) numărul de elemente din şirul final care nu mai conţine secvenţe munte.
OJI 2014, Clasa a VI-a
#1048
Schi
La proba de sărituri cu schiurile din cadrul jocurilor olimpice de iarnă participă N
concurenți, numerotați cu numere de la 1
la N
.
Regulile de desfășurare a probei sunt următoarele:
1
la N
;Pe tot parcursul concursului se ține în mod neoficial și un clasament parțial, pe baza rezultatelor obținute de concurenții care au evoluat până în acel moment. Asta pentru că șeful comisiei de arbitri are o curiozitate aparte și pune K
întrebări sub forma următoare: Câte minute s-a ocupat primul loc din clasament cu un punctaj egal cu X
puncte? Dacă nici un concurent nu s-a clasat pe primul loc cu X
puncte atunci primește ca răspuns valoarea 0
.
Scrieți un program care determină răspunsul pentru fiecare dintre cele K
întrebări puse de șeful comisiei de arbitri.
OJI 2014, Clasa a VII-a
#1050
TCIF
Avem la dispoziţie patru numere naturale N
, A
, B
, C
, precum şi trei cifre c1
, c2
, c3
distincte două câte două.
Să se determine numărul natural minim, strict mai mare decât N
, care are exact A
cifre c1
, B
cifre c2
, C
cifre c3
şi nu conţine alte cifre.
OJI 2014, Clasa a VIII-a
#1131
Arc
Irinuca a descoperit un nou joc pe calculator. Pe ecran sunt plasate pe o linie n
bile colorate. Culorile bilelor sunt codificate cu numere naturale. Un subșir de bile alăturate având toate aceeași culoare se numește secvență. O secvență va conține numărul maxim de bile alăturate având aceeași culoare. Lungimea unei secvențe este egală cu numărul de bile din care este compusă.
Irinuca are la dispoziție un arc special. Trăgând cu arcul asupra unei bile, dacă aceasta face parte dintr-o secvență de lungime cel puțin egală cu 3
, întreaga secvență va fi eliminată, iar bilele din dreapta secvenței se vor deplasa spre stânga pentru a umple “golul” lăsat de bilele eliminate. Dacă imediat în stânga și în dreapta secvenței eliminate se găseau două secvențe având aceeași culoare și dacă secvența obținută din unirea acestora după eliminare are o lungime cel puțin egală cu 3
, atunci va fi și ea eliminată la rândul ei. Procesul continuă până când secvențele din stânga și dreapta unei secvențe tocmai eliminate au culori diferite sau până când lungimea secvenței obținute prin alăturare este mai mică decât 3
sau până când în stânga ori în dreapta unei secvențe eliminate nu se mai găsesc bile sau până sunt eliminate toate bilele de pe ecran.
Scopul jocului este de a elimina cât mai multe bile de pe ecran. Cum Irinuca încă nu se pricepe prea bine la acest joc și-a stabilit o strategie. Va trage cu arcul întotdeauna asupra unei bile ce face parte din secvența de lungime maximă de pe ecran. Dacă sunt mai multe astfel de secvențe, ea va alege cea mai din stânga secvență de lungime maximă. Dacă toate secvențele de pe ecran au lungimi mai mici decât 3, Irinuca nu va mai putea elimina nici una din ele și jocul se încheie.
Cunoscând numărul de bile și culorile fiecărei bile de pe ecran se cere să se determine:
1. numărul de secvențe de bile care se aflau inițial pe ecran;
2. numărul de bile care rămân neeliminate de pe ecran și culorile bilelor rămase în ordine pe ecran la finalul jocului.
OJI 2015, Clasa a IX-a
#1141
ech
Numim număr echilibrat un număr natural pentru care suma cifrelor de pe poziţii pare este egală cu suma cifrelor de pe poziţii impare.
De exemplu numărul 13552
este echilibrat, pentru că 1+5+2=8=3+5
.
Dat fiind un număr natural N
să se determine cel mai mic număr echilibrat, strict mai mare decât N
.
OJI 2015, Clasa a VII-a
#1143
Dominant
Considerând un șir de valori binare, numim secvență dominantă un set de elemente aflate pe poziții consecutive în șir care are proprietatea că numărul valorilor egale cu 1
este strict mai mare decât numărul valorilor de 0
. De exemplu, în șirul 1,0,0,0,1,1,0,1,1,1,0,0
o secvență dominantă este 0,1,1
și o alta, de lungime mai mare, este 0,1,1,0,1,1,1
. Secvența dominantă maximală este secvența dominantă de lungime maximă. În șirul din exemplu secvența dominantă maximală este 1,0,0,0,1,1,0,1,1,1,0
(adică întreg șirul, fără ultimul zero).
Dat fiind un șir de valori binare, să se determine lungimea unei secvențe dominante maximale precum și numărul acestor secvențe.
OJI 2015, Clasa a VIII-a