Nivelul concursului: Național
http://oni2015.isj-db.ro/ http://onigim2015.cngmm.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#1195
NMult
Se consideră trei numere naturale nenule n
, k
și w
.
Să se scrie un program care determină numărul m
al mulțimilor de forma {x[1], x[2],… , x[k]}
având ca elemente numere naturale nenule, ce satisfac simultan condițiile:
1 ≤ x[1] < x[2] < ... < x[k] ≤ n
x[i+1] - x[i] ≥ w
, 1 ≤ i ≤ k - 1
ONI 2015, Clasa a X-a
#1223
Magic1
Pentru obținerea Pietrei Filosofale, un alchimist a preparat un elixir folosind un creuzet de capacitate C
, în care a turnat picături de metal topit, într-o ordine bine stabilită, în N
etape. Numărul de picături turnate într-o etapă este cuprins între 0
și C-1
, iar procesul începe când în creuzet s-a turnat prima picătură (în prima etapă numărul de picături turnate este nenul). Picăturile se adună în creuzet una câte una şi, de fiecare dată când acesta se umple complet, alchimistul rosteşte o formulă magică, provocând transformarea întregului conţinut într-o singură picătură, apoi continuă procesul. O rețetă de obținere a elixirului se exprimă printr-un șir de N
numere, reprezentând numărul de picături turnate în cele N
etape.
De exemplu, aplicând rețeta 5 6 1 0
, cu un creuzet de capacitate C=7
, în cele N=4
etape procesul este:
5
picături;6
picături, astfel: după primele 2
picături se umple creuzetul (5+2=7
) și deci se rosteşte formula magică, în creuzet rămânând o picătură; se continuă cu celelalte 4
picături; la finalul etapei în creuzet sunt 5
picături (1+4=5
);6
picături (5+1=6
);0
picături; după ultima etapă creuzetul conține 6
picături (6+0=6).O rețetă care corespunde Pietrei Filosofale trebuie să conducă, la finalul aplicării ei, la obținerea unei singure picături, chintesența metalelor amestecate. Bineînțeles, sunt mai multe astfel de rețete.
Fiind un tip responsabil, alchimistul a lăsat posterității un set de tratate, care cuprind toate aceste rețete. El a scris pe fiecare pagină câte o rețetă, astfel încât niciuna să nu se repete în cadrul întregii lucrări. Pe vremea aceea erau meșteri pricepuți, care fabricau tratate de dimensiuni corespunzătoare, încât fiecare pagină să poată cuprinde o rețetă ca a noastră, oricât de lungă ar fi ea. Fiecare tratat are P
pagini și doar după ce completează toate cele P
pagini ale unui tratat, alchimistul începe un nou tratat.
Se cere numărul de rețete publicate în ultimul tratat.
ONI GIM 2015, Clasa a VIII-a
#1227
Spioni
Gigel si Ionel se joacă de-a spionii! De aceea ei imaginează o modalitate de a codifica un mesaj astfel încât nimeni să nu îl poată descifra. Toate mesajele lor au lungimea o putere a lui 2
. Ei numerotează literele mesajului începând cu 1
. Apoi separă literele în două categorii: cele cu număr de ordine impar în stânga, cele cu număr de ordine par în dreapta, păstrând ordinea lor. Procedeul continuă pentru fiecare grupă nou rezultată începând cu cea din stânga, până când fiecare grupă obţinută conţine un singur caracter. După terminarea operaţiilor alipesc grupele de câte o literă rezultate, începând de la stânga spre dreapta şi obţin mesajul codificat.
De exemplu pentru mesajul MESAJNECODIFICAT
procedează astfel:
1. numerotează
MESAJNECODIFICAT 123456789...
2. separă
MSJEOIIA EANCDFCT apoi repetă paşii 1 şi 2 pentru 12345678 12345678 fiecare grupă rezultată MJOI SEIA ENDC ACFT 1234 1234 1234 1234 MO JI SI EA ED NC AF CT 12 12 12 12 12 12 12 12 M O J I S I E A E D N C A F C T 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
până se obţine un singur caracter în fiecare grupă şi alipind literele de la stânga spre dreapta rezultă mesajul codificat: MOJISIEAEDNCAFCT
Scrieţi un program care să rezolve următoarele două cerinţe:
ONI GIM 2015, Baraj
#1198
Sablon1
Se consideră alfabetul englez compus din literele mici, de la a
la z
.
Se numeşte cuvânt un şir finit, eventual vid, de litere din acest alfabet.
Se numeşte expresie şablon un şir de caractere din alfabet în care pot apărea și caracterele ?
şi *
.
Un cuvânt se potrivește cu o expresie șablon dacă se poate obține din aceasta astfel:
?
se înlocuiește cu o singură literă din alfabet;*
se înlocuiește cu un cuvânt oarecare, eventual vid;?
și *
, un singur caracter de tip literă.Considerându-se o expresie șablon și un șir de cuvinte, să se determine, pentru fiecare cuvânt în parte, dacă se potrivește sau nu cu expresia şablon dată.
ONI 2015, Clasa a X-a
#1219
Cript
Ilinca a citit despre criptarea mesajelor, acum dorește să comunice cu prietena ei Miruna numai prin mesaje criptate folosind un sistem propriu de criptare.
Ilinca ştie că fiecare caracter se reprezintă în memoria calculatorului pe 8
biți, în care se memorează scrierea în baza 2
a codului ASCII al caracterului respectiv. Pentru a cripta caracterul, Ilinca foloseşte o matrice pătratică având 8
linii (numerotate de la 0
la 7
de sus în jos) şi 8
coloane (numerotate de la 0
la 7
de la stânga la dreapta). Pe prima linie a matricei Ilinca scrie cei 8
biţi reprezentând scrierea în baza 2
a codului ASCII al caracterului, pe poziţia 0
fiind scrisă cifra cea mai semnificativă (corespunzătoare lui 27
). Pe fiecare dintre următoarele 7
linii din matrice scrie permutarea circulară cu o poziție la stânga a liniei anterioare. Ordonează lexicografic liniile matricei formate și defineşte cript-ul caracterului ca fiind succesiunea de biți reprezentată de ultima coloană din matrice, parcursă de sus în jos, urmată de indicele liniei din matrice pe care a ajuns după ordonarea lexicografică reprezentarea în baza 2
a codului ASCII al caracterului. Dacă există linii egale în matrice, după ordonarea lexicografică acestea îşi vor păstra ordinea relativă iniţială, astfel că linia conţinând reprezentarea în baza 2
a codului ASCII al caracterului va fi prima dintre acestea.
Pentru a cripta un mesaj, Ilinca scrie în ordine cript-urile caracterelor din mesajul respectiv.
Miruna cunoaşte sistemul de criptare al Ilincăi, ca urmare ştie să decripteze mesajele primite.
Scrieți un program care să rezolve următoarele două cerinţe:
1. citește un mesaj şi afişează mesajul criptat conform sistemului Ilincăi;
2. citeşte un mesaj criptat conform sistemului Ilincăi şi determină mesajul decriptat.
ONI GIM 2015, Clasa a VII-a
#1222
TV
Comisia Naţională a Audiovizualului (CNA) este autoritatea care coordonează activitatea posturilor media din România. Șeful CNA-ului dorește o statistică referitoare la publicitatea transmisă de posturile de televiziune. În acest scop, el primește pentru fiecare zi informații în următorul format: d hh:mm:ss
, unde d
este durata exprimată în secunde a publicității, iar hh:mm:ss
este momentul de start al publicității (hh
este ora, mm
este minutul, iar ss
este secunda). Observaţi că d
este separat de hh
printr-un singur spaţiu, iar următoarele valori sunt separate prin caracterul ':'
.
De exemplu o linie de forma:
150 05:02:45
se interpretează astfel: există un post TV care a transmis publicitate cu durata de 150
secunde, ora de început fiind 5
, 2
minute și 45
de secunde.
”Secunda de aur” este o secundă în care se difuzează cât mai multă publicitate, adică pe un număr maxim de posturi în acea secundă se transmite publicitate. Dacă sunt mai multe astfel de secunde, “secunda de aur” este considerată prima secundă cu această proprietate în derularea zilei.
Șeful CNA primește în fiecare dimineață lista cu activitatea din ziua anterioară ca o succesiune de linii, fiecare linie având forma descrisă mai sus.
Scrieţi un program care, cunoscând lista din ziua anterioară, să rezolve următoarele cerinţe:
ONI GIM 2015, Clasa a VII-a
#1203
KSecv
Fie un vector V
cu N
elemente și un număr K
. Vectorul V
trebuie împărțit în exact K
subsecvențe nevide, astfel încât fiecare element din vector să aparțină exact unei subsecvențe. Această împărțire trebuie făcută astfel încât maximul șmecheriei fiecărei subsecvențe să fie cât mai mic. (Această problemă concepe greșit sistemul de șmecherie și valoare). Șmecheria fiecărei subsecvențe se definește ca fiind parte întreagă din ((Vmax – Vmin + 1) / 2)
, unde Vmax
este valoarea maximă din subsecvență, iar Vmin
este valoarea minimă.
Vectorul V
de N
elemente va fi generat în felul următor: se dă un număr M
și 2
vectori A
și B
de lungime M
(indexați de la 0
la M - 1
). Fiecare element i
, 0 ≤ i < N
, din vectorul V
va fi calculat cu următoarea formulă: V[i] = (A[i % M] ^ B[i / M])
, unde x % y
reprezintă restul lui x
la împărțirea cu y
, x / y
reprezintă câtul împărțirii lui x
la y
și x ^ y
reprezintă rezultatul operației xor
(sau exclusiv pe biți) dintre x
și y
.
ONI 2015, Clasele XI-XII
#1204
Trenuri
Gara de Nord este cea mai vestită gară din lume. Japonezii, invidioşi pe sistemul performant de întârziere al trenurilor din Gara de Nord, s-au hotărât să analizeze motivul realizării unei astfel de performanțe.
În Gara de Nord (considerată stația 0
) există N
trenuri. Pentru fiecare tren i
știm că va pleca din Gara noastră protagonistă (stația 0
) și o să meargă până la stația statie[i]
. Staţiile x
şi x+1
sunt legate în mod direct pentru orice x
, astfel că trenul i
va opri în toate stațiile din intervalul [0, statie[i]]
. De asemenea, știm că trenul i
are o capacitate egală cu numărul maxim de oameni pe care îl poate transporta. Această capacitate este notată cu capacitate[i]
.
Avem M
pasageri dornici sa folosească magnificul traseu. Pentru fiecare pasager i
știm intervalul de stații [a[i], b[i]]
pe care vrea să îl parcurgă. Mai exact, acesta vrea să se urce într-un tren în stația a[i]
și să coboare în stația b[i]
.
Din cauza capacității limitate a trenurilor, este posibil ca nu toți pasagerii sa poată obțină un loc și să ajungă în destinația dorită. Să se determine numărul maxim de pasageri care pot ajunge din stația de plecare în stația de sosire, precum și o configurație în care aceștia se pot urca în trenuri.
ONI 2015, Clasele XI-XII
#1187
Roboti1
O firmă de construcţii imobiliare a achiziţionat recent un teren dreptunghiular de dimensiuni N×M
. Terenul este împărțit în parcele de dimensiune 1x1
. Pe unele dintre cele N×M
parcele sunt plantați copaci. Firma dorește construirea unui grandios complex comercial și este necesară defrișarea întregului teren. În acest scop sunt utilizați roboți, fiecare robot având baza un pătrat de latură L
. Suprafața defrișată de fiecare robot la un moment dat este chiar aria de acoperire a robotului, L×L
. Fiecare robot pătrunde prin colțul stânga sus de coordonate (1, 1)
, se poate deplasa doar în dreapta și în jos și poate părăsi suprafața numai prin colțul dreapta jos, de coordonate (N, M)
.
Cunoscând dimensiunile N
, M
ale terenului și coordonatele parcelelor în care sunt plantați copaci se cere:
1. Numărul minim de roboți necesari defrișării întregului teren.
2. Să se răspundă la Q
interogări de forma k
, unde k
este un număr natural. Pentru fiecare interogare de această formă va trebui determinată latura minimă a unui robot astfel încât să fie necesari pentru defrișare cel mult k
roboți.
ONI 2015, Clasa a IX-a
#1200
Spiridusi
Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din N
camere, unite între ele prin N-1
culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1
. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i
s-au stabilit s[i]
spiriduși de praf.
Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere a
și b
(nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera b
trece prin camera a
. Fetele vor merge apoi din camera a
în camera b
pe drumul cel mai scurt (fără a trece de două ori prin aceeași cameră), gonind spiridușii de praf aflați în fiecare cameră prin care trec, inclusiv pe cei din camerele a
și b
. După ce fetele ajung în camera b
, ele consideră că toate camerele din care au gonit spiridușii de praf au fost alese pentru spațiul de joacă.
Fetele au stabilit pentru fiecare cameră i
un coeficient p[i]
care reprezintă cât de plăcută ar fi camera i
pentru spațiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de C
spiriduși ai prafului din camerele prin care trec.
Cunoscând valorile lui N
și C
, numărul de spiriduși ai prafului s[i]
, coeficienții p[i]
pentru fiecare cameră i
, cât și modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienților p
ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.
ONI 2015, Clasele XI-XII