Ministerul Educaţiei Naţionale Olimpiada Judeţeană de Informatică Clasa a IX-a 2 martie 2013 Sursa: ID1.pas, ID1.cpp, ID1.c

Problema 1 – betasah 100 puncte

Jocul betaşah se joacă folosindu-se doar piese asemănătoare damelor clasicului şah, numite tot dame. Suprafaţa de joc are o formă triunghiulară şi este formată din

2)1N(*N + pătrate identice dispuse pe N rânduri şi N

coloane. Rândurile se numerotează de sus în jos, de la 1 la N. Coloanele se numerotează de la stânga la dreapta, de la 1 la N. Primul rând conţine un singur pătrat, al doilea rând conţine două pătrate alăturate,..., al N-lea rând conţine N pătrate alăturate, ca în suprafeţele de joc cu N=6 din figurile de mai jos. Din cele

2)1N(*N + pătrate, K sunt gri, iar

restul sunt albe. Poziţia fiecărui pătrat de pe suprafaţa de joc este dată de rândul şi coloana în care acesta este situat.

Pe suprafaţa de joc sunt aşezate D dame în D pătrate albe distincte, ocupându-le. Într-un pătrat alb poate fi aşezată o singură damă, iar într-un pătrat gri nu poate fi aşezată nicio damă. Poziţia unei dame pe suprafaţa de joc este dată de poziţia pătratului alb în care este aşezată dama. Damele pot accesa orice pătrat alb neocupat situat pe direcţiile: verticală, orizontală sau diagonală, numerotate de la 1 la 8 în figura b). Accesul pe o direcţie se face trecând din pătrat alb în pătrat alb (doar pătrate albe neocupate) până la întâlnirea unui pătrat gri sau a unui pătrat alb ocupat de o altă damă sau până la terminarea suprafeţei de joc. Numim pătrat accesibil orice pătrat alb neocupat (de pe suprafaţa de joc) care ar putea fi accesat de cel puţin una din cele D dame. De exemplu, pentru suprafaţa de joc din figura c) numărul de pătrate accesibile (marcate cu X) de pe suprafaţă este 11; pentru suprafaţa de joc cu N=6, D=3 şi K=4 din figura d) numărul de pătrate accesibile de pe suprafaţă este 13. În figura e) sunt marcate cu X pătratele accesibile fiecărei dame de pe suprafaţa de joc din figura d).

Pătratele accesibile damei din rândul 3 şi coloana 2

Pătratele accesibile damei din rândul 5 şi coloana 2

Pătratele accesibile damei din rândul 5 şi coloana 4

Pătratele accesibile de pe suprafaţa de joc

Figura e)

Cerinţe Scrieţi un program care să citească numerele naturale N, D, K, poziţiile damelor şi ale pătratelor gri pe suprafaţa de joc şi care să determine:

a) numărul maxim M de pătrate albe conţinute de un rând al suprafeţei de joc; b) numărul P de pătrate accesibile de pe suprafaţa de joc.

_____________ Problema 1 – betasah pag. 1 din 2

Ministerul Educaţiei Naţionale Olimpiada Judeţeană de Informatică Clasa a IX-a 2 martie 2013 Sursa: ID1.pas, ID1.cpp, ID1.c Date de intrare Fişierul de intrare betasah.in conţine: - pe prima linie cele trei numere naturale N, D şi K, separate prin câte un spaţiu, cu semnificaţia din enunţ; - pe linia i+1 două numere naturale nenule xi şi yi, separate printr-un singur spaţiu, reprezentând poziţia damei i

pe suprafaţa de joc (rândul xi şi coloana yi), pentru i=1,2,3,…,D; - pe linia D+1+j două numere naturale nenule zj şi tj, separate printr-un singur spaţiu, reprezentând poziţia

pătratului gri j pe suprafaţa de joc (rândul zj şi coloana tj), pentru j=1,2,3,…,K.

Date de ieşire Fişierul de ieşire betasah.out va conţine pe prima linie numărul natural M şi pe a doua linie numărul natural P, cu semnificaţia din enunţ. Restricţii şi precizări

• 2 ≤ N ≤ 1000; • 1 ≤ D ≤ 100; • 1 ≤ K ≤ 50; • D + K ≤

2)1N(*N + ;

• 1 ≤ yi ≤ xi ≤ N pentru i=1,2,3,...,D; • 1 ≤ tj ≤ zj ≤ N pentru j=1,2,3,...,K; • numărul M se va scrie obligatoriu pe prima linie a fişierului de ieşire betasah.out; • numărul P se va scrie obligatoriu pe a doua linie a fişierului de ieşire betasah.out; • pentru rezolvarea corectă a cerinţei a) se acordă 20% din punctaj, iar pentru rezolvarea corectă a cerinţei b) se

acordă 80% din punctaj. Exemplu: betasah.in betasah.out Explicaţie 6 3 4 3 2 5 2 5 4 3 1 4 3 6 4 1 1

5 13

N=6, D=3, K=4. Rândurile 5 şi 6 conţin numărul maxim M=5 de pătrate albe. Numărul de pătrate accesibile de pe suprafaţa de joc este P=13. În desenul alăturat corespunzător suprafeţei date, cele 13 pătrate accesibile sunt marcate cu X. Astfel, pe prima linie a fişierului betasah.out se va scrie numărul 5, iar pe a doua linie a fişierului se va scrie numărul 13.

Timp maxim de executare/test: 0.1 secunde Limite de memorie: total memorie disponibilă 64 MB, din care pentru stivă maxim 32 MB Dimensiunea maximă a sursei 10 KB

_____________ Problema 1 – betasah pag. 2 din 2

Ministerul Educaţiei Naţionale Olimpiada Judeţeană de Informatică Clasa a IX-a 2 martie 2013 Sursa: ID2.pas, ID2.cpp, ID2.c

Problema 2 - clepsidru 100 puncte 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ă : - dispozitivul poate fi utilizat atât în poziţia 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; - viteza de trecere a nisipului de la o incintă la alta, a aceleiaşi clepsidre, este de 1 bob de nisip/secundă, pentru

toate clepsidrele, indiferent de poziţie; - trecerea clepsidrului dintr-o poziţie în alta presupune răsturnarea acestuia şi reaşezarea boabelor de nisip; - timpul de trecere a boabelor de nisip de la o clepsidră la alta este 0.

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 si şi pi , 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 s1=3, p1=1; s2=1, p2=2.

Numărul de boabe de nisip din clepsidre va evolua ca în figura alăturată.

Cerinţă Să se scrie un program care citeşte valorile n şi b, precum şi valorile k, si, pi , 1 ≤ i ≤ k, şi calculează valorile obţinute de arheologi la realizarea celor două experimente. Date de intrare Prima linie a fişierului de intrare clepsidru.in conţine două numere naturale nenule n şi b, separate printr-un singur spaţiu, cu semnificaţia din enunţ; a doua linie conţine numărul natural nenul k având semnificaţia din enunţ, iar următoarele k linii conţin fiecare câte o pereche de valori si şi pi, 1 ≤ i ≤ k, separate printr-un singur spaţiu, cu semnificaţia din enunţ. Date de ieşire Fişierul de ieşire clepsidru.out va conţine pe prima linie un număr natural ce reprezintă valoarea obţinută la primul experiment, iar pe următoarele n linii va conţine câte o pereche de numere naturale, separate printr-un singur spaţiu, ce reprezintă cantităţile de boabe de nisip din incintele de sus şi de jos ale celor n clepsidre, scrise în ordinea de la 1 la n a clepsidrelor, după realizarea celui de-al doilea experiment.

_______________ Problema 2 – clepsidru pag. 1 din 2

Ministerul Educaţiei Naţionale Olimpiada Judeţeană de Informatică Clasa a IX-a 2 martie 2013 Sursa: ID2.pas, ID2.cpp, ID2.c

Restricţii şi precizări

• 1 ≤ n ≤ 1 000; • 1 ≤ b ≤ 1 000 000 000; • 1 ≤ k ≤ 1 000; • 1 ≤ si ≤ 1 000, 1 ≤ i ≤ k; • pi ∈{1, 2}, 1 ≤ i ≤ k; • pentru rezolvarea corectă a primei cerinţe se acordă 25% din punctaj, iar pentru rezolvarea corectă a celei de-a

doua cerinţe se acordă 75% din punctaj. • acordarea punctajului pentru a doua cerință se face numai dacă în fișierul de ieșire există un răspuns

pentru prima cerință, indiferent de corectitudinea acestuia. Exemplu

Timp maxim de executare: 0,5 secunde/test. Total memorie disponibilă 64 MB, din care pentru stivă maxim 32 MB. Dimensiunea maximă a sursei : 10 KB.

clepsidru.in clepsidru.out Explicaţii 2 3 2 3 1 1 2

4 1 1 0 1

- Clepsidrul este format din n=2 clepsidre şi în incinta de sus a primei clepsidre se introduc b=3 boabe de nisip. - Toate boabele de nisip vor ajunge în incinta de jos a ultimei clepsidre după 4 secunde. - După ce clepsidrul este aşezat 3 secunde în poziţia 1 şi 1 secundă în poziţia 2, în clepsidre se vor găsi câte (1,1), (0,1) boabe de nisip.

_______________ Problema 2 – clepsidru pag. 2 din 2

Ministerul Educaţiei si Cercetării Știintifice Olimpiada Judeţeană de Informatică Clasa a IX-a 7 martie 2015 Sursa: ID1.c, ID1.cpp, ID1.pas Problema 1 - arc 100 puncte

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.

De exemplu, dacă șirul inițial de bile este

5 1 3 3 2 2 2 2 3 1 1 5 6 4 4 4 4 7 Irinuca va acționa asupra unei bile de culoare 2. Prin eliminare se obține șirul de bile 5 1 3 3 3 1 1 5 6 4 4 4 4 7 din care se elimină și secvența de bile de culoare 3 obținându-se șirul de bile 5 1 1 1 5 6 4 4 4 4 7 din care se elimină și secvența de culoare 1. 5 5 6 4 4 4 4 7 Cum secvența de bile de culoare 5 nu este suficient de lungă, aceasta nu se mai elimină. Acum Irinuca trage asupra unei bile de culoare 4 și obține 5 5 6 7 dar cum în stânga și în dreapta secvenței eliminate sunt secvențe de culori diferite, nu se va mai elimina nici o secvență. Jocul se încheie deoarece nu mai există nici o secvență de lungime cel puțin 3 asupra căreia să se poată trage. Cerinţă

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.

Date de intrare

Fişierul de intrare arc.in conţine pe prima linie un număr natural V. Pentru toate testele de intrare, numărul V poate avea doar valoarea 1 sau 2.

A doua linie conține un număr natural n reprezentând numărul de bile, iar a treia linie conține n numere naturale c1, c2, ..., cn separate prin câte un spațiu, reprezentând culorile celor n bile de pe ecran.

Problema 1 – arc pag. 1 din 2

Ministerul Educaţiei si Cercetării Știintifice Olimpiada Judeţeană de Informatică Clasa a IX-a 7 martie 2015 Sursa: ID1.c, ID1.cpp, ID1.pas Date de ieşire

Dacă valoarea lui V este 1, se va rezolva numai punctul 1 din cerință. În acest caz, în fişierul de ieşire arc.out se va scrie un singur număr natural n1, reprezentând

numărul de secvențe de bile aflate inițial pe ecran. Dacă valoarea lui V este 2, se va rezolva numai punctul 2 din cerință. În acest caz, în fişierul de ieşire arc.out se va scrie pe prima linie un singur număr natural n2,

reprezentând numărul de bile care rămân neeliminate de pe ecran la finalul jocului, iar pe următoarele n2 linii se va scrie câte un număr natural reprezentând în ordine culorile bilelor rămase neeliminate la finalul jocului.

Dacă la finalul jocului nu mai rămâne nici o bilă neeliminată, fișierul de ieșire va conține pe prima sa linie valoarea 0.

Restricţii şi precizări

• 1 ≤ n ≤ 10 000 • 1 ≤ c1, c2, …, cn ≤ 100 000 • Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se

acordă 80 de puncte. Exemple arc.in arc.out Explicaţie 1 18 5 1 3 3 2 2 2 2 3 1 1 5 6 4 4 4 4 7

10

V = 1 Atenție! Pentru acest test se rezolvă doar cerința 1.

Secvențele sunt (5), (1), (3, 3), (2,2,2,2), (3), (1,1), (5), (6), (4,4,4,4), (7)

arc.in arc.out Explicaţie 2 18 5 1 3 3 2 2 2 2 3 1 1 5 6 4 4 4 4 7

4 5 5 6 7

V = 2 Atenție! Pentru acest test se rezolvă doar cerința 2.

arc.in arc.out Explicaţie 2 15 1 2 2 2 2 1 1 3 3 3 4 4 4 4 3

0 V = 2 Atenție! Pentru acest test se rezolvă doar cerința 2.

Timp maxim de execuţie: 0.2 secunde/test. Memorie totală disponibilă 4 MB Dimensiunea maximă a sursei: 10 KB.

Problema 1 – arc pag. 2 din 2

Ministerul Educaţiei Naționale și Cercetării Științifice Olimpiada Judeţeană de Informatică Clasa a IX-a 12 martie 2016 Sursa: ID1.c, ID1.cpp, ID1.pas

Problema 1 – cifre 100 puncte Un indicator numeric este un dispozitiv de afişaj electronic destinat afişării unei cifre zecimale. Acesta conține 7 segmente notate cu a, b, c, d, e, f, g, ca în figura alăturată. Afişarea unei cifre se face prin aprinderea unei combinații de segmente conform tabelului:

Cerință Cunoscând un număr natural N afișat cu ajutorul mai multor indicatoare numerice, să se scrie un program care determină:

1. Numărul de segmente aprinse pentru afișarea numărului N. 2. Numărul de numere distincte mai mari decât N,ce se pot forma prin aprinderea a cel puțin unui segment

în plus, față de cele utilizate pentru afișarea numărului N,fără a folosi alte indicatoare numerice, și fără a stinge nici un segment dintre cele deja aprinse.

Date de intrare Fișierul de intrare este cifre.in Pe prima linie a fişierului de intrare se găsește numărul natural V a cărui valoare poate fi doar 1 sau 2. Pe a doua linie a fișierului de intrare se găsește numărul natural N. Date de ieşire Fișierul de ieșire este cifre.out Dacă valoarea lui V este 1 atunci fişierul de ieşire va conţine pe prima linie un singur număr natural ce reprezintă numărul de segmente aprinse pentru afișarea numărului N. Dacă valoarea lui V este 2 atunci fişierul de ieşire va conține pe prima linie un singur număr natural reprezentând numărul de numere distincte mai mari decât N,ce se pot forma prin aprinderea a cel puțin unui segment în plus, față de cele utilizate pentru afișarea numărului N,fără a folosi alte indicatoare numerice.

Restricţii şi precizări • 10 ≤ N ≤ 10 19 • 20% din teste vor avea valoarea V = 1, iar 80% din teste vor avea valoarea V = 2.

Exemple

Timp maxim de executare: 0,1 secunde/test. Total memorie disponibilă: 2 MB.

Cifră 0 1 2 3 4 5 6 7 8 9 Segmente aprinse

a,b,c, d,e,f

b,c a,b,d, e,g

a,b,c, d,g

b,c, f,g

a,c,d, f,g

a,c,d, e,f,g

a,b,c a,b,c, d,e,f,g

a,b,c, d,f,g

cifre.in cifre.out Explicaţii 1 823

17 V = 1, deci se rezolvă NUMAI prima cerință. N = 823; Pentru afișarea cifrei 8 s-au aprins 7 segmente, pentru cifra 2 s-au aprins 5 segmente și pentru cifra 3 tot 5 segmente. În total s-au aprins 17 segmente.

cifre.in cifre.out Explicaţii 2 823

5 V = 2, deci se rezolvă NUMAI a doua cerință. N = 823; Din cifra 8 nu se mai pot obține alte cifre prin aprinderea de noi segmente. Din cifra 2 se poate obține cifra 8 iar din cifra 3 se pot obține cifrele 8 și 9 prin aprinderea de noi segmente. Așadar, se pot obține 5 numere mai mari ca 823: 828, 829, 883, 888, 889.

_____________ Problema 1 – cifre pag. 1 din 2

Ministerul Educaţiei Naționale și Cercetării Științifice Olimpiada Judeţeană de Informatică Clasa a IX-a 12 martie 2016 Sursa: ID1.c, ID1.cpp, ID1.pas

Dimensiunea maximă a sursei: 5 KB.

_____________ Problema 1 – cifre pag. 2 din 2

Ministerul Educaţiei și Cercetării Științifice Olimpiada Judeţeană de Informatică Clasa a IX-a 7 martie 2015 Sursa: ID2.c, ID2.cpp, ID2.pas Problema 2 - defrag 100 puncte

Discul dur (hard disk) este un dispozitiv utilizat pentru stocarea datelor. Stocarea se face pe o suprafață magnetică dispusă pe platane rotunde metalice. Pe un platan, datele sunt organizate în piste și sectoare, iar zona aflată la intersecția dintre o pistă și un sector poartă denumirea de cluster.

Un cluster poate avea două stări: liber, dacă nu conține date, sau ocupat, atunci când conține date. Un platan se numește defragmentat dacă toți clusterii ocupați de pe fiecare pistă sunt așezați în ordine

consecutivă. Defragmentarea se realizează prin mutarea unor clusteri ocupați și are rolul de a micșora timpul de acces la date. Mutarea unui cluster reprezintă transferul datelor de la un cluster ocupat către un cluster liber de pe aceeași pistă.

Cerință

Cunoscând numărul de piste P și de sectoare S al unui platan, numărul și poziția clusterilor ocupați, să se scrie un program care determină :

1. numărul de piste care au toți clusterii liberi; 2. numărul minim de mutări de clusteri, pentru fiecare pistă în parte, astfel încât platanul să devină defragmentat.

Date de intrare Pe prima linie a fişierului de intrare defrag.in se găsește numărul natural V a cărui valoare poate fi doar 1 sau 2.

Pe a doua linie a fișierului de intrare se găsesc două numere naturale P și S, separate printr-un spaţiu, cu semnificaţia din enunţ.

A treia linie conţine un număr natural C reprezentând numărul total de clusteri ocupați de pe platan, iar pe fiecare din următoarele C linii se găsește câte o pereche de valori pi şi si, 1 ≤ i ≤ C, separate printr-un spaţiu, reprezentând pista, respectiv sectorul unde se află fiecare cluster ocupat. Date de ieşire Fișierul de ieșire este defrag.out.

Dacă valoarea lui V este 1 atunci fişierul de ieşire va conţine pe prima linie un număr natural ce reprezintă numărul de piste care au toți clusterii liberi.

Dacă valoarea lui V este 2 atunci fişierul de ieşire va conține pe prima linie P numere naturale notate Mi, 1 ≤ i ≤ P, separate prin câte un singur spațiu, unde Mi reprezintă numărul minim de mutări de clusteri, dintre cei aflați pe pista i, astfel încât pe pista i clusterii ocupați să se găsească într-o ordine consecutivă. Restricţii şi precizări

• 1 ≤ P ≤ 100 • 1 ≤ S ≤ 360 • 1 ≤ C ≤ P*S • pistele sunt numerotate de la 1 la P începând cu pista exterioară; • sectoarele sunt numerotate de la 1 la S în sensul acelor de ceasornic începând cu sectorul 1; • dacă o pistă are toți clusterii liberi, atunci valoarea cerută la a doua cerință este 0; • 20% din teste vor avea valoarea V = 1, iar 80% din teste vor avea valoarea V = 2.

_______________ Problema 2 – defrag pag. 1 din 2

Ministerul Educaţiei și Cercetării Științifice Olimpiada Judeţeană de Informatică Clasa a IX-a 7 martie 2015 Sursa: ID2.c, ID2.cpp, ID2.pas Exemple

Timp maxim de executare: 0,2 secunde/test. Total memorie disponibilă: 4 MB. Dimensiunea maximă a sursei: 10 KB.

defrag.in defrag.out Explicaţii

1 4 8 10 1 1 1 3 1 5 1 7 4 5 4 1 4 6 4 8 2 2 2 4

1

Datele corespund figurilor anterioare : V = 1, deci se rezolvă NUMAI prima cerință. • Numărul de piste P = 4 , numărul de sectoare S = 8 • Numărul total de clusteri ocupați este C = 10 (cei marcați cu negru) • Pe prima pistă sunt 4 clusteri ocupați, în sectoarele 1, 3, 5 si 7. • Pe a doua pistă sunt 2 clusteri ocupați, în sectoarele 2 și 4. • Pe a treia pistă nu sunt clusteri ocupați. • Pe a patra pistă sunt 4 clusteri ocupați, în sectoarele 1, 5, 6 și 8. O singură pistă are toți clusterii liberi, pista numărul 3, deci valoarea cerută este 1;

defrag.in defrag.out Explicaţii

2 4 8 10 1 1 1 3 1 5 1 7 4 5 4 1 4 6 4 8 2 2 2 4

2 1 0 1 Datele corespund figurilor anterioare : V = 2, deci se rezolvă NUMAI a doua cerință. • Pe prima pistă sunt necesare minim două mutări de clusteri pentru ca toți

clusterii ocupați să se găsească într-o ordine consecutivă, deci valoarea cerută este 2.

• Pe a doua pistă este suficientă o singură mutare de cluster, pentru ca toți clusterii ocupați să se găsească într-o ordine consecutivă, deci valoarea cerută este 1.

• Pe a treia pistă nu sunt clusteri ocupați, deci valoarea cerută este 0.

• Pe a patra pistă este suficientă o singură mutare de cluster, pentru ca toți clusterii ocupați să se găsească într-o ordine consecutivă, deci valoarea cerută este 1.

_______________ Problema 2 – defrag pag. 2 din 2

Ministerul Educaţiei Naționale și Cercetării Științifice Olimpiada Județeană de Informatică Clasa a IX-a 12 martie 2016 Sursa: ID2.c, ID2.cpp, ID2.pas Problema 2 - pic 100 puncte

Alex s-a angajat în vacanța de vară ca barman. Pentru că îi place să transforme munca la bar într-un spectacol, uneori aranjează mai multe pahare identice ca formă și dimensiune, dar de capacități diferite, sub forma unei stive.

Un pahar din stivă, cu excepția celor de la bază, se sprijină pe exact două pahare din rândul de mai jos. Paharele sunt numerotate ca în imaginea alăturată. Nivelurile din stivă sunt deasemenea numerotate, începând cu 1, de la vârf, adică paharul 1 se află pe nivelul 1, paharele 2 și 3 pe nivelul 2, paharele 4, 5 și 6 sunt pe nivelul 3, ș.a.m.d.

Alex toarnă în fiecare secundă câte un mililitru de apă (o picătură) în paharul numărul 1. Paharele au o proprietate ciudată atunci când sunt pline: primul mililitru care ajunge într-un pahar plin se va scurge instantaneu în paharul aflat imediat în stânga sa pe rândul de dedesubt, următorul mililitru se va scurge instantaneu în paharul aflat imediat în dreapta sa pe rândul de dedesubt și tot așa, alternativ câte o picătură în cele două pahare.

De exemplu când paharul 2 este plin, primul mililitru ce va ajunge în el se va scurge în paharul 4, următorul mililitru se scurge în paharul 5, al treilea mililitru se va scurge din nou în paharul 4, ș.a.m.d.

Atunci când într-un pahar plin aflat la baza stivei ajunge un nou mililitru de apă, acesta se scurge instantaneu pe masă.

Cerinţă Cunoscând numărul de pahare din rândul de la baza stivei și faptul că stiva este completă (toate rândurile conțin numărul maxim de pahare ce se pot așeza după regula de mai sus, iar pe cel mai de sus rând se găsește un singur pahar), să se scrie un program care determină: 1. Care este nivelul minim (cel mai de sus) care are suma capacităților tuturor paharelor de pe nivel maximă? 2. Care este numărul minim de secunde necesar pentru a umple toate paharele folosind procedeul descris mai sus și

câți mililitri de apă se risipesc (se scurg pe masă) în acest caz?

Date de intrare Pe prima linie a fișierului de intrare pic.in se găsește un număr natural V a cărui valoare poate fi doar 1 sau 2. Pe a doua linie a fișierului de intrare se găsește un singur număr natural N reprezentând numărul de pahare din rândul de la baza stivei. Pe a treia linie a fișierului de intrare se găsesc M = N*(N+1)/2 numere naturale C1,C2,...,CM separate prin câte un spațiu, Ci reprezentând capacitatea (în mililitri) a paharului numărul i din stivă.

Date de ieşire Dacă valoarea lui V este 1 atunci fişierul de ieşire pic.out va conţine pe prima linie un singur număr natural ce reprezintă numărul de ordine al nivelului minim (cel mai de sus) care are suma capacităților tuturor paharelor de pe nivel maximă. Dacă valoarea lui V este 2 atunci fişierul de ieşire va conţine pe prima linie două numere naturale separate printr-un singur spațiu reprezentând numărul minim de secunde scurse până când toate paharele din stivă sunt pline și respectiv numărul de mililitri de apă risipiți (ajunși pe masă) în acel moment. Restricţii

• 2 ≤ N ≤ 50 • 20% din teste vor avea valoarea V = 1, iar 80% din teste vor avea valoarea V = 2. • 35% din teste vor avea N ≤ 17, iar 65% din teste vor avea N > 17. • 1 ≤ C1,C2,...,CM ≤ 25

_____________ Problema 2 – pic pag. 1 din 2

Ministerul Educaţiei Naționale și Cercetării Științifice Olimpiada Județeană de Informatică Clasa a IX-a 12 martie 2016 Sursa: ID2.c, ID2.cpp, ID2.pas Exemple: pic.in pic.out Explicaţii

1 3 2 4 2 1 2 3

2 V = 1, deci se rezolvă NUMAI prima cerință. Pe nivelul 1 se găsește un pahar de capacitate 2. Pe nivelul 2 se găsesc două pahare de capacități 4 și 2. Pe nivelul 3 se găsesc trei pahare de capacități 1, 2 și 3 . Suma capacităților paharelor este: 2 pe nivelul 1, 6 pe nivelul 2 și 6 pe nivelul 3, deci cel mai de sus nivel cu suma maximă - 6,este nivelul 2.

2 3 2 4 2 1 2 3

18 4 V = 2, deci se rezolvă NUMAI a doua cerință. După 10 secunde configurația paharelor este următoarea:

Pahar Număr picături Observații 1 2 Plin 2 4 Plin 3 2 Plin 4 0 5 1 6 1

Cea de a unsprezecea picătură se scurge din paharul 1 în paharul 2 și mai departe în paharul 4. Următoarea picătură se scurge din paharul 1 în paharul 3 si mai departe în paharul 5 care devine plin. ș.a.m.d. După 18 secunde toate paharele sunt pline, și din paharul 1 s-a risipit o picătură, din paharul 2 s-au risipit 3 picături, iar din paharul 3 nu se risipește nici o picătură, deci în total s-au risipit 4 picături.

Timp maxim de executare: 0.5 secunde/test. Total memorie disponibilă: 4 MB. Dimensiunea maximă a sursei: 5 KB.

_____________ Problema 2 – pic pag. 2 din 2

Ministerul Educaţiei şi Cercetării Olimpiada Judeţeană de Informatică Clasa a IX-a 10 martie 2007 Problema 2 – cartele 100 puncte În sediul unei firme se intră doar cu ajutorul cartelelor magnetice. De câte ori se schimbă codurile de acces, cartelele trebuie formatate. Formatarea presupune imprimarea unui model prin magnetizare. Dispozitivul în care se introduc cartelele, numit cititor de cartele, verifică acest model. Toate cartelele au aceleaşi dimensiuni, suprafaţa pătrată şi grosimea neglijabilă. Cele două feţe plane ale unei cartele se împart fiecare în NxN celule pătrate, identice ca dimensiuni. Prin formatare unele celule, marcate cu negru în exemplu, se magnetizează permiţând radiaţiei infraroşii să treacă dintr-o parte în cealaltă a cartelei. În interiorul cititorului de cartele se iluminează uniform una dintre feţele cartelei. De cealaltă parte fasciculele de lumină care străbat cartela sunt analizate electronic. Pentru a permite accesul în clădire modelul imprimat pe cartelă trebuie să coincidă exact cu modelul şablonului care memorează codul de intrare. Prin fanta dispozitivului nu se pot introduce mai multe cartele deodată. Cartela se poate introduce prin fantă cu oricare dintre muchii spre deschizătura fantei şi cu oricare dintre cele două feţe orientate către şablon. După introducere cartela se dispune în plan paralel cu şablonul, lipit de acesta, astfel încât cele patru colţuri ale cartelei se suprapun exact cu colţurile şablonului. Modelele imprimate pe cele două feţe ale unei cartele sunt identice. Unei celule magnetizate îi corespunde pe faţa opusă tot o celulă magnetizată, iar unei celule nemagnetizate îi corespunde una nemagnetizată. O celulă magnetizată este transparentă pentru radiaţia infraroşie indiferent de faţa care se iluminează. Un angajat al firmei are mai multe cartele. Pe unele dintre acestea a fost imprimat noul cod de intrare, iar pe altele sunt coduri mai vechi. Pentru a afla care sunt cartelele care-i permit accesul în sediul firmei angajatul este nevoit să le verifice pe toate, introducându-le pe rând, în toate modurile pe care le consideră necesare, în fanta cititorului de cartele. Cerinţă Scrieţi un program care determină care dintre cartele permite accesul în sediul firmei. Date de intrare Fişierul de intrare cartele.in conţine pe prima linie două numere naturale N şi C despărţite printr-un spaţiu. N este dimensiunea tablourilor care reprezintă modelul şablon şi modelele cartelelelor. C reprezintă numărul de cartele. Urmează C+1 blocuri de câte N linii fiecare. Primul bloc de N linii codifică şablonul. Următoarele C blocuri de câte N linii codifică fiecare câte o cartelă. Pe fiecare linie sunt câte N valori întregi, despărţite printr-un singur spaţiu. Celulelor magnetizate le corespunde valoarea 1, iar celorlalte, valoarea 0. Date de ieşire În fişierul de ieşire cartele.out se vor scrie C linii, câte o valoare pe linie. Pe linia i se va scrie valoarea 1 dacă cartela i permite accesul în clădire şi valoarea 0 în caz contrar. Restricţii şi precizări 1 < N, C

OLIMPIADA DE INFORMATICA 1998 SCUTURI - Ziua 2, Problema 4 Pe o linie orizontala, la distante egale, se afla n obiective punctiforme, numerotate de la 1 la n, inzestrate fiecare cu un scut. Pe o linie paralele cu aceasta se deplaseaza intr-o miscare de "du-te vino" doua dispozitive de tragere care incearca sa distruga obiectivele considerate. Primul dispozitiv porneste din dreptul pozitiei obiectivului 1, se depleaseaza succesiv in dreptul pozitiei obiectivelor 2, 3, ..., n-1, n, n-1, ... etc. Al doilea dispozitiv porneste din dreptul pozitiei obiectivului n, se deplaseaza si se deplaseaza in dreptul pozitiilor obiectivelor n-1, n-2, ..., 2, 1, 2, 3, ... etc. Ambele dispozitive parcurg distanta din dreptul pozitiei unui obiectiv pana in dreptul pozitiei obiectivului urmator intr-o secunda. Pentru fiecare dispozitiv se cunoaste un numar p1, respectiv p2, reprezentand numarul de secunde de la ultima tragere dupa care dispozitivul va trage din nou. Orice dispozitiv poate sa traga doar asupra obiectivului in dreptul caruia se afla. In momentul pornirii, ambele dispozitive trag. Pentru fiecare obiectiv i se cunoaste un numar ri (i

OLIMPIADA DE INFORMATICA 2000 COLIERUL ---------- Pt. numarul natural nenul n

Ministerul Educaţiei şi Cercetării Olimpiada Judeţeană de Informatică Clasa a IX–a 15 martie 2008 Problema 1 - Concurs 100 puncte La Olimpiada Naţională de Informatică participă elevi din mai multe judeţe, fiecare judeţ fiind identificat în mod unic printr-un număr natural. Elevii din fiecare judeţ au asociat câte un număr natural care permite identificarea în mod unic a elevului în cadrul judeţului.

Astfel, orice participant la olimpiada poate fi identificat prin două numere: identificatorul judeţului şi identificatorul elevului în cadrul judeţului.

Pentru a repartiza elevii la calculatoare, organizatorii au nevoie de o listă care să respecte următoarele condiţii:

- lista conţine toţi elevii participanţi la olimpiadă; - oricare doi elevi consecutivi în listă sunt din judeţe diferite; - elevii din orice judeţ apar în listă în ordinea crescătoare a numerelor de identificare.

Cerinţă Scrieţi un program care să genereze lista necesară organizatorilor.

Date de intrare Fişierul de intrare concurs.in conţine pe prima linie un număr natural P reprezentând numărul total de participanţi la ONI. Pe următoarele P linii este descrisă lista participanţilor, câte un participant pe o linie. Pentru fiecare participant sunt scrise două numere naturale separate prin spaţiu J E, unde J reprezintă identificatorul judeţului, iar E reprezintă identificatorul elevului în cadrul judeţului.

Date de ieşire Fişierul de ieşire concurs.out va conţine pe prima linie un număr natural NJ, reprezentând numărul de judeţe din care există participanţi la olimpiadă. Pe cea de a doua linie sunt scrise NJ numere naturale nenule separate prin câte un spaţiu reprezentând (în ordinea crescătoare a numerelor de identificare a judeţelor) numărul de participanţi din fiecare judeţ. Pe următoarele P linii este descrisă lista necesară organizatorilor, câte un elev pe o linie. Pentru fiecare elev este scris mai întâi identificatorul judeţului din care face parte, urmat de un spaţiu, apoi de identificatorul elevului în cadrul judeţului.

Restricţii şi precizări Identificatorii judeţelor sunt numere naturale cuprinse între 1 şi 50. Identificatorii elevilor în cadrul judeţelor sunt numere naturale cuprinse între 1 şi 1000. Numărul total de elevi participanţi la olimpiadă nu depăşeşte 500. Pentru datele de test există întotdeauna soluţie, nu neapărat unică. Pentru determinarea corectă a numărului de judeţe se acordă 20% din punctaj. Pentru determinarea corectă a numărului de judeţe, precum şi a numărului de participanţi din fiecare judeţ se acordă 30% din punctaj. Punctajul se acordă integral pentru rezolvarea tuturor celor 3 cerinţe (număr de judeţe, număr de participanţi din fiecare judeţ şi lista necesară organizatorilor).

Exemplu concurs.in concurs.out 7 1 3 2 4 1 2 5 2 5 3 1 6 1 9

3 4 1 2 1 2 5 2 1 3 5 3 1 6 2 4 1 9

Timp maxim de execuţie/test: 1 secundă.

Ministerul Educaţiei Naţionale Olimpiada Judeţeană de Informatică Clasa a IX-a 1 martie 2014 Sursa: ID1.c, ID1.cpp, ID1.pas

Problema 1 - cool 100 puncte 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 Ai, Ai+1,…, Ai+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.

Cerinţă 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 A1, A2,…, AK 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 A1, A2,…, AK, 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ă.

Date de intrare Fişierul de intrare cool.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare,

numărul p poate avea doar valoarea 1 sau valoarea 2. Pe linia a doua se găsesc, despărțite printr-un spațiu, două numere naturale N K. Pe următoarea linie se găsesc N numere întregi, separate prin câte un spațiu, ce reprezintă elementele şirului.

Date de ieşire Dacă valoarea lui p este 1, atunci se va rezolva numai punctul 1 din cerință. În acest caz, fişierul de ieşire

cool.out va conţine pe prima linie un număr natural, număr ce reprezintă conform cerinței 1, maximul secvenței A1,A2,…,AK, dacă secvența este secvență cool, sau numărul elementelor distincte din secvență, dacă aceasta nu este secvență cool.

Dacă valoarea lui p este 2, se va rezolva numai punctul 2 din cerință. În acest caz, fişierul de ieşire cool.out va avea două linii. Prima linie va conține un număr natural nenul ce reprezintă lungimea maximă a unei secvențe cool, iar următoarea linie un număr natural nenul ce reprezintă numărul de secvențe cool care au lungimea maximă.

Restricţii și precizări • 1 ≤ N ≤ 5000 • 2 ≤ K ≤ 1000 • 1 ≤ A[i] ≤ 1000, 1 ≤ i ≤ N • Pentru 30% dintre teste N ≤ 1000 • Pentru rezolvarea primei cerinţe se acordă 20% din punctaj, iar pentru cerința a doua se acordă 80% din punctaj.

Exemple cool.in cool.out Explicaţie 1 7 4 6 4 5 7 8 3 5

7 Atenție! Pentru acest test se rezolvă doar cerința 1. Secvența 6 4 5 7 este cool. Valoarea maximă din secvență este 7

cool.in cool.out Explicaţie 1 7 6 6 4 5 7 5 4 3

2 Atenție! Pentru acest test se rezolvă doar cerința 1. Secvența 6 4 5 7 5 4 nu este secvență cool. Numărul valorilor distincte din secvență este 2. Valorile distincte sunt: 6,7

cool.in cool.out Explicaţie 2 11 4 7 4 5 6 8 4 5 7 4 3 2

5 2

Atenție! Pentru acest test se rezolvă doar cerința 2. Cele două secvențe cool de lungime maximă 5 sunt: 7 4 5 6 8 6 8 4 5 7

Timp maxim de execuţie: 0.5 secunde/test. Memorie totală disponibilă 2 MB, din care 1 MB pentru stivă Dimensiunea maximă a sursei: 10 KB.

Ministerul Educaţiei, Cercetării,Tineretului şi Sportului Olimpiada Judeţeană de Informatică Clasa a-IX-a 3 martie 2012 Sursa: ID1.c, ID1.cpp, ID1.pas Problema 1 - elicop 100 puncte Un teren de fotbal este folosit pentru aterizarea elicopterelor. Gazonul de pe stadion este parcelat în pătrăţele de aceeaşi dimensiune, cu laturile paralele cu marginile terenului. Liniile cu pătrăţele de gazon sunt numerotate de sus în jos cu numerele 1, 2, ..., m, iar coloanele cu pătrăţele de gazon sunt numerotate de la stânga la dreapta cu numerele 1, 2, ..., n. Din cauza tipului diferit de iarbă se ştie care dintre pătrăţele de gazon sunt afectate sau nu de umbră. Acest lucru este precizat printr-un tablou bidimensional a cu m linii şi n coloane, cu elemente 0 şi 1 (aij= 0 înseamnă că pătrăţelul aflat pe linia i şi coloana j este afectat de umbră, iar aij= 1 înseamnă că pătrăţelul aflat pe linia i şi coloana j nu este afectat de umbră). Fiecare elicopter are 3 roţi pe care se sprijină. Roţile fiecărui elicopter determină un triunghi dreptunghic isoscel. Elicopterele aterizează, astfel încât triunghiurile formate să fie cu catetele paralele cu marginile terenului. În exemplul următor avem patru elicoptere. 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 Pentru a preciza poziţia unui elicopter pe teren este suficient să cunoaştem linia şi coloana vărfurilor ipotenuzei şi poziţia vârfului deasupra (codificată prin 1) sau dedesubtul ipotenuzei (codificată prin -1). Pentru exemplu, elicopterul din stânga sus este dat prin (1,1), (3,3) şi -1, cel din dreapta sus prin (1,9), (5,5) şi 1, cel din stânga jos prin (5,1), (6,2) şi 1, iar cel din dreapta jos prin (5,9), (6,8) şi 1. Un elicopter se consideră că a aterizat greşit, dacă triunghiul format sub el (definit mai sus) are mai mult de jumătate din pătrăţele afectate de umbră. Administratorul terenului de fotbal doreşte să determine numărul N1 de elicoptere, care nu afectează nici un pătrăţel din teren şi numerele de ordine al elicopterelor, care au aterizat greşit în ordine crescătoare: e1, e2, ..., eN2, ştiind că există k elicoptere codificate prin numerele 1, 2, ..., k. Cerinţă Scrieţi un program care să determine, pentru fişierul cu datele din enunţ: numărul de elicoptere N1, care nu afectează nici un pătrăţel din teren şi numerele de ordine al elicopterelor, care au aterizat greşit în ordine crescătoare, precedate de numărul lor N2. Date de intrare Prima linie a fişierului de intrare elicop.in conţine două numere naturale m şi n, separate printr-un spaţiu, cu semnificaţia din enunţ. Următoarele m linii conţin câte n numere 0 sau 1, separate prin câte un spaţiu cu semnificaţia 0 – pătrăţel de gazon care este afectat de umbră, respectiv 1- pătrăţel care nu este afectat de umbră. Pe linia m+2 se află numărul de elicoptere k, iar pe următoarele k linii (în ordinea codificării lor 1, 2, ..., k) câte cinci numere separate prin cate un spaţiu, pentru liniile şi coloanele ipotenuzelor şi poziţia vârfului (1 sau -1), triunghiurilor dreptunghice asociate elicopterelor: L1 C1 L2 C2 p. Date de ieşire Fişierul de ieşire elicop.out va conţine două linii: prima linie numărul N1 de elicoptere, care nu afectează nici un pătrăţel din teren, a doua linie cu numerele naturale N2, e1, e2, ..., eN2 separate prin câte un spaţiu, în ordine crescătoare. Restricţii şi precizări • 2 ≤ m,n ≤ 100; 1 ≤ k ≤ 40 • Nu există suprapuneri de triunghiuri asociate la două elicoptere. Triunghiurile asociate elicopterelor conţin cel puţin

trei pătrăţele. • Pentru determinarea corectă a valorilor N1 se obţine 40% din punctajul unui test, iar pentru determinarea corectă a

valorilor N2, e1, e2, ..., eN2 se obţine 60% din punctajul unui test. Exemplu elicop.in elicop.out Explicaţie

Ministerul Educaţiei, Cercetării,Tineretului şi Sportului Olimpiada Judeţeană de Informatică Clasa a-IX-a 3 martie 2012 Sursa: ID1.c, ID1.cpp, ID1.pas 7 9 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 4 1 1 3 3 -1 1 9 5 5 1 5 1 6 2 1 5 9 6 8 1

2 2 1 3

Elicopterele 2 şi 4 nu afectează niciun pătrăţel de gazon. Elicopterele 1 şi 3 afectează fiecare mai mult de jumătate din numărul pătrăţelelor asociate triunghiurilor dreptunghice şi deci aterizează greşit. Elicopterul 1 face umbră la 6 pătrăţele, din care afectate sunt 4. Elicopterul 3 face umbră la 3 pătrăţele, din care afectate sunt două.

Timp maxim de executare: 1 secundă/test Memorie totală disponibilă: 2 MB, din care 2 MB pentru stivă. Dimensiune maximă a sursei: 5 KB.

Olimpiada de Informatică Clasa a IX-a Faza judeţeană, 28 februarie 2004

Problema 1 – expresie 50 puncte Se dă un şir de n numere naturale nenule x1, x2, …, xn şi un număr natural m. Cerinţă Să se verifice dacă valoarea expresiei m nxxx ...21 exte un număr natural. În caz afirmativ să se afişeze acest număr descompus în factori primi. Date de intrare În fişierul exp.in se află pe prima linie m, pe linia a doua n, iar pe linia a treia numerele x1, x2, …, xn separate între ele prin câte un spaţiu. Date de ieşire În fişierul exp.out se va scrie pe prima linie cifra 0, dacă valoarea expresiei nu este un număr natural, respectiv 1 dacă este un număr natural. Dacă valoarea expresiei este un număr natural pe următoarele linii se vor scrie perechi de forma p e (p este factor prim care apare în descompunere la puterea e≥1). Aceste perechi se vor scrie în ordine crescătoare după primul număr (adică p). Restricţii

• n – număr natural nenul

Ministerul Educaţiei Cercetării şi Inovării Olimpiada Judeteana de Informatică Clasa a IX-a 14 martie 2009 Problema 1– expresie 100 puncte Costel are de rezolvat o temă grea la matematică: având la dispoziţie N numere naturale nenule trebuie să aşeze între acestea 2 operaţii de înmulţire şi N-3 operaţii de adunare, astfel încât rezultatul calculelor să fie cel mai mare posibil. Nu este permisă modificarea ordinii numerelor date. De exemplu, dacă N=5 şi numerele sunt 4, 7, 1, 5, 3, operaţiile pot fi aşezate 4 + 7 * 1 + 5 * 3, 4 * 7 *1 + 5 + 3 e.t.c Cerinţă Scrieţi un program care să aşeze două operaţii de înmulţire şi N-3 operaţii de adunare între cele N valori date astfel încât valoarea expresiei obţinute să fie maximă. Date de intrare Fişierul de intrare expresie.in are următoarea structură: Pe prima linie se află un număr natural N, reprezentând numărul elementelor date. Pe următoarele linii se află cele N numere naturale date, fiecare pe câte o linie. Date de ieşire Fişierul de ieşire expresie.out va conţine, pe prima linie, valoarea maximă obţinută prin evaluarea expresiei. Restricţii şi precizări 4

Ministerul Educaţiei şi Cercetării Olimpiada de Informatică Clasa a IX-a Faza judeţeană, 19 martie 2006 Problema 1 – Flori 100 puncte Fetiţele din grupa mare de la grădiniţă culeg flori şi vor să împletească coroniţe pentru festivitatea de premiere. În grădină sunt mai multe tipuri de flori. Fiecare dintre cele n fetiţe culege un buchet având acelaşi număr de flori, însă nu neapărat de acelaşi tip. Pentru a împleti coroniţele fetiţele se împart în grupe. O fetiţă se poate ataşa unui grup numai dacă are cel puţin o floare de acelaşi tip cu cel puţin o altă fetiţă din grupul respectiv. Cerinţă Fiind dat un număr natural n reprezentând numărul fetiţelor şi numărul natural k reprezentând numărul de flori dintr-un buchet, să se determine grupele care se formează. Date de intrare Fişierul de intrare flori.in conţine pe prima linie, separate printr-un spaţiu, numerele naturale n şi k, reprezentând numărul de fetiţe şi respectiv numărul de flori din fiecare buchet. Fiecare dintre următoarele n linii conţine, pentru fiecare fetiţă, câte k valori separate prin câte un spaţiu reprezentând tipurile de flori culese. Date de ieşire Fişierul de ieşire flori.out va conţine pe fiecare linie câte o grupă formată din numerele de ordine ale fetiţelor separate prin câte un spaţiu, în ordine crescătoare, ca în exemplu. Restricţii şi precizări

• 1

Ministerul Educaţiei, Cercetării,Tineretului şi Sportului Olimpiada Judeţeană de Informatică Clasa a IX–a 19 martie 2011 Sursa: ID2.pas, ID2.cpp, ID2.c Problema 2 – cri 100 puncte

Furnicuţa şi-a construit un depozit pentru grăunţe pe o suprafaţă

de teren dreptunghiulară şi l-a compartimentat în N*M camere identice, de formă pătratică, dispuse câte M pe direcţia Ox şi câte N pe direcţia Oy Din fiecare cameră se poate intra în orice cameră învecinată cu ea (cameră care are un perete comun cu aceasta).

În fiecare cameră, identificată prin coordonatele sale, ca în desenul alăturat în care N=5 şi M=4, furnica a depozitat o cantitate de grăunţe. De exemplu, în camera de coordonate (I,J) este depozitată cantitatea CIJ de grăunţe.

Atât intrarea cât şi ieşirea din depozit se poate face doar prin cele patru camere din colţurile depozitului, adică cele de coordonate (1,1), (1,M), (N,1) şi (N,M) care comunică cu exteriorul.

Pentru a asigura circulaţia aerului în depozit, furnica a montat un sistem de ventilaţie în camera de coordonate (X,Y).

Văzând ce multe grăunţe are furnica pentru iarnă, vecinul ei, leneşul greieraş Cri, s-a hotărât să fure din ele. Cri s-a gândit să intre în depozit prin sistemul de ventilaţie din camera de coordonate (X,Y) şi să iasă prin

una din cele 4 camere din colţurile depozitului care comunică cu exteriorul. A studiat planul depozitului şi a împărţit camerele în patru zone:

• prima zonă, numerotată cu 1, conţine toate camerele de cordonate (I,J) cu 1 ≤ I ≤ X şi 1 ≤ J ≤ Y, cu ieşirea prin camera de coordonate (1,1)

• a doua zonă, numerotată cu 2, conţine toate camerele de cordonate (I,J) cu 1 ≤ I ≤ X şi Y ≤ J ≤ M, cu ieşirea prin camera de coordonate (1,M)

• a treia zonă, numerotată cu 3, conţine toate camerele de cordonate (I,J) cu X ≤ I ≤ N şi 1 ≤ J ≤ Y, cu ieşirea prin camera de coordonate (N,1)

• a patra zonă, numerotată cu 4, conţine toate camerele de cordonate (I,J) cu X ≤ I ≤ N şi Y ≤ J ≤ M, cu ieşirea prin camera de coordonate (N,M)

Cri va intra doar într-una din cele patru zone şi va fura grăunţele doar din camerele conţinute de zona aleasă. Pentru a nu declanşa alarma furnicuţei, el va trebui să treacă cel mult o dată prin fiecare cameră din zonă, să fure întreaga cantitate de grăunţe din aceasta şi să iasă din depozit prin camera ce comunică cu exteriorul, corespunzătoare zonei alese. Cri va trebui să aleagă zona în care va intra astfel încât cantitatea totală T de grăunţe furate să fie maximă, iar numărul K de camere prin care va trece să fie minim.

Cerinţă Scrieţi un program care să determine numerele naturale Z, T şi K, unde Z reprezintă numărul zonei pe care va trebui s-o aleagă Cri astfel încât cantitatea totală T de grăunţe furate să fie maximă, iar numărul K de camere prin va trece să fie minim.

Date de intrare Fişierul cri.in conţine: N M X Y C11 C12...C1M C21 C22...C2M ........... CN1 CN2...CNM

- pe prima linie cele patru numere naturale nenule N M X Y, separate prin câte un spaţiu, cu semnificaţia din enunţ

- pe fiecare din următoarele N linii câte M numere naturale nenule, separate prin câte un spaţiu, reprezentând cantitatea de grăunţe CIJ depozitată în camera de coordonate (I,J) pentru 1 ≤ I ≤ N şi 1 ≤ J ≤ M.

Date de ieşire Fişierul de ieşire cri.out va conţine, pe o singură linie, cele trei numere naturale Z, T şi K determinate de program, separate prin câte un spaţiu, în această ordine.

_______________ Problema 2 - cri pag. 1 din 2

Ministerul Educaţiei, Cercetării,Tineretului şi Sportului Olimpiada Judeţeană de Informatică Clasa a IX–a 19 martie 2011 Sursa: ID2.pas, ID2.cpp, ID2.c Restricţii şi precizări: • 3 ≤ N ≤ 500; 3 ≤ M ≤ 500 • 2 ≤ X < N; 2 ≤ Y < M • M, N, X şi Y sunt numere naturale • Z∈{1,2,3,4} • 1 ≤ CIJ ≤ 8000 ( 1 ≤ I ≤ N şi 1 ≤ J ≤ M ) • CIJ sunt numere naturale ( 1 ≤ I ≤ N şi 1 ≤ J ≤ M ) • Dacă există zone pentru care se obţine aceeaşi cantitate totală maximă T de grăunţe şi se trece prin acelaşi

număr minim K de camere, se va alege zona numerotată cu numărul cel mai mic. • Se acordă:

- 20% din punctaj pentru determinarea corectă a numărului Z - 40% din punctaj pentru determinarea corectă a numărului T - 40% din punctaj pentru determinarea corectă a numărului K

Exemplu cri.in cri.out Explicaţii 5 4 2 3 1 2 3 33 5 4 3 9 2 13 4 15 1 2 3 3 1 5 2 6

2 45 3

Camera de pornire are coordonatele (2,3), iar N=5 şi M=4. Zona 1 conţine camerele de coordonate: (1,1), (1,2), (1,3), (2,1), (2,2), (2,3). Cantitatea maximă de grăunţe pe care o poate fura Cri este 18 trecând prin 6 camere. Zona 2 conţine camerele de coordonate: (1,3), (1,4), (2,3), (2,4). Cantitatea maximă de grăunţe pe care o poate fura Cri este 45 trecând prin 3 camere. Zona 3 conţine camerele de coordonate: (2,1), (2,2), (2,3), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3). Cantitatea maximă de grăunţe pe care o poate fura Cri este 45 trecând prin 12 camere. Zona 4 conţine camerele de coordonate: (2,3), (2,4), (3,3), (3,4), (4,3), (4,4), (5,3), (5,4). Cantitatea maximă de grăunţe pe care o poate fura Cri este 43 trecând prin 7 camere. Astfel, Cri va intra în zona Z=2, va fura cantitatea maximă de grăunţe T=45 trecând prin numărul K=3 minim de camere.

Timp maxim de executare: 0.7 secunde/test Memorie totală disponibilă: 2 MB, din care 1.5 MB pentru stivă. Dimensiune maximă a sursei: 10 KB.

_______________ Problema 2 - cri pag. 2 din 2

Ministerul Educaţiei, Cercetării, Tineretului şi Sportului Olimpiada Judeţeană de Informatică Clasa a IX-a 6 martie 2010 Problema 1 - livada 100 puncte Norocosul Gigel tocmai a primit în dar de la bunicul său, Nelu, o imensă plantaţie de pomi fructiferi. Fost profesor de geometrie, Nelu a plantat în mod riguros pomii fructiferi pe m rânduri paralele, iar pe fiecare rând a plantat exact câte n pomi fructiferi. Însă, din motive mai mult sau mai puţin obiective, domnul Nelu nu a plantat pe fiecare rând toţi pomii de acelaşi soi, ci din mai multe soiuri diferite. Soiurile de pomi plantaţi în livadă sunt codificate cu numere naturale cuprinse între 1 şi p. Cuprins de febra rigurozităţii matematice şi de cea a statisticii, Gigel a definit noţiunea de soi majoritar astfel: dacă pe un rând k format din n pomi fructiferi avem cel puţin [n/2]+1 pomi de acelaşi soi x, atunci spunem că soiul x este soi majoritar pe rândul k (prin [y] se înţelege partea întreagă a numărului real y). Cerinţă Cunoscând numerele m, n şi p, precum şi soiul fiecărui pom de pe fiecare rând al plantaţiei, ajutaţi-l pe Gigel să determine: 1. pe câte rânduri din livadă există un soi majoritar; 2. care este cel mai mare număr de pomi de acelaşi soi plantaţi în poziţii consecutive pe un rând. Date de intrare Fişierul de intrare livada.in conţine pe prima linie trei numere naturale m, n şi p cu semnificaţia din enunţ, iar pe fiecare dintre următoarele m linii se găsesc câte n numere, despărţite prin câte un spaţiu, reprezentând soiurile pomilor de pe rândul respectiv.

Date de iesire Fişierul de ieşire livada.out va conţine două linii: 1. pe prima linie se va scrie un număr natural reprezentând numărul de rânduri din livadă pe care există un soi majoritar; 2. pe a doua linie se va scrie un număr natural reprezentând cel mai mare numar de pomi de acelasi soi plantaţi în

poziţii consecutive pe un rând. Restricţii şi precizări • 1 ≤ m ≤ 100 • 1 ≤ n ≤ 700.000 • 1 ≤ m*n ≤ 700.000 • 1 ≤ p ≤ 998.560.000 • Pe fiecare rând diferenţa dintre valoarea maximă şi cea minimă este cel mult 250.000. • Dacă doar valoarea de pe prima linie este corectă, se acordă 40% din punctaj. Dacă doar valoarea de pe a doua linie

este corectă, se acordă 60% din punctaj. Dacă ambele valori sunt corecte, se acordă 100% din punctajul testului respectiv.

Exemplu livada.in livada.out Explicaţie 4 7 9 2 1 2 3 8 2 2 4 7 2 4 9 7 4 5 5 2 5 5 5 7 2 3 2 3 2 3 1

2 3

Plantaţia este formată din m=4 rânduri, iar pe fiecare rând avem câte n=7 pomi. Pentru ca un soi sa fie majoritar pe un rând trebuie ca pe acel rând să existe cel puţin [7/2]+1 = 4 pomi din soiul respectiv. Există soiuri majoritare pe două rânduri: primul şi al treilea. Pe randul al treilea exista 3 pozitii consecutive in care se afla pomi din acelasi soi (soiul 5).

Timp maxim de execuţie: 1 secundă/test Limita de memorie: 8Mb din care 4Mb pentru stivă Dimensiune maximă a sursei: 20 KB

Ministerul Educaţiei, Cercetării, Tineretului şi Sportului Olimpiada Judeţeană de Informatică Clasa a IX-a 19 martie 2011 Sursa: ID1.pas, ID1.cpp, ID1.c

Problema 1 - vase 100 puncte Specialiştii chimişti au reuşit crearea în laborator a unei game diversificate de substanţe lichide nemiscibile (care nu se amestecă între ele), de aceeaşi densitate şi de culori diferite.

Acest rezultat a fost utilizat de către specialiştii fizicieni pentru studiul principiului vaselor comunicante. Conform acestui principiu „într-un sistem de vase comunicante nivelul lichidului este acelaşi, indiferent de forma vaselor.“

Experimentele fizicienilor se desfăşoară astfel:

Într-un sistem cu două vase comunicante, gradat identic pe fiecare ramură cu 0, 1, 2, 3,..., fizicienii introduc un număr de n lichide, pe ramura din stânga sau pe ramura din dreapta. Volumele introduse din fiecare lichid, notate cu Vi (1≤i≤n), sunt numere naturale nenule pare astfel încât, la echilibru, orice lichid se va aşeza între două gradaţii de aceeaşi parte a unei ramuri sau pe cele două ramuri ale sistemului de vase comunicante. Lichidele sunt identificate prin intermediul culorii acestora, culori numerotate cu 1, 2, 3, ... , n. Introducerea lichidelor în sistemul cu două vase comunicante se face în ordinea crescătoare a numerelor culorilor, începând cu lichidul de culoare 1.

Scopul experimentului este de a determina gradaţia maximă la care se ridică lichidele în sistemul cu două vase comunicante, precum şi între ce gradaţii se găseşte un lichid de culoare x, dintre cele introduse.

De exemplu, dacă în sistemul cu două vase comunicante se introduc n=3 lichide în ordinea: V1=4 lichid de culoare 1 introdus prin ramura din dreapta (operaţie codificată 4 D), V2=4 lichid de culoare 2 introdus prin ramura din stânga (operaţie codificată 4 S) şi V3=2 lichid de culoare 3 introdus prin ramura din stânga (operaţie codificată 2 S) atunci gradaţia maximă la care se ridică nivelul lichidelor în sistemul cu două vase comunicante este 5, iar lichidul de culoare x=2 se găseşte între gradaţiile: 3 pe ramura din stânga (3 S) şi 1 pe ramura din dreapta (1 D), conform figurii alăturate.

Cerinţă Să se scrie un program care cunoscând numărul n de lichide introduse în sistemul cu două vase comunicante, volumul Vi şi ramura prin care se face introducerea lichidului de culoare i (1≤i≤n), precum şi culoarea x, să calculeze gradaţia maximă la care se ridică lichidele în acest sistem la echilibru şi între ce gradaţii se găseşte lichidul de culoare x.

Date de intrare Prima linie a fişierului de intrare vase.in conţine un singur număr natural nenul n, cu semnificaţia de mai sus. Fiecare linie, din următoarele n, conţine câte două valori separate printr-un spaţiu: un număr natural nenul par şi o literă mare, S sau D, reprezentând volumul introdus din lichidul de culoare i, respectiv ramura (S pentru ramura din stânga şi D pentru ramura din dreapta) prin care se face introducerea acestuia. Linia n+2 a fişierului de intrare conţine un singur număr nenul x ce reprezintă culoarea lichidului căutat. Date de ieşire Fişierul de ieşire vase.out va conţine pe prima linie un număr natural nenul ce reprezintă gradaţia maximă la care se ridică lichidele în sistemul de vase comunicante la echilibru. Următoarele două linii vor conţine fiecare câte două valori separate printr-un spaţiu: un număr natural şi o literă mare (S sau D), reprezentând gradaţia şi ramura între care se aşează lichidul căutat. Restricţii şi precizări

• 1 ≤ x ≤ n ≤ 100 000 • 2 ≤ Vi ≤ 100 000 pentru 1 ≤ i ≤ n • sistemul de vase este gradat în aceleaşi unităţi de măsură în care sunt exprimate volumele de lichid;

_______________ Problema 1 – vase pag. 1 din 2

Ministerul Educaţiei, Cercetării, Tineretului şi Sportului Olimpiada Judeţeană de Informatică Clasa a IX-a 19 martie 2011 Sursa: ID1.pas, ID1.cpp, ID1.c

• dacă lichidul căutat, de culoare x, se aşează pe aceeaşi ramură se va afişa întâi gradaţia superioară şi apoi cea

inferioară; • dacă lichidul căutat, de culoare x, se aşează pe ramuri diferite se va afişa întâi gradaţia de pe ramura din

stânga şi apoi cea de pe ramura din dreapta; • dacă una dintre gradaţiile între care se situează lichidul căutat, de culoare x, este 0 atunci se consideră că

aceasta gradaţie se găseşte pe aceeaşi ramură cu cealaltă gradaţie; • pentru rezolvarea primei cerinţe se acordă 20% din punctaj, iar pentru a doua cerinţă 80% din punctaj.

Exemplu

Timp maxim de executare: 0.5 secunde/test. Total memorie disponibilă 4 MB din care 3.5 MB pentru stivă. Dimensiunea maximă a sursei : 5 KB.

vase.in vase.out Explicaţii 3 4 D 4 S 2 S 2

5 3 S 1 D

Se introduc 3 lichide în sistemul de două vase comunicante: - primul cu volumul 4, se introduce prin dreapta şi are culoarea 1; - al doilea cu volumul 4, se introduce prin stânga şi are culoarea 2; - al treilea cu volumul 2, se introduce prin stânga şi are culoarea 3; Se caută gradaţiile ce corespund lichidului de culoare 2. Gradaţia maximă la care ajunge nivelul lichidului este 5. Lichidul de culoare 2 se aşează între gradaţiile 3 pe ramura din stânga şi 1 pe ramura din dreapta.

_______________ Problema 1 – vase pag. 2 din 2

OLIMPIADA DE INFORMATICA 1995 LIFTUL BUCLUCAS ----------------- Intr-un hotel cu cel mult 40 de etaje exista un lift a carui capacitate este de n persoane, 1

Ministerul Educaţiei şi Cercetării Olimpiada de Informatică Clasa a IX-a Faza judeţeană, 26-27 februarie 2005 Problema 2 – MaxD 100 puncte Fiind elev în clasa a IX-a, George, îşi propune să studieze capitolul divizibilitate cât mai bine. Ajungând la numărul de divizori asociat unui număr natural, constată că sunt numere într-un interval dat, cu acelaşi număr de divizori. De exemplu, în intervalul [1, 10], 6, 8 şi 10 au acelaşi număr de divizori, egal cu 4. De asemenea, 4 şi 9 au acelaşi număr de divizori, egal cu 3 etc. Cerinţă Scrieţi un program care pentru un interval dat determină care este cel mai mic număr din interval ce are număr maxim de divizori. Dacă sunt mai multe numere cu această proprietate se cere să se numere câte sunt. Date de intrare Fişierul de intrare maxd.in conţine pe prima linie două numere a şi b separate prin spaţiu (a≤b) reprezentând extremităţile intervalului. Date de ieşire Fişierul de ieşire maxd.out va conţine pe prima linie trei numere separate prin câte un spaţiu min nrdiv contor cu semnificaţia: min = cea mai mică valoare din interval care are număr maxim de divizori nrdiv = numărul de divizori ai lui min contor = câte numere din intervalul citit mai au acelaşi număr de divizori egal cu nrdiv Restricţii şi precizări 1 ≤ a ≤ b ≤ 1000000000 0 ≤ b-a ≤ 10000 Punctaj Dacă aţi determinat corect min, obţineţi 50% din punctaj. Dacă aţi determinat corect nrdiv, obţineţi 20% din punctaj Dacă aţi determinat corect contor, obţineţi 30% din punctaj. Exemplu maxd.in maxd.out Explicaţie 2 10 6 4 3 6 este cel mai mic număr din interval care are

maxim de divizori egal cu 4 şi sunt 3 astfel de numere 6, 8, 10

200 200 200 12 1 200 are 12 divizori iar în intervalul [200,200] există un singur număr cu această proprietate

Timp maxim de execuţie/test: 1 secundă

Olimpiada de Informatică Clasa a IX–a

Faza judeţeană, 23 martie 2003 Problema 2: NUMERE

Gigel este un mare pasionat al cifrelor. Orice moment liber şi-l petrece jucându-se cu numere. Jucându-se astfel, într-o zi a scris pe hârtie 10 numere distincte de câte două cifre şi a observat că printre acestea există două submulţimi disjuncte de sumă egală. Desigur, Gigel a crezut că este o întâmplare şi a scris alte 10 numere distincte de câte două cifre şi spre surpriza lui, după un timp a găsit din nou două submulţimi disjuncte de sumă egală. Cerinţă Date 10 numere distincte de câte două cifre, determinaţi numărul de perechi de submulţimi disjuncte de sumă egală care se pot forma cu numere din cele date, precum şi una dintre aceste perechi pentru care suma numerelor din fiecare dintre cele două submulţimi este maximă. Date de intrare Fişierul de intrare numere.in conţine pe prima linie 10 numere naturale distincte separate prin câte un spaţiu. x1 x2 ...x10 Date de ieşire Fişierul de ieşire numere.out conţine trei linii. Pe prima linie se află numărul de perechi de submulţimi de sumă egală, precum şi suma maximă obţinută, separate printr-un spaţiu. Pe linia a doua se află elementele primei submulţimi, iar pe linia a treia se află elementele celei de a doua submulţimi, separate prin câte un spaţiu. NrSol Smax NrSol – numărul de perechi; Smax – suma maximă x1 ... xk elementele primei submulţimi y1 ... yp elementele celei de a doua submulţimi Restricţii şi precizări 10 ≤ xi, yi ≤ 99, pentru 1 ≤ i ≤ 10 1 ≤ k, p ≤ 9 Ordinea submulţimilor în perechi nu contează. Perechea de submulţimi determinată nu este obligatoriu unică. Exemplu numere.in numere.out Semnificaţie 60 49 86 78 23 97 69 71 32 10 130 276

78 97 69 32 60 49 86 71 10

130 de soluţii; suma maximă este 276, s-au folosit 9 din cele 10 numere prima submulţime are 4 elemente, a doua are 5 elemente

Timp maxim de executare/test: 1 secundă

Ministerul Educaţiei şi Cercetării Olimpiada de Informatică Clasa a IX-a Faza judeţeană, 26-27 februarie 2005 Problema 1 – Numere 100 puncte Mircea este pasionat de programare. El a început să rezolve probleme din ce în ce mai grele. Astfel a ajuns la o problemă, care are ca date de intrare un tablou pătratic cu n linii şi n coloane, componente tabloului fiind toate numerele naturale distincte de la 1 la n2. Pentru a verifica programul pe care l-a scris îi trebuie un fişier care să conţină tabloul respectiv. După ce a creat acest fişier, fratele său, pus pe şotii îi umblă în fişier şi îi schimbă câteva numere consecutive, cu numărul 0. Când se întoarce Mircea de la joacă constată cu stupoare că nu îi merge programul pentru testul respectiv. După câteva ore de depanare îşi dă seama că programul lui este corect şi că fişierul de intrare are probleme. Cerinţă Scrieţi un program care să-l ajute pe Mircea, găsindu-i cel mai mic şi cel mai mare dintre numerele consecutive schimbate de fratele său. Date de intrare În fişierul numere.in se dă pe prima linie n, iar pe următoarele n linii elementele tabloului, câte n elemente pe o linie, separate între ele prin câte un spaţiu, după modificările făcute de fratele lui Mircea. Date de ieşire În fişierul numere.out se va scrie pe un singur rând cu un singur spaţiu între ele numerele cerute (primul fiind cel mai mic). Restricţii şi precizări

• 0

Ministerul Educaţiei şi Cercetării Olimpiada Judeţeană de Informatică Clasa a IX–a 10 martie 2007 Problema 1 – paritate 100 puncte În vederea asigurării unei transmiteri cât mai exacte a informaţiilor pe reţea, transmiterea se efectuează caracter cu caracter, fiecare caracter fiind dat prin codul său ASCII, adică o grupă de 8 biţi (octet). Pentru fiecare 8 biţi transmişi se calculează un bit de paritate care are valoarea 0 (dacă codul ASCII al caracterului conţine un număr par de cifre binare 1) sau 1 (în caz contrar). Deoarece în problema noastră se transmit numai caractere ASCII standard, cu codul ASCII din intervalul [32,127], codul lor ASCII are bitul 7 (primul bit din stânga) egal cu 0. Pe această poziţie va fi pus bitul de paritate, economisind astfel câte un bit pentru fiecare caracter transmis. De exemplu, dacă mesajul care trebuie trasmis conţine caracterele "Paritate", succesiunea de biţi transmisă va fi: 01010000 11100001 01110010 01101001 01110100 11100001 01110100 01100101 În plus, pe lângă caracterele amintite, în mesaj mai poate să apară un caracterul special, caracter care indică trecerea la începutul unui nou rând. Acest caracter are codul ASCII 10.

Cerinţă Să se scrie un program care să verifice dacă un text a fost sau nu transmis corect.

Date de intrare Fişierul de intrare paritate.in are pe prima linie o succesiune de caractere '0' şi '1' care reprezintă mesajul transmis. Între caractere nu există spaţii. Linia se termină cu caracterul marcaj de sfârşit de linie (newline).

Date de ieşire Fişierul de ieşire paritate.out are pe prima linie mesajul DA dacă textul a fost transmis corect sau NU în caz contrar. În cazul în care mesajul de pe prima linie este DA liniile următoare vor conţine textul transmis în clar. În cazul în care mesajul de pe prima linie este NU linia următoare va conţine numerele de ordine ale caracterelor care nu au fost transmise corect, în ordine strict crescătoare, separate prin câte un spaţiu.

Restricţii şi precizări • Cei 8 biţi ai codului ASCII a unui caracter se numerotează de la 0 la 7, de la dreapta la stânga, cel mai din

stânga bit fiind bitul 7 iar cel mai din dreapta bitul 0. • Textul transmis are cel mult 60000 caractere. • Numărul de caractere '0' şi '1' din prima linie a fişierului de intrare este multiplu de 8. • Codurile ASCII ale caracterelor din text aparţin mulţimii {10, 32–127}, codul 10 însemnând trecerea la

începutul unui rând nou. • Nici o linie din fişierul de ieşire nu va avea mai mult de 255 caractere. • Caracterele din text sunt numerotate începând de la 0. • mesajele DA/NU din prima linie a fişierului de ieşire se scriu cu majuscule.

Exemple paritate.in paritate.out Explicaţie 0101000011100001011100100110100101110100111000010111010001100101

DA Paritate

Toate codurile sunt corecte

paritate.in paritate.out Explicaţie 010000011111101001101001000010100110010100001010011010100110111101101001

DA Azi e joi

Toate codurile sunt corecte. În text există două caractere cu cod ASCII 10

Timp maxim de execuţie/test: 1 secundă

paritate.in paritate.out Explicaţie 1101000011100001111100100110100101110100111000010111010011100101

NU 0 2 7

Primul caracter a fost transmis ca succesiunea de biţi 11010000 ceea ce înseamnă că fără bitul de paritate ar fi trebuit să existe un număr impar de cifre 1, ceea ce este fals. Deci caracterul nu a fost transmis corect. Acelaşi lucru se verifică şi pentru caracterele cu numerele de ordine 2 şi 7

Ministerul Educaţiei Cercetării şi Inovării Olimpiada de Informatică Clasa a IX–a Faza judeţeană, 14 martie 2009

Problema 2– placare 100 puncte

O suprafaţă dreptunghiulară de înălţime N şi lăţime M unităţi trebuie acoperită perfect (placată) prin utilizarea unor plăci de formă dreptunghiulară de dimensiune 1 x P sau P x 1, unde P este un număr natural nenul. Suprafaţa dată poate fi privită ca un caroiaj cu NxM pătrăţele egale cu unitatea. O placare corectă a suprafeţei iniţiale se memorează într-un fişier text folosind următoarele convenţii de codificare:

• pe prima linie se precizează dimensiunile N şi M ale suprafeţei; • o placă dreptunghiulară de laţime P este codificată prin numărul natural P, iar o placă de înalţime P se

codifică prin numărul întreg –P; • convenim ca placa având ambele dimensiuni egale cu unitatea să se codifice cu valoarea 1; • pe fiecare din cele N linii ale codificării se află câte un şir de valori întregi reprezentând, în ordine de la

stânga la dreapta, codurile plăcilor care se găsesc amplasate începând de la respectiva linie; • codul P strict mai mare ca 1 al unei placi orizontale apare o singură dată pe linia corespunzătoare pe care se

află placa, iar codul –P al unei placi verticale va apare o singură dată şi anume pe prima linie de la care placa respectivă este amplasată în jos pe o anumita coloană a suprafeţei;

• Dacă pe o anumită linie a suprafeţei nu există astfel de coduri de plăci, atunci pe respectiva linie din fişier este o singură valoare de 0.

Folosind codificarea unei placări a suprafeţei iniţiale, se poate determina imaginea acestei placări sub forma unui tablou bidimensional A, cu N linii şi M coloane, unde Aij = valoarea absolută a codului plăcii care se suprapune peste pătrăţelul de pe linia i şi coloana j.

Cerinţă Cunoscând codificarea unei placări corecte a suprafeţei date să se obţină imaginea acestei placări (matricea de valori corespunzătoare codificării suprafeţei).

Date de intrare Fişierul de intrare placare.in are următoarea structură: -pe prima linie valorile naturale N M, separate printr-un spaţiu, unde N este înălţimea suprafeţei, M este lăţimea suprafeţei. -pe fiecare din următoarele N linii se află un şir de valori întregi, separate prin câte un spaţiu, reprezentând codificarea respectivei linii a placării.

Date de ieşire În fişierul de ieşire placare.out se va tipări tabloul bidimensional ce reprezintă imaginea placării, compus din N linii, pe fiecare dintre ele aflându-se M valori naturale separate prin câte un spaţiu, cu semnificaţia din enunţ.

Restricţii şi precizări 1

Ministerul Educaţiei şi Cercetării Olimpiada Judeţeană de Informatică Clasa a IX–a 15 martie 2008

Problema 2 - Pluricex 100 puncte Anul acesta se organizează prima ediţie a Olimpiadei Pluridisciplinare pentru Centrele de Excelenţă, PluriCEX. Fiecare Centru de Excelenţă din ţară va trimite la concurs o echipă formată din k membri (toţi participanţi la Centrul de Excelenţă). Echipa va trebui să rezolve probleme interdisciplinare, disciplinele vizate fiind cele de la Centrul de Excelenţă (D discipline, pe care le vom considera numerotate de la 1 la D). Directorul CEX Iaşi a făcut o listă cu primii n cei mai buni elevi de la CEX, apoi a numerotat elevii de la 1 la n, în ordinea apariţiei lor în listă. Pentru fiecare elev, directorul a notat disciplinele la care el participă la CEX. Cerinţă Scrieţi un program care să determine toate echipele ce pot fi formate din k dintre cei n elevi de pe lista directorului, cu condiţia ca pentru fiecare disciplină să existe în echipă cel puţin un membru care să studieze la CEX disciplina respectivă. Date de intrare Fişierul de intrare pluricex.in conţine pe prima linie trei numere naturale n k D (cu semnificaţia din enunţ). Urmează n linii care descriu participările la CEX ale celor n elevi de pe lista directorului. Mai exact, pe linia i+1 este descrisă participarea elevului i astfel: nr d1 d2 ... dnr Primul număr de pe linie (nr) indică numărul de discipline la care participă elevul i. Următoarele nr numere reprezintă disciplinele la care participă elevul i. Numerele scrise pe aceeaşi linie sunt separate prin spaţiu. Date de ieşire Fişierul de ieşire pluricex.out va conţine toate echipele ce se pot forma respectând condiţiile din enunţ, câte o echipă pe o linie. Membrii unei echipe vor fi scrişi în ordine crescătoare, separaţi prin câte un spaţiu. Echipele vor fi scrise în ordine lexicografică. Restricţii şi precizări • 0 < n ≤ 22 • 0 < k ≤ 8 • 0 < D ≤ 10 • Pentru datele de test problema admite întotdeauna soluţie, numărul de soluţii fiind < 20000. • Spunem că vectorul (x1, x2, ..., xn) precedă lexicografic vectorul (y1, y2, ..., yn) dacă există un indice i

astfel încât xj=yj, pentru orice 1≤j

Ministerul Educaţiei şi Cercetării Olimpiada de Informatică Clasa a IX-a Faza judeţeană, 19 martie 2006 Problema 2 – Pluton 100 puncte Î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. Cerinţă 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). Date de intrare Fişierul de intrare pluton.in conţine pe prima linie numărul n de soldaţi recuperaţi, iar pe fiecare dintre următoarele n linii câte un număr de identificare a celor n soldaţi. Date de ieşire Fişierul de ieşire pluton.out va conţine pe prima linie numărul de plutoane refăcute. Linia a doua va conţine numărul de soldaţi din cel mai numeros pluton refăcut. Linia a treia va conţine numărul de plutoane care au numărul maxim de soldaţi recuperaţi. Linia a patra va conţine componenţa unui astfel de pluton, cu număr maxim de soldaţi recuperaţi, numerele de identificare ale soldaţilor din componenţă fiind scrise unul după altul separate prin câte un spaţiu. Restricţii 0

Ministerul Educaţiei Naționale Olimpiada Judeţeană de Informatică Clasa a IX-a 1 martie 2014 Sursa: ID2.c, ID2.cpp, ID2.pas Problema 2 – pseudobil 100 puncte Suprafața plană a unei mese de pseudo-biliard este formată din n x n celule pătratice cu lungimea laturii egală cu 1 (o unitate), lipite, dispuse pe n linii numerotate de la 1 la n și n coloane, numerotate de la 1 la n. Pe masă se așează K bile, fiecare bilă găsindu-se în centrul unei anumite celule a mesei. Un jucător dorește să plaseze pe suprafața mesei un cadru pătratic având lungimea diagonalei egală cu D unități.

El trebuie să răspundă la m întrebări de forma: x y. Fiecare întrebare are semnificația: câte bile se găsesc în interiorul sau pe laturile cadrului ?

Cadrul se plasează astfel încât fiecare colț să fie poziționat în centrul unei celule, colțurile opuse să se găsească pe aceeași coloană, respectiv pe aceeași linie, iar colțul “de sus” să fie plasat în centrul celulei aflată pe linia x și coloana y. Cerinţă

Cunoscând lungimea n a laturilor mesei, numărul m de întrebări, numărul K de bile așezate pe masă, pozițiile lor și lungimea D a diagonalei cadrului pătratic, se cere:

1. Numărul de celule care se vor găsi în întregime în interiorul cadrului, dacă acesta se așează pe suprafața mesei, conform descrierii de mai sus.

2. Câte un răspuns pentru fiecare dintre cele m întrebări.

Date de intrare Fişierul de intrare pseudobil.in conţine pe prima linie un număr natural p. Pentru toate

testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe linia a doua se găsesc numerele naturale n, K și D separate prin câte un spațiu. Pe fiecare dintre următoarele K linii, se găsesc câte două numere a și b (a, b ≤ n)

reprezentând linia și coloana celulei în centrul căreia va fi așezată o bilă. Pe linia K + 3 se găsește un număr natural m. Următoarele m linii conțin câte două numere naturale x și y, reprezentând linia și coloana celulei

în centrul căreia se va plasa colțul „de sus” al cadrului. Date de ieşire

Dacă valoarea lui p este 1, se va rezolva numai punctul 1 din cerință. În acest caz, în fişierul de ieşire pseudobil.out se va scrie un singur număr natural n1, reprezentând numărul de celule care se vor găsi în întregime în interiorul cadrului.

Dacă valoarea lui p este 2, se va rezolva numai punctul 2 din cerință. În acest caz, fişierul de ieşire pseudobil.out va conține m linii. Pe fiecare linie i se va scrie câte un număr natural n2, reprezentând răspunsul pentru întrebarea i.

Restricţii şi precizări

• 3 ≤ n ≤ 1500 • 1 ≤ K ≤ 55 000 • 2 ≤ D ≤ n – 1 , D – număr par • 1 ≤ m ≤ 100 000 • Pozițiile cadrului sunt distince. • Se garantează pentru x și y valori pentru care cadrul este plasat în interiorul suprafeței mesei de

pseudo-biliard. • Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se

acordă 80 de puncte. • Pentru primele 35% dintre testele care verifică cerința 2, m ≤ 1000 și n ≤ 500 • Pentru primele 75% din testele care verifică cerința 2, m ≤ 10000 și n ≤ 1000

Ministerul Educaţiei Naționale Olimpiada Judeţeană de Informatică Clasa a IX-a 1 martie 2014 Sursa: ID2.c, ID2.cpp, ID2.pas

Exemple pseudobil.in pseudobil.out Explicaţie 1 5 2 4 3 4 5 2 1 1 3

5

p = 1 n = 5, K = 2, D = 4 D = (3 unități + 2*0.5 unități) = 4 Numărul de celule aflate în întregime în interiorul cadrului este n1 = 5

Atenție! Pentru acest test se rezolvă doar cerința 1. Se observă că în acest caz este suficient să se citească datele aflate pe primele două linii.

pseudobil.in pseudobil.out Explicaţie 2 6 5 4 2 3 1 1 5 6 4 4 3 5 2 1 3 2 4

3 2

p = 2, n = 6, K = 5, D = 4. Prima întrebare este: 1 3 . Sunt două bile pe laturile cadrului și una în interior, deci n2 = 3 A doua întrebare este: 2 4. O bilă se găsește pe una dintre laturile cadrului și una în interior, deci n2 = 2

Atenție! Pentru acest test se rezolvă doar cerința 2.

Timp maxim de execuţie: 1 secundă/test. Memorie totală disponibilă 64 MB, din care 16 MB pentru stivă Dimensiunea maximă a sursei: 10 KB.

Olimpiada de Informatică Clasa a IX-a Faza judeţeană, 28 februarie 2004 Problema 2 – reactivi 50 puncte Într-un laborator de analize chimice se utilizează N reactivi. Se ştie că, pentru a evita accidentele sau deprecierea reactivilor, aceştia trebuie să fie stocaţi în condiţii de mediu speciale. Mai exact, pentru fiecare reactiv x, se precizează intervalul de temperatură [minx, maxx] în care trebuie să se încadreze temperatura de stocare a acestuia. Reactivii vor fi plasaţi în frigidere. Orice frigider are un dispozitiv cu ajutorul căruia putem stabili temperatura (constantă) care va fi in interiorul acelui frigider (exprimată într-un număr întreg de grade Celsius). Cerinţă Scrieţi un program care să determine numărul minim de frigidere necesare pentru stocarea reactivilor chimici. Date de intrare Fişierul de intrare react.in conţine: – pe prima linie numărul natural N, care reprezintă numărul de reactivi; – pe fiecare dintre următoarele N linii se află min max (două numere întregi separate printr-un spaţiu);

numerele de pe linia x+1 reprezintă temperatura minimă, respectiv temperatura maximă de stocare a reactivului x.

Date de ieşire Fişierul de ieşire react.out va conţine o singură linie pe care este scris numărul minim de frigidere necesar. Restricţii

• 1

Ministerul Educaţiei, Cercetării, Tineretului şi Sportului Olimpiada Judeţeană de Informatică Clasa a IX-a 03 martie 2012 Sursa: ID2.c, ID2.cpp, ID2.pas Problema 2 - roata 100 puncte Una dintre atracţiile celebrului parc de distracţii Prater din Viena este Marea Roată Vieneză. Din ea se poate admira priveliştea întregii Viene.

Roata are n cabine, numerotate de la 1 la n în sens orar şi dispuse simetric pe circumferinţa roţii. Îmbarcarea clienţilor se face în cabina în care roata este tangentă cu solul, iar rotirea începe cu cabina 1 aflată în poziţia de îmbarcare şi se face în sens antiorar. Un client plăteşte pentru o rotire 1 EUR şi poate cumpăra un număr oarecare de rotiri. Cei p clienţi care doresc utilizarea roţii trebuie să respecte următoarea procedură: clientul cu numărul de ordine i îşi cumpără un bilet pe care sunt înscrise numărul său de ordine şi numărul de rotiri ci, 1≤ i ≤ p, apoi se aşează la rând. Când în poziţia de îmbarcare este o cabină liberă sau se eliberează o cabină, roata se opreşte şi urcă următorul clientul. Un client coboară după ce se efectuează numărul de rotiri înscris pe bilet. Cerinţă Să se scrie un program care, cunoscând numărul n de cabine al roţii, numărul p de clienţi, precum şi numărul de rotiri cumpărate de fiecare client, ci ,1≤ i ≤ p, să calculeze:

• suma totală încasată de administratorul roţii de la clienţi; • ordinea în care coboară clienţii din roată; • numărul cabinei din care coboară ultimul client.

Date de intrare Fişierul de intrare roata.in conţine pe primul rând numărul natural n, pe al doilea rând numărul natural p iar pe al treilea rând numerele naturale ci , 1≤ i ≤ p, separate printr-un spaţiu, cu semnificaţiile de mai sus. Date de ieşire Fişierul de ieşire roata.out va conţine pe prima linie suma totală încasată, pe a doua linie numerele de ordine ale clienţilor, în ordinea coborârii, separate printr-un spaţiu, iar pe a treia linie numărul cabinei din care va coborî ultimul client. Restricţii şi precizări

• 2 ≤ n ≤ 360 • 1 ≤ p ≤ 100 000 • 1 ≤ ci ≤ 100 000 • pentru rezolvarea primei cerinţe se acordă 20% din punctaj, iar pentru celelalte două cerinţe se acordă

câte 40% din punctaj fiecare. Exemplu roata.in roata.out Explicaţie 4 7