#1123
Iepurasi
Se construieşte un şir de numere naturale care respectă restricţiile:
9
;7
, 8
şi 9
cu proprietatea că numărul cifrelor 9
este mai mare sau egal decât numărul cifrelor 8
şi numărul cifrelor 8
este mai mare sau egal decât numărul cifrelor 7
.N
(reprezentând numărul de iepuraşi) şi a
1
, a
2
,…, a
N
(reprezentând, în ordine, numerele inscripţionate pe feţele gri) și care să determine:TAP
necesare rearanjării iepuraşilor;ONI GIM 2014, Clasa a V-a
#1208
Solitar
Se consideră un joc de cărţi cu un număr nelimitat de coloane. Iniţial, pe prima coloană există, într‑o ordine oarecare, N
cărţi cu numere distincte din mulţimea {1,2,…,N}
, următoarele coloane fiind vide (fără cărţi). Numim secvenţă de la sfârşitul coloanei ultima sau ultimele două sau ultimele trei etc. cărţi din coloană care au scrise pe ele numere consecutive în ordine crescătoare, considerate de jos în sus. De exemplu, în figurile 1 şi 2 sunt reprezentate două astfel de coloane cu câte 6
cărţi având numere între 1
şi 6
. În figura 1, secvenţa de la sfârşitul coloanei este formată doar din cartea 1
. În figura 2, secvenţa de la sfârşitul coloanei este formată din cărţile 3
, 4
şi 5
. Se observă că în coloana din figura 1 mai există o secvenţă formată din cărţile 2
, 3
şi 4
, dar aceasta nu este la sfârşitul coloanei.
Operaţiile permise ale jocului sunt:
A. mutarea secvenţei de cărţi de la sfârşitul unei coloane pe o coloană nouă, dacă acea coloană este vidă (nu conţine nicio carte);
B. mutarea secvenţei de cărţi de la sfârşitul unei coloane la sfârşitul altei coloane cu cărţi, doar dacă secvenţa mutată formează o secvenţă de numere consecutive cu cele de pe cartea sau cărţile aflate la sfârşitul coloanei respective.
Se doreşte ca, printr-un număr minim de operaţii permise, să se obţină pe una dintre coloane toate numerele de la 1
la N
, în ordine crescătoare, considerate de jos în sus.
De exemplu, de la configuraţia iniţială din figura 2 se va obţine, printr-o operaţie A
, configuraţia 1 de mai jos. Apoi, printr-o operaţie B
, se obţine configuraţia 2, printr-o nouă operaţie B
se obţine configuraţia 3, apoi se mută secvenţa 2,3,4,5,6
pe o coloană vidă (operaţia A
), apoi se mută secvenţa 1
peste secvenţa 2,3,4,5,6
(operaţia B
) şi se obţine, pe coloana a doua, configuraţia finală cerută.
Configurația 1 | Configurația 2 | Configurația 3 | Configurația 4 | Configurația 5 |
Cerința
Cunoscând valoarea lui N
, precum şi valorile cărţilor de pe prima coloană, să se determine numărul minim de operaţii prin care se poate obţine secvenţa 1, 2, …, N
pe una dintre coloane.
ONI GIM 2014, Clasa a VIII-a
#1209
TDrept
Se consideră N
puncte de coordonate întregi în sistemul de coordonate cartezian.
Scrieţi un program care determină numărul de triunghiuri dreptunghice având vârfurile plasate în 3
dintre punctele date şi catetele respectiv paralele cu axele de coordonate.
ONI GIM 2014, Clasa a VIII-a
#1225
sort2dist
Jocul pe care îl joaca Robo atunci când se plictisește este un joc inteligent pentru roboței. Pe ecranul tabletei lui roboțești, sunt N
căsuțe de formă pătrată, cu latura egală cu 1
. Căsuțele sunt așezate pe un rând, una lângă alta, fiind etichetate, în această ordine, cu numere de la 1
la N
. Fiecare căsuță conține câte un număr natural, identificatorul câte unuia dintre prietenii săi, roboței, ca și el. Identificatorii se pot repeta.
Robo poate interschimba conținutul a două căsuțe, numai dacă distanța dintre centrele acestora pe orizontală este egală cu distanța dintre brațele sale; distanța, pe orizontală, dintre centrele a două căsuțe etichetate cu i
, respectiv cu j
, este j-i
(1≤i<j≤N
).
El își poate fixa în orice moment distanța dintre brațe la 1
sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea N-1
. Astfel, distanța dintre brațele sale poate fi 1
, apoi, prin dublare, 2
, apoi, prin dublare 4
, apoi, prin dublare 8
etc. La începutul jocului, distanța dintre brațele lui Robo este 1
. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.
Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500
interschimbări de tipul celei precizate mai sus.
ONI GIM 2015, Clasa a VIII-a
#1217
LightBot
În acest an evenimentul ”Hour of Code” a înregistrat un număr record de participanți din țara noastră. În cadrul acestui eveniment una dintre cele mai accesate aplicații a fost Lightbot, care a permis elevilor să-și testeze abilitățile de programare.
Aplicația Lightbot are N
nivele, numerotate consecutiv de la 1
la N
, în ordinea strict crescătoare a complexității lor. Lightbot a permis fiecărui participant să înceapă cu orice nivel strict mai mic decât N-1
și să sară peste un singur nivel, fără a finaliza codul, trecând la nivelul următor celui sărit. La finalizarea cu succes a codului corespunzător nivelului curent, participantul este promovat la nivelul imediat următor. Fiecare participant a început scrierea codurilor la un nivel P
și a sărit peste un nivel L
(P < L < P + K
), finalizând K
nivele memorate ca o succesiune de numere naturale de forma P, P+1,..., L-1, L+1,..., P+K
. Succesiunile de nivele finalizate de participanți au fost memorate în fișierul lightbot.in
. Succesiunile corespunzătoare participanților nu se intercalează în fișier.
Scrieţi un program care citeşte succesiunile corespunzătoare nivelelor finalizate de participanții care au jucat Lightbot și determină:
1. numărul total de participanți;
2. numărul celui mai dificil nivel care a fost rezolvat de un număr maxim de participanți;
3. pentru fiecare participant, numărul nivelului sărit de acesta.
ONI GIM 2015, Clasa a VI-a
#1213
Iepuras
Iepurașul Coconaș vrea să ajungă la grădina cu morcovi. Pentru aceasta el trebuie să traverseze prin salturi o zonă cu proprietăți speciale. Zona este formată din N
căsuțe numerotate de la 1
la N
, dispuse una după cealaltă, iar fiecare căsuță conține un număr natural ce reprezintă cantitatea de energie necesară iepurașului pentru a sări într-o altă căsuță.
Iepurașul pleacă dintr-o anumită căsuță și se deplasează, de la stânga la dreapta, spre grădina cu morcovi după următoarele reguli:
5
, iepurașul va ajunge în căsuța cu numărul de ordine 13
(13=3+2*5
).0
, el rămâne acolo pentru că nu mai are energie să sară mai departe, altfel el continuă să sară după regulile descrise mai sus;N
.Scrieți un program care citește trei numere naturale P
, N
și K
iar apoi N
numere naturale și determină:
1) dacă iepurașul poate ajunge sau nu, la grădina cu morcovi pornind din căsuța K
și numărul de salturi pe care le face iepurașul pornind din căsuța K
;
2) căsuța de pornire a iepurașului, astfel încât drumul parcurs de el să traverseze un număr maxim de căsuțe. Pentru a determina numărul de căsuțe se vor lua în calcul: căsuța de pornire, toate căsuțele peste care iepurașul a sărit și toate căsuțele în care a ajuns în urma salturilor. Iepurașul poate porni din oricare căsuță. În cazul în care există două sau mai multe căsuțe de pornire care conduc la același număr maxim de căsuțe traversate se va lua în considerare căsuța cu numărul de ordine cel mai mic.
ONI GIM 2015, Clasa a V-a
#1215
Mesaj
În țara lui Piticot cuvintele au doar două litere, prima fiind o majusculă (literă mare) iar a doua o minusculă (literă mică). Piticii Mi și Gi se distrează și își trimit mesaje ascunzând cuvintele în cadrul unor secvențe transmise sub forma unor șiruri de litere. Piticul Mi scrie și trimite un mesaj piticului Gi respectând următoarele reguli:
De exemplu secvența s f u E e t R u E E
ascunde un cuvânt deoarece conține și majuscule și minuscule, iar litera terminator de secvență, E
, se repetă de exact două ori. Secvența ascunde cuvântul Eu
, iar costul cuvântului este 5
(3
litere E
+ 2
două litere u
).
La primirea mesajului, piticul Gi determină, pentru fiecare majusculă, costul maxim al cuvintelor care încep cu aceasta.
Scrieţi un program care determină:
1) numărul de secvențe trimise care nu ascund cuvinte;
2) cuvintele din mesaj, în ordinea în care au fost trimise de piticul Mi;
3) pentru fiecare majusculă, câte cuvinte care încep cu ea au costul maxim determinat de Gi.
ONI GIM 2015, Clasa a V-a
#1224
Restaurare
După descoperirea ruinelor unei cetăți medievale, arheologii au hotărât restaurarea acesteia, începând cu zidul principal. Acesta este format din N
piloni, fiecare cu lățimea de 1
metru, așezați unul lângă altul (lipiți). Se cunoaște înălțimea, în metri, a fiecărui pilon dar, din păcate, nu toți mai sunt acum la același nivel.
Pentru restaurarea zidului, arheologii dispun de cărămizi care au lățimea de câte 1
metru și lungimi variabile, exprimate în metri. Sunt disponibile oricâte cărămizi, de oricare lungime. Considerăm că toate cărămizile disponibile și toți pilonii care alcătuiesc zidul au aceeași grosime, de 1
metru.
Restaurarea constă în două etape:
H
se retează, aducându-se astfel la înălțimea H
, ceilalți, mai scunzi, păstrându-și înălțimea inițială;Arheologii au analizat situația, independent, pentru Q
valori posibile ale lui H
.
Pentru fiecare dintre cele Q
valori alese pentru înălțimea H
, se cere să se determine numărul minim de cărămizi necesare restaurării zidului, independent, pornind de la înălțimile inițiale ale pilonilor.
ONI GIM 2015, Clasa a VIII-a
#1380
pluton
În timpul acţiunii “Furtuna în deşert” din cauza unei furtuni de nisip, n
soldaţi s-au rătăcit de plutoanele lor. După trecerea furtunii se pune problema regrupării acestora pe plutoane. Pentru aceasta se folosesc plăcuţele de identificare pe care soldaţii le poartă la gât. Pe aceste plăcuţe sunt scrise numere care pot identifica fiecare soldat şi plutonul din care acesta face parte. Astfel, soldaţii din acelaşi pluton au numărul de identificare format din aceleaşi cifre, dispuse în altă ordine şi numerele de identificare sunt unice. De exemplu, numerele de identificare 78003433
, 83043073
, 33347008
indică faptul ca cei trei soldaţi care le poartă fac parte din acelaşi pluton.
Fiind date cele n
numere de pe plăcuţele de identificare, să se regrupeze cei n
soldaţi pe plutoane, indicându-se numărul de plutoane găsite (un pluton refăcut trebuie să aibă minimum un soldat), numărul de soldaţi din cel mai numeros pluton, numărul de plutoane care au acest număr maxim de soldaţi precum şi componenţa unui astfel de pluton (cu număr maxim de soldaţi regrupaţi).
OJI 2006, Clasa a IX-a
#2676
afise
Campania electorală s-a terminat de mult, dar zidul din parcul central al oraşului în care au fost puse afişele este încă într-o formă dezolantă. Ploile şi vântul au acţionat şi au urâţit şi mai mult această zonă pe care altă dată erau afişe frumos colorate. Primăria a decis să se ocupe de această problemă. A format o comisie şi a decis realizarea unor panouri reclamă care să ascundă porţiunile deteriorate. Deoarece fondurile sunt mici s-a decis să fie alocate doar un anumit număr de panouri publicitare care trebuie să ocupe o suprafaţă cât mai mică posibil. Comisia a primit datele din teren sub forma: lungime zid, câte unităţi sunt ocupate cu afişe ce trebuie acoperite şi care este numărul de panouri pe care le poate folosi. De asemenea se primesc ca date şi care sunt unităţile de zid ocupate cu afişe deja deteriorate.
OJI 2007 clasa a VIII-a