Lista de probleme 1987

Filtrare

#1228 SSK

Manole a învățat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii și M coloane. El numerotează liniile de la 1 la N și coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Șirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător.

Prin subtablou el înțelege o zonă dreptunghiulară din matricea A, identificată prin colțul stânga-sus (x1,y1) şi colţul dreapta-jos (x2,y2), elementele subtabloului fiind toate elementele A[i][j] pentru care x1≤i≤x2 şi y1≤j≤y2. Suma unui subtablou este suma tuturor elementelor sale.

În acest an evenimentul ”Hour of Code” a înregistrat un număr record de participanți din țara noastră. În cadrul acestui eveniment una dintre cele mai accesate aplicații a fost Lightbot, care a permis elevilor să-și testeze abilitățile de programare.

Aplicația Lightbot are N nivele, numerotate consecutiv de la 1 la N, în ordinea strict crescătoare a complexității lor. Lightbot a permis fiecărui participant să înceapă cu orice nivel strict mai mic decât N-1 și să sară peste un singur nivel, fără a finaliza codul, trecând la nivelul următor celui sărit. La finalizarea cu succes a codului corespunzător nivelului curent, participantul este promovat la nivelul imediat următor. Fiecare participant a început scrierea codurilor la un nivel P și a sărit peste un nivel L (P < L < P + K), finalizând K nivele memorate ca o succesiune de numere naturale de forma P, P+1,..., L-1, L+1,..., P+K. Succesiunile de nivele finalizate de participanți au fost memorate în fișierul lightbot.in. Succesiunile corespunzătoare participanților nu se intercalează în fișier.

Scrieţi un program care citeşte succesiunile corespunzătoare nivelelor finalizate de participanții care au jucat Lightbot și determină:

1. numărul total de participanți;
2. numărul celui mai dificil nivel care a fost rezolvat de un număr maxim de participanți;
3. pentru fiecare participant, numărul nivelului sărit de acesta.

Lui Mihai îi place matematica distractivă, sau poate mai mult distracția decât matematica. Pentru a scăpa de teme, el a inventat operația ”smile” notată cu semnul , operație care se aplică numerelor naturale nenule conform exemplelor de mai jos:

  • 6☺4=210
  • 9☺2=711
  • 8☺5=313
  • 7☺6=113
  • 6☺6=12
  • 6☺10=416
  • 43☺1500=14571543
  • 23☺23=46

Profesorul de matematică i-a promis nota 10 pentru invenție, numai dacă știe să determine corect numărul divizorilor pari pentru rezultatul obținut prin operația ”smile”. Astfel, Mihai a primit N perechi de numere (a,b) pentru care trebuie să calculeze a☺b și să determine dacă rezultatul obținut are divizori pari.

Scrieți un program care citește un număr natural N și N perechi de numere naturale (a,b) și afișează:

a) pentru fiecare pereche de numere (a,b), rezultatul a☺b;
b) cel mai mic și cel mai mare rezultat a☺b care nu are divizori pari.

ONI GIM 2015, Clasa a V-a

#1213 Iepuras

Iepurașul Coconaș vrea să ajungă la grădina cu morcovi. Pentru aceasta el trebuie să traverseze prin salturi o zonă cu proprietăți speciale. Zona este formată din N căsuțe numerotate de la 1 la N, dispuse una după cealaltă, iar fiecare căsuță conține un număr natural ce reprezintă cantitatea de energie necesară iepurașului pentru a sări într-o altă căsuță.

Iepurașul pleacă dintr-o anumită căsuță și se deplasează, de la stânga la dreapta, spre grădina cu morcovi după următoarele reguli:

  • numărul înscris în căsuța în care se află iepurașul reprezintă numărul de căsuțe peste care el va sări;
  • dacă numărul înscris în căsuța în care se află iepurașul este număr prim, atunci energia lui se dublează şi va sări peste un număr dublu de căsuţe;
  • numărarea căsuțelor peste care va sări se face de la stânga la dreapta și începe cu căsuța imediat următoare. Astfel, dacă iepurașul se află în căsuța a treia și numărul înscris în această căsuță este 5, iepurașul va ajunge în căsuța cu numărul de ordine 13 (13=3+2*5).
  • dacă iepurașul ajunge într-o căsuță care conține numărul 0, el rămâne acolo pentru că nu mai are energie să sară mai departe, altfel el continuă să sară după regulile descrise mai sus;
  • iepurașul ajunge la grădina cu morcovi dacă ultimul salt pe care îl face depășește căsuța N.

Scrieți un program care citește trei numere naturale P, N și K iar apoi N numere naturale și determină:

1) dacă iepurașul poate ajunge sau nu, la grădina cu morcovi pornind din căsuța K și numărul de salturi pe care le face iepurașul pornind din căsuța K;
2) căsuța de pornire a iepurașului, astfel încât drumul parcurs de el să traverseze un număr maxim de căsuțe. Pentru a determina numărul de căsuțe se vor lua în calcul: căsuța de pornire, toate căsuțele peste care iepurașul a sărit și toate căsuțele în care a ajuns în urma salturilor. Iepurașul poate porni din oricare căsuță. În cazul în care există două sau mai multe căsuțe de pornire care conduc la același număr maxim de căsuțe traversate se va lua în considerare căsuța cu numărul de ordine cel mai mic.

#1215 Mesaj

În țara lui Piticot cuvintele au doar două litere, prima fiind o majusculă (literă mare) iar a doua o minusculă (literă mică). Piticii Mi și Gi se distrează și își trimit mesaje ascunzând cuvintele în cadrul unor secvențe transmise sub forma unor șiruri de litere. Piticul Mi scrie și trimite un mesaj piticului Gi respectând următoarele reguli:

  • un mesaj conține una sau mai multe secvențe;
  • orice literă care apare în mesaj, de cel puțin două ori, pe poziții alăturate, este numită terminator;
  • o secvență se încheie când s-a întâlnit o succesiune de litere terminator;
  • cuvântul este format din prima majusculă și ultima minusculă din secvență, fără a lua în seamă litera terminator a secvenței;
  • o secvență ascunde un cuvânt dacă terminatorul său se repetă de exact două ori și dacă conține cel puțin o literă mare și o literă mică, ignorând terminatorul de secvență;
  • costul unui cuvânt este egal cu numărul total de apariții al celor două litere din care este format, în cadrul secvenței în care a fost ascuns, luând în considerare inclusiv literele terminator.

De exemplu secvența s f u E e t R u E E ascunde un cuvânt deoarece conține și majuscule și minuscule, iar litera terminator de secvență, E, se repetă de exact două ori. Secvența ascunde cuvântul Eu, iar costul cuvântului este 5 (3 litere E + 2 două litere u).

La primirea mesajului, piticul Gi determină, pentru fiecare majusculă, costul maxim al cuvintelor care încep cu aceasta.

Scrieţi un program care determină:

1) numărul de secvențe trimise care nu ascund cuvinte;
2) cuvintele din mesaj, în ordinea în care au fost trimise de piticul Mi;
3) pentru fiecare majusculă, câte cuvinte care încep cu ea au costul maxim determinat de Gi.

După descoperirea ruinelor unei cetăți medievale, arheologii au hotărât restaurarea acesteia, începând cu zidul principal. Acesta este format din N piloni, fiecare cu lățimea de 1 metru, așezați unul lângă altul (lipiți). Se cunoaște înălțimea, în metri, a fiecărui pilon dar, din păcate, nu toți mai sunt acum la același nivel.

Pentru restaurarea zidului, arheologii dispun de cărămizi care au lățimea de câte 1 metru și lungimi variabile, exprimate în metri. Sunt disponibile oricâte cărămizi, de oricare lungime. Considerăm că toate cărămizile disponibile și toți pilonii care alcătuiesc zidul au aceeași grosime, de 1 metru.

Restaurarea constă în două etape:

  • în prima etapă, toți pilonii cu înălțimea mai mare sau egală cu H se retează, aducându-se astfel la înălțimea H, ceilalți, mai scunzi, păstrându-și înălțimea inițială;
  • în a doua etapă se aduc toți pilonii la aceeași înălțime, umplându-se golurile dintre ei cu cărămizi, astfel încât zidul să devină compact; din motive neînțelese, arheologii vor așeza cărămizile “culcate”, fiecare dintre acestea ocupând, eventual, spațiul aflat deasupra mai multor piloni.

Arheologii au analizat situația, independent, pentru Q valori posibile ale lui H.

Pentru fiecare dintre cele Q valori alese pentru înălțimea H, se cere să se determine numărul minim de cărămizi necesare restaurării zidului, independent, pornind de la înălțimile inițiale ale pilonilor.

#1378 Flori2

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.

#1380 pluton

În timpul acţiunii “Furtuna în deşert” din cauza unei furtuni de nisip, n soldaţi s-au rătăcit de plutoanele lor. După trecerea furtunii se pune problema regrupării acestora pe plutoane. Pentru aceasta se folosesc plăcuţele de identificare pe care soldaţii le poartă la gât. Pe aceste plăcuţe sunt scrise numere care pot identifica fiecare soldat şi plutonul din care acesta face parte. Astfel, soldaţii din acelaşi pluton au numărul de identificare format din aceleaşi cifre, dispuse în altă ordine şi numerele de identificare sunt unice. De exemplu, numerele de identificare 78003433, 83043073, 33347008 indică faptul ca cei trei soldaţi care le poartă fac parte din acelaşi pluton.

Fiind date cele n numere de pe plăcuţele de identificare, să se regrupeze cei n soldaţi pe plutoane, indicându-se numărul de plutoane găsite (un pluton refăcut trebuie să aibă minimum un soldat), numărul de soldaţi din cel mai numeros pluton, numărul de plutoane care au acest număr maxim de soldaţi precum şi componenţa unui astfel de pluton (cu număr maxim de soldaţi regrupaţi).

#2178 Furnica

Pe o tablă de şah cu n linii şi n coloane se află firimituri de pâine şi o furnică. Pentru fiecare pătrăţel, inclusiv cel în care se găseşte furnica, aflat pe linia i şi coloana j, cantitatea de firimituri de pâine este egală cu restul împărţirii lui i+j la 6.

#1390 cartele

Î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.