Lista de probleme

#1896 ksir

Fie S un șir de caractere cu litere mici și litere mari. Se sortează în ordine lexicografică toate subsecvențele distincte ale lui S. Se dă un număr K și un vector k cu K numere întregi, se cere pentru fiecare număr cel de k i -lea subșir lexicografic.

Concursul de Informatica "Spiru Haret" Targu Jiu, ed. I

#1623 SumMax1

Avem o matrice triunghiulară cu n linii, cu elemente numere întregi. În această matrice putem construi un traseu după următoarea regulă:

  • primul element al traseului este elementul a1,1
  • dacă elementul ai,j aparţine traseului, atunci următorul element al traseului poate fi doar ai+1,j sau ai+1,j+1, pentru orice 1≤j≤i<n.
  • traseul se va codifica cu numerele de ordine ale coloanelor, parcurgând liniile de la 1 la n. Valoarea traseului este egală cu suma elementelor ce îl formează.
    Traseul evidenţiat în exemplul din dreapta are valoarea 5+4+6+5+4=24, şi se codifică cu 1,2,3,3,4.

Fie mulţimea tuturor traseelor de valoare maximă generate în ordine lexicografică și numerotate. Pentru exemplul de mai sus avem șase trasee de lungime maximă:

  • traseul 1. 1 1 1 1 2 (5+2+7+6+4=24)
  • traseul 2. 1 1 1 2 2 (5+2+7+6+4=24)
  • traseul 3. 1 2 2 2 2 (5+4+5+6+4=24)
  • traseul 4. 1 2 3 3 4 (5+4+6+5+4=24)
  • traseul 5. 1 2 3 4 4 (5+4+6+5+4=24)
  • traseul 6. 1 2 3 4 5 (5+4+6+5+4=24)

Cerința

Cunoscând dimensiunea și elementele unei matrice triunghiulare, respectiv două numere naturale st şi dr (st≤dr), se cere să se determine:

  1. Numărul total al traseelor de valoare maximă. În cazul în care această valoare depășește 2000000000, se va tipări valoarea 2000000001;
  2. Traseele cu numerele de ordine st, st+1, … , dr.

OJI 2016, Clasele XI-XII

#1811 Aritma

Shaka, regele zuluşilor, a dat ordin să se realizeze un sistem de comunicaţii bazat pe tobe (tamtam)care să acopere întreaga ţară. Pentru aceasta el a dispus instruirea celor ce vor urma să transmită mesajele. Problema intervenită este aceea că o parte din cursanţi nu pot face distincţie între sunete şi nu pot reda cu fidelitate succesiunea de sunete pe hârtie. S-a făcut următoarea convenţie de notare: un sunet lung va fi reprezentat prin +, unul scurt prin -, iar unul nedecis (receptorul nu e sigur de lungimea sunetului) prin *.

Spre finalul stagiului Shaka a mers să verifice nivelul de pregătire al cursanţilor. Pentru aceasta el a adunat n cursanţi pe care i-a pus să recepţioneze şi să noteze un mesaj format din m sunete. După transmiterea mesajului s-a constatat că mulţi dintre cursanţi au scris şiruri foarte diferite, ceea ce ducea la o alterare semnificativă a mesajului original, chiar dacă nici cel mai slab pregătit cursant nu a fost indecis la mai mult de jumătate din sunete. Supărat Shaka l-a chemat pe instructorul şef şi, ca să-l pedepsească, i-a cerut ca să determine câte mesaje distincte se pot forma din şirurile scrise de cursanţi.

Olimpiada Naţională de Informatică Gimnaziu Clasa a VIII-a

#1047 Patrat2

Cel mai mare observator astronomic din România și din Europa de Est, aflat la Galați, a captat o imagine a boltei cerești, ce surprinde toate stelele vizibile în acel moment. Imaginea este în format digital, codificată sub forma unui tablou bidimensional, cu N linii și M coloane. Fiecare element al tabloului conține un număr natural care reprezintă intensitatea luminoasă a unei stele.

Numim stea strălucitoare o stea care are intensitatea luminoasă mai mare decât a tuturor stelelor învecinate direct cu ea, pe orizontală, verticală sau diagonală. Numim constelație pătrată patru stele strălucitoare care se află plasate în colțurile unui pătrat cu laturile paralele cu marginile tabloului. Lungimea laturii unei constelații pătrate este egală cu numărul de stele din care este formată latura. O stea strălucitoare poate face parte din mai multe constelații pătrate.

Scrieți un program care să determine:

a) Numărul stelelor strălucitoare;
b) Numărul constelațiilor pătrate;
c) Lungimea laturii pătratului care reprezintă cea mai mare constelație pătrată.

OJI 2014, Clasa a VII-a

Cercetări recente au scos la iveală un vechi document scris într-un dialect ciudat denumit masaretu. Textul conţinut de acest document este format din cuvinte iar între două cuvinte există cel puţin un spaţiu.

Despre acest dialect se cunosc câteva caracteristici:

  • scrierile din acest dialect folosesc literele mici ale alfabetului englez;
  • toate cuvintele dialectului au exact opt litere;
  • cuvintele dialectului sunt formate din silabe. Fiecare silabă are două litere dintre care una este o vocală (adică una dintre literele a e i o u) iar cealaltă o consoană. Rezultă că fiecare cuvânt are patru silabe.

Din păcate documentul descoperit este deteriorat: din unele cuvinte au dispărut una sau mai multe litere. Astfel în document apar grupuri formate din mai puţin de opt litere care nu mai reprezintă cuvinte ale vocabularului dialectului masaretu.

Să se scrie un program care determină:

1) câte cuvinte corecte sunt în documentul recent descoperit.
2) silabele care apar cel mai des în cuvintele corecte din document.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1789 3secv

Să se scrie un program care pentru un şir cunoscut determină pentru câte subsecvenţe ale şirului suma elementelor care le alcătuiesc are un anumit rest dat la împărţirea cu 3.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1663 Vali

De Ziua Îndrăgostiţilor Vali a hotărât să organizeze o petrecere mare pe stadionul oraşului. La petrecere pot participa numai şi numai îndrăgostiţi care şi-au procurat biletele din timp. Biletele oricărui cuplu sunt aproape identice. Ele au proprietatea că numărul de serie are prima cifră 1 pentru băieţi şi *prima cifră 2 pentru fete, continuarea celor două numere este identică. De exemplu, dacă prietenul are biletul cu numărul 134, atunci prietena lui are biletul 234, iar dacă prietena are biletul 2234567890, atunci prietenul ei are biletul 1234567890.
Bineînțeles, că și Vali are bilet și speră să câștige un cadou. Biletul lui Vali are aceeași proprietate ca celelalte bilete, cu o singură excepție: Vali nu va participa cu pereche la acest eveniment.

Pe parcursul desfășurării petrecerii, biletele de intrare vor avea şi rolul de bilet de tombolă. Acestea vor fi introduse într-o urnă şi câteva dintre ele vor fi extrase, iar norocoşii proprietari ai biletelor vor primi cadouri valoroase. Se mai știe că există probabilitatea ca unii participanți să vină la petrecere cu bilete falsificate, având numere identice cu cele de pe un bilet original. Acest fapt se va depista cu ușurință în momentul extragerii.

De Ziua Îndrăgostiţilor Vali a hotărât să organizeze o petrecere mare pe stadionul oraşului. La petrecere pot participa numai şi numai îndrăgostiţi care şi-au procurat biletele din timp. Biletele oricărui cuplu sunt aproape identice. Ele au proprietatea că numărul de serie are prima cifră 1 pentru băieţi şi *prima cifră 2 pentru fete, continuarea celor două numere este identică. De exemplu, dacă prietenul are biletul cu numărul 134, atunci prietena lui are biletul 234, iar dacă prietena are biletul 2234567890, atunci prietenul ei are biletul 1234567890.
Bineînțeles, că și Vali are bilet și speră să câștige un cadou. Biletul lui Vali are aceeași proprietate ca celelalte bilete, cu o singură excepție: Vali nu va participa cu pereche la acest eveniment.

Pe parcursul desfășurării petrecerii, biletele de intrare vor avea şi rolul de bilet de tombolă. Acestea vor fi introduse într-o urnă şi câteva dintre ele vor fi extrase, iar norocoşii proprietari ai biletelor vor primi cadouri valoroase. Se mai știe că există probabilitatea ca unii participanți să vină la petrecere cu bilete falsificate, având numere identice cu cele de pe un bilet original. Acest fapt se va depista cu ușurință în momentul extragerii.

Cunoscând numerele de serie ale tuturor biletelor de intrare la acest eveniment, aflaţi:
a) dacă pe Vali o cheamă Valentina sau îl cheamă Valentin;
b) numărul biletului lui Vali.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1655 Platou C++

Fiind dat un şir de numere, denumim secvenţă a acestuia o parte dintre termenii şirului luaţi de pe poziţii consecutive. Denumim platou al acestui şir o secvenţă formată din valori identice. Lungimea unui platou este egală cu numărul de elemente care îl formează.

De exemplu, în şirul de numere 1 1 1 7 7 3 4 4 4 7 7 avem:

  • platourile 1 1 1 şi 4 4 4 ambele având lungimea 3;
  • platourile 7 7 (cel care începe în poziţia a patra) şi 7 7 (cel care începe pe poziţia a zecea), ambele având lungimea 2;
  • platoul 3 care are lungimea 1.

În schimb nu avem platoul 7 7 7 7 deoarece cele patru elemente egale cu 7 nu sunt pe poziţii consecutive!

Se dă un şir de n numere. Fiecare dintre aceste numere aparţine intervalului [0,1000000]. Asupra acestui şir se pot efectua o singură dată următoarele două operaţiuni în această ordine:

  1. se extrage un platou la alegere;
  2. se inserează platoul extras la pasul anterior într-o poziţie la alegere din şirul rezultat după extragere.

De exemplu, dacă avem următorul şir inițial: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 2 2 8 extragem platoul 2 2 format din elementele aflate în penultima şi antepenultima poziţie şi obţinem şirul: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

În şirul rezultat inserăm platoul 2 2 (pe care l-am extras în pasul anterior) în poziţia a doua şi obţinem şirul: 2 2 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

Să se scrie un program care pentru un şir dat determină:

  1. Lungimea maximă a unui platou din şirul dat iniţial precum şi valoarea cea mai mare a elementelor care formează un platou de lungime maximă.
  2. Lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni precum şi valoarea cea mai mare a elementelor care ar putea forma un astfel de platou.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1788 Rege1

Regele Leonidas trebuie să-și aleagă o armată de 300 de spartani. Surprins de mulțimea mare de voluntari care vor să-l urmeze în viitoarea luptă de la Termopile, regele are nevoie să facă o selecție a războinicilor. Astfel, el a decis să le dea următoarea problemă:

Se dă un arbore cu N noduri (etichetate cu numere consecutive începând de la 1) cu rădăcina în nodul 1, în care fiecare muchie are asociat un cost. Se definește un lanț în jos în arbore ca fiind orice lanț simplu ce unește un nod A cu alt nod B din subarborele lui A. Cu alte cuvinte, un lanț în jos este un lanț de la A la B în care A este strămoș al lui B. Definim costul unui lanț în jos ca fiind suma costurilor muchiilor din care este format lanțul.

Numim acoperire a unui arbore o partiționare a muchiilor în lanțuri disjuncte, a căror reuniune este arborele inițial. Regele Leonidas dorește să acopere întreg arborele cu lanțuri în jos, însa are un număr limitat de lanțuri, notat în continuare cu S.

Se cere să se determine cel mai mic număr K pentru care să existe o partiționare completă a arborelui cu maxim S lanțuri astfel încât costul fiecărui lanț să fie cel mult K. Dacă nu există un astfel de număr K, să se afișeze -1.

Pentru că și tu vrei să lupți alături de Leonidas pentru libertatea Spartei, trebuie să rezolvi această problemă ca să-ți asiguri un loc în primii 300 de spartani. Leonidas este un rege înțelept. Ca să se asigure că nu vor exista Spartani care vor încerca să ghicească rezultatul, el vă cere să răspundeți la T astfel de probleme.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1787 Mapal

Marele inginer NN, a fost numit inspector general al barajelor. În prima zi de lucru el primește un sector dintr-un baraj de lângă un lac de acumulare care conține stricăciuni și are misiunea de a realiza un plan de reparații. În plus, costurile reparațiilor trebuie să fie minime. Sectorul din baraj poate fi reprezentat ca o matrice binară de NxN. El a observat că liniile l1, l2 …, lk și coloanele c1,c2, …, cl sunt singurele care au stricăciuni. Pentru a le repara el trebuie să înlocuiască unele elemente din matrice astfel încât liniile și coloanele stricate să devină palindrom.

Ajutați-l pe NN să găsească numărul minim de înlocuiri și să dovedească că e maestru în baraje de toate felurile.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1769 albume

Tudoraș are o pasiune pentru muzică. El deține câte K albume din discografia fiecăreia dintre cele C formații pe care le ascultă. În fiecare zi, Tudoraș extrage la întamplare exact Q albume din colecția sa, pe care le ascultă în cursul zilei.

La finalul zilei, Tudoraș analizează albumele ascultate. Concret, el numără de la câte formații diferite provin cele Q albume alese și își notează această valoare.

Care va fi media aritmetică a valorilor notate, dacă procesul se repetă pentru un număr infinit de zile? Cu alte cuvinte, care este valoarea medie (expected value) a numărului de formații ascultate într-o zi?

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1786 NN

Marele inginer NN, expert în construirea de baraje, a primit de data aceasta o sarcină mai îmbârligată. Acesta are de construit M baraje peste mai multe râuri dintr-o deltă și îşi planifică pe hârtie milimetrică construcţia fiecărui baraj în parte.

Toate râurile peste care are de construit baraje sunt braţe ale aceluiaşi fluviu şi toate pornesc din exact acelaşi punct pe lungimea fluviului. Pentru a-şi explica schiţa, NN marchează locul de despărţire a tuturor braţelor fluviului printr-un punct O, numit origine. Apoi, din origine pornesc N semidrepte, fiecare reprezentând o porţiune de uscat, astfel încât spaţiul gol dintre 2 semidrepte consecutive va fi considerat un braţ al fluviului.

După ce a desenat schiţa proiectului, NN se întreabă care e numărul de râuri pe care le acoperă complet fiecare baraj. Un baraj acoperă complet un râu dacă intersectează fiecare dintre malurile acestuia. Sarcina voastră este să îl ajutaţi oferindu-i informaţii precise pentru a-şi putea realiza planul cât mai eficient, păstrându-şi renumele.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1785 MZ

Fericit că s-a calificat la ONI, XORin vrea să sărbătorească făcând cât mai mult zgomot. Deoarece e programator, acesta s-a gândit să automatizeze felul în care face zgomot.

Pentru a face zgomot el folosește o placă cu circuite de diverse intensități. Placa poate fi reprezentată sub forma unei matrice cu N linii și M coloane. Fiecare celulă din matrice are o intensitate între 0 și 9 (o celulă cu intensitatea 0 corespunde unei zone goale, fără nici un circuit).

Un circuit începe într-o celulă a matricei și se termină în altă celulă, fiind o succesiune de celule adiacente de aceeași intensitate de la un capăt la celălalt al circuitului, asemenea unui drum pe matrice între cele două celule. Două celule se consideră adiacente dacă au o latură comună, deci o celulă e adiacentă cu maxim patru alte celule.

Placa a fost concepută în așa fel încât să nu apară scurtcircuite, așadar curentul dintr-un circuit poate merge numai într-o singură direcție (cu alte cuvinte, fiecare celulă dintr-un circuit se învecinează cu maxim alte două celule din același circuit). Nu există circuite de aceeași intensitate care să se învecineze.

Zgomotul produs de un circuit este egal cu lungimea lui, adică cu numărul de celule din matrice corespunzătoare circuitului.

Cerințe:

1) Să se afle numărul de circuite.
2) Să se afle valoarea zgomotului maxim care poate fi obținut unind două circuite. Două circuite pot fi unite dacă se poate trage o legătură de la un capăt al unui circuit până la un capăt al celuilalt circuit, numai prin celulele libere ale matricei (de intensitate 0). Legătura trebuie să aibă forma unui circuit. Lungimea circuitului nou creat nu se adaugă la zgomotul produs de cele doua circuite.
3) Să se afișeze placa ce conține legătura care unește două circuite din care se obține zgomotul maxim de la cerința 2. Dacă există mai multe variante, se poate afișa orice placă care conține legătura validă.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1784 Flori3

După o amorţeală care durase mai bine de 3 luni, Mama Natură îşi dădu seama că primăvara stătea să vină şi florile cu care trebuia curând să umple câmpiile nu erau încă pregătite. Înainte de începerea iernii, a lucrat să combine nuanţe din care să creeze flori pline de culoare, iar acum are camera plină de discuri de diferite culori, care aşteaptă să fie asamblate în flori viu colorate, fie pe post de mijloc, fie ca şi petale.

Pentru a forma o floare, Mama Natură alege un mijloc de orice culoare şi cel puţin K petale. Totodată, ea nu îşi doreşte să strice ordinea firească a lucrurilor şi de aceea nu va folosi niciodată două culori diferite de petale pentru aceeaşi floare. Ea admite, în schimb, flori cu petalele și mijlocul de aceeași culoare.

Deoarece timpul e scurt şi Mama Natură are lucruri mai importante de făcut decât să stea să asambleze flori, ea îşi cheamă în ajutor toate prietenele şi doreşte să îi dea fiecăreia ceva de lucru. Pentru aceasta, ea are la dispoziţie un şir D de N numere, unde numărul de pe poziţia i din șir reprezintă câte discuri de culoarea i a pregătit. Apoi, Mama Natură îşi pune M întrebări de forma x y, prin care doreşte să afle care este numărul maxim de flori care se pot forma folosind doar discuri de culori din intervalul [x, y] din şirul D.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1783 FindMin

Se dă un șir P de lungime N cu elemente distincte din mulțimea {1,2..,N}. Pentru fiecare poziție i din șirul P se cere să aflați cea mai mică poziție j, astfel încât P[j] < P[i] și j < i. În caz că o astfel de poziție nu există se consideră -1 ca soluție.

Concursul Interjudeţean de Matematică şi Informatică Grigore Moisil, 2016

#1189 Lenes

Leneşul este un animal foarte leneş. El se deplasează numai în linie dreaptă, dar face din când în când câte un popas. În această problemă leneşul trebuie să traverseze de la nord la sud şi înapoi un teren reprezentat de o matrice de dimensiuni M×N cu valori numere naturale. Valorile reprezintă efortul cerut pentru traversarea zonei respective. Leneşul va alege o coloană pentru traversarea matricei, iar pentru popasuri, în număr de k1, va alege zone alăturate drumului din coloana din stânga sau cea din dreapta. În cazul în care se va întoarce va proceda la fel, dar va face k2 popasuri. Regulile problemei cer ca cele două drumuri să nu aibă zone comune.

Cunoscând dimensiunile M, N ale terenului, numărul de popasuri k1, k2 și efortul pentru traversarea fiecărei zone a terenului, să se determine:

  1. Efortul minim de parcurgere a terenului de la Nord la Sud, folosind k1 popasuri.
  2. Efortul minim de parcurgere a terenului de la Nord la Sud și înapoi de la Sud la Nord, folosind k1 popasuri la deplasarea Nord – Sud, respectiv k2 popasuri la deplasarea Sud – Nord.

ONI 2015, Clasa a IX-a

#1188 Casa

În această poveste este vorba despre o casă cu mai multe camere. O cameră are forma unui pătrat de latură 1. Dacă două camere au un perete comun, atunci se poate trece dintr-o cameră în alta. Casa nu are neapărat formă dreptunghiulară.

O asemenea casă poate fi descrisă în povestea noastră în două moduri:

  • prin matricea minimală: o matrice cu elemente 0 şi 1 în care există N valori egale cu 1, ce corespund camerelor, iar prima linie, ultima linie, prima coloană şi ultima coloană au cel puţin un element egal cu 1.
  • prin construcţie: un şir de N-1 perechi (a[i], b[i]) 1≤i<n în care a[i] din {1,2,…,i} şi b[i] din {N, S, E, V}. Camerele vor fi numerotate de la 1 la n. Perechea (a[i], b[i]) precizează poziţia camerei i+1 faţă de camera a[i]: E înseamnă la dreapta (est), N deasupra (nord), V la stânga (vest), S dedesubt (sud). Observaţi că pentru prima cameră nu există nicio precizare!

De exemplu, casa de mai sus poate fi descrisă de şirul (1 E) (2 E) (2 S) (3 S), adică a doua cameră e “lipită” la est de prima cameră, următoarea (a treia) la est de camera 2, a patra la sud de camera 2, iar ultima la sud de camera 3.

Cerința

  1. Se dă descrierea unei case prin construcţie şi se cere descrierea acesteia prin matricea minimală.
  2. Se dă descrierea unei case prin matricea minimală şi se cere descrierea acesteia prin construcţie.

ONI 2015, Clasa a IX-a

#1709 Asort

Se consideră un număr natural par N și șirul ordonat crescător X format din primele N numere naturale nenule:

X[1] = 1, X[2] = 2, …., X[N] = N.

Pozițiile numerelor din șir se pot modifica doar conform regulii A,după cum urmează:

  • dacă X[1] este număr impar, atunci se interschimbă X[1] cu X[2], X[3] cu X[4], …, X[N-1] cu X[N];
  • dacă X[1] este par atunci se interschimbă X[2] cu X[3], X[4] cu X[5], …, X[N-2] cu X[N-1], iar X[N] cu X[1].

Aplicând de R ori regula A șirului X se transformă șirul dat într-un șir “@A@ sortat”.

Cunoscându-se numerele naturale N, R, K și T, scrieți un program care să determine:
1) Numărul situat pe poziția K în șirul “ A sortat” obținut prin aplicarea de R ori a regulii “ A ” șirului X.
2) Predecesorul și succesorul numărului T în șirul “ A sortat” .

ONI GIM 2016, Baraj

#1706 Stele

Pasionată de astronomie, Teodora dorește să țină evidența numărului de stele din galaxii. Pentru a face lucrurile mai interesante, ea codifică aceste numere într-un sistem propriu, transformându-le într-o înșiruire de litere și cifre după algoritmul următor:

  • notează fiecare putere a lui 2, strict mai mică decât 226, cu o literă a alfabetului, astfel:

20 21 22 23 24 25 26 27 28 29 210 211 212
a b c d e f g h i j k l m
213 214 215 216 217 218 219 220 221 222 223 224 225
n o p q r s t u v w x y z
  • reprezintă fiecare număr ca un șir de cifre și litere obținut din scrierea acelui număr ca sumă de puteri ale lui 2; dacă o putere este folosită de mai multe ori în descompunerea numărului atunci ea va fi precedată în șir de numărul de utilizări.

Un număr poate fi reprezentat astfel în mai multe moduri. De exemplu, pentru numărul 100 printre variantele de reprezentare avem:

  • 100 = cfg = 22+25+26 = 4+32+64 = 100
  • 100 = 2ab2cde2f = 2*20+21+2*22+23+24+2*25 = 2*1+2+2*4+8+16+2*32 = 100
  • 100 = 16bcg = 16*21+22+26 = 16*2+4+64 = 100

Scrieți un program care rezolvă următoarele cerinţe:

  1. cunoscând s numărul de stele dintr-o galaxie, determină o reprezentare codificată a acestui număr formată doar din litere mici distincte ordonate alfabetic;
  2. cunoscând g, reprezentând numărul de galaxii și g numere în scriere codificată, reprezentând numărul de stele din fiecare galaxie, determină scrierea zecimală a numărului total de stele din cele g galaxii.

ONI 2016, clasa a VIII-a

#1705 Farma

Noile reguli din sistemul sanitar cer ca medicii să nu prescrie pe reţete un anumit medicament, ci să menţioneze substanţa activă. Reţeta este formată din n prescripţii, câte una pentru fiecare substanţă activă prescrisă.

Farmacista de la care cumpăr medicamentele mi-a făcut o listă în care pentru fiecare substanţă activă de pe reţetă sunt trecute medicamentele care conţin substanţa activă respectivă, precum şi preţul pastilelor prescrise din medicamentul respectiv, sub forma următoare:

  • substanţa activă : medicament1 preţ1, medicament2 preţ2, ..., medicamentk preţk

Din păcate, între anumite medicamente există incompatibilităţi şi ca urmare ele nu pot fi administrate simultan, deoarece ar produce reacţii adverse. De aceea, farmacista mea mi-a dat şi o listă de incompatibilităţi, în listă fiind specificate perechi de medicamente incompatibile, sub forma:

  • medicament1/medicament2

Când cumpăr reţeta, eu trebuie să iau câte un medicament pentru fiecare substanţă activă prescrisă de medic şi să am grijă să nu cumpăr medicamente care sunt incompatibile. Desigur, voi cumpăra pastilele prescrise pentru tratamentul complet.

Cunoscând lista pe care mi-a dat-o farmacista, precum şi incompatibilităţile dintre medicamente, scrieţi un program care să determine:

  1. câte medicamente am la dispoziţie pentru fiecare substanţă activă;
  2. suma minimă pe care trebuie să o cheltui pentru a cumpăra reţeta.

ONI 2016, clasa a VIII-a

Un grup de N cercetași, numerotați de la 1 la N, se află în tabără la munte. Pentru ei, organizatorii au pregătit N scaune, de asemenea numerotate de la 1 la N, așezate în cerc, astfel încât fiecare cercetaș să aibă locul său (locul cercetașului i este pe scaunul i, 1≤i≤N).

Pentru desfășurarea următoarei activități, organizatorii au decis ca M dintre cercetași să prezinte diferite exerciții. Numărul M este egal cu cea mai mare putere a lui 2 cu proprietatea că numărul N de cercetași aflați în tabără se poate scrie ca sumă de M numere consecutive în mulțimea numerelor impare. Cei M cercetași care vor prezenta sunt cei numerotați cu numerele impare consecutive a căror sumă este N. De exemplu, dacă N=8, atunci M este 2, iar exercițiile vor fi prezentate de cercetașii numerotați cu 3, respectiv cu 5.

Din joacă, micii cercetași s-au așezat pe scaune la întâmplare. Organizatorii au nevoie pentru a desfășura activitatea ca cel puțin cei M cercetași care vor prezenta exercițiile să se afle pe locurile lor. Pentru aceasta, o parte dintre cercetași trebuie să-și schimbe locul și organizatorii invită micii cercetași să participe la jocul numit ”Mutare”. Acest joc se desfășoară astfel: unul dintre cercetașii care nu se află pe locul lor se ridică și merge în interiorul cercului. Cercetașul numerotat cu numărul scaunului rămas liber își va ocupa locul, iar locul ocupat de el anterior rămâne astfel liber. Jocul continuă până când scaunul cercetașului aflat în interiorul cercului se eliberează și el se așază pe locul său.

Fiind dat numărul N, precum și ordinea în care s-au așezat cercetașii pe scaunele numerotate de la 1 la N, scrieți un program care să determine:

  • numărul M de cercetaşi care vor prezenta exerciţii în cadrul activităţii;
  • numerele de identificare ale celor M cercetaşi care vor prezenta exerciţiile, în ordine strict crescătoare;
  • numărul minim de cercetași care își vor schimba locul, astfel încât toţi cei M cercetași care vor prezenta exercițiile să se afle pe locurile lor.

ONI 2016, clasa a VIII-a

#1703 Parchet

Meseria de parchetar a devenit mai uşoară de când a apărut parchetul laminat. Acesta se livrează în plăci pătratice de câte 1 m2 şi montarea lui este destul de uşoară. Gigel este convins că este suficient de priceput să facă această operaţie în propria locuinţă. El dispune de planul locuinţei şi a cumpărat o anumită cantitate reprezentând X m2 de parchet laminat. Planul locuinţei este descris printr-un tablou bidimensional de dimensiuni N x M, fiecare element al tabloului reprezentând exact 1 m2. Pereţii sunt reprezentaţi prin caracterul ‘P’ iar suprafeţele camerelor prin caracterul ‘S’ (spaţiu). În planul din figura următoare este descrisă o locuinţă cu 5 camere acestea având respectiv, suprafeţele de 10, 2, 1, 3, 5 m2.

PPPPPPPPP
PSSSPSPSP
PSSSPSPPP
PSSPPPPSP
PSPPSSPSP
PSPSSSPSP
PPPPPPPPP

Gigel nu este sigur de faptul că parchetul cumpărat îi ajunge. Din această cauză a hotărât iniţial să pună parchetul începând cu camera cea mai mare, apoi în următoarea, în ordinea descrescătoare a suprafeţei şi aşa mai departe, până în momentul în care parchetul rămas nu mai este suficient pentru acoperirea suprafeţei următoarei camere. Nu va lăsa neparchetată o cameră pentru a parcheta una cu o suprafaţă mai mică.

Gigel se mai gândeşte şi la posibilitatea de a acoperi complet un număr maxim de camere folosind întreaga cantitate de parchet.

Fiind date N, M, X şi planul locuinţei să se determine:

  1. numărul C de camere pe care a reuşit să le acopere Gigel şi numărul R de m2 de parchet care îi rămân, procedând aşa cum a hotărât iniţial;
  2. numărul de posibilităţi de parchetare a unui număr maxim de camere, folosind întreaga cantitate de parchet.

ONI 2016, clasa a VII-a

Pietrele preţioase au fascinat omenirea încă din timpuri străvechi iar cele mai renumite dintre ele, cristalele, au devenit atât simbolul durităţii cât şi al eternităţii. În urma unui studiu ştiinţific, pe un eşantion de formă dreptunghiulară se pot observa diferite tipuri de molecule, dispuse într-o geometrie perfectă, pe M rânduri a câte N molecule fiecare, aliniate una lângă alta. O formaţiune cristalizabilă este alcătuită din 3 molecule de acelaşi tip, învecinate două câte două, având una dintre cele patru forme din imaginea alăturată (fig.1).

Fiecare formaţiune este înconjurată de jur-împrejur, ca în fig.2, de un înveliş special format şi el din molecule identice, de alt tip decât cele din formaţiunea cristalizabilă pe care o înconjoară şi o izolează de restul formaţiunilor moleculare. În acest fel, fiecare moleculă din formaţiunea cristalizabilă se învecinează la Nord, Sud, Est şi Vest cu o moleculă din aceeaşi formaţiune cristalizabilă sau cu o moleculă din învelişul special.

Fiecare formaţiune cristalizabilă se bombardează cu raze X şi în acest fel are loc cristalizarea, proces prin care învelişul special se extinde peste formaţiunea cristalizabilă pe care o înconjoară, formând o singură structură din care se va dezvolta cristalul.

Cerințe

  1. Determinaţi numărul formaţiunilor cristalizabile ce pot fi identificate pe eşantionul analizat.
  2. Afişaţi eşantionul rezultat după cristalizare.

ONI 2016, clasa a VII-a

#1701 Birouri

Arhi şi-a propus să extindă clădirea de birouri pe care a proiectat-o iniţial pe un singur nivel numerotat cu 1, împărţit în n*n zone pătratice de latură 1, fiecare corespunzând unui birou, prin construirea mai multor niveluri. În colţurile tuturor birourilor se construiesc grinzi de rezistenţă. Pentru a asigura rezistenţa întregii clădiri, Arhi va proiecta niveluri noi, numerotate cu 2, 3,… atât timp cât conțin cel puțin un birou și sunt respectate următoarele patru reguli:

  • R1: fiecare nivel nou va fi proiectat sub forma unui dreptunghi sau pătrat de arie maximă pentru nivelele cu număr impar, respectiv, sub forma unui pătrat de arie maximă pentru nivelele cu număr par;
  • R2: fiecare dintre colţurile zidurilor unui nivel nou trebuie plasat pe câte o grindă de rezistenţă dintre două sau mai multe birouri de pe nivelul precedent;
  • R3: oricare două dintre colţurile zidurilor unui nivel nou vor fi plasate pe ziduri diferite (un zid nu se poate suprapune în totalitate pe alt zid) şi cel puţin două vârfuri opuse ale unui nivel nou se vor afla pe ziduri opuse ale nivelului precedent;
  • R4: orice porţiune de zid de pe nivelul k (k>1), construită deasupra unui birou de pe nivelul k-1, se va suprapune exact peste una dintre laturile biroului, sau îl va străbate în diagonală.

Birourile de pe nivelul k (k>1), vor fi construite exact deasupra celor de pe nivelul precedent, astfel, nivelurile 2, 4 etc. vor avea lângă ziduri spaţii triunghiulare care nu vor aparţine niciunui birou.

Numerele inscripţionate pe birouri în imaginea de mai sus, indică nivelul corespunzător birourilor vizibile de deasupra clădirii.

Cunoscându-se lungimea n a laturii primului nivel al clădirii, să se determine:

  1. numărul maxim de niveluri pe care le poate avea clădirea;
  2. numărul total de birouri ale clădirii cu număr maxim de niveluri.

ONI 2016, clasa a VII-a

Fie un şir a[1], a[2], …, a[n] de numere naturale, unde n este impar. Avem la dispoziţie o singură operaţie admisă şi anume: putem aduna la două poziţii diferite din şir o aceeaşi valoare naturală nenulă.

Cerințe:

  1. Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
  2. Folosind de mai multe ori operaţia admisă, să se obţină șirul cu toate elementele egale, dar valoarea egală obţinută să nu depăşească dublul valorii maxime din şirul iniţial.

ONI 2016, clasa a V-a

#1699 Robotel

Tudor a primit un joc educaţional numit “Roboţel” cu ajutorul căruia va învăţa punctele cardinale Nord, Est, Sud, Vest. Jocul constă dintr-un roboţel care se deplasează pe o tablă de forma unei matrici pătratice, împărţită în R linii şi R coloane. Fiecare căsuţă, aflată la intersecţia dintre o linie şi o coloană, este fie căsuță „liberă”, fie căsuță „semnalizator”, caz în care este etichetată cu una din literele N, E, S, V, reprezentând 4 sensuri posibile de deplasare. Când roboțelul ajunge într-o „căsuţă semnalizator”, el îşi schimbă sensul de deplasare astfel:

  • Dacă căsuţa este etichetată cu N atunci roboţelul se va deplasa în continuare de jos în sus;
  • Dacă căsuţa este etichetată cu E atunci roboţelul se va deplasa în continuare de la stânga la dreapta;
  • Dacă căsuţa este etichetată cu S atunci roboţelul se va deplasa în continuare de sus în jos;
  • Dacă căsuţa este etichetată cu V atunci roboţelul se va deplasa în continuare de la dreapta la stânga.

Două căsuțe semnalizator formează o pereche „blocantă” dacă:

  • Se află pe aceeași linie și conțin literele E și V, căsuța cu E are coloana mai mică decât a celei etichetate cu V și între ele, pe aceeași linie nu există alte căsuțe semnalizatoare.
  • Se află pe aceeași coloană și conțin literele S și N, căsuța cu S are linia mai mică decât a celei etichetate cu N și între ele, pe aceeași coloană nu există alte căsuțe semnalizatoare.

În figura 1, de exemplu, sunt 2 perechi blocante: Perechea (1,2) (5.2) și perechea (2,3) (2,5).

Roboţelul porneşte din căsuţa (1,1), aflată pe prima linie și prima coloană şi dacă aceasta este liberă, se deplasează, în cadrul primei linii, de la stânga la dreapta. În cazul în care căsuța de pornire (1,1) este semnalizator, atunci roboțelul se va deplasa pe direcția indicată de litera cu care este etichetată. Considerând că roboțelul se deplasează pe tablă, el se oprește doar în următoarele situații:

  • Roboţelul intră într-o căsuţă liberă aflată pe prima sau ultima linie, respectiv prima sau ultima coloană, caz în care dacă s-ar menține sensul deplasării actuale roboțelul ar părăsi tabla;
  • Roboțelul intră într-o „căsuţă semnalizator” a unei perechi blocantă și se va opri în cealaltă căsuță a perechii.

De exemplu, în Figura 2, roboțelul ajunge în căsuța liberă (3,5) unde se oprește. În Figura 3, roboțelul se va opri în căsuța (4,1) deoarece dacă ar schimba sensul spre Est, ar reveni în ultima căsuță semnalizator vizitată, (4,3).
Roboțelul înaintează o căsuță într-un pas, în sensul de deplasare.

Scrieţi un program care, cunoscând numărul R de linii şi coloane și cele K căsuţe semnalizator, determină:

  1. Toate perechile blocante de pe tablă;
  2. Numărul de pași efectuați pe fiecare sens în parte: Nord, Est, Sud și Vest

ONI 2016, clasa a VI-a

#1698 Perm

Considerând K un număr natural, vom numi permutare de mărime K o aranjare într-o ordine oarecare a elementelor mulțimii {1,2,..,K}. Ana găsește scris pe o foaie de hârtie, un șir de numere naturale v = (v[1],v[2],v[3],...,v[N])

Plecând de la acest șir, Ana numește secvență a lui v, un subșir de numere care apar pe poziții consecutive în șirul inițial. De exemplu, șirul 5 7 8 9 1 6 conține secvența 8 9 1, secvența 7 8 9 1 6, dar nu conține secvența 8 9 6.

Anei îi vine ideea să încerce să verifice dacă șirul de numere poate fi împărțit în secvențe care reprezintă permutări de diferite mărimi.

De exemplu, dacă Ana găsește șirul v =(2, 1, 4, 1, 3, 2), atunci ea îl poate împărți în două secvențe de permutări astfel: secvența v[1], v[2] respectiv secvența v[3] , v[4], v[5], v[6].

Dacă Ana găsește șirul v =( 1, 2, 2, 3) atunci nu va putea obține o împărțire în secvențe de permutări.

Realizați un program care citește un șir de N numere naturale și rezolvă următoarea cerință:

  • determină o împărțire a acestuia în secvențe de permutări. Dacă există mai multe soluții se va afișa soluția minim lexicografică.

Dacă șirul poate fi împărțit în secvențe de permutări, pentru fiecare număr din șir, în ordinea v[1], .., v[N], se va afișa numărul permutării din care face parte.

Numerotarea permutărilor se va face consecutiv începând cu numărul 1.

ONI 2016, clasa a VI-a

#1697 Cod1

Ionel și Georgel sunt colegi de clasă și doresc să facă schimb de fișiere prin email. Fiecare dintre ei își arhivează fișierele cu câte o parolă. Fiecare copil își construiește parola pe baza unui șir format din N numere naturale.

Numerele din șir care se folosesc efectiv pentru construirea parolelor sunt doar cele divizibile cu numerele din mulțimea {2,3,4,5,6,7,8,9,10,11,12,13,14,15}. Copiii numără câte din valorile din șir sunt divizibile cu fiecare din aceste numere.

Parola folosită de Ionel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea {2,3,4,5,6,7,8,9}. Parola folosită de Georgel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea {10,11,12,13,14,15}.

Scrieţi un program care citește șirul celor N numere și determină:

  1. câte numere din șir nu se vor folosi în construirea parolelor celor doi copii;
  2. parola construită de Ionel;
  3. parola construită de Georgel.

ONI 2016, clasa a VI-a

#1694 Norocos

Un număr natural nenul m se numește norocos dacă pătratul lui se poate scrie ca sumă de m numere naturale consecutive. Un număr natural m se numește k-norocos, dacă este egal cu produsul a exact k numere prime distincte. Observați că între cele două proprietăți definite nu există nicio legătură.

Dându-se k și N numere naturale, scrieți un program care să determine:

a) Cel mai mic și cel mai mare număr norocos dintre cele N numere citite
b) Câte numere k-norocoase sunt în șirul de N numere citite

ONI 2016, clasa a V-a

#1695 Oglinda

Pentru un număr natural N se consideră șirul a=(1,2,3...,N), deci a[i]=i pentru orice i, 1≤i≤N.

Asupra acestui șir se pot aplica operații de două tipuri:

a) la operația de tipul 1 se specifică două valori i și j, cu 1≤i≤j≤N. Efectul acestei operații asupra șirului este de oglindire a secvenței din șir care începe cu elementul de pe poziția i și se termină cu cel de pe poziția j. De exemplu, dacă în șirul a=(1,2,3,4,5,6,7) se aplică operația 3 6, atunci șirul devine a=(1,2,6,5,4,3,7). Iar în șirul a=(1,4,3,2,5,6,7), dacă se aplică operația 4 6, atunci a=(1,4,3,6,5,2,7).
b) Operația de tipul 2 conține un indice i, 1≤i≤N, și cere să afișăm valoarea elementului care se află în acel moment pe poziția i în șir.

Se consideră M astfel de operații într-o ordine dată.

Scrieți un program care să determine și să afișeze rezultatul pentru fiecare operație de tipul 2.

ONI 2016, clasa a V-a

O matrice pătratică de dimensiuni N x N cu liniile și coloanele indexate de la 1 la N se numește matrice șmecheră de Calafat dacă pe fiecare linie și fiecare coloană există exact două valori de 1, restul elementelor fiind 0.

Având două matrice șmechere de Calafat notate cu A și B, se cere ca prin interschimbări de linii și coloane să se transforme matricea B în matricea A.

ONI 2016, clasele XI-XII

#1692 Calafat

Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între 2 indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st,dr], se cere să se calculeze suma distanțelor corespunzătoare tuturor valorilor distincte din subsecvență.

ONI 2016, clasele XI-XII

#1691 Arbore1

Se dă un arbore (graf conex aciclic) cu N noduri. Vrem să eliminăm noduri (împreună cu muchiile adiacente) din arborele dat, astfel încât numărul de componente conexe ale grafului rămas să fie maxim. Aflați care este numărul maxim de componente conexe pe care le putem obține și câte submulțimi distincte de noduri se pot elimina din arbore astfel încât să rămână la final acest număr maxim de componente conexe.

ONI 2016, clasele XI-XII

#1690 Undo

XORin este nemulțumit de problemele primite în prima zi de concurs de la Olimpiada Națională de Informatică și decide astfel să se implice în comisie. În scurt timp devine specialistul comisiei în generarea de teste formate din șiruri de numere. Din când în când el trebuie să adauge sau să șteargă elemente din șir. Câteodată el decide să readauge dintre elemente șterse anterior. Fie șirul de numere a=(a[1], a[2], … ,a[N]) și N numărul de elemente din șir după fiecare operație.

Astfel el are de realizat următoarele operații pornind de la un șir vid:

  • Inserează la sfârșitul șirului o valoare x;
  • Șterge ultimele x elemente din șir;
  • Readaugă la sfârșitul șirului primele x elemente șterse. Dacă, de exemplu, în operația anterioară de ștergere a unui număr y de elemente, am șters elementele a[N-y+1], a[N-y+2],…, a[N], iar acum urmează o operație de readăugare a x elemente, vor fi adăugate în ordine elementele a[N-y+1], a[N-y+2],…, a[N-y+x] la sfârșitul șirului.

Din când în când XORin își pune următoarea întrebare: de câte ori există valoarea x în șir?

ONI 2016, clasa a X-a

#1689 MoveDel

Se consideră două șiruri de caractere A și B, ambele șiruri având același număr de caractere.

Asupra șirurilor se aplică următorul algoritm:

  • șirul A se permută circular cu ki poziții spre stânga
  • din cele două șiruri se elimină caracterele care coincid din punct de vedere al poziției și valorilor

Algoritmul se oprește când fie ambele șiruri devin vide, fie șirurile nu mai au caractere comune. Valoarea ki pentru fiecare pas i reprezintă al i-lea număr prim din mulțimea numerelor prime.

Dându-se N și M, să se genereze șirurile A și B, ambele având lungimea N, astfel încât numărul de repetări ale algoritmului aplicat celor două șiruri să fie M.

ONI 2016, clasa a X-a

#1688 Intrus

Terminalul unui aeroport este o sală foarte mare având forma unui dreptunghi împărțit în pătrate cu latură unitară. Aici se află mai multe persoane, care trebuie să poarte la vedere un ecuson cu un cod de bare care poate fi citit în orice moment de camerele de supraveghere și decodificat de calculatoarele serviciului de protecție și pază. Într-un pătrat cu latură unitară poate să se afle doar o singură persoană la un moment dat. Sala este reprezentată printr-o matrice cu R linii și C coloane, elementele sale fiind numere naturale de cel mult 6 cifre cu valorile: 0 – pentru spațiu neocupat, respectiv numere naturale nenule, care reprezintă identificatorul (ID-ul) persoanelor. Printre aceste persoane există persoane infiltrate (intruși) care au ID-uri cu valori identice cu ale altor persoane. Dacă există două sau mai multe persoane cu același ID, acestea sunt considerate toate suspecte.

Intrușii vor să ajungă în apropierea unor VIP-uri (persoane importante), pentru a le înregistra discuțiile cu un microfon care poate înregistra sunete în interiorul unui pătrat cu latura D, în centrul căruia se află chiar el. Acest pătrat nu este cuprins neapărat integral în matricea sălii (vedeți figura alăturată)!

Prin convenție, ID-urile VIP-urilor sunt numere prime distincte. În plus, și un ID al unui VIP poate fi copiat, crescând astfel numărul suspecților. Un VIP se caracterizează printr-un nivel de importanță: cu cât ID-ul este un număr mai mare, cu atât nivelul de importanță este mai mare (este „mai importantă”).

Persoanele suspecte au asociat un „grad de periculozitate”. Acesta este cu atât mai mare cu cât numărul de VIP-uri aflate în interiorul pătratului de latură D, în centrul căruia se află suspectul, este mai mare. Dacă există doi suspecți cu același grad de periculozitate, se consideră „mai periculoasă” persoana care are în pătratul său VIP-ul cu ID-ul cel mai mare. În caz de egalitate, se consideră „mai periculoasă” persoana care este așezată pe o linie cu un indice mai mic, iar la egalitate de indici de linii, pe o coloană cu indice mai mic. Există și persoane suspecte cu gradul de periculozitate 0, dacă în interiorul pătratului în centrul căruia se plasează nu există niciun număr prim.

Cerințe

1) Să se determine numărul persoanelor suspecte aflate în sala de așteptare.
2) Să se determine ID-ul și coordonatele persoanelor suspecte, (RSi -linia suspectului i, CSi -coloana suspectului i) în ordinea descrescătoare a „gradului de periculozitate”.

ONI 2016, clasa a X-a

#1687 Omogene

Se consideră o matrice cu L linii și C coloane care memorează doar valori din mulțimea {0,1,2}. O submatrice nevidă (formată din cel puțin o linie și cel puțin o coloană) a acestei matrice o numim omogenă dacă numărul valorilor de 0 este egal cu numărul de valori de 1 și egal cu numărul valorilor de 2.

Să se determine câte submatrice nevide omogene există.

ONI 2016, clasa a IX-a

#1686 Leduri

Am un cablu cu N leduri (numerotate de la 1 la N) aşezate echidistant. Inițial, unele leduri sunt aprinse, iar altele sunt stinse. Ledurile sunt legate între ele astfel încât atingerea fiecărui led produce modificarea atât a stării lui, cât şi a ledurilor vecine lui. Deci, dacă se atinge ledul i (2≤i≤N-1) atunci se modifică stările ledurilor i-1, i și i+1. Dacă se atinge ledul 1, atunci se modifică stările ledurilor 1 și 2, iar dacă se atinge ledul N, atunci se modifică stările ledurilor N-1 și N. Vreau să modific starea ledurilor astfel încât să semene cu cablul cu N leduri pe care îl are Ionuț, prietenul meu (două cabluri seamănă dacă pentru orice i=1..N stările ledurilor de pe poziția i sunt identice).

Cunoscând cum arată cablul lui Ionuț, ajutați-mă să determin numărul minim de atingeri ale unor leduri astfel încât cablul meu să arate ca și cablul lui Ionuț.

ONI 2016, clasa a IX-a

#1685 Dif2

Sandu a studiat la ora de informatică mai multe aplicații cu vectori de numere naturale, iar acum are de rezolvat o problemă interesantă. Se dă un șir X=(X[1],X[2],…,X[n]) de numere naturale nenule și două numere naturale p1 și p2, unde p1<p2. Sandu trebuie să construiască un nou șir Y=(Y[1],Y[2],…,Y[n*n]) cu n*n elemente obținute din toate produsele de câte două elemente din șirul X (fiecare element din șirul Y este de forma X[i]*X[j], 1<=i, j<=n). Sandu are de calculat două valori naturale d1 și d2 obținute din șirul Y. Valoarea d1 este egală cu diferența maximă posibilă dintre două valori ale șirului Y. Pentru a obține valoarea d2, Sandu trebuie să considere că șirul Y are elementele ordonate descrescător iar d2 va fi diferența dintre valorile aflate pe pozițiile p1 și p2 în șirul ordonat descrescător. Sandu a găsit rapid valorile d1 și d2 și, pentru a le verifica, vă roagă să le determinați și voi.

Dându-se șirul X cu n elemente și valorile p1 și p2, determinați valorile d1 și d2.

ONI 2016, clasa a IX-a

#1683 xor1

Se consideră o matrice cu un număr infinit de linii și coloane indexate începând cu 0.
Pe prima linie matricea conține șirul numerelor naturale (0, 1, 2, 3 …).
Pe fiecare linie începând cu linia a doua pe poziția j matricea conține suma xor a elementelor situate pe linia anterioara de la poziția 0 până la poziția j.

Se cere să se răspundă la q întrebări de forma “Pentru i și j date, să se determine numărul situat pe linia i coloana j a matricei”. Pentru a genera cele q întrebări vor fi cunoscute următoarele valori: \( i_1, j_1, a, b, m \).
\( i_1, j_1\) reprezintă valorile pentru prima întrebare. Următoarele întrebări \( i_k, j_k \) vor fi generate una din alta folosind următoarea regulă:

\( {i}_{k} = \left (a* {i}_{k-1} +b \right) \text{ mod } m \)
\( {j}_{k} = \left (a* {j}_{k-1} +b \right) \text{ mod } m \)

ONI 2016, clasele XI-XII

#1680 Sushi

După o zi productivă de făcut curățenie, Henry și Hetty au ieșit în oraș la un restaurant de sushi. În acest restaurant există N mese unite între ele prin N-1 benzi rulante cu dublu sens, astfel încât oricare două mese sunt conectate direct sau indirect prin benzi rulante. Pentru fiecare masă i, 1 ≤ i ≤ N, cunoaștem atât numărul K[i] de mese cu care este conectată direct, cât și lista ordonată de mese vecine acesteia: V[i,1], V[i,2]V[i,K[i]].

Benzile rulante au rolul de a transporta preparatele la clienți. Acestea urmează un traseu unic, definit după următoarea regulă: pentru orice masă i, un preparat aflat la masa i care tocmai a venit dinspre masa V[i,j], va pleca de la masa i spre masa:

  • V[i,j+1], dacă 1 ≤ j < K[i]
  • V[i,1], dacă j = K[i].

În plus, dacă un preparat nou este trimis de la masa 1 spre masa V[1,1], știm că acesta va ajunge la masa i pentru prima oară venind dinspre masa V[i,1], pentru orice i, 1 ≤ i ≤ N.

Henry și Hetty au intrat în restaurant la momentul de timp 0. Ei știu că pe parcursul vizitei lor pe benzile rulante vor fi așezate M preparate. Pentru fiecare din cele M preparate ei cunosc tripletul (x, y, t), semnificând faptul că la momentul de timp t preparatul va fi așezat pe bandă în dreptul mesei x pentru a pleca spre spre masa V[x,y]. Ei mai știu și că timpul necesar unui preparat de a parcurge distanța dintre două mese vecine este de o unitate. Cei doi se vor așeza la o masă și vor lua de pe bandă toate preparatele care trec prin dreptul mesei respective. Henry și Hetty se întreabă: pentru fiecare masă i, care este timpul minim după care culeg toate cele M preparate ce vor fi puse pe bandă?

ONI 2016, clasele XI-XII

#1679 Euro

După calificarea la campionatul european de fotbal din Franța, având în vizor N jucători din care trebuie să convoace câțiva în echipa națională, selecționerul României a apelat la niște metode mai puțin ortodoxe. Acesta a mers la vrăjitoarele renumite din Craiova pentru a-l ajuta să găsească formula câștigătoare pentru meciul de deschidere cu Franța. Vrăjitoarele, după descântece îndelungate, au ajuns la concluzia că lotul de jucători trebuie sa aibă valoarea exact X și coeficientul de aroganță cât mai mic. Valoarea unui lot de jucători e definită ca suma valorilor jucătorilor ce intră în componența lotului. Coeficientul de aroganță al unui lot de jucători e definit ca diferența dintre valoarea maximă a unui jucător din lot și valoarea minimă a unui jucător din lot. Se mai știe că valoarea lotului nu poate depăși o valoare cunoscută Vmax. Un lot de jucători e definit ca o submulțime nevidă de jucători aleși dintre cei N. Atenție, un lot poate fi format și dintr-un singur jucător.

Se dă numărul N de jucători, numărul Vmax definit mai sus și valoarea fiecărui jucător. Selecționerul României a găsit formula câștigătoare și e curios dacă puteți și voi. Fiindcă nu are încredere totală în vrăjitoare, acesta vă cere să aflați pentru fiecare valoare X din intervalul [1,Vmax] coeficientul de aroganță minim posibil pentru care există cel puțin un lot dintre cei N jucători cu valoare exact X. Dacă nu se poate obține nici un lot de valoare exact X, se consideră ca răspuns -1.

ONI 2016, clasele XI-XII

#1677 Tort

Pentru că s-a calificat la Olimpiada Națională de Informatică de la Craiova, NN îi pregătește lui XORin un tort. Tortul este dreptunghiular, format din linii și coloane numerotate de la 1 la N pentru linii și de la 1 la M pentru coloane. Tortul este format din bucăți de dimensiune 1x1, fiecare fiind acoperită cu un alt tip de glazură. În fiecare zi NN îi taie lui XORin câte o felie, alegând cel mai mare pătrat care conține bucăți acoperite cu același tip de glazură. În cazul în care există mai multe astfel de felii, NN o alege pe cea care are colțul din dreapta jos situat pe linia cu indicele cel mai mic. Dacă și în acest caz există mai multe posibilități, el o va alege pe cea cu colțul din dreapta jos situat în coloana cu indicele cel mai mic.

Precizați latura și coordonatele colțului din dreapta jos pentru fiecare felie de tort primită, în ordinea specificată mai sus.

ONI 2016, clasa a X-a

#1676 Elmer

În antrenamentul său intens pentru prinderea lui Daffy Duck, celebrul vânător Elmer Fudd a început să vâneze rațe în orașul său preferat, Craiova. Se știe că există N rațe reprezentate prin puncte în planul de coordonate xOy, având coordonatele (x,y) și M ziduri sub forma unor segmente verticale având un capăt pe axa Ox și o anumită înălţime fiecare.

Vânătorul Elmer dorește să împuște cât mai multe rațe. El poate fi poziționat în orice punct de abscisă număr natural nenul, pe axa Ox. O rață poate fi ochită de vânător dacă zidul nu blochează glonțul vânătorului, adică segmentul imaginar delimitat de rață și de vânător nu se intersectează cu nici un zid.

Să se afle numărul maxim de rațe care pot fi ochite de vânătorul Elmer.

ONI 2016, clasa a X-a

#1675 Calc

La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu aceeași configurație a rețelei.

Exemplu: pentru N=3, cei 6 elevi au fost împărțiți în 3 echipe, iar aranjarea rețelei în cele 3 zile de concurs este cea din figura de mai jos.

Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configurațiile folosite în zilele de concurs. Cablul orizontal se notează prin 0, iar cel vertical prin 1. Lucrând ordonat și eficient, pentru cele trei zile el își va nota valorile: 001, 100, respectiv 111. Se observă că o reprezentare de genul 000, 010, 011, 101 nu poate fi realizată.

Cunoscând N, să se determine:

  1. Numărul de zile modulo 1000000007 în care se desfășoară concursul.
  2. Configurațiile laboratorului în ziua X-1 și ziua X+1, cunoscând configurația zilei X.

ONI 2016, clasa a X-a

#1674 Livada1

Fermierul Quinto are o livadă plină cu pomi fructiferi. Livada are N rânduri, numerotate de la 1 la N, pe fiecare rând aflându-se câte M pomi fructiferi, numerotaţi de la 1 la M. Livada lui Quinto este una specială, aşa că pentru unii pomi se cunoaşte cantitatea de fructe (exprimată în kg) care poate fi culeasă, iar pentru alţii aceasta poate fi determinată pe baza unei formule. Quinto şi-a propus să recolteze C kg de fructe din pomii aflaţi în livada lui. Acesta foloseşte un utilaj modern pentru culesul fructelor. Utilajul poate fi folosit pe oricare din rândurile livezii, dar poate aduna doar fructele dintr-un şir consecutiv de pomi, începând cu primul pom de pe rândul respectiv, neavând posibilitatea de a culege parţial fructele dintr-un pom. Preocupat de frumuseţea livezii sale, Quinto s-a gândit la restricţii suplimentare pentru recoltarea cantităţii C de fructe. Astfel, el doreşte să adune fructele din pomi de pe maximum R rânduri diferite, pentru ca N-R rânduri să rămână complete. De asemenea, el doreşte să culeagă cu prioritate pomii care au o cantitate cât mai mică de fructe, pentru ca în livadă să rămână cei mai roditori pomi. Quinto şi-a dat seama că este dificil să culeagă fix C kg de fructe, prin urmare este mulţumit şi cu o cantitate mai mare, care respectă celelalte condiţii impuse de el.

Determinaţi cea mai mică valoare X posibilă astfel încât să se poată culege, în condițiile de mai sus, o cantitate de cel puțin C kg de fructe și orice pom din care se culeg fructe să conțină cel mult X kg de fructe.

ONI 2016, clasa a IX-a

#1673 Cmmdc1

Fie un șir de numere naturale nenule a[1], a[2], …, a[n] și un număr natural k. Să se determine un grup de k numere din șir care au proprietatea că cel mai mare divizor comun al lor este maxim. Dacă există mai multe astfel de grupuri, se cere acel grup pentru care suma elementelor este maximă.

ONI 2016, clasa a IX-a

În vremuri străvechi Pământul era locuit de către o civilizaţie neobişnuită condusă după reguli matematice foarte riguroase. Această civilizaţie era formată din mai multe oraşe-stat asemeni oraşelor antice. Fiecare oraş s-a dezvoltat treptat pornind de la un singur cartier de formă pătrată cu suprafaţa de un hectar, în jurul căruia se adăugau în fiecare an cartiere de câte un hectar fiecare în felul următor: în primul an s-a format cartierul iniţial, în al doilea an oraşul s-a extins formând patru noi cartiere în toate cele patru puncte cardinale, în anul următor oraşul s-a extins cu 8 noi cartiere dispuse în jurul cartierelor deja formate, şi aşa mai departe, în fiecare an oraşul extinzându-se cu încă un rând de cartiere.

Primul an Al doilea an Al treilea an Al patrulea an Al cincilea an

Extinderea unui oraş se opreşte când întâlnește un alt oraş sau dacă, deşi nu a întâlnit încă un alt oraş, ajunge la marginea hărţii pe oricare dintre cele patru puncte cardinale. Două oraşe se întâlnesc când suprafeţele ocupate de ele ajung să se atingă sau între cartierele marginale ale celor două orașe se mai află doar un hectar.

Situaţii în care suprafeţele orașelor se ating Situaţii în care între suprafeţele orașelor există un spaţiu de un hectar

Cerințe:

  1. Dimensiunea suprafeţei (în hectare) pe care ar ocupa-o după t ani, dacă nu ar întâlni nici un alt oraş şi nici nu ar ajunge la marginea hărţii.
  2. Timpul scurs până când toate cele N oraşe şi-au încetat extinderea, începută din cartierele iniţiale ale căror coordonate se citesc din fişier, şi aria suprafeţei din hartă rămasă neocupată, exprimată în hectare.

ONI 2016, clasa a IX-a

Un showroom din Strasbourg comercializează o gamă foarte mare de modele de autoturisme, aşezate pe n linii. Pe câte o linie se găsesc numai modele de autoturisme comercializate de acelaşi dealer. Un dealer poate avea modele pe mai multe linii. Parlamentul European doreşte să-şi înoiască parcul auto şi trimite responsabilul cu activitatea de transport la showroom pentru a se informa cu privire la variantele pe care le are pentru rezolvarea acestei probleme de achiziţie. Responsabilul trebuie să aleagă de la primul dealer \(f_1\) modele, de la al doilea dealer \(f_2\) modele, etc. Şirul de numere \(f_1, f_2, f_3, …\) reprezintă termenii modulo k ai unei progresii aritmetice cu primul termen a şi raţia r. Să se scrie un program care determină: a) Numărul de dealeri prezenţi în showroom; b) Numărul de modalităţi de achiziţie al modelelor de către Parlamentul European, modulo 9001.

ONI 2013, Clasa a X-a

Considerăm şirul de numere naturale nenule distincte \(a_1,a_2, …,a_N\). Notăm cu \(L_i\) lungimea maximă a unei secvențe de elemente cu valori consecutive care se poate obţine prin ordonarea crescătoare a primelor i elemente din şirul dat. Să se determine \(L_1,L_2, …,L_N\).

ONI 2013, Clasa a IX-a

#1637 Split

Fie un șir de numere naturale. Se împarte şirul în patru secvenţe astfel încât orice element din şir să aparţină unei singure secvenţe şi fiecare secvenţă să conţină cel puţin două elemente. Pentru fiecare secvenţă se determină costul ei ca fiind diferenţa dintre valoarea maximă şi cea minimă din acea secvenţă.

ONI 2013, Clasa a IX-a

Un număr natural nenul n se numește cumpănit dacă în descompunerea sa în factori primi suma bazelor este egală cu suma exponenților. Să se scrie un program care citește două numere naturale nenule a și b și determină toate numerele cumpănite din intervalul închis [a, b].

ONI 2013, Clasa a X-a

#1648 Diez

Negrimon a găsit într-o culegere această problemă #legendară: peste un şir de caractere de lungime N, alcătuit din litere mici ale alfabetului englez, se efectuează M operaţii de următoarele tipuri:

  1. Se inserează în şir caracterul x, pe poziţia p, după deplasarea cu o poziţie la dreapta a caracterelor situate pe poziţiile mai mari sau egale cu p. Dacă valoarea p este egală cu lungimea şirului, x este alipit la finalul şirului.
  2. Se răspunde cu 1 dacă secvenţa de litere care începe la poziţia q1 şi are lungimea lg coincide literă cu literă, cu secvenţa care începe la poziţia q2 şi are aceeaşi lungime lg şi se răspunde cu 0 în caz contrar. Este posibil ca cele două secvenţe să se suprapună complet sau parţial în şirul din care ele fac parte.

Fiind dat un şir de N litere mici şi o listă de M operaţii, să se afişeze răspunsurile la operaţiile de tip 2, respectând ordinea din succesiunea de operaţii date.

Urmasii lui Moisil, 2016

Aurel a învăţat la matematică despre şiruri de numere. Fiind curios din fire, el ar vrea acum să ştie câte şiruri crescătoare de numere naturale nenule cu suma elementelor mai mică sau egală cu S există.

Ajutaţi-l pe Aurel să afle câte astfel de şiruri există.

Urmasii lui Moisil, 2016

#1645 Fibocel

Toată lumea ştie că Fibocel este pasionat de numere şi că vrea să iasă în evidenţă cu orice preţ. Într-o zi, el s-a decis să numească un număr fibocel (după numele lui) dacă numărul de biţi egali cu 1 din reprezentarea binară a numărului este un număr Fibonacci.

Cum asta nu e de ajuns pentru el, Fibocel s-a decis să propună şi o problemă la concursul lui preferat de la Iaşi.

Să se raspundă la Q întrebări de forma: Câte numere fibocel există în intervalul închis [A, B]?

Urmasii lui Moisil, 2016

#1644 Bilute1

X şi Y se joacă cu N biluţe, fiecare biluţă având scrisă pe ea o cifră nenulă. Inventivi din fire, aceştia au împărţit cele N biluţe în două grămezi, astfel încât valoarea medie a grămezii lui X să fie egală cu valoarea medie a grămezii lui Y. Valoarea medie a unei grămezi este egală cu suma tuturor numerelor din grămadă împărţită la numărul de elemente ale acesteia.

Dându-se cele N valori scrise pe biluţe, aflaţi în câte moduri pot fi împărţite biluţele în două grămezi ale căror valori medii să fie egale. Cum acest număr poate fi prea mare, afişaţi doar restul împărţirii acestui număr la 666013.

Urmasii lui Moisil, 2016

#1643 Tromino

Bulbuka a primit de curând cadou un infinit de tromino-uri în formă de L. După ce s-a jucat un timp cu ele, a ajuns la următoarea concluzie: poate să acopere cu tromino-uri o tablă de dimensiuni 2Kx2K aproape complet (mai puţin un pătrăţel de dimensiune 1x1). Deşteapta de Bulbuka are un algoritm pentru asta: porneşte de la o configuraţie 2K-1x2K-1, o copiază de încă 3 ori, apoi roteşte 2 dintre copii şi la sfârşit, adaugă un tromino la mijloc (v-a făcut un desen mai jos, ca să înţelegeţi mai bine, pentru K = 1, 2 şi 3). Pornind de la o configuraţie de acest tip, ea a observat că poate roti la 90o câte un tromino, în sensul acelor de ceasornic sau invers, doar dacă după rotire încape înapoi pe tablă. Folosind astfel de rotaţii, pătrăţelul lipsă poate ajunge pe orice poziţie de pe tablă.

Bulbuka vă pune acum Q întrebări de tipul: care este numărul minim de rotaţii necesare pentru ca pătrăţelul lipsă să ajungă de la coordonatele (SR,SC) la coordonatele (FR,FC)?

Urmasii lui Moisil, 2016

Urmasii lui Moisil, 2016

Arhipelagul Zopopan este format din n insule de formă triunghiulară numerotate de la 1 la n. Fiecare insulă este localizată prin coordonatele carteziene ale vârfurilor.

Administrația dorește să cumpere elicoptere pentru a realiza transportul între insule. Un elicopter va putea să asigure o rută între două insule pe distanța minimă obținută pe orizontală sau verticală (paralel cu axele de coordonate). În plus, datorită capacității rezervorului o astfel de rută nu poate să depășească o valoare k – număr natural. Elicopterele parcurg rutele în ambele sensuri.
Investiția trebuie să îndeplinească următoarele condiții:

  1. Numărul de elicoptere cumpărate să fie minim.
  2. Numărul de perechi de insule între care se poate realiza transportul, folosind unul sau mai multe elicoptere să fie maxim.
  3. Suma lungimii tuturor rutelor să fie minimă.

Să se scrie un program care pentru n, k şi coordonatele vârfurilor insulelor cunoscute, determină:

  1. numărul minim de elicoptere ce vor fi cumpărate de administraţie;
  2. numărul perechilor neordonate de insule între care se poate realiza transportul prin elicoptere direct sau indirect;
  3. suma distantelor parcurse de toate elicopterele cumpărate (distanța parcursă de un elicopter se consideră distanța dintre insulele între care acesta asigură transportul).

OJI 2016, Clasele XI-XII

#1621 Miting

În Orașul Liniștit un număr de k tineri prieteni doresc să participe la un miting de protest. Deoarece cartierul în care locuiesc aceștia este mare, ei se vor deplasa spre punctul de întâlnire cu mașinile personale. Fiecare tânăr va aduce cu el o pancartă, pe care a desenat o singură literă din mulțimea A ... Z. Nu există două pancarte cu litere identice. Cele k litere formează un cuvânt, să-l notăm cuv, cunoscut.

Cartierul în care locuiesc tinerii poate fi codificat printr-o matrice cu n*m zone pătratice, dintre care unele sunt interzise. Se știe că o mașină consumă o unitate de combustibil la trecerea dintr-o zonă în zona vecină și nu consumă combustibil dacă staționează. Două zone sunt vecine dacă au în comun o latură. Pentru a face economie de combustibil, tinerii decid că dacă două mașini se întâlnesc într-o zonă și toate literele aflate în cele două mașini reprezintă o secvență din cuvântul cuv, atunci ei vor continua drumul cu o singură mașină, luând desigur toate pancartele cu ei. În caz contrar, mașinile își continuă drumul separat.

De exemplu, dacă cuvântul cuv este JOS, atunci mașina care transportă litera J poate prelua tânărul care aduce pancarta cu litera O, sau invers: mașina având litera O poate prelua tânărul care aduce litera J. Apoi se poate continua drumul spre mașina care transportă litera S. În altă variantă se pot reuni mai întâi literele S și O într-o singură mașină, dacă mașinile care le transportau se întâlnesc în aceeași zonă. Totuși, între mașina care transportă doar litera J și cea care transportă doar litera S nu se poate realiza un transfer, adică o reunire a literelor.

Cunoscând dimensiunile cartierului n și m, cuvântul cuv, configurația cartierului și pozițiile inițiale ale tinerilor, se cere:

  1. Aria minimă a unei submatrice a matricei care codifică cartierul, în care se situează toate pozițiile inițiale ale tinerilor.
  2. Numărul minim de unități de combustibil consumați de către toate mașinile, știind că în final toți tinerii se vor reuni într-o singură mașină.

OJI 2016, Clasa a X-a

Se consideră o mulțime S care conține N șiruri de caractere formate din litere mici ale alfabetului englezesc.

Un șir de caractere se numește interesant în raport cu celelalte șiruri ale mulțimii, dacă nu există un alt șir în mulțime care să-l conțină ca subșir. De exemplu, dacă mulțimea S conține șirurile abc, bde și abcdef, atunci singurul șir interesant este abcdef deoarece abc și bde nu îl conțin ca subșir. Mai mult, abc și bde sunt subșiruri în abcdef, deci nu sunt interesante.

Fiind dată o mulțime S formată din N șiruri de caractere se cere:

  1. Să se determine cel mai lung șir. Dacă sunt mai multe șiruri având aceeași lungime maximă, se cere cel mai mic din punct de vedere lexicografic.
  2. Să se determine toate șirurile interesante din mulțimea S.

OJI 2016, Clasa a X-a

#1619 Pic

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 de mai jos. Nivelurile din stivă sunt de asemenea 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ă.

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?

OJI 2016, Clasa a IX-a

#1618 Cifre12

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 de mai jos.

Afişarea unei cifre se face prin aprinderea unei combinații de segmente conform tabelului:

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

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 niciun segment dintre cele deja aprinse.

OJI 2016, Clasa a IX-a

#1617 ks

Ana şi Bogdan au inventat din nou un joc, pe care l-au denumit ks. Pe tabla de joc sunt plasate pe poziţii consecutive n jetoane, pe fiecare jeton fiind scris un număr natural nenul.

Ana este prima la mutare şi are voie să extragă de pe tablă exact k jetoane situate pe poziţii consecutive.

Bogdan mută al doilea şi are şi el voie să extragă exact k jetoane, dintre cele rămase pe tablă, situate de asemenea pe poziţii consecutive.

Punctajul asociat unei mutări este egal cu suma numerelor scrise pe jetoanele extrase la mutarea respectivă.

Scopul Anei este să efectueze mutarea sa astfel încât punctajul obţinut de Bogdan să fie cât mai mic. Considerăm că atât Ana, cât şi Bogdan joacă optim.

Cunoscând numărul de jetoane de pe tabla de joc, valorile înscrise pe acestea, precum şi valoarea k, scrieţi un program care să determine care este cel mai bun punctaj pe care Bogdan îl poate obţine, ştiind că ambii jucători joacă optim.

OJI 2016, Clasa a VIII-a

#1616 Galerie

La întâlnirea anuală a cârtițelor, la concursul pentru selecția noilor membri ai consiliului director, a fost propusă următoarea problemă:

De jur-împrejurul unui teren dreptunghiular împărțit în n*m celule de formă pătrată, cu aceeași arie, cârtițele au săpat galerii exterioare. Celulele aflate pe marginea terenului sunt numerotate consecutiv, de la 1 la 2*(n+m), începând din colțul din stânga-sus, ca în imaginea alăturată. În galeriile exterioare, pe marginea terenului, se află t cârtițe care sunt pregătite să sape galerii interioare. Cârtițele aflate pe latura de Nord a terenului se vor deplasa către Sud, cele care se află pe latura de la Est se vor deplasa către Vest, cele care se află pe latura de la Sud se vor deplasa către Nord, iar cele care se află pe latura de la Vest se vor deplasa către Est.

Cârtițele încep să sape în același timp. În fiecare oră, o cârtiță sapă într-o singură celulă a terenului.

O cârtiță se oprește dacă:

  • ajunge într-o altă galerie interioară; ea nu sapă în aceasta, iar galeria ei se unește cu cea în care ajunge;
  • în celula în care sapă, mai sapă și alte cârtițe, în aceeași oră; galeriile lor se unesc într-o singură galerie și toate aceste cârtițe se opresc;
  • ajunge pe marginea terenului, în partea opusă celei din care a plecat, galeria săpată de ea până în acest moment comunicând acum cu galeria exterioară, în care ea nu sapă.

De exemplu, dacă pe marginea unui teren format din 7x5 celule, se află 5 cârtițe, în celulele 3, 8, 10, 19 și 23, atunci, după o oră, terenul are configurația din fig.1, după două ore, configurația din fig.2, după trei ore, configurația din fig.3 (ultima cârtiță ajunge în galeria primei cârtițe și primele două cârtițe sapă în aceeași celulă și apoi se opresc), după 4 ore, configurația din fig.4, după 5 ore, configurația din fig.5, când cele două cârtițe rămase sapă pe marginea terenului și apoi se opresc pentru că au ajuns în galeria exterioară (fig.6). Galeriile acestora nu se unesc pentru că niciuna dintre ele nu a intrat în galeria celeilalte și nici nu s-au întâlnit într-o celulă.

Cunoscându-se numerele n, m, t și cele t celule exterioare în care se află cârtițele, să se determine:

1. numărul maxim de celule în care sapă o cârtiță până la oprirea tuturor cârtițelor;
2. numărul maxim de celule din care este formată o galerie interioară.

OJI 2016, Clasa a VII-a

#1615 AXYZ

Se consideră numerele naturale A (format din două sau trei cifre, toate distincte și nenule) și X (format din N cifre, toate nenule).

Din numărul X, folosind toate cele N cifre ale sale, se poate construi un cel mai mare număr natural Y strict mai mic decât X. De exemplu, pentru X=121621 se construiește Y=121612.

Tot din numărul X, se poate obține numărul A prin ștergerea unor cifre din scrierea lui X și alipirea celor rămase, fără a le schimba ordinea. De exemplu, dacă X=121621 și A=12, există Z=3 posibilități distincte prin care să obținem numărul A din X și anume: 1) 121621; 2) 121621; 3) 121621.

Cunoscându-se numerele A, N și cele N cifre ale lui X, să se determine:

1. cel mai mare număr natural Y, strict mai mic decât X, care se poate obține rearanjând cifrele lui X;
2. numărul maxim Z de posibilități distincte prin care se poate obține numărul A din numărul X prin ștergerea unor cifre și alipirea celor rămase, fără a le schimba ordinea.

OJI 2016, Clasa a VII-a

#1614 Litere1

Un copil dorește să găsească un mod original de a-și codifica numele și folosește în acest scop o figură formată doar din triunghiuri, desenată pe o foaie de hârtie. El plasează fiecare literă din numele său, în câte un triunghi. Dacă numele lui este DARIUS, atunci foaia de hârtie va arăta ca în figura 1. Pe primul rând așează prima literă, pe al doilea rând următoarele trei litere, pe al treilea rând următoarele cinci litere, și așa mai departe până când așează toate literele din nume. Dacă numele nu are suficiente litere, copilul folosește caracterul * pentru a completa ultimul rând pe care pe care a așezat litere. Nemulțumit că numele poate fi citit relativ ușor, răstoarnă figura, rotind foaia de hârtie, în sensul acelor de ceasornic, obținând astfel figura 2.

Cunoscând literele numelui, scrieți un program care determină și afișează în fișierul de ieșire:

1. Numărul de caractere * pe care trebuie să le utilizeze pentru a completa ultimul rând;
2. Prima literă de pe fiecare rând din figura inițială;
3. Șirul literelor de pe fiecare rând, după rotirea foii de hârtie.

OJI 2016, Clasa a VI-a

#1612 Cifre10

Elevii clasei pregătitoare se joacă la matematică cu numere. Învățătoarea are un săculeț plin cu jetoane, pe fiecare dintre ele fiind scrisă câte o cifră. Fiecare elev și-a ales din săculeț mai multe jetoane, cu care și-a format un număr. Pentru ca totul să fie mai interesant, elevii s-au grupat în perechi. Doamna învățătoare a oferit fiecărei perechi de elevi câte o cutiuță pentru ca cei doi să își pună împreună jetoanele. De exemplu, dacă unul din elevii unei echipe și-a ales jetoane cu care a format numărul 5137131 iar celălalt elev și-a ales jetoane cu care a format numărul 6551813, atunci cutiuța echipei va conţine 5 jetoane cu cifra 1, câte 3 jetoane cu cifra 3 şi 5 şi câte un jeton cu cifrele 6, 7 şi 8.

Doar Andrei stătea supărat pentru că numărul de elevi al clasei era impar iar el nu avea partener, motiv pentru care nu și-a mai ales jetoane. Din această cauză, doamna învățătoare i-a spus:

“- Alege o echipă din a cărei cutiuță poţi lua o parte din jetoane, dar ai grijă ca fiecare dintre cei doi elevi să-și mai poată forma numărul lui din jetoanele rămase, iar tu să poți forma un număr nenul cu jetoanele extrase!“.

Dar cum Andrei nu se mulţumea cu puţin, a vrut să aleagă acea echipă din a cărei cutiuță îşi poată forma un număr de valoare maximă folosind jetoanele extrase.

Scrieţi un program care să citească numărul N de cutiuțe și numerele formate de elevii fiecărei perechi și care să determine:

1) Numărul de cutiuțe din care Andrei poate lua jetoane respectând condiția pusă de doamna învățătoare;
2) Care este cel mai mare număr nenul pe care îl poate forma Andrei respectând aceeași condiție.

OJI 2016, Clasa a VI-a

Un număr se numește palindrom dacă prima lui cifră este egală cu ultima, a doua cu penultima și așa mai departe. De exemplu numerele 1221, 505 și 7 sunt palindromuri, în vreme ce 500, 1410 și 2424 nu sunt palindromuri.

Similar, un număr se numește aproape palindrom dacă are aceleași perechi de cifre identice ca un palindrom, mai puțin o pereche în care cifrele diferă. De exemplu numerele 500, 1411, 2444, 1220, 53625, 14 și 4014 sunt numere aproape palindromuri, în vreme ce 1221, 1410, 6, 505, 22 și 512125 nu sunt numere aproape palindromuri deoarece fie sunt palindromuri, fie au prea multe perechi de cifre diferite.

Mai definim palindromul asociat al unui număr x ca fiind cel mai mic număr palindrom p strict mai mare decât x (p>x). De exemplu palindromul asociat al lui 5442 este 5445, palindromul asociat al lui 2445 este 2552, al lui 545 este 555, al lui 39995 este 40004, al lui 500 este 505, iar al lui 512125 este 512215.

Scrieţi un program care citind un număr natural nenul n și apoi un șir de n numere naturale determină:

1. câte dintre cele n numere sunt palindrom
2. câte dintre cele n numere sunt aproape palindrom
3. palindromurile asociate pentru cele n numere citite.

OJI 2016, Clasa a V-a

#1610 Colier

Maria are în camera sa N mărgele așezate una lângă alta. Pe fiecare dintre ele este scris un număr natural format din cifre nenule distincte. Pentru fiecare mărgea, Maria șterge numărul și în locul său scrie altul, având doar două cifre, respectiv cifra minimă și cifra maximă din numărul scris inițial, în ordinea în care aceste cifre apăreau înainte de ștergere. Acum Maria consideră că mărgelele sunt de două tipuri, în funcție de numărul de două cifre scris pe ele: tipul 1 (cele care au cifra zecilor mai mică decât cifra unităților) și tipul 2 (celelalte). Folosind mărgelele, fetița dorește ca prin eliminarea unora dintre ele (dar fără să le schimbe ordinea celorlalte) să obțină un colier circular cât mai lung care să respecte proprietatea că oricare două mărgele vecine ale sale sunt de tipuri diferite. În colierul format cu mărgelele rămase după eliminare se consideră că prima mărgea este vecină cu ultima.

1) determinați numărul de mărgele de tipul 1;
2) determinați numărul maxim de mărgele pe care le poate avea colierul;

OJI 2016, Clasa a V-a

#1590 Arma1

În anul 2214 a izbucnit primul război interstelar. Pământul a fost atacat de către n civilizaţii extraterestre, pe care le vom numerota pentru simplicitate de la 1 la n.

Pentru a se apăra, pământenii au inventat o armă specială ce poate fi încărcată cu proiectile de diferite greutăţi, fabricate dintr-un material special denumit narun. Dacă arma este programată la nivelul p, atunci un proiectil de greutate k va ajunge exact la distanţa kp km (k la puterea p) faţă de Pământ şi dacă în acel punct se află cartierul general al unui atacator, acesta va fi distrus. De exemplu, dacă arma este programată la nivelul 2, un proiectil de greutate 10 va distruge cartierul general al extratereştrilor situat la distanţa 102 = 100 km de Pământ.

Arma poate fi încărcată cu proiectile de diferite greutăţi, dar cum narunul este un material foarte rar şi foarte scump, pământenii vor să folosească proiectile cât mai uşoare pentru a distruge cartierele generale inamice.

Cunoscându-se n, numărul atacatorilor, precum şi cele n distanţe până la cartierele generale ale acestora, să se scrie un program care determină:

  • cantitatea minimă de narun necesară pentru a distruge toate cartierele generale inamice;
  • nivelurile la care trebuie programată arma, pentru a distruge fiecare cartier general inamic cu o cantitate minimă de narun.

OJI 2016, Clasa a VIII-a

#1548 Minioni

Kevin și-a deschis un nou complex hotelier în Dubai și acesta se compune din M clădiri etichetate de la 1 la M. La inaugurare s-a hotărât să îi invite pe toți prietenii lui, cei N minioni.

Inițial complexul este gol, iar primii invitați vor fi Bob, apoi Stuart. Kevin s-a gândit să invite exact un prieten în fiecare zi pentru a putea organiza o petrecere la fiecare sosire a unui minion în complexul său. Zgomotul petrecerii este egal cu numărul de minioni situați în interiorul clădirii.

În calitate de manager, Kevin nu este deosebit de încântat de reclamațiile cauzate de zgomotul petrecerilor, astfel încât el va goli ocazional o anumită clădire pentru a păstra petrecerile la un nivel de zgomot rezonabil. Când este nevoit să facă această golire, clădirea rămâne goală, toți minionii fiind mutați într-un complex diferit. Conducerea poate decide să facă acest lucru la sfârșitul oricărei zile, dar pentru a limita costurile și-a dat seama că nu poate realiza această schimbare de un număr mai mare de K ori.

Ajutați-l pe Kevin, știind care sunt clădirile unde se vor caza prietenii lui, să determine nivelul minim total de zgomot posibil (suma tuturor nivelurilor de zgomot a celor N petreceri), care poate fi realizat prin golirea unor clădiri de un număr maxim de K ori.

Olimpiada de informatică, etapa locală, Suceava, 2016

#1185 Cub2

ONI 2015, Clasa a IX-a

Se presupune că unele dintre primele instrumente de calcul au fost beţişoarele de socotit. În problema noastră vom considera un număr ca fiind o succesiune de unul sau mai multe beţişoare, un beţişor fiind reprezentat de litera I. Într-o expresie, între oricare două numere există semnul + sau semnul *.

Exemple de numere

I
III
IIIIIIIIIII

Exemple de expresii

III
II*III
I+I*III+IIIIIII

Scrieţi un program care evaluează astfel de expresii.

ONI GIM 2014, Clasa a VI-a

#1127 Praslea

A fost odată ca niciodată un împărat puternic care avea o grădină minunată, situată pe un teren de formă dreptunghiulară din jurul palatului. În grădină creştea un măr cu mere de aur, dar împăratul nu a putut să se bucure vreodată de merele din pom deoarece grădina a fost mereu atacată de tâlhari şi merele au fost furate. Cu toate că aceasta a fost păzită zi şi noapte de cei mai viteji ostaşi din împărăţie, ei nu au putut face faţă tâlhăriilor. Deznădăjduit, împăratul şi-a pus în gând să taie pomul cu mere de aur, dar fiul său cel mic, Prâslea, l-a rugat să-l lase şi pe el să-şi încerce norocul. Prâslea a cugetat foarte bine la cele întâmplate şi a procedat astfel:

  • a delimitat în grădină, de-a lungul acesteia, N parcele alăturate, numerotate de la stânga la dreapta cu valori în ordine, de la 1 la N. Dintre acestea, a dat spre pază fraţilor şi verişorilor săi M parcele, iar restul de N-M parcele oştenilor din împărăţie. Cele N-M parcele date oştenilor sunt identice şi au fiecare lăţimea L.
  • a măsurat distanţa D la care se află pomul cu merele de aur faţă de marginea din stânga a grădinii, pentru a întări chiar el paza parcelei în care e situat acesta.

Cerinţă

a) Cunoscând lăţimea fiecărei parcele, determinaţi cel mai mare număr de parcele alăturate, de lăţime L fiecare, date spre pază oştenilor ;
b) Determinaţi numărul de ordine al parcelei în care se află pomul cu merele de aur.

ONI GIM 2014, Clasa a VI-a

#1129 Tinta

Alex are o pasiune pentru trasul la țintă. Jucându-se cu numere, visează la o nouă tablă pentru pasiunea sa. Tabla visată este de formă pătrată cu n linii și n coloane, iar numerele, de la 1 la n * n, le poziționează în țintă, ca în imaginea alăturată.

Alex, fiind un foarte bun țintaș, nu nimerește niciodată pe pătrățelele de pe contur. Când țintește o pătrățică din interior, el obține drept punctaj suma valorilor din cele opt pătrățele vecine.

Cunoscând n numărul de linii și de coloane ale țintei:

a. Ajutați-l pe Alex să construiască ținta visată.
b. Câte punctaje distincte poate să obțină Alex dacă are o singură săgeată?
c. Afișați punctajele distincte găsite.

ONI GIM 2014, Clasa a VI-a

#1130 Codat

Se consideră un șir de N numere naturale, notate x 1, x 2, x 3,…, x N. Definim pentru orice pereche de indici i, j, 1 ≤ i ≤ j ≤ N, distanța între elementele x i și x j ca fiind egală cu j – i.

Acest șir va fi codificat după următoarele reguli:

  • fiecare element din șir este înlocuit cu indicele celui mai apropiat element din șir (cel față de care distanța este minimă) strict mai mare decât el;
  • dacă pentru un element din șir există două elemente care respectă regula de mai sus, atunci el va fi înlocuit cu indicele mai mare, adică al elementului strict mai mare decât el, aflat în dreapta lui;
  • elementele de valoare maximă din șir vor fi înlocuite cu -1.

Scrieți un program care codifică un șir de N valori, după regulile descrise.

ONI GIM 2014, Clasa a VII-a

#1131 Arc

Irinuca a descoperit un nou joc pe calculator. Pe ecran sunt plasate pe o linie n bile colorate. Culorile bilelor sunt codificate cu numere naturale. Un subșir de bile alăturate având toate aceeași culoare se numește secvență. O secvență va conține numărul maxim de bile alăturate având aceeași culoare. Lungimea unei secvențe este egală cu numărul de bile din care este compusă.

Irinuca are la dispoziție un arc special. Trăgând cu arcul asupra unei bile, dacă aceasta face parte dintr-o secvență de lungime cel puțin egală cu 3, întreaga secvență va fi eliminată, iar bilele din dreapta secvenței se vor deplasa spre stânga pentru a umple “golul” lăsat de bilele eliminate. Dacă imediat în stânga și în dreapta secvenței eliminate se găseau două secvențe având aceeași culoare și dacă secvența obținută din unirea acestora după eliminare are o lungime cel puțin egală cu 3, atunci va fi și ea eliminată la rândul ei. Procesul continuă până când secvențele din stânga și dreapta unei secvențe tocmai eliminate au culori diferite sau până când lungimea secvenței obținute prin alăturare este mai mică decât 3 sau până când în stânga ori în dreapta unei secvențe eliminate nu se mai găsesc bile sau până sunt eliminate toate bilele de pe ecran.

Scopul jocului este de a elimina cât mai multe bile de pe ecran. Cum Irinuca încă nu se pricepe prea bine la acest joc și-a stabilit o strategie. Va trage cu arcul întotdeauna asupra unei bile ce face parte din secvența de lungime maximă de pe ecran. Dacă sunt mai multe astfel de secvențe, ea va alege cea mai din stânga secvență de lungime maximă. Dacă toate secvențele de pe ecran au lungimi mai mici decât 3, Irinuca nu va mai putea elimina nici una din ele și jocul se încheie.

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.

Cunoscând numărul de bile și culorile fiecărei bile de pe ecran se cere să se determine:

1. numărul de secvențe de bile care se aflau inițial pe ecran;
2. numărul de bile care rămân neeliminate de pe ecran și culorile bilelor rămase în ordine pe ecran la finalul jocului.

OJI 2015, Clasa a IX-a

#1132 Defrag

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

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.

OJI 2015, Clasa a IX-a

#1133 Charlie

Charlie a decis să se joace cu literele dintr-un șir de caractere, șir ce conține doar literele mici ale alfabetului englez ’a’…’z’. Jocul constă în a elimina litere din șir după următoarea regulă: fie L1, L2, L3 trei litere aflate pe poziții consecutive în șir, atunci litera L2 poate fi eliminată dacă și numai dacă este strict mai mică lexicografic decât literele L1 și L3.

Pentru a face jocul mai interesant, Charlie atașează eliminării literei L2 un cost egal cu valoarea maximă dintre ō(L1) și ō(L3), unde prin ō(litera) înțelegem numărul de ordine al literei respective în alfabet (ō(’a’)=1, ō(’b’)=2,…, ō(’z’)=26). Charlie aplică în mod repetat procedeul de eliminare și calculează suma costurilor eliminărilor efectuate.

Fiind dat un șir de caractere să se determine:

a) Lungimea maximă a unei secvențe de litere alternante, adică o secvență pentru care literele aflate pe poziții consecutive sunt de forma: Li > Li+1 < Li+2 > Li+3 < Li+4 > … < Lj.
b) Suma maximă pe care o poate obține Charlie aplicând în mod repetat procedeul de eliminare a literelor, precum și șirul obținut în final.

OJI 2015, Clasa a X-a

#1134 Panda

O rezervație de urși panda, privită de sus, are formă dreptunghiulară și este compusă din n rânduri identice, iar pe fiecare rând sunt m țarcuri identice cu baza pătrată. Țarcurile sunt îngrădite și sunt prevăzute cu uși către toate cele 4 țarcuri vecine. Ușile sunt prevăzute cu câte un cod de acces, ca atare acestea se închid și se deschid automat. Prin acest sistem, unele ţarcuri sunt accesibile ursuleților, iar altele le sunt interzise acestora. În T țarcuri se găsește mâncare pentru ursuleți.

Ursuleții din rezervație poartă câte un microcip care le deschide automat ușile țarcurilor unde pot intra și închide automat uşile țarcurilor interzise. Un țarc este accesibil ursulețului dacă ultimele S cifre ale reprezentărilor binare ale codului țarcului și ale codului k de pe microcip sunt complementare. (Exemplu: pentru S=8, 11101011 și 00010100 sunt complementare).

Într-un țarc este un ursuleț căruia i s-a făcut foame. Ursulețul se deplasează doar paralel cu laturile dreptunghiului. Trecerea dintr-un țarc în altul vecin cu el se face într-o secundă.

Cunoscând n și m dimensiunile rezervației, codurile de acces de la fiecare dintre cele n*m țarcuri, coordonatele celor T țarcuri cu mâncare, coordonatele țarcului L și C unde se află inițial ursulețul, codul k al microcipului său și numărul S, determinați:

a) Numărul X de țarcuri care îndeplinesc proprietatea că ultimele S cifre din reprezentarea binară a codului lor sunt complementare cu ultimele S cifre din reprezentarea binară a codului k purtat de ursuleț, cu excepția țarcului în care se află acesta inițial.
b) Numărul minim de secunde Smin în care poate ajunge la un țarc cu mâncare precum și numărul de țarcuri cu mâncare nt la care poate ajunge în acest timp minim.

OJI 2015, Clasa a X-a

#1135 p2sah

Se dă o tablă de șah cu n+1 linii (numerotate de sus în jos începând cu 1) și 2n+1 coloane (numerotate de la stânga la dreapta începând cu 1). Pe prima linie pătratul din mijloc conține 1 gram de fân, iar celelalte pătrate de pe prima linie nu conțin nimic. Începând cu linia a doua fiecare pătrat conține o cantitate de fân obținută prin adunarea cantităților de fân din cele 3 pătrate ale liniei anterioare cu care se învecinează (pe verticală și diagonală). De exemplu dacă n=3 tabla are 4 linii, 7 coloane și următoarea configurație.

Un cal pleacă de pe prima linie, de pe o coloana k<=n, sare din orice poziție (i,j) în poziția (i+1,j+2) atât timp cât este posibil și mănâncă tot fânul din pătratele prin care trece. De exemplu, pentru n=3 și k=2, pătratele prin care trece calul sunt marcate cu asterisc ( * )

Cerinţe:

1. Cunoscând n și k, să se calculeze cantitatea de fân de pe linia k a tablei.
2. Cunoscând n și k, să se calculeze câte grame de fân mănâncă un cal care pleacă de pe prima linie, de pe coloana k.

OJI 2015, Clasele XI-XII

#1136 Dragoni

Supărați că lansarea părții a treia a filmului lor preferat s-a amânat până în iunie 2018, Henry și Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:

Într-o lume în care vikingii pot zbura cu dragonii există N insule. Hiccup, șeful tribului de vikingi aflat pe insula 1, știe M rute directe de zbor bidirecționale între insule. Pentru fiecare j intre 1 si M, ruta j unește insulele A j și B j și are lungime D j.

Pe fiecare insulă i, (1 ≤ i ≤ n) există dragoni din specia i care pot zbura fără a se opri pentru odihnă o distanță maximă Dmax i. Cu alte cuvinte, dragonii de pe insula i vor putea parcurge orice rută j, (1 ≤ j ≤ m) pentru care Dj ≤ Dmaxi, indiferent de ce alte drumuri au făcut anterior.

Hiccup dorește să ajungă de pe insula 1 pe insula N pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua inițial un dragon din specia 1 (de pe insula 1). Apoi, dacă la un moment dat Hiccup se află pe o insula i, (1 ≤ i ≤ n) având cu el un dragon din specia t, el poate:

  1. Să zboare de pe insula i pe o altă insulă x cu dragonul pe care îl are, folosind o rută directă j între insulele i si x, bineînțeles doar dacă Dj ≤ Dmaxt.
  2. Să schimbe dragonul din specia t pe care îl are cu un dragon din specia i aflat pe insula respectivă.

Cerințe:

a. Să se determine distanța maxima Dmaxi caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula 1.
b. Să se determine distanța minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula 1 pe insula N.

OJI 2015, Clasele XI-XII

#1137 Cuart

Gina şi Mihai joacă împreună jocul Cuart. Ei au la dispoziție un șir de 2*N cartonașe ce conțin numere naturale. Primele N cartonașe, de la stânga la dreapta, sunt ale Ginei, iar următoarele N ale lui Mihai. Gina traversează șirul, de la stânga la dreapta și scrie pe o foaie de hârtie, pe primul rând, un șir de numere obținut din numerele de pe cartonașele sale, din care a șters toate cifrele pare. La fel procedează Mihai care scrie pe foaia sa de hârtie, pe primul rând, șirul de numere obținut din numerele de pe cartonașele sale, din care a șters toate cifrele impare. Dacă dintr-un număr s-au șters toate cifrele, sau au rămas doar cifre egale cu 0, atunci numărul este ignorat, deci pe hârtie nu se scrie nimic.
Fiecare copil, notează pe hârtia sa, pe al doilea rând, un alt șir de numere obținut astfel: pentru fiecare număr X scris pe primul rând, copilul va scrie cel mai mare număr natural K cu proprietatea că 1+5+9+13+...+ K ≤ X. În jocul copiilor, numărul X se numește cuarț dacă 1+5+9+13+...+K = X.

În exemplul de mai sus, Gina nu a scris niciun număr cuarț pe primul rând, iar Mihai a scris unul singur (6=1+5).

Regulile de câștig ale jocului sunt următoarele:

  • Câștigă acel copil care are scrise pe primul rând cele mai multe numere cuarț. În acest caz, valoarea de câștig a jocului este egală cu numărul de numere cuarț scrise de copilul câștigător.
  • Dacă cei doi copii au scris același număr de numere cuarț, atunci va câștiga cel care are primul număr scris pe primul rând, mai mare decât al celuilalt. Acest prim număr scris de câștigător va reprezenta valoarea de câștig.
  • Dacă nici Gina și nici Mihai nu au scris niciun număr pe hârtie, se consideră egalitate și nu câștigă niciunul.

Scrieţi un program care să citească numărul N reprezentând numărul de cartonașe ale unui copil şi cele 2*N numere de pe cartonașe, în ordine de la stânga la dreapta și care să determine:

1) Cel mai mare număr de pe cele 2*N catonașe, pentru care nu s-a scris niciun număr pe primul rând (a fost omis), nici pe hârtia Ginei, nici pe hârtia lui Mihai; dacă nu a fost omis niciun număr, se va scrie 0;
2) Câștigătorul jocului și afișează numărul 1 dacă a câștigat Gina, 2 pentru Mihai sau 0 în caz de egalitate.
3) Valoarea de câștig a jocului, sau 0, în caz de egalitate.

OJI 2015, Clasa a V-a

Maria a aflat că numerele naturale care încep cu cifra 1 și au toate cifrele ordonate strict crescător şi consecutive sau încep cu cifra 9 și au toate cifrele ordonate strict descrescător şi consecutive se numesc numere speciale. Interesată să descopere legătura dintre numerele speciale cu același număr de cifre, a observat că poate construi tabelul alăturat.

Scrieţi un program care citind patru numere naturale K, N, A şi B determină:

1) cel mai mare număr special situat în tabel pe linia K;
2) numărul special obţinut din numărul N prin ştergerea unei cifre;
3) numărul de numere speciale din mulțimea {A , A +1, A+2, A+3…,B-1,B}.

OJI 2015, Clasa a V-a

#1139 Covor

Bunica Marei țese un covor. Mara urmărește cu mare atenție modelul și încearcă să-l reconstituie pe caietul de matematică. Modelul este format din romburi. Primul romb, de indice 1, are latura formată din două pătrățele, al doilea romb, de indice 2, are latura formată din trei pătrățele etc. Un romb de indice i are latura formată din i+1 pătrățele.
Romburile sunt unite, consecutiv, ca în exemplul din imaginea alăturată. Săgețile indică sensul în care bunica țese covorul.

Ca să nu uite modelul, Mara scrie pe caiet, începând cu 1, numere consecutive care să indice modul în care țese bunica covorul.

În exemplul următor este reprezentat modul în care se țese un model format din patru romburi.

Cunoscându-se numerele n și k să se determine:

1. numărul maxim de romburi complete care pot forma modelul unui covor, descris cu ajutorul unui șir format din maximum n numere naturale consecutive (primul număr din șir fiind 1);
2. cel mai mic indice al unui romb ce conține numărul k.

OJI 2015, Clasa a VI-a

#1140 Ordine

Gigel a primit de ziua lui un joc cu bile. Jocul conţine n bile numerotate cu numerele naturale distincte de la 1 la n. Jucându-se, Gigel a amestecat bilele astfel încât acum ele nu mai sunt în ordine. Ca să le pună înapoi în cutia jocului, Gigel ia de pe masă bilele una câte una, şi le pune în cutie formând un şir. Însă Gigel se joacă şi acum, astfel încât el nu pune bilele la rând, una după alta, ci are o regulă pe care o respectă cu stricteţe. Astfel, Gigel încearcă să plaseze fiecare bilă pe care a luat-o de pe masă exact la mijlocul şirului de bile deja format. Dacă acest lucru nu este posibil (șirul are lungime impară), atunci el plasează bila la sfârşitul şirului de bile deja format. După ce toate bilele au fost puse în cutie, Gigel îşi dă seama că nu a notat ordinea în care a luat bilele de pe masă şi, în mod firesc, îşi pune problema dacă nu cumva poate deduce acest lucru din şirul de bile pe care tocmai l-a format.

Cunoscându-se numărul de bile şi configuraţia finală a bilelor în şir să se determine:

1. numărul ultimei bile luate de pe masă;
2. ordinea în care bilele au fost luate de pe masă.

OJI 2015, Clasa a VI-a

#1141 ech

Numim număr echilibrat un număr natural pentru care suma cifrelor de pe poziţii pare este egală cu suma cifrelor de pe poziţii impare.

De exemplu numărul 13552 este echilibrat, pentru că 1+5+2=8=3+5.

Dat fiind un număr natural N să se determine cel mai mic număr echilibrat, strict mai mare decât N.

OJI 2015, Clasa a VII-a

#1142 Lasere

Se consideră un teren reprezentat printr-o matrice cu n linii şi n coloane având elemente numere naturale. În fiecare element al matricei este memorată înălţimea zonei de teren corespunzătoare ca poziţie elementului respectiv. Pe acest teren sunt amplasate m lasere, în poziţii cunoscute. Un laser este îndreptat spre unul dintre cele 4 puncte cardinale, codificate prin numere astfel: Nord prin valoarea 1, Est prin valoarea 2, Sud prin valoarea 3 şi respectiv Vest prin valoarea 4. Fiecare laser va executa o singură tragere şi ca urmare va scădea cu 1 valorile tuturor elementelor din matrice din direcţia sa de tragere, exceptând poziţia laserului respectiv.

După efectuarea tuturor tragerilor, se caută poziţiile tuturor gropilor şi ale tranşeelor.

Numim groapă un element din matrice pentru care toate cele 8 elemente învecinate pe linie, coloană sau diagonale au valori mai mari sau egale decât el.

Numim tranşee o secvenţă maximală formată din două sau mai multe gropi situate pe aceeaşi linie, pe coloane consecutive. Secvenţa se numeşte maximală dacă nu mai poate fi prelungită la niciunul dintre capete.

Cunoscând configuraţia terenului şi amplasarea laserelor, să se rezolve una dintre următoarele două cerinţe:

1. să se determine numărul de gropi din teren, după executarea tragerilor;
2. să se determine numărul de tranşee existente, după executarea tragerilor.

OJI 2015, Clasa a VII-a

Considerând un șir de valori binare, numim secvență dominantă un set de elemente aflate pe poziții consecutive în șir care are proprietatea că numărul valorilor egale cu 1 este strict mai mare decât numărul valorilor de 0. De exemplu, în șirul 1,0,0,0,1,1,0,1,1,1,0,0 o secvență dominantă este 0,1,1 și o alta, de lungime mai mare, este 0,1,1,0,1,1,1. Secvența dominantă maximală este secvența dominantă de lungime maximă. În șirul din exemplu secvența dominantă maximală este 1,0,0,0,1,1,0,1,1,1,0 (adică întreg șirul, fără ultimul zero).

Dat fiind un șir de valori binare, să se determine lungimea unei secvențe dominante maximale precum și numărul acestor secvențe.

OJI 2015, Clasa a VIII-a

#1144 Pavare1

Ca în mai toate poveștile, Făt-Frumos a căutat o Cosânzeană și a găsit-o, dar tatăl ei i-a cerut să-i paveze drumul de lungime N care leagă castelele sale. Dalele cu care va pava drumul au aceeași lățime (egală cu lățimea drumului) și lungimi numere naturale. Fiind un împărat cam sâcâit, acesta dorește ca pavarea să se facă folosind un număr minim de dale, diferența de lungime între două dale vecine să nu fie mai mare ca 1, iar prima și ultima dală să fie de lungime 1. Împăratul nu se mulțumește să primească de la Făt-Frumos doar un număr (numărul minim de dale necesare): el vrea și posibilitatea de pavare cea mai mică din punct de vedere lexicografic.

Cunoscând lungimea drumului, determinați numărul minim de dale necesare pavării și posibilitatea de pavare cu număr minim de dale, care este cea mai mică din punct de vedere lexicografic.

OJI 2015, Clasa a VIII-a

Gigel, mare amator de probleme de matematică şi informatică, a observat că unele numere prime au o proprietate interesantă: orice cifră ar elimina dintr-un astfel de număr, numărul obţinut este tot număr prim. A numit astfel de numere numere extraprime. De exemplu, numărul 317 este un număr extraprim: el este număr prim şi, în plus, dacă eliminăm cifra 3, obţinem 17, care este prim; dacă eliminăm 1, obţinem 37, care este prim; dacă eliminăm 7, obţinem 31, care este şi el număr prim.

Spunem că x este între a şi b dacă x≥a şi x≤b. Fiind date două valori naturale a şi b, să se determine câte numere extraprime există între a şi b, precum şi cel mai mic şi cel mai mare număr extraprim dintre a şi b.

ONI 2013, Clasa a V-a

#1146 Greieri

Pe o linie orizontală se găsesc n greieri. Ei încep să stea „capră” într-o ordine prestabilită începând cu ultimul, pe rând, până la primul. Toţi greierii care îl preced pe cel care stă „capră” sar peste acesta, în ordine.

De exemplu pentru n=4, mai întâi stă „capră” greierul 4 și peste el sar, în ordine, 3, 2 și 1. Apoi stă „capră” greierul 3 și sar peste el, în ordine, 2, 1 și 4. Apoi stă „capră” greierul 2 și peste el sar, în ordine, 1, 3 și 4. Apoi stă „capră” greierul 1 și sar peste el, în ordine, 4 , 3 și 2, și se revine la ordinea inițială.

Scrieți un program care citește numerele naturale n și m și determină:

a) De câte sărituri este nevoie pentru a se ajunge la ordinea inițială?
b) Cum vor fi așezați greierii după m sărituri?

ONI 2013, Clasa a V-a

#1147 OniGim

La ONIGIM2013 participă N elevi de clasa a V-a având ca id-uri, în ordine, numerele naturale de la 1 la N. Anul acesta organizatorii au afişat la clasa a V-a toate punctajele distincte obţinute de elevi, în ordine strict crescătoare p1, p2,…, pK, şi un şir de N valori a1, a2,…, aN, unde ai reprezintă numărul de elevi care au punctaje strict mai mici decât punctajul elevului având id-ul i (1≤i≤N).

Cunoscând numărul de elevi (N), numărul de punctaje distincte (K) obţinute de elevii de clasa a V-a, punctajele p1, p2,…, pK, în ordine strict crescătoare, şi valorile a1, a2,…, aN cu semnificaţia din enunţ, să se scrie un program care determină:

a) Punctajul obţinut de fiecare elev în ordinea crescătoare a id-urilor.
b) Numărul de distincţii acordate de organizatori. Numărul de distincţii este egal cu numărul de elevi care au obţinut cele mai mari trei punctaje distincte.
c) Numărul maxim de elevi care au obţinut acelaşi punctaj.

ONI 2013, Clasa a V-a

Algorel tocmai a avut un interviu la AlgoTech. Fiind isteţ din fire, el a reuşit să rezolve toate problemele, mai puţin una de care nu reuşeşte nicicum să se prindă cum se face. Aflând că la Iaşi are loc Concursul Urmaşii lui Moisil, s-a gândit să propună această problemă şi să ofere 100 de puncte ca recompensă celor care o rezolvă corect.

Fie un şir cu N cifre asupra căruia se poate efectua operaţia swap de maxim X ori. Prin swap se înţelege interschimbarea a două elemente din şir aflate pe poziţii vecine.

Să se determine numărul maxim care se poate obţine din şirul cu N cifre, după efectuarea a maxim X operaţii swap.

Urmasii lui Moisil, 2015

#1162 Rox

Părinții lui Rox au cumpărat de curând un teren care are N metri lățime și M metri lungime, pe care l-au împărţit în pătrate cu latura de un metru, denumite celule. Văzând planul terenului, lui Rox i-a venit o idee. Ea s-a decis să semene florile ei preferate în etape, pe U dintre parcele de teren. Denumirile florilor sunt litere mari ale alfabetului
englez. O parcelă este un dreptunghi inclus în teren, cu laturile paralele cu ale terenului și care conține doar celule complete.

În fiecare etapă în care Rox seamănă flori, procedează astfel: alege o parcelă pentru care reține indicii celulelor din stânga sus și dreapta jos, stabilește tipul florii pe care dorește să o semene peste tot în parcelă, apoi scrie aceste informații pe o foaie de hârtie. Documentându-se pe Internet, Rox ajunge la concluzia că apare următorul fenomen ciudat: dacă într-o celulă se seamănă același tip de floare într-un număr par de etape, semințele de acel tip pur și simplu dispar.

Când finalizează semănatul, Rox le povesteşte părinților despre isprava ei. Entuziasmați, părinții fetei îi pun mai multe întrebări de tipul ”Câte tipuri de flori au rămas semănate în celula de pe linia L și coloana C?”

Deoarece Rox a plantat foarte multe flori, ea nu poate să răspundă rapid întrebărilor părinților, așa încât vă cere ajutorul și vă va răsplăti efortul cu maxim 100 de puncte.

Urmasii lui Moisil, 2015

În seara dinaintea probei de concurs, Cobby a avut un vis demn de un Oscar, cu mai multe evenimente. Se făcea că lumea era reprezentată ca o matrice pătratică de latură N, cu liniile și coloanele numerotate de la 1 la N, în care fiecare element era inițial vid. Privind în jur, a realizat că atunci când visează un element al matricei, situat la intersecția liniei i cu coloana j, interiorul acestuia se împarte în N linii și N coloane, ca o nouă matrice. Apoi, dacă visează la un element din matricea nou formată sau
din cea inițială, se întâmplă la fel.

Pentru a nu se rătăci, eroul nopții a decis să atribuie un indice fiecărei matrice formată începând cu cea inițială căreia i-a asociat indicele 1. Matricele care se creează primesc indici numere naturale consecutive (2, 3, …), în ordinea în care se obţin. Astfel, fiecare element din visul lui Cobby este definit de 3 numere: id – indicele atribuit matricei din care face parte, i şi j – indicii liniei şi coloanei pe care se află elementul.

Cobby realizează că, oricât ar încerca, nu poate visa un element decât o singură dată. Pentru a face visul şi mai interesant, el reţine pentru fiecare matrice un număr natural denumit “coeficient de importanţă”, iniţial 0 pentru fiecare matrice din vis. Din când în când, eroul nostru alege una dintre matrice şi adaugă o valoare VAL la coeficientul de importanță al ultimelor NR matrice din care s-a obținut aceasta, inclusiv ea.

După ce au loc toate evenimentele din vis, Cobby vrea să ştie valoarea finală a coeficientului de importanţă pentru un șir de K matrice date prin indicii lor. Deoarece el se grăbeşte să participe la Concursul Naţional Urmaşii lui Moisil, îţi revine ţie misiunea de a găsi răspunsul pentru fiecare matrice.

Urmasii lui Moisil, 2015

#1165 Puncte2

Bulbuka este o elevă foarte conștiincioasă. În orele de matematică, ea desenează puncte în unele pătrăţele de pe o foaie a caietului, după care le înconjoară cu un dreptunghi de mărime N*M (N≤M) trasat pe liniile imprimate pe foaie. Într-o zi, ea a observat că unele dreptunghiuri pe care le-a trasat au o proprietate specială: toate pătratele de mărime N*N incluse în dreptunghi au același număr de puncte (să-l numim P) desenate în interior.

După oră, profesorul a chemat-o să o întrebe ce desena așa interesant în timpul orei. Bulbuka i-a explicat entuziasmată descoperirea, iar profesorul i-a propus o temă specială: pentru trei valori date N, M și P, să determine câte modalități de a desena punctele există.
Bulbuka a acceptat imediat dar, pentru că nu știe să scrie numere foarte mari, s-a hotărât să prezinte răspunsul modulo 1000000007 (109+7).

Ajunsă acasă, a descoperit că problema e mai grea decât credea inițial și i-ar trebui multe caiete să scrie toate rezolvările posibile. De aceea, vă cere ajutorul.

Date fiind N, M și P, să se afișeze rezultatul cerut modulo 1000000007 (109+7).

Urmasii lui Moisil, 2015

Fie A o mulțime de N puncte Ai în plan de coordonate întregi cunoscute (Ai.x, Ai.y). Pentru o întrebare definită printr-un punct Q=(Q.x, Q.y) se cere aria înfășurătorii convexe a punctelor: {Q} ∪ {Ai | Ai.x < Q.x și Ai ∈ A }.

Înfășurătoarea convexă a unei mulțimi de puncte este poligonul convex de arie minimă care conține toate punctele în interior sau pe laturile acestuia.

Determinați răspunsurile pentru M întrebări de tipul enunţat mai sus, relativ la mulțimea inițială A.

Urmasii lui Moisil, 2015

Grigorel tocmai a descoperit un joc nou de care este atât de încântat încât s-a gândit să-l propună la concursul Urmaşii lui Moisil de la Iaşi. Cum probabil v-aţi aşteptat deja, el oferă 100 de puncte ca recompensă celor care rezolvă corect jocul.

Fie N nave planare aflate la diferite coordonate întregi (x,y). În fiecare secundă, poate fi efectuată o operaţie de tipul: se selectează o navă i aflată la poziţia (xi,yi) şi se mută în una dintre cele 4 poziţii vecine: (xi+1,yi), (xi-1,yi), (xi,yi+1), (xi,yi-1).

Grigorel vrea să afle numărul minim de secunde după care vor fi cel puţin K linii cu măcar o navă şi cel puţin K coloane cu măcar o navă.

Cunoscând coordonatele celor N nave planare, aflaţi numărul minim de secunde cerut de Grigorel.

Urmasii lui Moisil, 2015

#1186 Risc

Pentru a participa la un concert, n persoane s-au așezat la coadă pe un singur rând în așteptarea deschiderii casei de bilete. Înălțimile celor n persoane sunt toate distincte. Pe baza acestei informații cruciale, agenții de securitate au decis ca din motive de … securitate, ordinea persoanelor care așteaptă la coadă trebuie schimbată în funcție de înălțimile lor.

Astfel, agentii de pază vor alege, pe rând, câte o persoană și o vor trimite la sfârșitul rândului. După fiecare operație de tipul acesta, să-i spunem “de mutare”, rândul se restrânge, ocupându-se poziția rămasă liberă. Strategia agenților de pază este aceasta: la terminarea tuturor operațiilor de mutare, riscul minim de securitate se obține dacă toate persoanele aflate în dreapta persoanei celei mai înalte vor fi mai înalte decât cele aflate în stânga persoanei cele mai înalte. În plus, înalțimile persoanelor vor fi crescătoare până la poziția k a persoanei celei mai înalte și descrescătoare după poziția k.

Mai exact: dacă h[1], h[2], …, h[n] sunt înălțimile persoanelor după finalizarea operațiilor de mutare, atunci: există o poziție k, cu 1 ≤ k ≤ n astfel încât h[1] < h[2] < ... h[k-1] < h[k] > h[k+1] > … > h[n-1] > h[n] și în plus h[i] < h[j] pentru oricare i < k și k < j.

Deoarece o asemenea logică este greu de combătut, iar agenții nu au aerul că vor să glumească, persoanele care așteaptă la coadă vor accepta toate mutările impuse de către aceștia.

Cunoscând numărul de persoane n și înălțimile h[1], h[2], …, h[n] ale acestora să se scrie un program care determină :

1. Poziția persoanei celei mai înalte în rândul inițial, în cazul în care nu sunt necesare operații de mutare.
2. Numărul minim de mutări necesare pentru ca rândul de persoane să prezinte un risc minim de securitate.

ONI 2015, Clasa a IX-a

#1187 Roboti1

O firmă de construcţii imobiliare a achiziţionat recent un teren dreptunghiular de dimensiuni N×M. Terenul este împărțit în parcele de dimensiune 1x1. Pe unele dintre cele N×M parcele sunt plantați copaci. Firma dorește construirea unui grandios complex comercial și este necesară defrișarea întregului teren. În acest scop sunt utilizați roboți, fiecare robot având baza un pătrat de latură L. Suprafața defrișată de fiecare robot la un moment dat este chiar aria de acoperire a robotului, L×L. Fiecare robot pătrunde prin colțul stânga sus de coordonate (1, 1), se poate deplasa doar în dreapta și în jos și poate părăsi suprafața numai prin colțul dreapta jos, de coordonate (N, M).

Cunoscând dimensiunile N, M ale terenului și coordonatele parcelelor în care sunt plantați copaci se cere:

1. Numărul minim de roboți necesari defrișării întregului teren.
2. Să se răspundă la Q interogări de forma k, unde k este un număr natural. Pentru fiecare interogare de această formă va trebui determinată latura minimă a unui robot astfel încât să fie necesari pentru defrișare cel mult k roboți.

ONI 2015, Clasa a IX-a

#1190 Sipet

Un arheolog a găsit un sipet interesant. După ce l-a deschis cu grijă, a constatat cu surprindere că sipetul conține bănuți de aur. Uitându-se mai atent a mai găsit ceva: un pergament ascuns într-un compartiment secret al sipetului, cu un text scris într-o limbă antică, pe care, din fericire, arheologul o cunoștea. Din text a reieșit că un grup de negustori foarte bogați a vrut să ascundă în mare secret averea breslei lor, formată din monede de aur, deoarece se prevestea un război cumplit. Negustorii știau că există șanse ca această comoară să fie găsită și confiscată de dușmani, deci s-au sfătuit cum e mai bine să procedeze, cum să ascundă comoara. Arheologul a reușit să deducă din text următoarele:

a) Cele N monede, care formau averea breslei, au fost împărțite în maximum trei feluri de grămezi, formate din p1, p2 și p3 bănuți, p1, p2 și p3 fiind numere prime consecutive, p1<p2<p3. Fiecare grămadă a fost pusă în întregime într-un sipet.
b) Este posibil să existe 0 (zero) grămezi formate din p1 sau p2 sau p3 monede, scopul fiind să se obțină o împărțire în care numărul monedelor rămase nedistribuite să fie minim, iar dacă există mai multe posibilități, se alege aceea pentru care numărul de grămezi este mai mare. Dacă există mai multe astfel de soluții, se consideră corectă oricare dintre ele.
c) Monedele care nu au putut fi distribuite conform regulilor stabilite, au fost donate bisericii.

Scrieți un program care determină numărul maxim S de sipete și numărul sipetelor cu p1, p2 respectiv p3 monede, precum și suma donată bisericii.

ONI 2015, Clasa a IX-a

#1193 Cabana

Ben are un teren pe care se află o pădure cu arbori seculari. Acolo vrea să-şi construiască o cabană, însă el fiind ecologist nu vrea să taie niciun arbore, ci vrea să găsească cea mai mare suprafaţă dreptunghiulară fără arbori. El caută o suprafaţă dreptunghiulară străjuită doar în colţuri de arbori şi cu laturile paralele cu axele de coordonate. Ben cunoaşte coordonatele tuturor arborilor din pădure şi vă roagă să-l ajutaţi să găsească aria dreptunghiului cu suprafaţă maximă care are arbori doar în cele patru colțuri.

Cunoscând numărul arborilor din pădure şi coordonatele acestora, se cere să se determine aria dreptunghiului de suprafaţă maximă cu copaci doar în cele 4 colţuri, unde Ben intenţionează să-şi construiască cabana.

ONI 2015, Clasa a X-a

#1194 Fence

Un proprietar vinde un teren de formă dreptunghiulară împărțit în MxN parcele de formă pătrată cu lungimea laturii de o unitate. Fiecare parcelă costă V lei. Vlad s-a interesat și a aflat pentru fiecare din parcelele terenului care este valoarea de revânzare. El constată că unele parcele i-ar putea aduce profit, iar altele i-ar aduce pierdere. Fiind isteț, negociază cu proprietarul să cumpere atâtea parcele de teren câte pot fi împrejmuite cu un singur gard de lungime egală cu 2M+2N unități. Terenul are pe fiecare din cele patru laturi acces la drumul exterior, pe o porțiune de lungime egală cu o unitate. Vlad negociază astfel încât terenul achiziționat să conțină și cele patru parcele de acces la exterior.

Cunoscând M și N – dimensiunile terenului, V – prețul de cumpărare al fiecărei parcele, x_nord, x_sud, y_vest și y_est – pozițiile parcelelor cu acces la drumul exterior și A[i][j], 1≤i≤M și 1≤j≤N – valorile de revânzare pentru fiecare parcelă, să se determine:

a) Profitul P_arie_minimă pe care-l poate obține Vlad după cumpărarea și apoi revânzarea suprafeței de teren de arie minimă, împrejmuită conform condițiilor negociate.
b) Profitul maxim P_max pe care-l poate obține Vlad după cumpărarea și apoi revânzarea unei suprafețe de teren împrejmuită conform condițiilor negociate.

ONI 2015, Clasa a X-a

#1195 NMult

Se consideră trei numere naturale nenule n, k și w.

Să se scrie un program care determină numărul m al mulțimilor de forma {x[1], x[2],… , x[k]} având ca elemente numere naturale nenule, ce satisfac simultan condițiile:

  • 1 ≤ x[1] < x[2] < ... < x[k] ≤ n
  • x[i+1] - x[i] ≥ w, 1 ≤ i ≤ k - 1

ONI 2015, Clasa a X-a

Definim o modificare procentuală de preț ca fiind o pereche (c p) formată dintr-un caracter din {‘+‘,‘-‘} și un număr natural p. Dacă c = ‘+‘ atunci are loc o scumpire iar dacă c = ‘-‘ atunci are loc o ieftinire a unui preț, iar numărul p reprezintă procentul de modificare a prețului.

Exemple de modificări procentuale de preț: (+ 35) – reprezintă scumpirea unui preț cu 35%; (– 50) – reprezintă ieftinirea unui preț cu 50%.

Unui preț inițial i se poate aplica o succesiune de n modificări procentuale de preț obținându-se un preț final. Numim ciclu de preț de lungime n o succesiune de n modificări procentuale de preț, cu proprietatea că prețul final este egal cu prețul inițial.

Să se scrie un program care citește un număr natural n și determină numărul de cicluri de preț de lungime n distincte ce conțin cel puțin o dată o modificare procentuală cunoscută (C P).

ONI 2015, Clasa a X-a

Ne aflăm în secția de vopsitorie a uzinei Toyota Motor unde inginerii japonezi prezintă ultimul tip de robot industrial de vopsire. În dorința de a evidenția calitatea și viteza de execuție a roboților, inginerii folosesc pentru demonstrație o tablă de dimensiunea n×n, împărțită în pătrate cu latura egală cu 1, reprezentată sub forma unui tablou bidimensional cu n linii şi n coloane.

Un robot utilizat pentru vopsire are două brațe telescopice care se deplasează de-a lungul unei axe. Fiecare braț poate vopsi într-o unitate de timp un singur pătrat. La momentul de timp t=0 robotul primește comanda de a se poziționa într-un pătrat specificat prin coordonatele (x,y).

În funcție de traiectoria de deplasare roboții folosiți sunt de două tipuri. La momentul de timp t robotul de tip 1 vopsește pătratele aflate la coordonatele: (x-t,y+t) și (x+t,y-t), iar robotul de tip 2 vopsește pătratele aflate la coordonatele: (x+t,y+t) și (x-t,y-t). Pentru vopsirea unui pătrat se consumă 1 litru de vopsea.

Pe tablă sunt așezați m roboți.

Cunoscând pentru cei m roboți coordonatele inițiale (x[i],y[i]), i=1,…,m, se cere să se determine:

a) Cantitatea totală de vopsea care a fost folosită de roboți după t unități de timp
b) Numărul minim de unități de timp necesare formării primului dreptunghi cu arie nenulă. Un dreptunghi corect format este rezultatul intersecției a două traiectorii paralele a doi roboți de tip 1 cu două traiectorii paralele a doi roboți de tip 2, iar colțurile dreptunghiului sunt 4 pătrate care au fost vopsite de doi roboți de tipuri diferite.

ONI 2015, Clasa a X-a

#1198 Sablon1

Se consideră alfabetul englez compus din literele mici, de la a la z.
Se numeşte cuvânt un şir finit, eventual vid, de litere din acest alfabet.
Se numeşte expresie şablon un şir de caractere din alfabet în care pot apărea și caracterele ? şi *.

Un cuvânt se potrivește cu o expresie șablon dacă se poate obține din aceasta astfel:

  • caracterul ? se înlocuiește cu o singură literă din alfabet;
  • caracterul * se înlocuiește cu un cuvânt oarecare, eventual vid;
  • din expresia șablon se poate elimina sau nu, înainte de a efectua înlocuirea caracterelor ? și *, un singur caracter de tip literă.

Considerându-se o expresie șablon și un șir de cuvinte, să se determine, pentru fiecare cuvânt în parte, dacă se potrivește sau nu cu expresia şablon dată.

ONI 2015, Clasa a X-a

#1199 Metrou

Această problemă este dedicată celor care așteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei.

Se dă planul unei rețele de metrou cu N stații și M tuneluri bidirecționale între stații. Două stații de metrou se numesc vecine dacă există un tunel între ele în acest plan. Fiecare stație i are asociat un profit p[i] dat.

Henry a fost recent promovat dintr-un post de angajat al departamentului de curățenie pe postul de project manager al firmei. Deoarece nu există fonduri pentru construirea întregii rețele de metrou, Henry trebuie să aleagă o submulțime de stații care vor fi construite, astfel încât oricare două stații alese să nu fie vecine în planul inițial. Pentru a-și păstra poziția în companie, suma profiturilor stațiilor alese în această submulțime trebuie să fie maximă.

Dându-se N, M, profiturile aduse de fiecare din cele N stații și planul inițial al rețelei, să se determine suma maximă a profiturilor stațiilor pe care le poate alege Henry astfel încât oricare două stații alese să nu fie vecine în planul inițial.

ONI 2015, Clasele XI-XII

Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din N camere, unite între ele prin N-1 culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i s-au stabilit s[i] spiriduși de praf.

Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere a și b (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera b trece prin camera a. Fetele vor merge apoi din camera a în camera b pe drumul cel mai scurt (fără a trece de două ori prin aceeași cameră), gonind spiridușii de praf aflați în fiecare cameră prin care trec, inclusiv pe cei din camerele a și b. După ce fetele ajung în camera b, ele consideră că toate camerele din care au gonit spiridușii de praf au fost alese pentru spațiul de joacă.

Fetele au stabilit pentru fiecare cameră i un coeficient p[i] care reprezintă cât de plăcută ar fi camera i pentru spațiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de C spiriduși ai prafului din camerele prin care trec.

Cunoscând valorile lui N și C, numărul de spiriduși ai prafului s[i], coeficienții p[i] pentru fiecare cameră i, cât și modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienților p ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.

ONI 2015, Clasele XI-XII

#1201 Text1

Un şir format din cifre trebuie să fie tastat în una sau mai multe sesiuni.

Există două tastaturi: tastatura A care conţine taste cu toate combinaţiile de exact două cifre: tasta 00, tasta 01, 02, …, 98, 99 și tastatura B care conţine taste cu toate combinaţiile de exact trei cifre: tasta 000, tasta 001, …, 998, 999. Cifrele se vor introduce în una sau mai multe sesiuni, pentru o sesiune putându-se folosi o singură tastatură. Datorită unei ordonanțe de urgență, dacă o combinație de taste a fost introdusă cu una din tastaturi în sesiunea curentă și, continuând sesiunea, această combinație poate fi introdusă din nou, este necesar să continuăm sesiunea cel puțin până când o vom introduce din nou. În cazul în care introducem până atunci și alte taste, trebuie să continuăm sesiunea până când vom introduce ultima apariție a lor.

Astfel, dacă şirul 255222255257 este început folosind tastatura A, se va scrie obligatoriu într‑o sesiune 25 52 22 25 52. Suntem obligați să tastăm până la ultima apariție a tastei 25 în sesiunea curentă, și când folosim tasta 52 suntem obligați să continuăm până la ultima apariție a acesteia. A se observa că cifrele de pe pozițiile subliniate sunt tot 2 și 5, însă nu formează o tastă care se poate apăsa în sesiunea curentă. Deoarece se dorește un număr cât mai mare de sesiuni, se va începe o nouă sesiune în care se va scrie doar 57.

Cunoscându-se numărul total de cifre și secvența de cifre ce formează şirul, să se determine o modalitate de a despărţi textul astfel încât el să poată fi scris într-un număr maxim de sesiuni.

ONI 2015, Clasele XI-XII

Se dă un arbore cu N noduri numerotate de la 1 la N cu rădăcina în nodul 1. Fiecare nod din arborele dat are o valoare întreagă atașată. Se dau M întrebări de forma (x, y), unde x este un strămoș al nodului y: dacă s-ar elimina toate nodurile de pe lanțul care unește x cu y (inclusiv nodurile x și y), care ar fi valoarea maximă din nodurile neeliminate?

Cunoscând numărul de noduri N, configurația arborelui, valorile atașate celor N noduri, și cele M întrebări, să se răspundă la fiecare întrebare dată.

ONI 2015, Clasele XI-XII

#1203 KSecv

Fie un vector V cu N elemente și un număr K. Vectorul V trebuie împărțit în exact K subsecvențe nevide, astfel încât fiecare element din vector să aparțină exact unei subsecvențe. Această împărțire trebuie făcută astfel încât maximul șmecheriei fiecărei subsecvențe să fie cât mai mic. (Această problemă concepe greșit sistemul de șmecherie și valoare). Șmecheria fiecărei subsecvențe se definește ca fiind parte întreagă din ((Vmax – Vmin + 1) / 2), unde Vmax este valoarea maximă din subsecvență, iar Vmin este valoarea minimă.

Vectorul V de N elemente va fi generat în felul următor: se dă un număr M și 2 vectori A și B de lungime M (indexați de la 0 la M - 1). Fiecare element i, 0 ≤ i < N, din vectorul V va fi calculat cu următoarea formulă: V[i] = (A[i % M] ^ B[i / M]), unde x % y reprezintă restul lui x la împărțirea cu y, x / y reprezintă câtul împărțirii lui x la y și x ^ y reprezintă rezultatul operației xor (sau exclusiv pe biți) dintre x și y.

ONI 2015, Clasele XI-XII

#1204 Trenuri

Gara de Nord este cea mai vestită gară din lume. Japonezii, invidioşi pe sistemul performant de întârziere al trenurilor din Gara de Nord, s-au hotărât să analizeze motivul realizării unei astfel de performanțe.

În Gara de Nord (considerată stația 0) există N trenuri. Pentru fiecare tren i știm că va pleca din Gara noastră protagonistă (stația 0) și o să meargă până la stația statie[i]. Staţiile x şi x+1 sunt legate în mod direct pentru orice x, astfel că trenul i va opri în toate stațiile din intervalul [0, statie[i]]. De asemenea, știm că trenul i are o capacitate egală cu numărul maxim de oameni pe care îl poate transporta. Această capacitate este notată cu capacitate[i].

Avem M pasageri dornici sa folosească magnificul traseu. Pentru fiecare pasager i știm intervalul de stații [a[i], b[i]] pe care vrea să îl parcurgă. Mai exact, acesta vrea să se urce într-un tren în stația a[i] și să coboare în stația b[i].

Din cauza capacității limitate a trenurilor, este posibil ca nu toți pasagerii sa poată obțină un loc și să ajungă în destinația dorită. Să se determine numărul maxim de pasageri care pot ajunge din stația de plecare în stația de sosire, precum și o configurație în care aceștia se pot urca în trenuri.

ONI 2015, Clasele XI-XII

#1205 Nod

Pe vremea maurilor, transmiterea unor mesaje codificate între două persoane se făcea folosind un cifru numit nod. Cele două persoane alegeau în secret o poveste. Aceasta era scrisă într-o carte folosind litere mici și mari ale alfabetului englez, pe P pagini, numerotate de la 1 la P, fiecare conținând exact R rânduri, numerotate în cadrul fiecărei pagini de la 1 la R, iar fiecare rând fiind format din exact C cuvinte, numerotate în cadrul fiecărui rând de la 1 la C.

Un cuvânt al mesajului de transmis era codificat prin poziția sa în povestea aleasă de cei doi, folosind trei numere scrise cu cifre romane, ce indicau în ordine: numărul paginii, numărul rândului în cadrul paginii, respectiv al cuvântului în cadrul rândului.
Mesajul astfel codificat era scris pe trei linii. Pe prima linie erau scrise numerele paginilor, pe a doua linie numerele rândurilor, iar pe a treia linie erau scrise numerele de ordine ale cuvintelor.

Presupunem că mesajul este format din primul cuvânt de pe al cincilea rând al celei de a doua pagini și din al patrulea cuvânt de pe rândul al doilea al primei pagini. Mesajul putea fi transmis pe trei linii în modul următor:

  • II I (numerele paginilor)
  • V II (numerele rândurilor)
  • I IV (numerele cuvintelor)

Cifrele romane sunt scrise cu majusculele M, D, C, L, X, V, I, iar valorile corespunzătoare lor sunt în ordine: 1000, 500, 100, 50, 10, 5, 1. Valoarea unui număr scris cu cifre romane se calculează parcurgând de la stânga la dreapta cifrele numărului astfel:

  • cifra curentă se adună la valoarea obținută până în acel moment, dacă cifra următoare este mai mică sau egală cu ea;
  • cifra curentă se scade din valoarea obținută până în acel moment, dacă cifra următoare este mai mare decât ea;
  • ultima cifră se adună întotdeauna la valoarea obținută până în acel moment.

De exemplu pentru numărul MCDXLVI scris cu cifre romane, se obține valoarea 1446 în sistem zecimal, astfel: 1000-100+500-10+50+5+1, iar pentru numărul XXI scris cu cifre romane se obține valoarea 21 în sistemul zecimal astfel: 10+10+1.

Cunoscându-se textul poveștii ales de cei doi și mesajul codificat de ei scrieți un program care rezolvă următoarele două cerințe:

a) Rescrie mesajul codificat folosind scrierea cu cifre din sistemul zecimal.
b) Afișează toate cuvintele mesajului decodificat în ordinea în care acestea apar în poveste.

ONI GIM 2014, Clasa a VII-a

#1206 Placa

Un gard este format din mai multe plăci dreptunghiulare. Fiecare placă este, la rândul ei, construită din NxM cărămizi. Una dintre plăci ridică o problemă, deoarece este deteriorată. Placa este reprezentată pe hârtie cu ajutorul unei matrice cu N linii și M coloane, numerotate de la 1 la N, respectiv de la 1 la M. Matricea conține doar valori 0 și 1, și respectă următoarele reguli:

  • un element egal cu 1 indică prezența în aceea poziție a unei cărămizi, iar un element egal cu 0 indică absența ei;
  • linia 1 și linia N conțin numai valori egale cu 1, pentru că marginea de sus și cea de jos a plăcii este intactă;
  • din orice element egal cu 1, situat în interiorul matricei, se poate ajunge pe linia 1 sau pe linia N sau pe amândouă, mergând doar în sus sau doar în jos, parcurgând numai valorile egale cu 1;
  • există cel puțin o coloană stabilă (formată numai din elemente egale cu 1).

Se dorește modificarea plăcii și pentru aceasta se pot șterge din matrice maximum K coloane alăturate. După ștergere se alipesc coloanele rămase și se deplasează pe verticală partea de sus a plăcii spre cea de jos, până când se va forma o coloană stabilă.

Să se determine înălțimea minimă Hmin pe care o poate avea placa ștergând cel mult @K@ coloane alăturate. Identificați numărul minim de coloane alăturate care trebuie șterse pentru a obține înălțimea Hmin.

ONI GIM 2014, Clasa a VII-a

#1207 Cifre9

Maia tocmai a învăţat la şcoală să facă adunări cu numere naturale având mai multe cifre. Pentru că îi place foarte mult matematica s-a apucat să scrie pe o foaie multe numere naturale, cu una sau mai multe cifre, şi a început să le adune.

După o vreme s-a cam plictisit şi s-a gândit să afle cea mai mare sumă ce s-ar putea obţine dacă s-ar schimba între ele cifrele numerelor de pe foaie. Are însă o singură dorinţă: după ce schimbă cifrele între ele să rămână acelaşi număr de numere cu o cifră, acelaşi număr de numere cu două cifre şi aşa mai departe.

Cerinţe

Scrieţi un program care să determine

a) suma maximă ce se poate obţine schimbând între ele cifrele numerelor iniţiale;
b) un şir de numere pentru care se obţine suma maximă, respectând restricţiile din enunţ.

ONI GIM 2014, Clasa a VIII-a

#1208 Solitar

Se consideră un joc de cărţi cu un număr nelimitat de coloane. Iniţial, pe prima coloană există, într‑o ordine oarecare, N cărţi cu numere distincte din mulţimea {1,2,…,N}, următoarele coloane fiind vide (fără cărţi). Numim secvenţă de la sfârşitul coloanei ultima sau ultimele două sau ultimele trei etc. cărţi din coloană care au scrise pe ele numere consecutive în ordine crescătoare, considerate de jos în sus. De exemplu, în figurile 1 şi 2 sunt reprezentate două astfel de coloane cu câte 6 cărţi având numere între 1 şi 6. În figura 1, secvenţa de la sfârşitul coloanei este formată doar din cartea 1. În figura 2, secvenţa de la sfârşitul coloanei este formată din cărţile 3, 4 şi 5. Se observă că în coloana din figura 1 mai există o secvenţă formată din cărţile 2, 3 şi 4, dar aceasta nu este la sfârşitul coloanei.

Operaţiile permise ale jocului sunt:

A. mutarea secvenţei de cărţi de la sfârşitul unei coloane pe o coloană nouă, dacă acea coloană este vidă (nu conţine nicio carte);
B. mutarea secvenţei de cărţi de la sfârşitul unei coloane la sfârşitul altei coloane cu cărţi, doar dacă secvenţa mutată formează o secvenţă de numere consecutive cu cele de pe cartea sau cărţile aflate la sfârşitul coloanei respective.

Se doreşte ca, printr-un număr minim de operaţii permise, să se obţină pe una dintre coloane toate numerele de la 1 la N, în ordine crescătoare, considerate de jos în sus.

De exemplu, de la configuraţia iniţială din figura 2 se va obţine, printr-o operaţie A, configuraţia 1 de mai jos. Apoi, printr-o operaţie B, se obţine configuraţia 2, printr-o nouă operaţie B se obţine configuraţia 3, apoi se mută secvenţa 2,3,4,5,6 pe o coloană vidă (operaţia A), apoi se mută secvenţa 1 peste secvenţa 2,3,4,5,6 (operaţia B) şi se obţine, pe coloana a doua, configuraţia finală cerută.

Configurația 1 Configurația 2 Configurația 3 Configurația 4 Configurația 5

Cerința

Cunoscând valoarea lui N, precum şi valorile cărţilor de pe prima coloană, să se determine numărul minim de operaţii prin care se poate obţine secvenţa 1, 2, …, N pe una dintre coloane.

ONI GIM 2014, Clasa a VIII-a

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

ONI GIM 2015, Clasa a V-a

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

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

ONI GIM 2015, Clasa a V-a

#1216 Echer

Oli are un echer de forma unui triunghi dreptunghic, cu catetele de lungimi L1 și L2 unități, și o foaie de caiet de matematică cu M rânduri și N coloane de pătrățele având latura de o unitate.

Oli a poziționat echerul în colțul din stânga sus al foii de hârtie, ca în imaginea alăturată și vrea să îl mute astfel încât să atingă colțul din dreapta jos al foii de hârtie cu oricare din colțurile echerului, utilizând doar mutări de forma:

Scrieţi un program care citeşte lungimile catetelor echerului, numărul de rânduri, respectiv numărul de coloane ale foii de hârtie și determină:

1. numărul minim de mutări K, prin care poate muta echerul din colțul din stânga sus al foii de matematică, astfel încât echerul să atingă colțul din dreapta jos al foii;
2. cele K mutări efectuate pentru a deplasa echerul din colțul din stânga sus al foii, până când un colț al echerului atinge colțul din dreapta jos al foii; dacă există mai multe soluții, se va afișa soluția minimă în sens lexicografic.

ONI GIM 2015, Clasa a VI-a

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

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

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

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

ONI GIM 2015, Clasa a VI-a

#1218 Teren

În satul vecin există un teren agricol de formă dreptunghiulară împărțit în N*M pătrate elementare identice, dispuse alăturat câte M pe fiecare rând şi câte N pe fiecare coloană. Rândurile sunt numerotate de la 1 la N, iar coloanele de la 1 la M. Un pătrat elementar situat în teren pe rândul R și coloana C este identificat prin coordonatele (R,C).

Suprafețe dreptunghiulare din teren (formate fiecare din unul sau mai multe pătrate elementare alăturate) sunt revendicate de T fermieri din sat, în calitate de moștenitori, pe baza actelor primite de la strămoșii lor. Pentru că au apărut și acte false, s-a constat că pot exista mai mulți fermieri care revendică aceleași pătrate elementare.

În cele T acte ale fermierilor, suprafețele dreptunghiulare sunt precizate fiecare prin câte două perechi de numere (X,Y) și (Z,U), reprezentând coordonatele primului pătrat elementar din colțul stânga-sus al suprafeței (rândul X și coloana Y), respectiv coordonatele ultimului pătrat elementar situat în colțul dreapta-jos al suprafeței (rândul Z și coloana U).

Scrieţi un program care să citească numerele naturale N, M, T, R, C apoi cele T perechi de coordonate (X,Y) și (Z,U) precizate în acte (corespunzătoare suprafețelor dreptunghiulare revendicate) și care să determine:

  1. numărul fermierilor care revendică pătratul elementar identificat prin coordonatele (R,C);
  2. numărul maxim de fermieri care revendică același pătrat elementar;
  3. numărul maxim de pătrate elementare ce formează o suprafață pătratică nerevendicată de niciun fermier.

ONI GIM 2015, Clasa a VI-a

#1219 Cript

Ilinca a citit despre criptarea mesajelor, acum dorește să comunice cu prietena ei Miruna numai prin mesaje criptate folosind un sistem propriu de criptare.

Ilinca ştie că fiecare caracter se reprezintă în memoria calculatorului pe 8 biți, în care se memorează scrierea în baza 2 a codului ASCII al caracterului respectiv. Pentru a cripta caracterul, Ilinca foloseşte o matrice pătratică având 8 linii (numerotate de la 0 la 7 de sus în jos) şi 8 coloane (numerotate de la 0 la 7 de la stânga la dreapta). Pe prima linie a matricei Ilinca scrie cei 8 biţi reprezentând scrierea în baza 2 a codului ASCII al caracterului, pe poziţia 0 fiind scrisă cifra cea mai semnificativă (corespunzătoare lui 27). Pe fiecare dintre următoarele 7 linii din matrice scrie permutarea circulară cu o poziție la stânga a liniei anterioare. Ordonează lexicografic liniile matricei formate și defineşte cript-ul caracterului ca fiind succesi­unea de biți reprezentată de ultima coloană din matrice, parcursă de sus în jos, urmată de indicele liniei din matrice pe care a ajuns după ordonarea lexicografică reprezentarea în baza 2 a codului ASCII al caracterului. Dacă există linii egale în matrice, după ordonarea lexicografică acestea îşi vor păstra ordinea relativă iniţială, astfel că linia conţinând reprezentarea în baza 2 a codului ASCII al caracterului va fi prima dintre acestea.

Pentru a cripta un mesaj, Ilinca scrie în ordine cript-urile caracterelor din mesajul respectiv.

Miruna cunoaşte sistemul de criptare al Ilincăi, ca urmare ştie să decripteze mesajele primite.

Scrieți un program care să rezolve următoarele două cerinţe:
1. citește un mesaj şi afişează mesajul criptat conform sistemului Ilincăi;
2. citeşte un mesaj criptat conform sistemului Ilincăi şi determină mesajul decriptat.

ONI GIM 2015, Clasa a VII-a

#1220 Scadere

Fie n un număr natural nenul.

Să considerăm o expresie de forma: x[1]-x[2]-x[3]-...-x[n]

Se ştie că scăderea nu este o operaţie asociativă, adică x[1]-(x[2]-x[3])≠(x[1]-x[2])-x[3].

Ca urmare, prin plasarea unor perechi de paranteze în expresie, putem obţine diferite valori.
Pentru problema noastră, vom denumi scădere o expresie de forma de mai sus în care pot apărea şi paranteze rotunde care se închid corect. Valoarea unei scăderi se obţine efectuând operaţiile de scădere în ordine de la stânga la dreapta; dacă apar paranteze, se efectuează mai întâi operaţiile din paranteze.

Date fiind valorile x[1], x[2], …, x[n] care intervin în scădere, scrieţi un program care să rezolve următoarele două cerinţe:

  1. să se determine valoarea maximă a unei scăderi (obţinută prin inserarea convenabilă a unor paranteze rotunde în expresia x[1]-x[2]-x[3]-...-x[n]), precum şi o scădere având valoare maximă.
  2. să se determine valoarea unei scăderi specificate.

ONI GIM 2015, Clasa a VII-a

#1222 TV

Comisia Naţională a Audiovizualului (CNA) este autoritatea care coordonează activitatea posturilor media din România. Șeful CNA-ului dorește o statistică referitoare la publicitatea transmisă de posturile de televiziune. În acest scop, el primește pentru fiecare zi informații în următorul format: d hh:mm:ss, unde d este durata exprimată în secunde a publicității, iar hh:mm:ss este momentul de start al publicității (hh este ora, mm este minutul, iar ss este secunda). Observaţi că d este separat de hh printr-un singur spaţiu, iar următoarele valori sunt separate prin caracterul ':'.

De exemplu o linie de forma:

150 05:02:45

se interpretează astfel: există un post TV care a transmis publicitate cu durata de 150 secunde, ora de început fiind 5, 2 minute și 45 de secunde.

”Secunda de aur” este o secundă în care se difuzează cât mai multă publicitate, adică pe un număr maxim de posturi în acea secundă se transmite publicitate. Dacă sunt mai multe astfel de secunde, “secunda de aur” este considerată prima secundă cu această proprietate în derularea zilei.

Șeful CNA primește în fiecare dimineață lista cu activitatea din ziua anterioară ca o succesiune de linii, fiecare linie având forma descrisă mai sus.

Scrieţi un program care, cunoscând lista din ziua anterioară, să rezolve următoarele cerinţe:

  1. să determine durata totală în care niciun post de televiziune nu a difuzat publicitate;
  2. să determine care este “secunda de aur”.

ONI GIM 2015, Clasa a VII-a

#1223 Magic1

Pentru obținerea Pietrei Filosofale, un alchimist a preparat un elixir folosind un creuzet de capacitate C, în care a turnat picături de metal topit, într-o ordine bine stabilită, în N etape. Numărul de picături turnate într-o etapă este cuprins între 0 și C-1, iar procesul începe când în creuzet s-a turnat prima picătură (în prima etapă numărul de picături turnate este nenul). Picăturile se adună în creuzet una câte una şi, de fiecare dată când acesta se umple complet, alchimistul rosteşte o formulă magică, provocând transformarea întregului conţinut într-o singură picătură, apoi continuă procesul. O rețetă de obținere a elixirului se exprimă printr-un șir de N numere, reprezentând numărul de picături turnate în cele N etape.

De exemplu, aplicând rețeta 5 6 1 0, cu un creuzet de capacitate C=7, în cele N=4 etape procesul este:

  • etapa 1: se toarnă 5 picături;
  • etapa a 2-a: se toarnă 6 picături, astfel: după primele 2 picături se umple creuzetul (5+2=7) și deci se rosteşte formula magică, în creuzet rămânând o picătură; se continuă cu celelalte 4 picături; la finalul etapei în creuzet sunt 5 picături (1+4=5);
  • etapa a 3-a: se toarnă o picătură; la finalul etapei în creuzet sunt 6 picături (5+1=6);
  • etapa a 4-a: se toarnă 0 picături; după ultima etapă creuzetul conține 6 picături (6+0=6).

O rețetă care corespunde Pietrei Filosofale trebuie să conducă, la finalul aplicării ei, la obținerea unei singure picături, chintesența metalelor amestecate. Bineînțeles, sunt mai multe astfel de rețete.

Fiind un tip responsabil, alchimistul a lăsat posterității un set de tratate, care cuprind toate aceste rețete. El a scris pe fiecare pagină câte o rețetă, astfel încât niciuna să nu se repete în cadrul întregii lucrări. Pe vremea aceea erau meșteri pricepuți, care fabricau tratate de dimensiuni corespunzătoare, încât fiecare pagină să poată cuprinde o rețetă ca a noastră, oricât de lungă ar fi ea. Fiecare tratat are P pagini și doar după ce completează toate cele P pagini ale unui tratat, alchimistul începe un nou tratat.

Se cere numărul de rețete publicate în ultimul tratat.

ONI GIM 2015, Clasa a VIII-a

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.

ONI GIM 2015, Clasa a VIII-a

Jocul pe care îl joaca Robo atunci când se plictisește este un joc inteligent pentru roboței. Pe ecranul tabletei lui roboțești, sunt N căsuțe de formă pătrată, cu latura egală cu 1. Căsuțele sunt așezate pe un rând, una lângă alta, fiind etichetate, în această ordine, cu numere de la 1 la N. Fiecare căsuță conține câte un număr natural, identificatorul câte unuia dintre prietenii săi, roboței, ca și el. Identificatorii se pot repeta.

Robo poate interschimba conținutul a două căsuțe, numai dacă distanța dintre centrele acestora pe orizontală este egală cu distanța dintre brațele sale; distanța, pe orizontală, dintre centrele a două căsuțe etichetate cu i, respectiv cu j, este j-i (1≤i<j≤N).

El își poate fixa în orice moment distanța dintre brațe la 1 sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea N-1. Astfel, distanța dintre brațele sale poate fi 1, apoi, prin dublare, 2, apoi, prin dublare 4, apoi, prin dublare 8 etc. La începutul jocului, distanța dintre brațele lui Robo este 1. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.

Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus.

ONI GIM 2015, Clasa a VIII-a

#1226 Nebuni

Pe o tablă de şah cu N linii şi N coloane sunt plasaţi M nebuni. După cum se ştie de la jocul de şah, nebunii atacă doar în diagonală.

O poziţie de pe tabla de şah este considerată sigură dacă nu este atacată de niciun nebun aflat pe tablă.

Scrieţi un program care să determine numărul de poziţii sigure de pe tabla de şah.

ONI GIM 2015, Baraj

#1227 Spioni

Gigel si Ionel se joacă de-a spionii! De aceea ei imaginează o modalitate de a codifica un mesaj astfel încât nimeni să nu îl poată descifra. Toate mesajele lor au lungimea o putere a lui 2. Ei numerotează literele mesajului începând cu 1. Apoi separă literele în două categorii: cele cu număr de ordine impar în stânga, cele cu număr de ordine par în dreapta, păstrând ordinea lor. Procedeul continuă pentru fiecare grupă nou rezultată începând cu cea din stânga, până când fiecare grupă obţinută conţine un singur caracter. După terminarea operaţiilor alipesc grupele de câte o literă rezultate, începând de la stânga spre dreapta şi obţin mesajul codificat.

De exemplu pentru mesajul MESAJNECODIFICAT procedează astfel:
1. numerotează

MESAJNECODIFICAT
123456789...

2. separă

MSJEOIIA                   EANCDFCT            apoi repetă paşii 1 şi 2 pentru 
12345678                   12345678            fiecare grupă rezultată

MJOI        SEIA           ENDC       ACFT
1234        1234           1234       1234

MO   JI     SI   EA        ED  NC     AF  CT
12   12     12   12        12  12     12  12

M O  J I    S I  E A       E D  N C   A F  C T
1 2  1 2    1 2  1 2       1 2  1 2   1 2  1 2    

până se obţine un singur caracter în fiecare grupă şi alipind literele de la stânga spre dreapta rezultă mesajul codificat: MOJISIEAEDNCAFCT

Scrieţi un program care să rezolve următoarele două cerinţe:

  1. dat fiind un mesaj, să determine codificarea acestuia;
  2. dat fiind un mesaj codificat, să determine decodificarea acestuia.

ONI GIM 2015, Baraj

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

ONI GIM 2015, Baraj

Fie n și p două numere naturale.

Notăm cu A(n,p) mulțimea tuturor numerelor naturale cu proprietățile :

  • sunt mai mari sau egale cu 2 și mai mici sau egale cu n;
  • descompunerea lor în factori primi conține doar exponenți mai mici sau egali cu p.

Să se scrie un program care citește două numere naturale n și p și determină cardinalul mulțimii A(n,p).

Lot Juniori, Valcea, 2015

#1232 kswap

Fie A = (a[1],a[2],…,a[N]) o permutare a mulțimii {1,2,…,N}.

Permutarea A o numim K-swap dacă prin aplicarea algoritmului de sortare bubble-sort sunt necesare exact K swapuri (interschimbări) pentru ca aceasta să devină permutarea identică.
Reamintim algoritmul bubble-sort:

do {   
    ok = 1;    
    for ( i = 1; i < N; i ++ )      
        if ( a[i] > a[i+1] ){        
             swap(a[i], a[i+1]);   
             ok = 0;   
        }
}while( ok == 0 );          

Pentru N și K dat să se determine numărul de permutări K-swap ale mulțimii {1,2,…,N}.

Lot Juniori, Valcea, 2015

#1233 Paint

Roberto are suflet de artist. El visează să ajungă într-o bună zi un pictor celebru, dar pentru moment își câştigă existența ca zugrav.

Roberto a primit sarcina de a zugrăvi un zid având lungimea n metri şi înălţimea un metru. Pentru aceasta are la dispoziţie m zile. În fiecare zi i, el acoperă cu un singur strat de vopsea o porţiune compactă de înălțime un metru și de lungime l[i] metri, începând de la distanţa d[i] metri faţă de capătul din stânga al zidului.

Roberto ştie din experienţă că fiecare porţiune de zid trebuie acoperită cu cel puţin K straturi de vopsea pentru ca stratul final de vopsea să aibă consistenţa dorită. Din nefericire, firea lui de artist nu i-a permis să-şi poată planifica munca în mod optim, astfel că la capătul celor m zile de efort, Roberto a constatat că zidul are porţiuni pe care le-a acoperit de mai mult de k ori şi alte porţiuni pe care le-a acoperit de mai puţin de k ori.

Pentru a recupera în proprii săi ochi dar mai ales în ochii şefului de echipă, el trebuie să afle mai întâi suprafaţa totală a tuturor porţiunilor de zid care mai trebuie zugrăvite.

Cunoscând lungimea zidului n, numărul de zile m şi porţiunile compacte pe care le zugrăveşte în fiecare zi, determinaţi suprafaţa totală a zidului care mai trebuie zugrăvită.

Lot Juniori, Valcea, 2015

#1234 easydel

Victor are la dispoziție multe cuburi din lemn, toate de aceeași dimensiune, fiecare fiind colorat cu una din culorile 0, 1, 2, …, 9. El a inventat un joc sub forma unui algoritm:

  • Pasul 0 – Se inițializează variabila X cu zero.
  • Pasul 1 – Se aleg la întâmplare un număr de cuburi și se formează cu ele un șir. Cuburile din șir sunt lipite unul de altul.
  • Pasul 2 – Dacă toate cuburile din șir au aceeași culoare, atunci se afișează valoarea variabilei X și jocul se oprește. În caz contrar se trece la pasul 3.
  • Pasul 3 – Se alege o culoare C și apoi toate cuburile de culoarea C se elimină din șir. Locurile cuburilor eliminate rămân temporar libere.
  • Pasul 4 – Orice cub din șir va fi deplasat spre stânga lui, cât timp pozițiile vecine sunt libere. Se mărește X cu 1 la fiecare deplasare cu o poziție. Operațiile de deplasare se încheie când nu se mai pot efectua mutări spre stânga. Apoi se revine la pasul 2.

Se consideră un șir cu cel puțin două elemente reprezentând culorile cuburilor din șir. Se cere să se calculeze valoarea maximă pe care o poate avea X.

Lot Juniori, Valcea, 2015

#1235 Nessie

Aţi auzit despre Nessie? Este un pleziozaur misterios care trăieşte în adâncurile lacului Loch Ness din munţii Scoţiei. Cu mulţi ani în urmă el a fost zărit pentru prima oară la suprafaţa lacului, iar de atunci, spre desfătarea turiştilor, el îşi face apariţia în mod periodic.

Nessie ştie de la managerii Loch Ness care este programul de vizitare a lacului pentru un interval de N zile. Mai exact, el cunoaşte datele primei și ultimei zile de şedere în preajma lacului pentru fiecare turist.

Contractul pe care Nessie l-a semnat cu managerii prevede faptul că fiecare dintre turişti trebuie să aibă posibilitatea să-l zărească, însă doar de departe şi doar o singură dată, deoarece Nessie intenţionează să rămână în continuare misterios. Pot exista zile fără turişti şi în aceste zile Nessie profită de fiecare dată ca să iasă la suprafaţa lacului.

Cunoscând prima şi ultima zi de şedere pentru fiecare turist, şi numărul total de zile prevăzute în contract, determinaţi numărul maxim de ieşiri la suprafaţa lacului, pe care Nessie le poate face, astfel încât fiecare turist să-l zărească o singură dată.

Lot Juniori, Valcea, 2015

#1236 Pastile

Manole este extrem de răcit. Din această cauză a mers la medicul de familie care l-a sfătuit urmeze un tratament cu N pastile, din care trebuie să ia în fiecare zi câte o jumătate. A cumpărat de la farmacie o cutie în care se aflau exact N pastile, fiecare dintre ele având pe suprafață o dungă care marchează jumătatea ei.

Manole începe să își ia tratamentul și constată că poate proceda doar astfel:

  • scoate din cutie o pastilă întreagă din care folosește, în ziua respectivă, doar jumătate din ea, iar jumătatea rămasă o pune înapoi în cutie;
  • scoate din cutie o jumătate de pastilă, rămasă din una din zilele anterioare, pe care o folosește în ziua respectivă.

Scrieți un program care determină numărul de posibilități în care poate lua toate cele N pastile, procedând după procedeul descris mai sus.

Lot Juniori, Valcea, 2015

  • Fișiere
  • Silviu Candale
  • Daniela Lica
  • Clasa 12
  • concurs

#1247 Torturi

Adela lucrează la un laborator de cofetărie. Ea trebuie să pregătească două torturi de nuntă şi în acest scop va folosi n blaturi de tort. Blaturile de tort au formă cilindrică, având toate aceeaşi înălţime, eventual diametre diferite. Blaturile ies pe rând din cuptor. Când un blat iese din cuptor, Adela îl va aşeza deasupra uneia dintre cele două stive de blaturi aflate pe cele două tăvi pe care se pregătesc torturile.

Blaturile diferă între ele prin rezistenţa la presiune. Rezistenţa unui blat creşte odată cu creşterea diametrului. Astfel, un blat va suporta deasupra sa oricâte alte blaturi cu diametre mai mici sau egale cu diametrul său. Pe de altă parte, dacă se aşează un blat de diametru d, deasupra altuia de diametru mai mic, atunci atât blatul aflat imediat dedesubt, cât şi toate blaturile din tort cu diametrul mai mic decât d vor colapsa. Blatul de diametru d se va stabiliza pe un blat cu diametru mai mare sau egal cu al său sau după caz, pe fundul tăvii.

Adela trebuie să folosească toate cele n blaturi pentru pregătirea celor două torturi, şi să le aşeze pe cele două tăvi, în ordinea în care blaturile ies din cuptor. Dorinţa Adelei este ca numărul total de blaturi care nu vor colapsa în cele două torturi să fie maximă.

Cunoscând diametrele blaturilor şi ordinea în care acestea ies din cuptor, să se determine numărul maxim de blaturi care nu vor colapsa.

Lot Juniori Severin, 2015

Specificul insulelor din arhipelagul Maldive (Oceanul Indian) este faptul că toate cele N insule ale sale au forma unui triunghi. Localizarea acestor insule folosește coordonatele carteziene ale celor trei vârfuri.

Administrația acestor insule dorește să instaleze un dispozitiv de emisie-recepţie pe apă sau pe o insulă, într-un punct având coordonate numere naturale (xD, yD), ce transmite semnale numai pe direcții orizontale și verticale concomitent, cu următoarele proprietăţi:

  • notând cu NRO numărul de insule la care ajunge semnalul pe orizontală și cu NRV numărul de insule la care ajunge semnalul pe verticală, suma NRO + NRV trebuie să fie maximă;
  • dacă există mai multe puncte cu proprietatea anterioară, atunci se va alege punctul cel mai mic în ordine lexicografică.

Să se scrie un program care cunoscând numărul de insule N şi coordonatele carteziene ale vârfurilor acestora, determină coordonatele xD și yD cu proprietățile din enunţ.

Lot Juniori Severin, 2015

#1245 Birot

Emil are un mouse special, cu două rotițe de scroll. Pe fiecare rotiță de scroll el poate fixa câte o bandă circulară de cauciuc pe care sunt printate în format 3D caracterele utilizate frecvent pentru editare.

Apăsând vertical rotița de scroll în punctul ei cel mai înalt, caracterul aflat în punctul de apăsare va fi generat de către mouse. Astfel se pot edita diferite texte doar cu ajutorul mouse-ului. Ordinea în care sunt printate caracterele influențează viteza de tastare și energia consumată în procesul de editare a textelor. Efortul de trecere de la un caracter la următorul sau la anteriorul consumă o cantitate de energie egală cu o unitate. Apăsarea pe rotiță nu consumă energie. Emil vrea să afle care este cantitatea minimă de energie pe care trebuie să o consume pentru construirea unui text dat.

Lot Juniori Severin, 2015

#1244 Trapeze

Se consideră două semidrepte orizontale paralele notate a şi b. Fiecare dintre ele are capătul din stânga situat pe axa Oy. Distanţa dintre ele este de două unităţi.

Pe semidreapta a se află n1 puncte iar pe semidreapta b se află n2 puncte. Pentru fiecare dintre aceste puncte se cunoaşte distanţa faţă de axa Oy.

Să se determine :

  1. Câte trapeze dreptunghice, cu una dintre baze pe semidreapta a, cu cealaltă bază pe semidreapta b şi cu vârfurile în cele două mulțimi de puncte date se pot forma?
  2. Care este cea mai mare arie a unuia dintre aceste trapeze?

Lot Juniori Severin, 2015

#1243 Insula

Pe țărmul insulei Mauritius sunt N localități, numerotate de la 1 la N, considerate puncte de maximă atracție pentru turiști. Acestea sunt conectate printr-o rețea feroviară cu linie ferată dublă ce leagă localitățile 1 de 2, 2 de 3, … , N-1 de N și N de 1, putându-se realiza astfel două circuite. Primul circuit presupune vizitarea localităţilor 1 2 .., N 1, în această ordine, iar cel de-al doilea, vizitarea localităţilor 1 N N – 1 … 2 1. În fiecare localitate există agenții ale tuturor celor M operatori de turism, numerotați de la 1 la M.

Un tichet de călătorie se poate achiziționa doar din localitatea în care se găsește călătorul și permite deplasarea din acea localitate până la următoarea localitate a circuitului. Pentru fidelizarea clienților, operatorii de turism utilizează următoarea regulă pentru prețurile tichetelor: dacă un călător a ajuns într-o gară, cu un tichet cumpărat de la un anumit operator de turism și își continuă călătoria către următoarea destinație cu un tichet pe care-l va cumpăra de la un alt operator de turism, atunci noul tichet își va dubla prețul.

Ștefan se află în concediu pe insulă în localitatea 1 și tocmai a câștigat un premiu oferit de operatorul de turism numerotat cu 1, pentru o excursie cu N tichete de călătorie pe insula Mauritius.

El pornește din localitatea în care se află și apoi parcurge cu trenul întregul circuit, astfel încât cu ultimul tichet cumpărat să se întoarcă în localitatea 1, de unde a plecat. Același operator de turism îi oferă contra cost, primul tichet de călătorie. Ștefan va studia toate ofertele și dacă e cazul poate refuza inclusiv acest prim tichet pentru a-l achiziționa de un alt operator de turism, chiar dacă i se va dubla prețul (fiindcă a schimbat operatorul).

Cunoscând prețul tichetelor de călătorie, stabilite de fiecare operator de turism, determinați suma minimă cu care Ștefan poate achiziționa cele N tichete necesare călătoriei sale.

Lot Juniori Severin, 2015

#1242 Ecluze

Ecluza este o construcție hidrotehnică amenajată pe traseul unei căi navigabile, care asigură trecerea navelor între două suprafețe de apă cu niveluri diferite. O ecluză se compune dintr-un bazin numit “sas” sau “camera ecluzei”, prevăzut la ambele capete cu porţi etanşe şi dintr-o instalaţie puternică de pompare pentru umplerea sau golirea sasului până la nivelul dorit.

Specialiștii români au construit pe cursul navigabil al Dunării o succesiune de N ecluze numerotate de la 1 la N, care asigură condiții optime de navigare în sezoanele secetoase. Astfel, dacă o navă se află la un moment dat în ecluza i și nivelul apei din ecluză diferă de nivelul apei din ecluza i+1, pentru a-și continua navigarea în condiții optime se face modificarea nivelului apei fie din ecluza i la nivelul ecluzei i+1, fie se face modificarea nivelului apei din ecluza i+1 la nivelul ecluzei i.

De exemplu, dacă pentru un sector navigabil există 9 ecluze pentru care nivelul apei este următorul:

ecluză: 1 2 3 4 5 6 7 8 9
nivel apă: 2 2 4 1 2 2 1 2 2

numărul minim de ecluze la care se impun modificări ale nivelului apei este 3, după cum urmează:

  • nivelul din ecluza 3 este coborât până la nivelul 2
  • ecluza 4 este umplută până la nivelul 2
  • ecluza 7 este umplută până la nivelul 2

Cunoscând nivelul apei din cele N ecluze, să se determine numărul minim de modificări ale nivelului apei din ecluze care să permită o trecere prin toate ecluzele.

Lot Juniori Severin, 2015

Se construieşte un şir de numere naturale care respectă restricţiile:

  • primul număr din şir este 9;
  • numerele se generează în ordine strict crescătoare;
  • şirul conţine toate numerele formate doar cu cifrele 7, 8 şi 9 cu proprietatea că numărul cifrelor 9 este mai mare sau egal decât numărul cifrelor 8 şi numărul cifrelor 8 este mai mare sau egal decât numărul cifrelor 7.
    Primii 14 termeni ai şirului, în ordine, sunt: 9, 89, 98, 99, 789, 798, 879, 897, 899, 978, 987, 989, 998, 999.

Pornind de la aceste numere, Liv a inventat un joc interactiv: N iepuraşi sunt aşezaţi în şir, fiecare având câte un cartonaş. Fiecare cartonaş are două feţe, o faţă albă pe care este inscripţionat un număr din acest şir şi o faţă gri, pe care este inscripţionată poziţia acelui număr în şir, poziţii numerotate în ordine, începând cu valoarea 1.

Exemple. Cartonaşul care are pe faţa gri inscripţionat numărul 1 va avea pe faţa albă inscripţionat numărul 9, iar cartonaşul care are pe faţa gri inscripţionat numărul 5 va avea pe faţa albă inscripţionat numărul 789.

Iepuraşii sunt aşezaţi într-o ordine oarecare şi ţin cartonaşele astfel încât să se vadă faţa gri. Jocul constă în a rearanja iepuraşii de la stânga la dreapta, descrescător după numerele inscripţionate pe feţele gri, având la dispoziţie doar operaţia TAP pe un iepuraş. Când se aplică operaţia TAP unui iepuraş atunci secvenţa de iepuraşi, începând de la cel pe care s-a făcut TAP şi până la sfârşitul şirului (spre dreapta), este oglindită (ca în imaginea de mai sus). După oglindire, toţi iepuraşii din acea secvenţă ţin cartonaşele astfel încât să se vadă faţa albă. Se doreşte aplicarea unui număr cât mai mic de operaţii TAP pentru rearanjarea iepuraşilor.

Scrieţi un program care să citească numerele naturale N (reprezentând numărul de iepuraşi) şi a1, a2,…, aN (reprezentând, în ordine, numerele inscripţionate pe feţele gri) și care să determine:

a) Numărul minim de operaţii TAP necesare rearanjării iepuraşilor;
b) Cel mai mic număr aflat pe o faţă albă care nu se vede, în cazul în care au rămas cartonaşe neîntoarse. Dacă toate cartonaşele au fost întoarse (la toate fiind vizibilă faţa albă) se va afişa cel mai mare număr aflat pe o faţă albă a unui cartonaş.

ONI GIM 2014, Clasa a V-a

#1209 TDrept

Se consideră N puncte de coordonate întregi în sistemul de coordonate cartezian.

Scrieţi un program care determină numărul de triunghiuri dreptunghice având vârfurile plasate în 3 dintre punctele date şi catetele respectiv paralele cu axele de coordonate.

ONI GIM 2014, Clasa a VIII-a

Se consideră algoritmul:

citeşte  k , n;
s = 0;
for (i1 = 1 ; i1 ≤ k ; i1++)
  for (i2 = 1 ; i2 ≤ i1 ; i2++)
    for (i3 = 1 ; i3 ≤ i2 ; i3++)
      ........................................
        for (in = 1 ; in ≤ in-1 ; in++)
          s = s + in;
scrie s;
stop.

Să se scrie un program care implementează algoritmul de mai sus.

Lot Juniori, Resita, 2012

Fie N un număr natural format din cifre nenule.

Să se determine suma tuturor numerelor distincte ce se pot forma cu toate cifrele numărului N.

Lot Juniori, Sovata, 2014

Se consideră două numere naturale impare p şi q şi A={1,2,3,4,5,. . .,p*q} mulţimea tuturor numerelor naturale cuprinse între 1 şi p*q.

Să se scrie un program care determină p mulţimi, notate A1, A2,…, Ap cu proprietăţile:

  • Numărul de elemente ale fiecărei mulţimi Ai, 1 ≤ i ≤ p, este egal cu q;
  • Ai ∩ Aj = ∅ , 1≤i<j≤p;
  • A1 ∪ A2 ∪ ... ∪ Ap = A;
  • Sumele elementelor fiecărei mulţimi Ai, 1≤i≤p, sunt egale.

Lot Juniori, Deva, 2013

Triunghiul lui Pascal este un aranjament geometric de numere ce poartă numele celebrului matematician francez Blaise Pascal (19 iunie 1623 – 19 august 1662), deoarece el a fost prima persoană care a descoperit importanţa tuturor modelelor din componenţa acestuia.

Triunghiul începe cu numărul 1. Acest rând este considerat rândul 0 al triunghiului. Restul numerelor din acest triunghi se formează ca suma celor două numere de deasupra (considerând că toate numerele din afara triunghiului sunt întotdeauna zero). Prin urmare, rândul 1 va fi format din 1 = 0 + 1, 1 = 1 + 0, iar rândul 2 va fi format din 1 = 0 + 1, 2 = 1 + 1, 1 = 1 + 0.

Fie n și p două numere naturale nenule cu proprietățile:

  • p este număr prim;
  • n+1 este o putere naturală a lui p;

Notăm cu M(p) numărul de multipli de p din primele n+1 rânduri ale triunghiului lui Pascal.

Să se scrie un program care citeşte numerele naturale n şi p și determină numărul M(p).

Lot Juniori, Baia Mare, 2013

Se consideră un număr natural N și fie A mulţimea tuturor numerelor naturale cuprinse între 1 şi N2.

Numim partiție a mulțimii A un set de submulțimi A1, A2, ..., AN cu proprietățile:

  • Reuniunea celor N submulțimi are ca rezultat mulțimea A;
  • Intersecția oricăror două submulțimi distincte este mulțimea vidă;
  • Numărul de elemente ale fiecărei submulțimi Ai, 1 ≤ i ≤ N, este N;
  • Elementele fiecărei submulţimi sunt aşezate în ordine crescătoare;

Să se scrie un program care determină o partiție a mulțimii A cu proprietăţile:

  • Sumele elementelor fiecărei submulţimi Ai, 1 ≤ i ≤ N, sunt egale;
  • Pentru oricare submulțime Ai, 1 ≤ i ≤ N, diferența oricăror două elemente succesive ale sale este diferită de N+1 și de N-1;

Lot Juniori, Vaslui, 2014

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.

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.

OJI 2014, Clasa a IX-a

#144 copii

În Bistriţa sunt N copii, fiecare dintre ei având un număr preferat Xi . Copii se aşează pe un rând, cu poziţiile numerotate de la 1 la N. După ce copii s-au aşezat, profesoara de educaţie fizică le cere să execute M mişcări de tipul (a, b), cu semnificaţia că îşi vor schimba ordinea copii care se află între poziţiile a şi b, inclusiv.

Să se răspundă la Q întrebări de tipul p, cu semnificaţia: care este numărul preferat al copilului, care se află pe poziţia p, după executarea mişcărilor cerute de profesoara de educaţie fizică.

Grigore Moisil 2013

#1122 Babilon

Babilonienii au dezvoltat un sistem pozițional de scriere a numerelor, în care orice număr natural se poate reprezenta utilizând semnele (unu), (zece) şi spaţii.

Valorile k din {2, 3, … , 9} se obțin scriind semnul de k ori (scrierea babiloniană a lui 3 este ).

Numerele 11, 12, … , 59 se obțin ca succesiuni de semne urmate de semne (43 se reprezintă ca
).

Sistemul folosește gruparea unităților câte șaizeci. Astfel, pentru a scrie umărul șaizeci se folosește același semn ca pentru unu, dar valoarea sa este dată de poziția în care se găsește semnul !/resurse/9dc152/p-1100/babilon1.png!.

Babilonienii nu foloseau cifra 0. Pentru poziţionarea corectă a semnelor se utiliza spațiu (60 se reprezintă ca , 3600 se reprezintă ca etc.).

Se codifică scrierea babiloniană a unui număr utilizând cifra 1 în locul semnului , cifra 2 în locul semnului și cifra 3 în loc de spațiu.

Dându-se un număr natural n și un șir de n cifre din mulțimea {1, 2, 3}, reprezentând codificarea scrierii babiloniene a unui număr natural, să se determine:
a) numărul maxim de cifre 1 aflate pe poziții consecutive în codificarea scrierii babiloniene date;
b) numărul natural din sistemul zecimal corespunzător scrierii babiloniene date.

ONI GIM 2014, Clasa a V-a

#1121 p2048

Ada și Ben sunt pasionați de jocurile pe calculator și tocmai au descoperit cea mai recentă versiune a jocului 2048.

Regulile jocului sunt foarte simple:

  • se pornește de la un șir de N piese pe care sunt înscrise numere din mulțimea {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
  • piesele sunt așezate în locații numerotate consecutiv cu numerele 1,2,…, N;
  • la fiecare pas, poate avea loc o MUTARE la STÂNGA sau o MUTARE la DREAPTA;
  • pentru fiecare joc este stabilit un număr maxim de mutări M;
  • dacă are loc o MUTARE la DREAPTA, atunci:
    • piesele pot fuziona la dreapta, începând cu penultima piesă din şir: dacă o piesă se află pe o poziție i și are înscrisă valoarea k, iar pe poziția i+1 se află o piesă cu aceeași valoare k, atunci aceste piese vor “fuziona”, pe poziția i+1 se va obține o piesă cu valoarea 2•k, iar pe poziția i rămâne o locație liberă;
    • după efectuarea fuzionărilor, piesele se aliniază la dreapta, astfel încât ultima piesă să se afle pe poziția n;
  • dacă are loc o MUTARE la STÂNGA, atunci:
    • piesele pot fuziona la stânga, începând cu a doua piesă din șir: dacă o piesă se află pe o poziție i și are înscrisă valoarea k, iar pe poziția i-1 se află o piesă cu aceeași valoare k , atunci aceste piese vor “fuziona”, pe poziția i-1 se va obține o piesă cu valoarea 2•k, iar pe poziția i rămâne o locație liberă;
    • după efectuarea fuzionărilor, piesele se aliniază la stânga, astfel încât prima piesă să se afle pe poziția 1;
  • jocul se încheie atunci când se ajunge în una dintre următoarele situații:
    • pe cel puțin una dintre piese se află înscrisă valoarea 2048;
    • valorile înscrise nu se mai pot modifica prin mutarea pieselor;
    • s-au efectuat toate cele M mutări.

Scrieţi un program care să citească numerele naturale N (numărul inițial de piese) și M (numărul maxim de mutări), un șir de N numere reprezentând, în ordine, numerele înscrise pe cele N piese și cel mult M caractere din mulțimea {S, D} ce reprezintă mutările fixate de către Ada și Ben, și care determină:

a) numărul X de mutări efectuate până la încheierea jocului;
b) numărul maxim Y înscris pe una dintre piese la încheierea jocului;
c) numărul maxim Z de fuzionări efectuate la o mutare.

ONI GIM 2014, Clasa a V-a

#1120 xcmmdc

Se dă o matrice cu m linii şi n coloane, cu elementele numere naturale nenule şi un număr natural nenul fixat k.

Pentru matricea dată şi numărul k dat să se răspundă la q întrebări de forma: “Câte submatrice pătratice de latură L cu cel mai mare divizor comun al elementelor egal cu k există în matricea dată?”

ONI 2014, Clasele XI-XII

Se dă o matrice cu m linii şi n coloane, fiecare linie reprezentând o permutare. Se ştie că liniile de la 2 la m sunt permutări circulare ale primei linii. Unei linii x (1 ≤ x ≤ m) i se pot aplica următoarele operaţii:

  • o permutare circulară la stânga: elementul de pe poziţia i (1 < i ≤ n) se mută pe poziţia i-1, mai puţin primul primul element, care devine ultimul;
  • o permutare circulară la dreapta: elementul de pe pozitia i (1 ≤ i < n) se mută pe poziţia i+1, mai puţin ultimul element care devine primul.

Scopul este să permutăm circular liniile, la stânga sau la dreapta, astfel încât în final toate liniile să fie egale, folosind un număr minim de operaţii.

Dându-se o matrice cu proprietatea din enunţ se cere să se determine numărul minim de operaţii necesare pentru a ajunge la o matrice în care toate liniile sunt egale.

ONI 2014, Clasele XI-XII

Un graf conex cu N noduri și M muchii poate fi privit ca o clepsidră cu centrul în nodul X, 1 ≤ X ≤ N, dacă putem împărți toate nodurile, mai puțin nodul X, în două submulțimi nevide astfel încât orice drum de la un nod dintr-o mulțime la un nod din cealaltă mulțime trece prin nodul X. Voi trebuie să determinați numărul de moduri distincte în care putem privi graful ca o clepsidră pentru fiecare din cele N noduri alese drept centru, modulo 666013. Două moduri se consideră distincte dacă cele două submulțimi aferente sunt diferite. Ordinea submulțimilor într-un mod este relevantă, dar ordinea nodurilor în cadrul unei mulțimi nu este. Spre exemplu, soluțiile ({1,2,3}, {4,5}) şi ({4,5}, {1,2,3}) sunt distincte, dar soluţiile ({4,5}, {1,2,3}) şi ({4,5}, {1,3,2}) nu sunt distincte.

ONI 2014, Clasele XI-XII

#1117 Volum

K.L. 2.0 și-a dorit o piscină pe un grid A cu N linii și M coloane. Cum K.L. 2.0 nu a fost foarte inspirat, el a uitat să își niveleze terenul înainte de a construi piscina, astfel încât fiecare celulă de coordonate (i, j) a gridului are o înalțime Ai,j (1 ≤ i ≤ N și 1 ≤ j ≤ M). La un moment dat începe o ploaie puternică, care umple piscina cu apă. După terminarea ploii, K.L. 2.0 se întreabă câtă apă are în piscină.

Dintr-o celulă apa se varsă în celulele vecine cu care are o latură comună şi care au înălţimea strict mai mică decât celula curentă. Apa de pe marginea piscinei se scurge în exterior.

Pentru N, M și gridul A date, să se determine volumul de apă care a rămas în piscină.

ONI 2014, Clasele XI-XII

#1116 karb

În perioada Campionatului Mondial din Brazilia se preconizează o creştere a traficului de cafea. Se ştie că sunt N orase, conectate prin N-1 străzi bidirecţionale, astfel încât se poate ajunge din orice oraş în altul. În prezent există K carteluri de cafea aflate în oraşe distincte, care își exercita influența în propriul oraș. Se ştie că fiecare din aceste carteluri doreşte să-şi extindă influenţa în oraşele vecine. Astfel, la un moment de timp, un cartel poate să-şi extindă influenţa într-un oraş vecin doar dacă acesta nu se află sub influenţa altui cartel. O dată ce un cartel îşi extinde influenta asupra unui nou oraş, cartelul îşi poate extinde influenţa şi în oraşele vecine acestuia. Se ştie că până la începerea campionatului mondial, fiecare oraş va fi sub influenţa unui cartel.

ABIN (Agência Brasileira de Inteligência) doreşte să afle în câte moduri poate fi dominată ţara de influenţele celor K carteluri la data începerii campionatului mondial, modulo 666013.

Cunoscând numărul de orașe N, modul în care acestea sunt conectate, numărul de carteluri inițiale K și cele K orașe în care se află cartelurile, să se determine numărul de moduri în care ţara poate fi împărţită între cartelurile de cafea, modulo 666013.

ONI 2014, Clasele XI-XII

Un vârcolac bântuie ulițele satului Bosston, semănând panică printre săteni. Satul Bosston este compus din 2*N săteni, fiecare dintre aceștia fiind rudă cu exact un vârcolac. Vârcolacii sunt codificați cu numere naturale. Pentru a afla care este vârcolacul care le cauzează probleme, aceștia s-au dus la vraciul local. Acesta a spus că, dacă există un vârcolac V astfel încât oricum s-ar împărți cei 2*N săteni în două grupuri de N săteni, există cel puțin un sătean în primul grup și cel puțin un sătean în al doilea care să fie rude cu V, atunci vârcolacul V sigur este cel care bântuie satul. Dacă nu există un astfel de vârcolac, atunci sătenii nu își pot da seama cine le bântuie satul.

Cunoscând N și indicii vârcolacilor cu care se înrudesc fiecare dintre cei 2*N săteni, să se determine vârcolacul care bântuie satul, în cazul în care acesta există.

ONI 2014, Clasele XI-XII

#1114 Stiva1

Olivius d’Info a primit de ziua lui o stivă şi s-a bucurat foarte tare. S-a tot gândit ce să facă cu ea şi a inventat un joc de logică pentru colegii lui de clasă.

În prima fază el a scris mai multe bileţele, conţinând fiecare câte o permutare a primelor n numere naturale nenule: 1, 2, 3, … , n. Bileţelele scrise conţin permutări pentru diferite valori ale lui n.

A clasificat aceste permutări în permutări stivuite şi permutări nestivuite.

O permutare este stivuită dacă se poate obţine pe parcursul introducerii în stivă a numerelor 1, 2, 3, ...,n în această ordine, prin extragerea elementelor, în ordinea indicată în permutare.

O permutare nestivuită este o permutare care NU se poate obţine prin procedeul de mai sus.

Respectând procedeul lui Olivius, pentru n=4, permutarea stivuită (2,1,3,4) se obţine astfel:

Succesiunile (3,1,2,4) şi (4,2,1,3) sunt permutări nestivuite.

În faza a doua, unele bileţele au fost scurtate din stânga şi/sau din dreapta. Astfel, din permutarea stivuită (2,1,3,4) se pot obţine succesiuni de lungime mai mică: (1,3,4), (2,1,3), (1,3), (3) etc.

Orice succesiune care aparţine unei permutări stivuite, poate aparţine şi unei permutări nestivuite. De exemplu, succesiunea (2,1,3) aparţine atât permutării stivuite (2,1,3,4), cât şi permutării nestivuite (4,2,1,3).

Dându-se mai multe succesiuni de numere naturale distincte, determinaţi, pentru fiecare dintre acestea, dacă aparţin cel puţin unei permutări stivuite.

ONI 2014, Clasa a X-a

Suleiman I s-a confruntat în anul 1548 cu mari probleme interne. În acel an, el a primit vestea că într-una din regiunile Imperiului se pregăteşte o răscoală. Harta Imperiului este realizată sub forma unui tablou bidimensional cu n linii şi m coloane, iar fiecare element al tabloului corespunde unei regiuni a Imperiului. În fiecare regiune erau deja cantonaţi soldaţi, dar pentru a preîntâmpina răscoala sultanul decide ca toţi cei k soldaţi din Garda Imperială să fie trimişi în regiuni, întărindu-le pe cele păzite de mai puţini soldaţi. Distribuirea lor respectă următoarele reguli:

  • Dacă există o singură regiune cu număr de soldaţi mai mic decât al tuturor celorlalte regiuni, trimite un soldat în această regiune.
  • Dacă există mai multe regiuni cu acelaşi număr minim de soldaţi, trimite un soldat în regiunea care iniţial avea un număr mai mic de soldaţi. Dacă mai multe regiuni aveau acelaşi număr iniţial de soldaţi, se trimite un soldat în regiunea cu indicele liniei mai mic, iar dacă regiunile sunt pe aceeaşi linie, în regiunea cu indicele coloanei mai mic.

Suleiman continuă distribuirea soldaţilor din garda imperială în regiuni conform celor precizate anterior, până la epuizarea soldaţilor din Garda Imperială.

Cunoscându-se n, m şi k reprezentând numărul de linii, numărul de coloane, respectiv numărul de soldaţi din Garda Imperială, precum şi numărul de soldaţi existent deja în regiunile Imperiului, să se determine:
a) numărul de regiuni din Imperiu în care vor fi trimişi soldaţii din Garda Imperială, respectiv numărul minim de soldaţi care se vor găsi într-o regiune, după trimiterea soldaţilor din Garda Imperială;
b) distanța maximă între două regiuni în care au fost trimiși soldaţi ai Gărzii Imperiale. Distanța între o regiune A și o regiune B se calculează folosind formula |LA- LB| + |CA- CB|, unde (LA ,CA) reprezintă coordonatele regiunii A, precizate prin numărul liniei și coloanei, respectiv (LB ,CB) reprezintă coordonatele regiunii B, precizate prin numărul liniei și coloanei.

ONI 2014, Clasa a X-a

#1112 Puteri4

Nu e un secret pentru nimeni faptul că Mireluş se antrenează în timpul liber cu probleme de algoritmică. De curând a aflat că un număr natural N, pentru care există două numere naturale nenule A şi B (B>1) astfel încât N = A^B, se numeşte putere. Mireluş şi-a propus să determine numărul de puteri din intervalul [X, Y], unde X şi Y sunt numere naturale nenule.

Cum probabil v-aţi imaginat deja, Mireluş nu a reuşit să rezolve această problemă şi a decis să ceară ajutorul Olimpiei D’Info. Pentru a fi sigur că nici ea nu greşeşte, i-a dat un set de intervale şi i-a cerut să determine pentru fiecare interval numărul de puteri corespunzător.

Dându-se numărul de intervale T şi pentru fiecare din cele T intervale cele două extremităţi, determinaţi numărul de puteri corespunzător fiecărui interval dat de Mireluş Olimpiei.

ONI 2014, Clasa a X-a

#1111 Zimeria

Olimpia D’Info a găsit o placă gravată ce conţine mai multe cuvinte scrise cu semne grafice necunoscute, fiecare cuvânt fiind format din exact 5 semne grafice. Studiind cu atenție cuvintele, a dedus că în scrierea acestora sunt utilizate 12 semne grafice distincte şi a asociat câte o literă mică din alfabetul englez fiecărui semn. După asociere, a stabilit pentru fiecare semn o complexitate, scriind literele în ordinea crescătoare a complexităților pe care le-a stabilit anterior. Olimpia consideră că această ”complexitate” este cel mai potrivit criteriu de ordonare lexicografică.

Cunoscând ordinea semnelor și cuvintele de pe placă determinaţi:
a) Numărul de cuvinte distincte existente pe placă.
b) Şirul de cuvinte ordonat lexicografic, conform criteriului formulat de Olimpia.

ONI 2014, Clasa a X-a

#1110 Spion1

Spionul 008 vrea să găsească o locație secretă în junglă, având asupra lui un dispozitiv de localizare. Iniţial spionul se află la intrarea în junglă pe nivelul 1 şi cu fiecare pas, el avansează de la nivelul i la nivelul i+1, ajungând la locaţia secretă, aflată pe ultimul nivel, în poziţia u faţă de marginea stângă a nivelului curent. Pentru a ajunge în locaţia secretă, el poate să se deplaseze cu o poziţie spre Sud-Est (codificat cu caracterul E) sau spre Sud-Vest (codificat cu caracterul V), trecând de pe nivelul i pe nivelul i+1 cu viteză constantă. Numărul de poziţii de pe un nivel creşte cu unu faţă de nivelul anterior, conform imaginii alăturate. Numim traseu o succesiune formată din caracterele E sau V, corespunzătoare deplasării spionului de pe nivelul 1 la locaţia secretă. Pentru exemplul din figura alăturată succesiunea de caractere VEEVE reprezintă un traseu ce corespunde locaţiei secrete din poziţia 4 a nivelului 6.

Cunoscând succesiunea de caractere corespunzătoare unui traseu, determinaţi:
a) poziţia locației secrete de pe ultimul nivel;
b) numărul de trasee distincte pe care le poate urma spionul plecând din poziţia inițială pentru a ajunge în locaţia secretă corespunzătoare traseului dat. Două trasee se consideră distincte dacă diferă prin cel puţin o poziţie.

ONI 2014, Clasa a X-a

#1109 Joc5

Costel are o mare pasiune pentru rezolvarea cubului Rubik, atât de mare încât a început să facă cercetări și calcule diverse pornind de la acest joc. Ultima lui idee, inspirată de cubul Rubik, folosește un cub de latură 2 unități, compus din 8 cuburi cu latura de o unitate (cub unitate), având fețele exterioare colorate. Fiecare cub unitate are 3 fețe exterioare şi fiecare dintre acestea este colorată cu una din cele 10 culori disponibile, codificate prin cifrele de la 0 la 9.

Figura 1 Figura 2

Identificarea cuburilor unitate se face conform specificaţiilor din Figura 1. Cubul care nu este vizibil în Figura 1 are coordonatele (1, 1, 2). Cubul lui Costel permite efectuarea următoarelor tipuri de mutări, asemănătoare cu cele din cubul Rubik:

M1: Paralelipipedul 1 conține cuburile unitate de coordonate: (1, 1, 1); (1, 2, 1); (2, 1, 1); (2, 2, 1). Acesta este un disc așezat orizontal și poate fi rotit cu 90 de grade către dreapta, în sensul acelor de ceasornic.
M2: Paralelipipedul 2 conține cuburile unitate de coordonate: (1, 1, 2); (1, 2, 2); (2, 1, 2); (2, 2, 2). Acesta este un disc așezat orizontal și poate fi rotit cu 90 de grade către dreapta, în sens invers acelor de ceasornic.
M3: Paralelipipedul 3 conține cuburile unitate de coordonate: (1, 1, 1); (2, 1, 1); (1, 1, 2); (2, 1, 2). Acesta este un disc așezat vertical și poate fi rotit cu 90 de grade către planul îndepărtat, în sens invers acelor de ceasornic.
M4: Paralelipipedul 4 conține cuburile unitate de coordonate: (1, 2, 1); (2, 2, 1); (1, 2, 2); (2, 2, 2). Acesta este un disc așezat vertical și poate fi rotit cu 90 de grade către planul îndepărtat, în sensul acelor de ceasornic.

Prin configurație se înțelege memorarea culorii fiecărei fețe exterioare a celor 8 cuburi unitate, deci culorile celor 24 de feţe exterioare. Aplicând o succesiune validă de mutări se obține o altă configurație.

Pentru ușurința memorării unei configurații, Costel utilizează desfășurarea în plan a celor 6 fețe ale cubului său după modelul din Figura 2, care ilustrează modul în care sunt dispuse fețele în desfăşurare. Fiecare faţă a cubului conţine patru feţe exterioare ale cuburilor unitate având, în ordine, coordonatele specificate în figură.

Fiind date o configuraţie iniţială şi o configuraţie finală ale jocului, determinați numărul minim de mutări prin care se poate ajunge de la configurația inițială la configurația finală şi succesiunea corespunzătoare de mutări prin care se poate obţine configuraţia finală.

ONI 2014, Clasa a X-a

#1108 Traseu

Într-un oraș există un hotel de formă cubică, cu N etaje, numerotate de la 1 la N. Suprafața fiecărui etaj K (1 ≤ K ≤ N) este pătratică și este împărțită în N x N camere identice alăturate, dispuse pe N linii și N coloane, fiecare cameră având drept etichetă un triplet de numere naturale (K L C) (K=etajul, L=linia, C=coloana, 1 ≤ L, C ≤ N), ca în imaginea alăturată.

Dintre cele N x N x N camere ale hotelului, una este specială deoarece în ea locuiește de mult timp un șoricel. Fiind isteț, el știe eticheta camerei în care se află precum și eticheta camerei în care bucătarul hotelului depozitează alimente.

Studiind hotelul, șoricelul a constatat că pe fiecare etaj, din orice cameră poate intra în toate camerele care au un perete comun cu aceasta (existând un mic orificiu pentru aerisire).

De asemenea, șoricelul a constatat că din fiecare cameră (situată la etajele 2, 3, …, sau N-1) poate intra în camera situată imediat deasupra ei și în camera situată imediat sub ea.

Fiind un șoricel binecrescut, el nu intră în nicio cameră ocupată de clienți ca să nu-i deranjeze. Hotelul având mulți clienți, șoricelul trebuie să-și găsească cel mai scurt traseu de la camera lui la camera cu alimente, traseu care să treacă printr-un număr minim de camere, toate neocupate.

Se cere să se determine:
a) numărul de camere prin care trece cel mai scurt traseu al șoricelului de la camera lui la camera cu alimente (inclusiv camera lui şi camera cu alimente);
b) etichetele camerelor prin care trece traseul determinat la punctul a).

ONI 2014, Clasa a IX-a

#1107 Reflex

La un concurs de robotică, în timpul prezentării, un roboţel cu corp cilindric cu diametrul de o unitate scapă de sub control şi se deplasează într-un ring de formă dreptunghiulară. Ringul este împărţit în N x M pătrate identice, cu latura de o unitate, aşezate pe N linii şi M coloane.

Robotul poate părăsi ringul numai pe la colţuri, acestea fiind numerotate de la 1 la 4, colţul cu numărul 1 fiind cel din stânga jos apoi restul fiind numerotate în sens trigonometric. Suprafaţa ringului este delimitată de exterior prin intermediul a patru pereţi despărţitori: doi pereţi “verticali” (aşezaţi de la colţul 1 la colţul 4, respectiv de la colţul 2 la colţul 3) şi doi pereţi “orizontali” (aşezaţi de la colţul 1 la colţul 2, respectiv de la colţul 3 la colţul 4), fără a bloca ieşirile, ca în desenul alăturat.

Robotul pătrunde în ring prin colţul cu numărul 1 sub un unghi de 45 grade şi cu o viteză de un pătrat/s. Ciocnirile cu pereţii sunt considerate perfect elastice (robotul nu-şi pierde din viteză) iar unghiul de incidenţă este egal cu cel de reflexie.

Se cere să se determine:

a) după câte secunde şi prin ce colţ al ringului va ieşi robotul;
b) de câte ori se ciocneşte robotul de pereţii orizontali şi verticali, rezultând o schimbare de direcţie, până la ieşirea din ring.

ONI 2014, Clasa a IX-a

Să se determine un șir strict crescător, cu lungimea N, format din numere naturale nenule, \( 1 ≤ a_1 < a_2 < a_3 < … < a_N ≤ [2 \cdot N \cdot \sqrt{N}] \), cu proprietatea că oricare trei termeni distincți ai șirului nu sunt în progresie aritmetică, adică pentru oricare numere naturale i, j şi k cu 1 ≤ i < j < k ≤ N, este îndeplinită condiţia: \( a_i + a_j \neq 2 \cdot a_j \). Prin [x] s-a notat partea întreagă a lui x.

De exemplu, pentru N = 5, cel mai mare termen al șirului va trebui să fie mai mic sau egal cu \( [2 \cdot 5 \cdot \sqrt{5} ] \), adică aN ≤ 22, deci o soluție este: 1, 2, 4, 5, 10.

ONI 2014, Clasa a IX-a

#1105 TG

Fie un număr natural N. Spunem că (a, b, c) este un triplet geometric limitat de N, dacă a, b și c sunt trei numere naturale astfel încât 1 ≤ a < b < c ≤ N și \( b = \sqrt {a \cdot c} \).

Să se determine numărul tripletelor geometrice limitate de numărul natural N.

ONI 2014, Clasa a IX-a

#1104 qvect

Se consideră N vectori cu elemente întregi, numerotați de la 1 la N, sortați crescător, fiecare vector având un număr precizat de elemente.

Să se răspundă la Q întrebări de tipul:
a) 1 i j, cu semnificaţia: care este minimul dintre modulele diferențelor oricăror două elemente, primul element aparținând vectorului numerotat cu i, iar cel de al doilea element aparținând vectorului numerotat cu j ?
b) 2 i j, cu semnificația: care este valoarea ce se găsește pe poziția mediană în vectorul obținut prin interclasarea vectorilor având numerele de ordine i,i+1,…,j (i<j).

ONI 2014, Clasa a IX-a

#1103 Harta

Pe baza unei imagini preluate din satelit, se realizează harta unei mici localități. Localitatea ocupă o suprafață dreptunghiulară, cu laturile orientate pe direcțiile Nord-Sud, respectiv Est-Vest. Studiind imaginea obținută de la satelit, cartografii au constatat că toate cele k clădiri au forma unor dreptunghiuri distincte. Imaginea poate fi reprezentată sub forma unui tablou cu n•m celule așezate pe n linii numerotate de la 1 la n și m coloane numerotate de la 1 la m.

Numim drum, un dreptunghi al tabloului care străbate întreaga localitate pe direcția Est-Vest și are un număr maxim de linii sau un dreptunghi care străbate întreaga localitate pe direcția Nord-Sud și are un număr maxim de coloane. Drumurile, evident, nu trebuie să treacă prin clădiri.

Cartografii sunt interesați ca pe această hartă să fie reprezentate la scară doar clădirile, nu și drumurile. De aceea, pentru realizarea hărții, lățimile drumurilor au fost reduse la o singură celulă

Tabloul care reprezintă imaginea localității se codifică astfel: 1 pentru o celulă ocupată de o clădire și 0 pentru o celulă neocupată.

Cunoscând n, m și k, precum și tabloul care codifică imaginea, se cere să se determine:

1. Numărul S de celule ocupate de către clădirea pătratică cu latura maximă și numărul de clădiri C alese dintre celelalte k – 1 clădiri, cu proprietatea că fiecare dintre ele “încape” în interiorul clădirii pătratice cu latură maximă, fără să se suprapună peste celulele marginale ale acesteia.
2. Tabloul care reprezintă harta, în urma prelucrării imaginii inițiale.

ONI 2014, Clasa a IX-a

Gigel este un pasionat al triunghiurilor. El colectează beţişoare de diferite lungimi şi le asamblează în diferite triunghiuri. Ieri, el avea 6 beţişoare de lungimi 5, 2, 7, 3, 12 şi 3. Din aceste bețișoare, Gigel a construit un triunghi de laturi 3, 3 şi 5, iar beţişoarele de lungimi 2, 7, 12 au rămas nefolosite pentru că aceste lungimi nu pot forma laturile unui triunghi.
Din acest motiv, Gigel s-a hotărât să facă o colecţie de beţişoare, dintre care oricum ar alege 3 elemente, acestea să nu poată forma laturile unui triunghi, proprietate pe care o vom numi în continuare proprietate anti-triunghi. Gigel, pornind de la setul iniţial de lungimi 2, 7, 12, s-a gândit la două metode de realizare a unei colecţii de 5 beţişoare cu proprietatea anti-triunghi, şi anume:
1.Păstrează cel mai scurt beţişor, cel de lungime 2, şi creează un set nou adăugând alte beţişoare de lungime mai mare sau egală cu cel iniţial. De exemplu, următoarele 5 lungimi sunt corecte: 2, 2, 12, 50, 30.
2.Păstreză toate beţişoarele, şi anume 2, 7,12, pe care le va completa cu alte beţişoare de diferite lungimi (mai scurte sau mai lungi), astfel ca proprietatea anti-triunghi să se păstreze. Următoarele 5 lungimi respectă proprietatea anti-triunghi: 2, 7, 12, 4, 1.

Cunoscând un şir de n numere naturale nenule a 1 ,a 2 ,…,a n având proprietatea
anti-triunghi, şi un număr k (k>n), se cere să construiţi un şir de k numere naturale având proprietatea anti-triunghi, în conformitate cu una dintre următoarele două restricţii:
Varianta 1. Cel mai mic element este identic cu cel mai mic element din şirul iniţial.
Varianta 2. Printre cele k elemente ale şirului construit se regăsesc toate elementele şirului iniţial.

OJI 2014, Clasa a X-a

#1028 Ferma

Un fermier deține o fermă de formă dreptunghiulară cu lungimea m metri și lățimea n metri. Respectând principiul rotației culturilor, fermierul și a realizat un plan pentru semănarea culturilor în noul an. Astfel ,el a desenat un dreptunghi pe care l-a împărțit în m * n celule, fiecare corespunzând unui metru pătrat, și a colorat în culori diferite zonele care corespund unor culturi diferite. O cultură poate fi semănată pe mai multe parcele. Două celule care au o latură comună aparțin aceleiași parcele dacă au aceeași culoare (sunt însămânțate cu aceeași cultură). Fermierul are posibilitatea să irige o sigură parcelă și dorește să aleagă parcela cu cea mai mare suprafață. Nefiind mulțumit de suprafața rezultată, s-a întrebat dacă ar putea schimba cultura de pe o singură celulă, astfel încât să obțină o parcelă de suprafață mai mare.

Dându-se dimensiunile fermei și pentru fiecare celulă culoarea corespunzătoare culturii semănate, determinați:

  • Cerința 1: Suprafața maximă a unei parcele în planul inițial.
  • Cerința 2: Numărul liniei, respectiv al coloanei celulei pe care va semăna o altă cultură și culoarea corespunzătoare noii culturi în vederea obţinerii celei mai mari parcele posibile.

OJI 2014, Clasa a X-a

#1027 Cool

Se consideră un șir A format din N elemente naturale nenule. Numim secvență de lungime K a șirului A orice succesiune de elemente consecutive din șir de forma 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.

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

OJI 2014, Clasa a IX-a

Numărul 1 poate fi scris în diverse moduri ca sumă de fracţii cu numărătorul 1 şi numitorul o putere a lui 2. De exemplu:

1 = 1/2 + 1/2 = 1/2 + 1/4 + 1/8 + 1/8 = 1/8 + 1/4 + 1/2 + 1/8

Două scrieri nu sunt considerate distincte dacă folosesc aceleaşi fracţii scrise în altă ordine. În exemplul de mai sus ultimele două scrieri nu sunt distincte.

Pentru N – număr natural nenul să se determine:
a) O modalitate de scriere a numărului 1 ca sumă de exact N fracţii cu numărătorul 1 şi numitorul o putere a lui 2.
b) Numărul de scrieri distincte a numărului 1 ca sumă de exact N fracţii cu numărătorul 1 şi numitorul o putere a lui 2. Deoarece acest număr poate fi foarte mare acest număr trebuie calculat modulo 100003.

OJI 2014, Clasele XI-XII

#1021 Cartite

Cârtițele sunt animale de dimensiuni mici care își duc traiul pe suprafețe de teren deschis, având ca dușman principal vulpea. Lângă o pădure se află o zonă agricolă în forma dreptunghiulară, împărțită în pătrățele de aceeași dimensiune. Zona agricolă este reprezentată printr-un tablou bidimensional cu M linii și N coloane, având liniile și coloanele numerotate începând cu 1. În aceasta zona agricolă trăiește o cârtiță și K vulpi.

Pentru cârtiță cunoaștem coordonatele ei (linia și coloana) pe care se găsește, la fel și pentru vulpi, care stau la pânda pentru a ataca cârtita în momentele ei de neatenție.
Pe suprafața terenului cârtita se poate deplasa din patrațelul în care se afla doar într-unul dintre cele 4 pătrățele vecine pe direcțiile nord, sud, est sau vest.
Vulpile pot ataca instantaneu pe o raza de acțiune de lungime 0, 1 sau 2 pe orizontala și verticala, inclusiv în poziția unde se găsesc, după care tot instantaneu se întorc în pozițiile inițiale. În figura de mai jos sunt desenate pătrățele unde poate ataca o vulpe poziționață în pătrățelul cu cifra reprezentând raza de acțiune.

Pentru a micșora riscul de deplasare în zona agricolă cârtița sapă în pământ un sistem de G galerii, care leagă între ele pătrățele din zona agricola. Aceste galerii nu se intersectează sub pamânt, ci doar la suprafață, trecerea dintr-o galerie în alta, care se intersectează în același pătrățel făcându-se printr-un sistem ce nu îi pune viata în pericol. Galeriile sunt indicate prin coordonatele pătrățelelor pe care le unesc. Acestea sunt săpate astfel încât, dacă pornim dintr-un capăt al unei galerii le putem parcurge pe toate. Nu exista doua galerii care sa pornească din același pătrățel și să ajungă tot în același pătrățel (galeriile sunt distincte).

Cârtița dorește sa se plimbe prin toate galeriile de sub teren trecând o singura data prin fiecare, dar pentru acest lucru trebuie sa ajungă nevătămată mergând la suprafața terenului la un pătrățel de unde să intre în sistemul de galerii.

Determinați:

1. cel mai apropiat pătrățel de poziția inițială a cârtitei prin care ea poate să intre în galerie pentru a se plimba, precum și lungimea traseului parcurs la suprafață astfel încât fiecare pătrățel de pe traseu sa nu fie atacat de nicio vulpe;
2. traseul de plimbare numai prin galerii, specificat prin coordonatele pătrățelelor care constituie capetelor acestora.

OJI 2014, Clasele XI-XII

Pentru a putea ţine evidenţa mai uşor, administratorul unui magazin întocmeşte o listă cu produsele care se găsesc în magazin la începutul zilei. El scrie numele produselor, folosind cuvinte de aceeaşi lungime, formate doar din literele mici ale alfabetului englez. Îndată finalizată lista, el îi asociază un cod reprezentând cel mai mic cuvânt în sens lexicografic, obţinut prin preluarea unei litere din fiecare nume de produs, în ordinea în care acestea au fost scrise pe listă.

El observă că acest cod poate fi obţinut în mai multe moduri. Doreşte însă să identifice varianta în care literele alese sunt cât mai apropiate, altfel spus, distanţa, reprezentând numărul de poziţii, între poziţia cea mai mică şi poziţia cea mai mare pe care sunt plasate caracterele alese, este minimă. De exemplu:

Pentru lista care cuprinde produsele de mai jos:

c a i e t
l a p t e
m i e r e
c a f e a

Codul asociat este: aaea

O variantă de obţinere în care distanţa este 4. Poziţia literei a din al doilea cuvânt este 2 iar a lui e, ales în al treilea cuvânt este 5:

c @a@ i e t
l @a@ p t e
m i e r @e@
c @a@ f e a

Varianta optimă este caracterizată de distanţa 2. deoarece, poziţia minimă a unui caracter ales este 2 iar cea maximă este 3:

c @a@ i e t
l @a@ p t e
m i @e@ r e
c @a@ f e a

Scrieţi un program care să determine codul asociat listei de produse şi distanţa minimă prin care poate fi obţinut.

Lot Juniori, Resita, 2012

#705 2d

Gigel îşi imaginează lumea în varianta 2d, adică reprezentată în sistem de coordonate cartezian XOY. Fiecare persoană din grupul celor N prieteni ai săi este reprezentată în plan printr-un punct identificat prin abscisa şi ordonata sa. În lumea sa 2d, plouă ca în Anglia, iar picăturile de ploaie pică paralel cu axa OY, de la o înălţime infinită. Ca să îi ferească pe prietenii săi de ploaie, îşi propune să le construiască apărători pe care le va reprezenta pe hartă prin segmente de dreaptă.

Ştiind că nu poate să deseneze pe hartă decât segmente de lungimi egale, determinaţi care este lungimea minimă a unui segment astfel încât trasând cel mult K segmente, toți cei N prieteni ai săi să fie protejați de ploaie.

Lot Juniori, Baia Mare, 2013

#1058 Puncte1

Andrei se descurcă foarte bine la geometrie şi de aceea născoceşte tot felul de jocuri pe care le testează cu Alexandru, colegul său de bancă. Pentru a pregăti noul joc cu trei niveluri, Andrei desenează pe o foaie de matematică reperul cartezian xOy şi mai multe puncte distincte. Fiecare punct desenat are atât abscisa x, cât şi ordonata y, numere întregi.

La primul nivel, Alexandru determină numărul maxim de puncte (dintre cele desenate) aflate pe una dintre axele sistemului cartezian sau pe o dreaptă paralelă cu una dintre cele două axe.
La al doilea nivel, Alexandru consideră toate punctele desenate a căror abscisă x şi ordonată y verifică cel puţin una dintre relaţiile x=y sau x+y=0 şi apoi calculează câte drepte distincte trec prin cel puţin două dintre aceste puncte.

La al treilea nivel, Alexandru numără şi şterge punctele din 3 în 3 (primul, al 4-lea, al 7-lea etc.), începând cu cel mai din stânga punct desenat şi continuând către dreapta. Dacă două sau mai multe puncte au aceeaşi abscisă, el le numără pe acestea de jos în sus (începând de la punctul cu ordonata cea mai mică). Când a ajuns cu număratul la cel mai din dreapta punct continuă cu cel mai din stânga punct rămas.

Alexandru se opreşte cu numărarea şi ştergerea când rămâne un singur punct desenat pe foaie.

Scrieţi un program care citeşte numărul natural nenul N, apoi cele 2*N numere întregi ce reprezintă coordonatele celor N puncte şi determină:

a) NRP, numărul maxim de puncte (dintre cele desenate) aflate pe una dintre axele sistemului cartezian sau pe o dreaptă paralelă cu una dintre cele două axe;
b) NRD, numărul de drepte distincte care trec prin cel puţin două dintre punctele desenate a căror abscisa x şi ordonată y verifică cel puţin una dintre relaţiile x=y sau x+y=0;
c) XP reprezentând abscisa punctului rămas pe foaie la sfârşitul celui de-al treilea nivel al jocului.

OJI 2013, Clasa a VIII-a

#1057 MaxP

Considerăm un şir de numere a1, a2, …, aN. O secvenţă nevidă în acest şir este de forma ai, ai+1, …, aj, unde i ≤ j. De exemplu, pentru N=4 şi şirul 2 3 4 3, secvenţele nevide sunt: 2, 2 3, 2 3 4, 2 3 4 3, 3, 3 4, 3 4 3, 4, 4 3, 3. Definim puterea unui element ai ca fiind numărul de secvenţe care-l conţin pe ai şi în care ai este strict mai mare decât celelalte elemente ale fiecăreia dintre respectivele secvenţe. Astfel în şirul 2 3 4 3 puterea elementului a1 este 1 (fiind maxim doar în secvenţa formată din el însuşi), a elementului a2 este 2 (a2 fiind maxim în secvenţele 2 3 şi 3), a elementului a3 este 6 (fiind maxim în secvenţele 2 3 4, 2 3 4 3, 3 4, 3 4 3, 4 şi 4 3), iar a elementului a este 1.

Scrieţi un program care determină puterea cea mai mare a unui element din şirul dat, precum şi numărul de elemente din şir care au cea mai mare putere.

OJI 2013, Clasa a VIII-a

#1056 Unific

Se consideră un şir A=(A1, A2, ..., AN), format din N numere naturale nenule. Două numere se consideră vecine dacă se află pe poziţii alăturate (Ai are ca vecini pe Ai-1 şi Ai+1, pentru orice 1<i<N, A1 are ca vecin doar pe A2, iar AN are ca vecin doar pe AN-1).

Dacă două elemente vecine Ai, Ai+1 (1≤i<N) au cel puţin o cifră comună, ele se pot unifica. Procedeul de unificare constă în eliminarea din numerele Ai şi Ai+1 a tuturor cifrelor comune şi adăugarea prin alipirea numărului obţinut din Ai+1 la numărul obţinut din Ai, formându-se astfel un nou număr. Numărul Ai va fi înlocuit cu noul număr, iar numărul Ai+1 va fi eliminat din şir.

De exemplu, numerele Ai=23814 şi Ai+1=40273 au cifrele 2, 3, 4 comune, după unificare obţinem Ai=817, iar Ai+1 este eliminat; observaţi că dacă după eliminarea cifrelor comune, numerele încep cu zerouri nesemnificative, acestea vor fi eliminate, apoi se realizează alipirea.

Dacă în urma eliminării cifrelor comune, unul dintre numere nu mai are cifre, atunci numărul rezultat va avea cifrele rămase în celălalt. Dacă în urma eliminării cifrelor comune atât Ai cât şi Ai+1 nu mai au cifre, atunci ambele numere vor fi eliminate din şir, fără a fi înlocuite cu o altă valoare.

Ordinea în care se fac unificările în şir este importantă: la fiecare pas se alege prima pereche de elemente vecine Ai Ai+1 care poate fi unificată, considerând şirul parcurs de la stânga la dreapta. (De exemplu, considerând Ai=123, Ai+1=234, Ai+2=235, se unifică Ai cu Ai+1 => Ai=14, iar unificarea cu următorul număr nu mai este posibilă).

Cunoscându-se şirul celor N numere naturale, să se determine:

a) cifra care apare cel mai frecvent în scrierea tuturor celor N numere; dacă există mai multe cifre cu aceeaşi frecvenţă de apariţie maximă, se va reţine cea mai mică cifră.
b) şirul obţinut prin efectuarea unui număr maxim de unificări, după regulile descrise în enunţ.

OJI 2013, Clasa a VII-a

#1055 Compar

Ana şi Bogdan au inventat jocul “Compar”. Ana scrie pe tablă o secvenţă formată din N numere naturale distincte cuprinse între 1 şi N, apoi compară fiecare două numere învecinate din secvenţă scriind între ele semnul < sau semnul >, după caz.
De exemplu, dacă secvenţa de pe tablă este 6 4 2 1 3 5, după compararea elementelor învecinate şi inserarea semnelor în secvenţă, Ana obţine:
6>4>2>1<3<5
După aceea Ana şterge cele N elemente ale secvenţei şi păstrează numai semnele, astfel:
>>><<
La final, Ana îi arată lui Bogdan şirul semnelor şi îi cere să reconstituie secvenţa de numere naturale scrisă iniţial pe tablă.

Cunoscând şirul semnelor construit de Ana, scrieţi un program care să îl ajute pe Bogdan să reconstituie secvenţa de numere naturale distincte scrisă iniţial pe tablă.

OJI 2013, Clasa a VII-a

#1054 Galbeni

După ce au descoperit ascunzătoarea piratului Spânu, marinarii de pe corabia “Speranţa” au hotărât să ofere sătenilor o parte din comoara acestuia. Întrucât comoara avea un număr nelimitat de bani din aur, numiţi galbeni, singura problemă a marinarilor a fost regula după care să împartă banii.

După îndelungi discuţii au procedat astfel: i-au rugat pe săteni să se aşeze în ordine la coadă şi să vină, pe rând, unul câte unul pentru a-şi ridica galbenii cuveniţi. Primul sătean a fost rugat să îşi aleagă numărul de galbeni, cu condiţia ca acest număr să fie format din exact K cifre. Al doilea sătean va primi un număr de galbeni calculat astfel: se înmulţeşte numărul de galbeni ai primului sătean cu toate cifrele nenule ale acelui număr, rezultatul se înmulţeşte cu 8 şi apoi se împarte la 9 păstrându-se doar ultimele K cifre ale câtului împărţirii. Dacă numărul obţinut are mai puţin de K cifre, atunci acestuia i se adaugă la final cifra 9, până când se completează K cifre.

Pentru a stabili câţi galbeni primeşte al treilea sătean, se aplică aceeaşi regulă, dar pornind de la numărul de galbeni ai celui de-al doilea sătean. Regula se aplică în continuare fiecărui sătean, plecând de la numărul de galbeni primiţi de săteanul care a stat la coadă exact în faţa lui.

Cunoscând numărul de galbeni aleşi de primul sătean, determinaţi numărul de galbeni pe care îl va primi al N-lea sătean.

OJI 2013, Clasa a VI-a

#1053 Cladiri

Având mai multe cuburi la dispoziţie, Crina şi Rareş au hotărât să construiască clădiri prin alipirea a două sau mai multor turnuri. Turnurile au fost obţinute prin aşezarea cuburilor unul peste celălalt. Înălţimea unui turn este dată de numărul de cuburi din care este format.
Clădirile construite au fost aşezate în linie, una lângă alta formând astfel o stradă, pe care cei doi copii se vor plimba.

Pentru numerotarea clădirilor Crina şi Rareş au stabilit următoarele reguli:

  • Crina porneşte dintr-un capăt al străzii, iar Rareş din celălalt capăt al acesteia; fiecare dintre ei traversează strada complet, trecând prin dreptul fiecărei clădiri
  • Crina lipeşte pe fiecare clădire câte un bileţel pe care scrie înălţimea turnurilor din care aceasta este construită, în ordinea în care ea le vede când trece prin dreptul lor (de exemplu, pentru imaginea de mai sus, Crina va lipi pe prima clădire un bileţel pe care va scrie numărul 3112 deoarece, primul turn e format din 3 cuburi, următoarele două turnuri ale acestei clădiri sunt formate din câte un cub iar cel de-al patrulea turn e format din 2 cuburi);
  • Rareş va proceda la fel, dar începe plimbarea din celalalt capăt al străzii. În exemplul din imagine, el va lipi pe prima clădire pe care o întâlneşte un bileţel pe care scrie numărul 2121.
  • La finalul plimbării, Crina şi Rareş îşi dau seama că există clădiri pe care au lipit amândoi bileţele cu numere identice.

a) Care este înălţimea celui mai înalt turn şi care este numărul clădirilor care au în construcţia lor un astfel de turn?
b) Care este numărul clădirilor pe care cei doi copii au lipit bileţele cu numere identice?
c) Care este cel mai mic număr de cuburi necesar pentru a completa clădirile astfel încât, pe fiecare clădire, bileţelul pe care îl va lipi Crina să conţină acelaşi număr cu cel pe care îl va lipi Rareş? Cuburile din care a fost construită iniţial clădirea nu se pot muta.

OJI 2013, Clasa a VI-a

Lui Gigel, elev în clasa a V-a, îi place grozav de tare să se joace cu cifrele, cu numerele şi creează tot felul de probleme pe care apoi încearcă să le rezolve. Acum se joacă cu o cutie de chibrituri şi formează cu ele cifre. Apoi privirea i-a căzut pe cadranul unui ceas electronic şi a văzut că cifrele sunt formate din segmente orizontale şi verticale şi a început să formeze cu chibriturile cifrele care indică ora (vezi figura). Şi imediat şi-a pus o întrebare: “oare dacă am n chibrituri puse vertical şi m chibrituri puse orizontal, care este ora minimă pe care o pot forma cu aceste chibrituri?”

Fiind date un număr n de chibrituri verticale şi un număr m de chibrituri orizontale, să se scrie un program care determină numărul de ore posibile, ora minimă şi ora maximă care se pot forma cu aceste chibrituri, în modul indicat mai sus, utilizând toate chibriturile respective şi nemodificând orientarea acestora.

OJI 2013, Clasa a V-a

#1051 Bete1

Ana şi Bogdan au găsit la bunicul lor o cutie cu N beţe de aceeaşi lungime. După câteva minute de joacă urmează cearta. Bunicul le-a propus să rupă cele N beţe și apoi Ana să primească fragmentele din mâna stângă, iar Bogdan fragmentele din mâna dreaptă. Zis şi făcut. Copiii au luat fragmentele, le-au numerotat fiecare cu numere de la 1 la N, le-au măsurat şi acum îşi doresc să lipească fragmentele primite, dar mai au nevoie de câteva informaţii.

Cunoscând N numărul de beţe, a1, a2,…, aN lungimile fragmentelor primite de Ana şi b1, b2,…, bN lungimile fragmentelor primite de Bogdan, să se scrie un program care să determine:

a) lungimea iniţială a beţelor;
b) lungimea celui mai lung băţ care se poate obţine prin lipirea unui fragment aparţinând Anei cu un fragment care aparţine lui Bogdan;
c) numărul beţelor de lungime maximă care se pot obţine prin lipirea unui fragment aparţinând Anei cu un fragment care aparţine lui Bogdan.

OJI 2013, Clasa a V-a

#1041 Biperm

Pentru un număr natural nenul n, să considerăm toate numerele naturale nenule mai mici sau egale cu n, luând fiecare număr de câte două ori: 1, 1, 2, 2, 3, 3, ... , n, n. Aceste numere le amestecăm aleator, şi le aranjăm pe două linii a câte n elemente. Structura astfel obţinută o vom numi o bipermutare. În figurile 1, 2 şi 3 avem câte un exemplu de bipermutare pentru n=5.

O bipermutare este perfectă, dacă ambele linii ale structurii reprezintă câte o permutare (vezi figurile 2 şi 3).

Prin mutare pe poziţia p, înţelegem interschimbarea elementelor de pe aceeaşi coloană p. În exemplele de mai jos, bipermutarea perfectă din figura 2 s-a obţinut din bipermutarea din figura 1, aplicând o mutare pe poziţa 2. Bipermutarea perfectă din figura 3 s-a obţinut din bipermutarea din figura 1, aplicând mutări pe poziţiile 1, 2, 4 şi 5.

Cunoscând o bipermutare, determinaţi:

  • numărul bipermutărilor perfecte distincte ce se pot obţine prin mutări;
  • numărul minim de mutări prin care se poate obţine o bipermutare perfectă;
  • o bipermutare perfectă obţinută din bipermutarea iniţială.

OJI 2013, clasele XI-XII

#1050 TCIF

Avem la dispoziţie patru numere naturale N, A, B, C, precum şi trei cifre c1, c2, c3 distincte două câte două.

Să se determine numărul natural minim, strict mai mare decât N, care are exact A cifre c1, B cifre c2, C cifre c3 şi nu conţine alte cifre.

OJI 2014, Clasa a VIII-a

#1049 Arrows

“Arrows” este un joc care se joacă pe o tablă dreptunghiulară a cărei suprafaţă este împărţită în NxM celule, aranjate pe N linii şi M coloane. În fiecare celulă se află o săgeată (sus, jos, stânga sau dreapta), ca în figura de mai jos:

Când este la mutare, un jucător poate alege o poziţie de start pe care plasează un jeton, apoi deplasează jetonul la celula învecinată în sensul indicat de săgeată. Deplasarea continuă până când jetonul părăseşte tabla de joc, caz în care jucătorul obţine un punctaj egal cu numărul de celule parcurse de jetonul său.

Există însă poziţii de start denumite favorabile, pentru care jetonul nu va părăsi niciodată tabla de joc. De exemplu, toate poziţiile din figură cu fundal gri sunt favorabile. Jucătorul care alege o poziţie de start favorabilă obţine un punctaj egal cu numărul de celule distincte vizitate înmulţit cu 1000.

Scrieţi un program care, cunoscând configuraţia tablei de joc, rezolvă una dintre următoarele cerinţe:

1. determină punctajul pe care îl obţine un jucător care plasează jetonul său pe o poziţie de start specificată;
2. determină numărul de celule favorabile de pe tabla de joc;
3. determină punctajul maxim pe care jucătorul îl poate obţine la o mutare, alegând convenabil poziţia de start.

OJI 2014, Clasa a VIII-a

#1048 Schi

La proba de sărituri cu schiurile din cadrul jocurilor olimpice de iarnă participă N concurenți, numerotați cu numere de la 1 la N.

Regulile de desfășurare a probei sunt următoarele:

  • concurenții evoluează pe rând, în ordine de la 1 la N;
  • fiecare concurent va efectua o singură săritură;
  • după efectuarea săriturii fiecare concurent primește un anumit punctaj;
  • pe tot parcursul concursului, comisia de arbitri are obligația să alcătuiască o listă cu punctajele obținute de concurenți, în ordinea evoluției lor;
  • evoluția unui concurent durează exact un minut;
  • nu se face pauză între evoluțiile a doi concurenți care au numere de ordine consecutive;
  • afișarea punctajului nu necesită timp suplimentar după efectuarea săriturii;
  • proba se încheie la un minut după evoluția ultimului concurent.

Pe tot parcursul concursului se ține în mod neoficial și un clasament parțial, pe baza rezultatelor obținute de concurenții care au evoluat până în acel moment. Asta pentru că șeful comisiei de arbitri are o curiozitate aparte și pune K întrebări sub forma următoare: Câte minute s-a ocupat primul loc din clasament cu un punctaj egal cu X puncte? Dacă nici un concurent nu s-a clasat pe primul loc cu X puncte atunci primește ca răspuns valoarea 0.

Scrieți un program care determină răspunsul pentru fiecare dintre cele K întrebări puse de șeful comisiei de arbitri.

OJI 2014, Clasa a VII-a

#1046 Munte

Se consideră un şir x1, x2,…, xn format din n numere naturale distincte. O secvenţă de număr maxim de elemente vecine în şir, de forma xi, xi+1,…, xk-1, xk, xk+1,…, xj (1≤i<k<j≤n) cu proprietatea că xi < xi+1 < ...< xk-1 < xk > xk+1 > ... > xj, se numeşte munte cu vârful xk. Două secvenţe munte au maxim un element comun în şir. O secvenţă munte are cel puţin 3 elemente. Un exemplu de şir format cu valorile 3 4 6 8 nu conţine nicio secvenţă munte, iar unul format cu valorile 3 4 8 1 2 5 0 conţine 2 secvenţe munte: 3 4 8 1 şi 1 2 5 0.

După determinarea tuturor secvenţelor munte şi a vârfurilor acestora, se elimină din şir vârfurile secvenţelor munte şi procedura continuă repetat cu determinarea noilor secvenţe munte şi a vârfurilor lor din şirul nou obţinut. Procedura se opreşte în momentul în care în şir nu mai există nicio secvenţă munte.

Scrieţi un program care citeşte numerele n, x1, x2, …, xn şi apoi determină:

a) numărul de secvenţe munte din şirul iniţial;
b) numărul total de secvenţe munte obţinute pornind de la şirul iniţial până la cel care nu mai conţine nicio secvenţă munte;
c) numărul de elemente din şirul final care nu mai conţine secvenţe munte.

OJI 2014, Clasa a VI-a

Cif-Oji6 este o imprimantă matriceală numită şi imprimantă cu ace, deoarece tipărirea se realizează prin impactul acelor capului de imprimare pe o bandă cu tuş.
Acele sunt aranjate într-o grilă dreptunghiulară formată din 5 rânduri de ace, pe fiecare rând aflându-se la distanţe egale câte 3 ace, aşa cum se observă în figura alăturată.
Prin acţionarea diferitelor combinaţii de ace din grilă, se defineşte forma fiecărei cifre ce permite tipărirea acesteia prin puncte, în felul următor:

De exemplu, cifra 2 va fi tipărită prin 11 puncte ca rezultat al acţionării a 11 ace din grilă: din primul rând de ace al grilei se vor acţiona toate cele 3 ace, din următorul rând doar acul din dreapta, apoi de pe următorul rând toate cele 3 ace, apoi acul din stânga de pe penultimul rând iar din ultimul rând toate cele 3 ace.

a) Ştiind că imprimanta Cif-Oji6 a tipărit numărul N, determinaţi care este cea mai mare cifră a numărul N pentru care s-a acţionat un număr minim de ace ale grilei.
b) Ştiind că imprimanta mai are tuş pe bandă doar pentru imprimarea a K puncte, determinaţi cel mai mare număr natural ce poate fi tipărit prin exact K puncte.

OJI 2014, Clasa a VI-a

Fascinat de Egiptul Antic, Rareș vrea să construiască cât mai multe piramide din cartonașe pătratice identice. El are la dispoziție N cartonașe numerotate de la 1 la N, albe sau gri, așezate în ordinea strict crescătoare a numerelor.

  • Prima piramidă o va construi folosind primele trei cartonașe. Baza piramidei va fi formată din cartonașele 1 și 2 așezate alăturat, peste care va așeza cartonașul 3 (vârful piramidei).
  • A doua piramidă va avea baza formată din cartonașele 4,@5@ și 6 așezate alăturat, deasupra cărora se vor așeza cartonașele 7 și 8, alăturate, peste care se va așeza cartonașul 9 (vârful piramidei).
  • Mai departe, va construi în ordine piramidele complete cu bazele formate din 4 cartonașe (cu numerele de la 10 la 13), respectiv 5 cartonașe (cu numerele de la 20 la 24), 6 cartonașe (cu numerele de la 35 la 40) etc., cât timp va putea construi o piramidă completă. De exemplu, dacă Rareș are N=75 cartonașe atunci el va construi piramidele complete 1,@2@,@3@,@4@ și 5 din imaginile următoare. Din cele 75 de cartonașe el va folosi doar primele 55 de cartonașe, deoarece ultimele 20 cartonașe nu sunt suficiente pentru a construi piramida 6, cu baza formată din 7 cartonașe.

Scrieţi un program care să citească numerele naturale N (reprezentând numărul de cartonașe), X (reprezentând numărul unui cartonaș), K (reprezentând numărul de cartonașe albe), numerele celor K cartonașe albe c1, c2, …, cK și care să determine:

a) numărul P al piramidei complete ce conține cartonașul numerotat cu X;
b) numărul M maxim de piramide complete construite de Rareș;
c) numărul C de cartonașe nefolosite;
d) numărul A al primei piramide complete care conține cele mai multe cartonașe albe.

OJI 2014, Clasa a V-a

Gică şi Lică lucrează la o fabrică de jucării, în schimburi diferite. Anul acesta patronul fabricii a hotărât să confecţioneze şi mărţişoare. Mărţişoarele gata confecţionate sunt puse în cutii numerotate consecutiv.

Cutiile sunt aranjate în ordinea strict crescătoare şi consecutivă a numerelor de pe acestea.
Gică trebuie să ia, în ordine, fiecare cutie, să lege la fiecare mărţişor câte un şnur alb-roşu şi apoi să le pună la loc în cutie.

În fiecare schimb, Gică scrie pe o tablă magnetică, utilizând cifre magnetice, în ordine strict crescătoare, numerele cutiilor pentru care a legat șnururi la mărțișoare.

Când se termină schimbul lui Gică, Lică, care lucrează în schimbul următor, vine şi ambalează cutiile cu numerele de pe tablă şi le trimite la magazine. Totul merge ca pe roate, până într-o zi, când, două cifre de pe tablă se demagnetizează şi cad, rămânând două locuri goale. Lică observă acest lucru, le ia de jos şi le pune la întâmplare pe tablă, în cele două locuri goale. Singurul lucru de care ţine cont este acela că cifra 0 nu poate fi prima cifră a unui număr.

Scrieţi un program care să citească numerele naturale N (reprezentând numărul de numere scrise pe tablă) şi c1, c2, …, cN (reprezentând numerele scrise, în ordine, pe tablă, după ce Lică a completat cele două locuri goale cu cifrele căzute) și care să determine:
a) cele două cifre care au fost schimbate între ele, dacă, după ce au completat locurile goale, acestea au schimbat șirul numerelor scrise de Gică;
b) numărul maxim scris pe tablă de Gică.

OJI 2014, Clasa a V-a

Fie n un număr natural și M={S1,S2,…,Sn} o mulțime de șiruri de caractere nevide. Fie Sk un șir de caractere din M. Atunci, orice caracter al lui Sk aparține mulțimii {'a','b'}. Notăm prin |Sk| numărul caracterelor șirului Sk sau, echivalent, lungimea sa. O subsecvență Sk[i:j] a lui Sk este formată din caracterele situate pe pozițiile consecutive i, i+1, .., j. Astfel, dacă Sk = 'abbbaababa', atunci Sk[3:6] = 'bbaa' sau subsecvența evidențiată: 'abbbaababa'.

Fiind dată o mulțime M, se cere să se determine lungimea maximă a unei subsecvențe care se găsește în toate șirurile din M.

OJI 2013, clasele XI-XII

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

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.

OJI 2013, clasa a IX-a

#1039 Betasah

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 N*(N+1)/2 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 N*(N+1)/2 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)

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.

OJI 2013, clasa a IX-a

#1038 Zona2

Ionuţ pleacă în drumeţie într-o porţiune de teren de formă pătratică cu latura de N metri. O hartă a zonei are trasat un caroiaj care împarte zona în N*N pătrate unitate, cu latura de 1 metru. Astfel harta zonei are aspectul unui tablou pătratic cu N linii şi N coloane. Liniile şi coloanele sunt numerotate de la 1 la N. Elementele tabloului bidimensional corespund pătratelor unitate. Zona poate fi parcursă străbătând oricare dintre laturile pătratelor unitate cel mult o singură dată.

Ionuţ pleacă din punctul aflat în colţul din dreapta jos al pătratului unitate din linia X, coloana Y şi se deplasează făcând un pas (parcurgând o latură a unui pătrat unitate) în una din direcţiile Nord, Est, Sud, Vest. Pentru a reţine mai uşor traseul foloseşte următoarea codificare pentru cele 4 direcţii: 1 pentru deplasarea spre Nord, 2 pentru deplasarea spre Est, 3 pentru deplasarea spre Sud, respectiv 4 pentru deplasarea spre Vest.

Ajuns într-alt punct (colţ de pătrat unitate), Ionuţ continuă să se deplaseze fără a trece de mai multe ori pe aceeaşi latură a unui pătrat unitate.

Ionuţ se opreşte în momentul în care ajunge într-un punct prin care a mai trecut. Traseul străbătut între cele două treceri prin acelaşi punct delimitează o zonă de teren formată din pătrate unitate.

Dându-se linia X şi coloana Y corespunzătoare poziţiei de plecare a lui Ionuţ, dimensiunea zonei N, lungimea traseului L şi traseul determinaţi:
a) Numărul de paşi parcurşi între prima şi a doua trecere prin punctul de oprire.
b) Numărul de pătrate unitate interioare zonei delimitată de traseul străbătut între cele două treceri prin acelaşi punct.

OJI 2013, clasa a X-a

#1037 Calcule

Gigel a studiat recent şirurile cu n elemente, numere naturale. Pentru un astfel de şir S, Gigel doreşte să afle răspunsul la întrebările:

a) Care este numărul minim de subşiruri strict crescătoare în care se poate partiţiona S?
b) Care este numărul de secvenţe, modulo 20011, cu suma elementelor divizibilă cu k care se pot obţine din S?

Dându-se un şir S cu n elemente numere naturale şi un număr natural k se cere să se răspundă la cele două întrebări.

OJI 2013, clasa a X-a

#152 sir

GM are un şir de N numere naturale a1 , a2 ,…, aN , cu proprietatea ai ai+1 2*ai pentru orice i, 1 ≤i < N. El doreşte să scrie în faţa fiecărei valori din şir un semn + sau - astfel încât valoarea S a expresiei obţinute să aibă proprietatea 0 ≤ S ≤ a1 .

Scrieţi un program care să-l ajute pe GM să determine un mod de a scrie cele N semne.

Urmasii lui Moisil, Iasi, 2013

#151 drum

Oraşele Nordemos şi Suderim sunt separate de un munte foarte înalt. Inginerul Negrimon a fost desemnat să construiască un drum prin munte care să unească cele două oraşe. Harta care i s-a pus la dispoziţie descrie muntele ca o matrice cu N linii şi M coloane numerotate de la 1 la N, respectiv de la 1 la M . Un drum reprezintă o succesiune de elemente din matrice cu proprietatea că oricare două elemente consecutive sunt alăturate, pe linie sau pe coloană. Un drum uneşte oraşul Nordemos (linia 1) şi oraşul Suderim (linia N). Valorile din matrice reprezintă densităţile rocilor din munte în acele zone. Pentru fiecare drum posibil se poate calcula valoarea dmax, egală cu densitatea maximă a rocilor pe care le traversează. Negrimon trebuie să construiască un drum pentru care valoarea dmax este cea mai mică.

Ajută-l pe Negrimon să afle cea mai mică dintre densităţile dmax corespunzătoare drumurilor care unesc Nordemos şi Suderim în condiţiile de mai sus.

Urmasii lui Moisil, Iasi, 2013

Nici nu ştiţi cât de greu este să fii funcţionar. Zeci de rapoarte de întocmit, sute de cereri ce trebuiesc redactate, mii de semnături, sute de mii de hârtii de înregistrat. Circuitul nesfârşit al hârtiilor este cunoscut sub numele de birocraţie. În instituţia noastră sunt angajaţi N funcţionari, numerotaţi de la 1 la N.

Fiecare dintre ei trebuie să înregistreze un număr considerabil de documente. Acesta este motivul pentru care în fiecare zi, încă de la prima oră, funcţionarii se aşază la coadă la secretariat, în ordine de la 1 la N. Modalitatea de înregistrare a documentelor este următoarea: funcţionarul se aşează la coadă, aşteaptă până îi vine rândul, înregistrează un singur document, apoi, dacă mai are alte documente se reaşează la coadă, ş.a.m.d. Din păcate, serviciul de secretariat înregistrează într-o zi cel mult M documente.

Dacă se cunoaşte, pentru fiecare din cei N de funcţionari, numărul de documente pe care trebuie să le înregistreze la secretariat, determinaţi numărul de ordine al funcţionarilor care nu au reuşit semnarea tuturor documentelor până la încheierea zilei de muncă.

Lot Juniori, Resita, 2012

#718 Sah2

Lot Juniori, Resita, 2012

#716 cmin

Lot Juniori, Resita, 2012

Lot Juniori, Resita, 2012

#707 sumk

Lot Juniori, Baia Mare, 2013

Lot Juniori, Baia Mare, 2013

#704 smsm

Lot Juniori, Baia Mare, 2013

Lot Juniori, Baia Mare, 2013

Lot Juniori, Deva, 2013

#700 Labir

Lot Juniori, Deva, 2013

Lot Juniori, Deva, 2013

Lot Juniori, Deva, 2013

#696 Mario

Lot Juniori, Deva, 2013

#694 sam

Aranjăm primele N numere naturale nenule sub forma unui șir A[1], A[2], ..., A[N].

Fie X[1], X[2],...,X[K] (K ≥ 3), un subșir al șirului A. Numim extrem local al subșirului X termenul din mijlocul unei secvențe de lungime trei din subșir, X[i-1], X[i], X[i+1], cu proprietatea: X[i-1]<X[i]>X[i+1], 1<i<K sau X[i-1]>X[i]<X[i+1], 1<i<K.

Vom nota cu nrex(X) numărul de extreme locale ale subșirului X.

Spunem că un subșir X[1], X[2],...,X[K] (K≥2) al șirului A este subșir alternant dacă nrex(X)=K-2, adică exceptând primul și ultimul termen din subșir toți ceilalți termeni sunt extreme locale ale subșirului X.

Dintre toate subșirurile alternante ale șirului A ne interesează cele de lungime maximă pe care le vom numi subșiruri alternante maximale.

Cunoscând N și tabloul A se cere să se determine restul obținut la împărțirea dintre numărul M al subșirurilor alternante maximale ale tabloului A și numărul 1000003.

Lot Juniori, Sovata, 2014

Lot Juniori, Sovata, 2014

#692 robot

Lot Juniori, Sovata, 2014

Lot Juniori, Sovata, 2014

Lot Juniori, Sovata, 2014

#683 ssce

Avem la dispoziţie un şir X cu n numere naturale date într-o bază b. Trebuie determinat un subşir al şirului dat care are anumite proprietăţi, precizate în enunț.

Lot Juniori, Vaslui, 2014

Pe axa reală există N orașe, numerotate cu numerele 1, 2, 3, …, N. Deși într-o lume unidimensională lucrurile par a fi mult mai simple, totuși majoritatea locuitorilor sunt nemulțumiți de distanțele mari parcurse între orașe în scopul rezolvării diferitelor probleme. Astfel, pentru o mai bună organizare, s-a supus la vot și s-a decis promovarea a cel mult K orașe la rangul de centru adminstrativ. Centrele trebuie amplasate într-un mod isteț, în așa fel încât distanța maximă calculată dintre distanțele de la fiecare oraș la cel mai apropiat centru administrativ să fie cât mai mică. Întrucât costurile de administrare ale unui astfel de centru sunt ridicate, se dorește să se amplaseze un număr cât mai mic de centre administrative astfel încât distanța maximă să nu fie modificată.

Lot Juniori, Vaslui, 2014

Se cere determinarea unor informații despre secvențele unui șir dat.

Lot Juniori, Vaslui, 2014

Să se determine numărul de trasee din punctul (0,0) în punctul (X,X) care respectă anumite reguli.

Lot Juniori, Vaslui, 2014

#678 mts

Lot Juniori, Vaslui, 2014

#142 n3579

Grigore Moisil 2013

Grigore Moisil 2013

Grigore Moisil, 2014

#630 Joc

Grigore Moisil, 2014

#629 Zet

Grigore Moisil, 2014

#628 Cub1

Grigore Moisil, 2014

Grigore Moisil 2013

Grigore Moisil, 2014

Grigore Moisil, 2014

#625 vraji

Grigore Moisil, 2014

#624 Sah1

Grigore Moisil, 2014

Grigore Moisil, 2014

Grigore Moisil, 2014

#614 carti

#139 n311

Grigore Moisil 2013

#146 graph

Grigore Moisil 2013

Grigore Moisil 2013

Grigore Moisil 2013

#154 xor

Grigore Moisil 2013

#153 drept

Grigore Moisil 2013

Urmasii lui Moisil, Iasi, 2013

#149 scara

Urmasii lui Moisil, Iasi, 2013

Grigore Moisil 2013

Grigore Moisil 2013