Lista de probleme 345

Filtrare

Dificultate

Operații intrare/ieșire

#1979 rbtree

Gigel se joacă cu un graf orientat cu N noduri. Inițial toate nodurile grafului sunt transparente, dar lui Gigel îi place schimbarea. Fire ambițioasă, el colorează unele noduri în roșu, altele în negru, iar pe celelalte în alb (probabil din cauza crizei de vopsea colorată din 2017).

Gigel recrutează o armată de furnici pe care o așează în nodul 1, cu el în fruntea lor și se hotărăște să cucerească graful.În fiecare moment, Gigel poate trimite un număr de furnici din orice nod X (în care se află deja furnici) în vecinii lui X, cu condiția ca cel puțin o furnică să rămână în nodul X. Excepție de la această regulă face nodul 1, cel în care se află Gigel, unde nu este obligatoriu să rămână furnici.

Dacă într-un nod se află Gigel sau cel puțin o furnică, atunci acel nod se numește ocupat. Graful este cucerit atunci când Gigel a ocupat cel puțin un nod roșu și cel puțin un nod negru.

Cerința

Sa se determine numărul minim de furnici pentru ca Gigel să cucerească graful.

Info Oltenia 2017, Clasele XI-XII, individual

După o confruntare eroică, Trump a fost ales democratic președintele unei republici prospere, TrumpLandia. Natural, prima sa prioritate e să construiască o rețea de buncăre, pentru a veni în întâmpinarea unui atac al vecinilor imperaliști.
N buncăre au fost deja construite. Trump trebuie să aleagă între M posibile rute bidirecționale pentru a le conecta. Un plan de conectare este alcătuit dintr-un subset minim de astfel de legături, astfel încât din fiecare locație să se poată ajunge în orice altă locație. Costul unui plan este dat de suma distanțelor legăturilor.

Deoarece rutele sunt vulnerabile la bombardamente aeriene, Trump vă cere să estimați un plan de cost minim. În plus, Trump vă cere să calculați Q soluții de rezervă, pentru situația în care una dintre cele M legături este sigur inclusă în plan.

Info Oltenia 2017, Clasele XI-XII, echipaje

#1976 srh

Definim recursiv nivelul unui nod într-un arbore cu rădăcină astfel:
• nivelul rădăcinii este 0
• nivelul fiilor unui nod cu adâncimea H este H+1
Fie S(R,H) numărul de noduri din subarborele cu rădăcina în R și care au adâncimea H. Subarborele nodului R îl include și pe el însuși. Doi arbori cu rădăcinile R și R’ sunt similari numai dacă S(R,H) este egal cu S(R’,H), pentru oricare număr natural H.

Se consideră un arbore cu N noduri și rădăcina în nodul 1. Nodurile sunt numerotate de la 1 la N.
Fie TX = subarborele cu rădăcina în nodul X. Se cere să se calculeze numărul de perechi (X,Y) astfel încât subarborii TX și TY sunt similari și X<Y.

Info Oltenia 2017, Clase XI-XII echipaje

#1977 parcele

Ion și Gheorghe au primit moștenire două parcele de pământ de formă poligonală. Într-o zi, Ion l-a văzut pe Gheorghe că a folosit o parte din bucata lui. Certându-se, aceștia au remarcat că acea bucată era parte din moștenirea amândurora. Au hotărât să se ducă la judecată și să se rezolve eroarea care a făcut ca parcelele moștenite să se intersecteze. Dar cum procesul va începe destul de târziu, au hotărât să nu folosească acea bucată comună până nu va fi rezolvată problema.

Info - Oltenia 2017

Sabin merge la colindat de Halloween. Ştiind ca poate colinda la n case, iar la fiecare primeşte g[1], g[2], ..., g[n] bomboane, iar în rucsacul lui încap G bomboane, aflaţi numărul minim de case pe care trebuie să le colinde Sabin pentru a umple ghiozdanul.

#1958 MPalind

TH este foarte pasionat de șiruri palindromuri. El are un șir de caractere ce conține litere ale alfabetului englezesc A, indexat de la 1 și își pune M întrebări de forma: “Pentru x și y, în câte moduri pot împărți șirul A[x...y] în secvențe palindrom? Acest număr poate fi foarte mare, așa că mă mulțumesc cu rezultatul modulo 666013”.

#1957 QMunte

Șcuțu, elev pe clasa a 10-a, s-a plictisit să lucreze probleme de clasa a 6-a. Mygo a văzut că Șcuțu a reușit să obțină 100p pe problema Munte de la OJI2014, însă nu cu o soluție prea inteligentă, așa că îi va pune o provocare. Se dă un vector A de N elemente indexat de la 1. Un vârf este un element A[i] cu proprietatea că A[i-1] < A[i] > A[i+1] (1 < i < N). Mygo îi oferă lui Șcuțu Q operații de tipul:

1 x y: “Elementul de pe poziția x ia valoarea y”.
2 x y: “Având o copie a vectorului A[x...y] (ceea ce urmează nu va afecta cu nimic vectorul A), se determină toate vârfurile iar acestea se elimină, procedeul acesta continuă până când nu vor mai exista vârfuri. Se cere să se afișeze câte vârfuri au existat de la început până la final”.

#587 Mall

Într-un mall sunt n centre comerciale, numerotate de la 1 la n, unite între ele prin coridoare unidirecționale. Să se determine, dacă există, un centru comercial în care se poate ajunge din oricare altul.

Aflaţi numărul de cicluri Hamiltoniene dintr-un graf complet cu N noduri.

#1930 Zen

Muncitorul Zen are de urcat N trepte. Pentru a călca pe o treaptă i, acesta trebuie să plătească o sumă C[i]. Fiind un tip sportiv, acesta poate ajunge pe treapta i de pe treptele i-1, i-2, ..., i-K. Știind că acesta se află inițial la baza scării (pe treapta 0, cu C[0] = 0), se întreabă care este suma totală minimă pe care Zen trebuie să o plătească să ajungă pe treapta N.

Cătălin avea un singur prieten dar, fiind foarte sociabil, el se împrietenește automat cu toți prietenii prietenului său și cu prietenii prietenilor acestuia ș.a.m.d. (s-a inspirat din modelul Facebook).

Inițial, în grupul de persoane, nimeni nu are prieteni dar, pe parcursul timpului, se leagă noi relații de prietenie.

Definim două tipuri de operații:

  • 1 x y – ce reprezintă faptul că x se împrietenește cu y.
  • 2 p – Cătălin vă întreabă care este numărul de prieteni pe care îi poate avea, dacă inițial ar fi prieten doar cu p. Se va ține cont doar de relațiile de prietenie stabilite până în acel moment.

Moisil++, 2016

Îl cunoașteți, cred, pe Cătălin, fan-ul numărul 1 al greșelilor. Ei bine, în teza la mate, Cătălin a făcut N greșeli. Presupunând, prin reducere la absurd, că el corectează o greșeală i, poate alege să corecteze o singură greșeală j, cu proprietatea 1<j<i şi i%j=0. El știe că, dacă face această alegere poate să continue din greșeala j, după aceeași regulă și nu mai poate reveni la o greșeala anterioară.

Cătălin alege T greșeli G[1] G[2] … G[T] și dorește să știe, pentru fiecare G[i], numărul maxim de greșeli pe care le poate corecta dacă începe rezolvând-o pe aceasta.

Moisil++, 2016

#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

Tudor este foarte indecis, deoarece a fost chemat la r festivaluri și puterea lui fizică nu îi permite să ajungă la toate. În orașul în care locuiește sunt m străzi bidirecționale și n intersecții numerotate cu numere de la 1 până la n. Festivalurile au loc în r intersecții. El pornește din intersecția cu numărul z.

Pentru a ajunge dintr-o intersecție în alta, folosește străzile. Când parcurge o stradă, el consumă o anumită energie, care diferă de la stradă la stradă.

După terminarea fiecărui festival, Tudor se va reîntoarce la casa lui, adică la intersecția cu numărul z, costul drumului de această dată fiind 0, pornind din nou la următorul festival.

Întrucât este un om foarte dedicat muzicii, Tudor vrea să participe la cât mai multe festivaluri, dar fără să-și depășească puterea lui fizică p.

Determinați numărul maxim de festivaluri la care poate participa.

Se dă o matrice pătratică de dimensiune n. Să se calculeze determinantul ei.

Dijkstra are nevoie de ajutorul vostru pentru a-și duce la bun sfârșit datoria. Acesta vrea să afle drumurile de lungime minimă de la casa prietenului său Vlad la celelalte case ale vecinilor. Nu are foarte mult timp la dispoziție așa ca trebuie să vă mișcați repede. Îl veți ajuta?

Un nou joc vă este adus de Vlad. O tablă de n*m căsuțe goale, câteva cartonașe și o singură întrebare! Voi știți răspunsul?

#1886 Rucsac1

Într-un magazin sunt n obiecte; pentru fiecare se cunoaște greutatea G și valoarea V. Un hoț intră în magazin având un rucsac ce poate transporta o greutate maximă GMax. El va fura anumite obiecte, astfel încât suma greutăților obiectelor furate să nu depășească GMax.

Să se stabilească câștigul maxim pe care îl poate obține hoțul. Câștigul este egal cu suma valorilor obiectelor furate.

#1760 Optim

Gigel primea de la mama lui, ca temă, o foaie pe care era scris un şir de N numere întregi. Singurul calcul pe care ştia să îl facă până acum era suma tuturor numerelor. Pentru aceasta el plasa N-1 semne de adunare, +, între numerele aflate pe poziţii consecutive în şir şi calcula astfel suma acestor numere. Între timp a crescut şi a învăţat şi operaţia de înmulţire pentru care foloseşte semnul *. Din şirul celor N-1 semne de adunare, îi trece prin minte să înlocuiască K semne + cu K semne *.
Îşi dă seama că tema se complică, deoarece înmulţirile trebuie efectuate înaintea adunărilor, dar nu se dă bătut şi duce calculul până la capăt.
Scrieţi un program care să determine valoarea minimă pe care o poate obţine şi valoarea maximă pe care o poate obţine după înlocuirea menţionată.

ONI 2012, Clasa a VIII-a

Dându-se un graf conex, să se determine componentele biconexe, punctele de articulaţie şi muchiile critice ale acestuia.

#1876 SCLM2

Doi prieteni te provoacă la un joc. Cerința este simplă: trebuie doar să ghicești lungimea maximă a unui subșir crescător al șirului dat. Accepți provocarea?

#1877 kMax

Se dă un șir cu n elemente, numere întregi, și un număr natural k ≤ n. Calculați cea mai mare sumă care poate fi obținută schimbând semnul a exact k elemente aflate pe poziții distincte din șirul dat.

#1867 cuvant2

Oricare cuvânt care nu este de tip palindrom se poate separa în mai multe părți care, fiecare, să fie de tip palindrom. Care este numărul minim de secvențe de tip palindrom în care se poate separa un cuvânt și care este cea mai mare lungime a unei asemenea secvențe?

#1872 Palin

Dându-se un cuvânt format din litere mari și mici ale alfabetului englez și cifre, să se afle numărul minim de caractere care pot fi inserate în cuvânt pentru a deveni PALINDROM. Caracterele pot fi inserate oriunde în cuvânt.

IOI 2000, enunt modificat

#1870 easyxy

Se dă un vector v cu N elemente numere naturale numerotate de la 1 la N și M întrebări de forma:

  • x y p: se afișează valoarea ce s-ar afla pe poziția p dacă v[x...y] ar fi ordonat crescător.

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

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

#1861 TopSort

Se dă un graf orientat aciclic cu N noduri numerotate de la 1 la N. Să se realizeze o sortare topologică a nodurilor.

Rufus pleacă din punctul de linie 1 și coloană 1 al matricei, iar Rufia îl asteaptă în punctul de linie N și coloană M. Fiind un teren accidentat, acesta consumă o anumită energie și un anumit timp pentru a ajunge dintr-un punct în unul din cele maxim 8 puncte vecine ale sale, cu condiția să rămână în interiorul spațiului bine delimitat.
Energia consumată pentru a ajunge în punctul de linie i și coloană j din unul din punctele sale vecine este dată de valoarea lui | A[i][j] | (valoarea lui A[i][j] în modul ), iar timpul consumat pentru a ajunge în acest punct dintr-un punct vecin este dat de valoarea T[i][j].

Ajutați-l pe Rufus să ajungă la prietena sa Rufia în cel mai scurt timp posibil și găsiți, de asemenea, capacitatea fizică inițială minimă, știind că aceasta poate fi cel mult K.

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

#1855 Heap

Se consideră o colecție de numere naturale, inițial vidă. Asupra ei se fac două tipuri de operații:

  • 1 x – valoarea x se adaugă în colecție;
  • 2 – cea mai mare valoare din colecție se afișează, apoi se elimină din colecție.

Dându-se un șir de m operații, să se afișeze în ordine rezultatele operațiilor de tip 2.

Se dau n numere naturale, reprezentând în ordine valorile nodurilor dintr-un arbore binar complet și m operații de tip 1 sau 2, aplicate unui nod k.

Operația de tip 1 determină valoarea nodului părinte a lui k, iar operația de tip 2 determină suma valorilor fiilor nodului k. Dacă k=1 sau dacă nodul k nu are fii, rezultatul va fi 0.

Afișați pentru fiecare operație rezultatul ei.

Călin este supărat și stă pe o bancă. Prin fața lui trec Q perechi de mașini care o iau pe scurtătură (o pereche este formată din două maşini). Mașinile sunt numerotate de la 1 la N. Valoarea unei mașini este reprezentata de numărul ei. Aceeași mașina poate să treacă de maxim două ori prin fața lui Călin.

Ajutați-l pe Călin să aleagă din fiecare pereche câte o maşină, astfel încât suma mașinilor sa fie maximă. De asemenea, Călin vrea să știe câte dubluri a ales.

#1841 fortuna

În orășelul Cota trăiesc N oameni între care se cunosc M relații de prietenie. Atunci când persoana K este afectată de boala Fortuna, maladia începe să se răspândească la toți prietenii săi și apoi mai departe, la prietenii prietenilor, până când toată populația va fi afectată. În ziua D după îmbolnăvirea cu boala Fortuna, un om va avea boala Fortuna de grad D. Știind aceste informații, Doctorul Bilet îi poate vindeca doar după ce toți oamenii vor fi afectați, iar fiecare va avea boala de cel puțin gradul P.
Sarcina ta este sa îi ajuți pe oamenii din orășelul Cota să afle după câte zile vor putea fi vindecați.

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

#1837 Scufita

Majoritatea participanţilor la ONI2003 au auzit, în copilărie, povestea Scufiţei Roşii. Pentru cei care o ştiu, urmează partea a doua; pentru cei care nu o ştiu, nu vă faceţi griji, cunoaşterea ei nu este necesară pentru a rezolva această problemă. Povestea nu spune ce s-a întâmplat pe drumul pe care Scufiţa Roşie s-a întors de la bunicuţă. Veţi afla amănunte în continuare.

Pe drum, ea s-a întâlnit cu Lupul (fratele lupului care a părăsit povestea în prima parte). Acesta dorea să o mănânce, dar a decis să-i acorde o şansă de scăpare, provocând-o la un concurs de cules ciupercuţe.

Scufiţa Roşie se află în poziţia (1,1) a unei matrici cu N linii şi N coloane, în fiecare poziţie a matricei fiind amplasate ciupercuţe. Lupul se află în poziţia (1,1) a unei alte matrici similare. Pe parcursul unui minut, atât Scufiţa, cât şi Lupul se deplasează într-una din poziţiile vecine (pe linie sau pe coloană) şi culeg ciupercuţele din poziţia respectivă. Dacă Scufiţa Roşie ajunge într-o poziţie în care nu sunt ciupercuţe, va pierde jocul. Dacă la sfârşitul unui minut ea are mai puţine ciupercuţe decât Lupul, ea va pierde jocul de asemenea. Jocul începe după ce amândoi participanţii au cules ciupercuţele din poziţiile lor iniţiale (nu contează cine are mai multe la începutul jocului, ci doar după un număr întreg strict pozitiv de minute de la început). Dacă Scufiţa Roşie pierde jocul, Lupul o va mânca.

Înainte de începerea jocului, Scufiţa Roşie l-a sunat pe Vânător, care i-a promis că va veni într-un sfert de oră (15 minute) pentru a o salva. Deci Scufiţa Roşie va fi liberă să plece dacă nu va pierde jocul după 15 minute.
Din acest moment, scopul ei este nu numai să rămână în viaţă, ci şi să culeagă cât mai multe ciupercuțe, pentru a le duce acasă (după ce va veni, vânătorul nu o va mai lăsa să culeagă).

Lupul, cunoscut pentru lăcomia sa proverbială, va alege la fiecare minut mutarea în câmpul vecin cu cele mai multe ciupercuțe (matricea sa este dată astfel încât să nu existe mai multe posibilităţi de alegere la un moment dat).
Povestea spune că Scufiţa Roşie a plecat acasă cu coşuleţul plin de ciupercuțe, folosind indicaţiile date de un program scris de un concurent la ONI 2003 (nu vom da detalii suplimentare despre alte aspecte, cum ar fi călătoria în timp, pentru a nu complica inutil enunţul problemei). Să fi fost acest program scris de dumneavoastră? Vom vedea…

Scrieţi un program care să o ajute pe Scufiţa Roşie să rămână în joc şi să culeagă cât mai multe ciupercuţe la sfârşitul celor 15 minute!

ONI 2003, clasa a X-a

#1824 Pitic

Carmen, piticul de gradina vrea sa meargă în vizita la piticul Tulosba. Pentru a ajunge la Tulosba, Carmen trebuie sa meargă printr-o rețea de N galerii, fiecare alcătuită din M sectoare.

Rețeaua poate fi reprezentată printr-un tablou cu N linii, numerotate de la 1 la N și M coloane, numerotate de la 1 la N. Carmen ocupă sectorul 1 al galeriei 1. Tulosba ocupă sectorul M al galeriei 1.

La galeria n se termina rețeaua și începe gradina unde sunt niște copii răi care vor sa-l spargă pe Carmen cu bâtele de Baseball.

Dacă sectorul curent a lui Carmen este (i,j), atunci se poate deplasa:

  • La dreapta, ajungând în sectorul (i,j+1) .
  • Pe diagonala la dreapta în sus, ajungând în sectorul (i+1,j+1).
  • Pe diagonala la dreapta în jos, ajungând în sectorul (j+1,i-1) .

Sa se afișeze în câte moduri poate Carmen sa ajungă la Tulosba.

#1832 pd

Se dă un număr natural s. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe s ca produs de divizori proprii distincți ai lui s.

Programatoarea Petra a început un curs de criptografie. Fiind un spirit creativ, Petra a creat deja o metodă elaborată de criptare a unei parole sub forma unei perechi (tabel de litere aparţinând mulţimii {‘a’...’z’}, dicţionar de cuvinte). Din păcate pentru Petra, metoda ei de criptare a parolei, poate fi decriptată de oricine astfel:

  • se iau tabelul de litere şi dicţionarul de cuvinte permise
  • se listează, sortează şi numără toate cuvintele care se găsesc în tabel. Un cuvânt \(c_1c_2:::c_k\) care există în dicţionar există şi în tabel dacă, fiecare literă ci apare în tabel şi pentru i>1, \(c_i\) este vecină în tabel cu litera \(c_{i-1}\).
  • din lista sortata de T perechi (\(cuvânt_i\), \(a_i\)), unde \(cuvânt_i\) este un cuvânt iar \(a_i\) este numărul de apariţii în tabel, reconstituie litera \(p_i\) a parolei astfel: \(p_i =\) ‘a’ + ( \(a_i\) mod 26). Încercând să îmbunătăţească algoritmul, Petra a decis să înlocuiască unele litere din tabel cu semnul întrebării '?'. Un semn '?' poate fi înlocuit cu orice literă când se parcurge tabelul. Convinge-o pe Petra că, în ciuda îmbunătăţirii, îi poţi găsi parola pornind de la orice pereche de (dicţionar, tabel de litere) dată.

Concursul EMPOWERSOFT, 2016

#1825 zoomba

În țara Zoomba trăiesc K prieteni, fiecare în localități diferite. În această țară se găsesc N orașe, oricare două fiind legate prin cel mult o șosea bidirecțională. Deoarece nu s-au mai întâlnit de mult, cei K prieteni s-au hotărât să se reîntâlnească într-un oraș. Fiecare are câte o mașină cu număr nelimitat de locuri. Pentru a trece de la un oraș la altul, o mașină consumă 1 litru de benzină.

Știind că odată ce au ajuns în același oraș 2 sau mai mulți prieteni, aceștia iși pot continua drumul cu o singură mașină, să se determine consumul minim de benzină pentru ca aceștia să ajungă în orașul Z.

Alex s-a decis să organizeze pentru colegii lui un concurs de orientare turistică, pe care l-a intitulat “Treasure Hunt”, nu pentru că ar fi avut ceva bogății de ascuns, ci pentru a-i face curioși și a-i mobiliza să mai lase puțin joaca pe calculator și să facă mișcare în aer liber. Pentru aceasta el a cercetat terenul pe care s-a decis să organizeze acest concurs și a identificat n puncte posibile de amplasare a posturilor de control, prin care concurenții să treacă obligatoriu și de unde să primească indicii referitoare la următorul punct. Bineînțeles că în punctele de control există și “comori” ascunse, care au asociate anumite punctaje, de valori cunoscute. A notat pe o hartă coordonatele (x,y) ale acestor puncte, în ordinea necesară parcurgerii lor, dar și altitudinea la care se
află acestea și punctajul p atribuit “comorii” din acel punct. Problema a apărut mai târziu, atunci când Alex s-a decis să nu lase un concurent să se oprească în toate punctele, pentru că atunci colegii lui ar găsi un motiv să mai tragă de timp pentru a se odihni și concursul ar dura prea mult. Așa că a stabilit să permită maxim M opriri din cele N puncte, cu condiția ca între două opriri succesive distanța de pe traseu să nu fie mai mică decât o valoare impusă, d, stabilită de Alex printr-o metodă proprie. Trecerea prin toate punctele este obligatorie, așa că distanța se calculează ca suma distanțelor dintre puncte. Curios din fire, Alex vrea să știe:

  • Care este efortul total pentru parcurgerea întregului traseu și care este distanța maximă între două puncte de pe traseu. Efortul trebuie calculat după o formulă pe care tot Alex a stabilit-o ca suma eforturilor de pe fiecare tronson în parte, definit astfel
    \( e =
    \begin{cases}
    𝑑 + 𝑑 ∗ ∆ℎ/10 & \text {, 𝑑𝑎𝑐a 𝑢𝑟𝑐a} \\
    𝑑 + 𝑑 ∗\frac{|∆ℎ|}{5∗10} & \text{, 𝑑𝑎𝑐a 𝑐𝑜𝑏𝑜𝑎𝑟a} \\
    \end{cases} \), unde ∆ℎ este diferența de altitudine dintre două puncte consecutive de pe traseu, chiar dacă în acestea concurentul nu se oprește.
  • Care este punctajul maxim pe care îl poate obține un concurent, și care ar trebui să fie punctele de control în care să se oprească pentru a le obține. Din păcate Alex nu e prea bun la informatică, așa ca vă roagă pe voi să-l ajutați.

Concursul EMPOWERSOFT, 2016

#1816 Unicorn

Este ziua unicornului Corn şi prietenii lui vor să-i pregătească o surpriză, un mare turn de clătite! Totul trebuie să fie perfect, și toată lumea știe că cel mai frumos turn are formă de corn (clătitele sunt așezate în ordine strict descrescătoare după rază). Ei pregătesc clătite de diferite mărimi și le așază una peste alta. Fiecare clătită are o anumită valoare nutritivă. După ce termină de gătit, aceștia vor să creeze un turn de clătite in formă de corn pentru prietenul lor Corn. Astfel, unicornii pot alege să mânance oricâte clătite vor, clătitele rămase păstrându-și ordinea inițială. Clătitele care rămân în farfurie (pastrând ordinea inițială) trebuie să aibă formă de corn (strict descrescător după rază). Deoarece Corn adoră clătitele, ei vor ca turnul Corn format din clătitele rămase după ce aceștia mănâncă să aibă cea mai mare valoare nutritivă (suma valorilor nutritive ale clătitelor rămase).

Concursul EMPOWERSOFT, 2016

Scrieți un program care citeşte o valoare naturală impară pentru n şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din n litere mici care îndeplinesc următoarele proprietăţi:

- încep şi se termină cu a;
- oricare două litere alăturate dintr-o combinaţie sunt consecutive în alfabet.

Un program citeşte o valoare naturală nenulă impară pentru n şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din n cifre care îndeplinesc următoarele proprietăţi:

- încep şi se termină cu 0;
- modulul diferenţei între oricare două cifre alăturate dintr-o combinaţie este 1.

La un concurs au participat N elevi, fiecare având punctaj un număr natural. Comisia dorește să găsească un subșir de sumă maximă, punând următoarea condiție: pentru fiecare elev există o limită atât la stânga left [] cât și la dreapta right [] în care nu se mai poate alege un alt elev. Cu alte cuvinte, dacă am selectat punctajul elevului i pentru subșir, nu mai putem selecta un elev din intervalul [ i­-left[i] , i+right[i] ].

Ajutați comisia să găsească subșirul de sumă maximă.

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

#1794 aint

Se dă un vector cu N elemente numere naturale numerotate de la 1 la N și M operații de forma:

  • 1 x y, cu semnificația: elementul de poziția x ia valoarea valoarea y.
  • 2 x y: se determină valoarea minimă a elementelor cu indici cuprinși între x și y.

Afișați rezultatele operațiilor de tipul 2.

#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

#1661 Fotbal1

Se dau 2 numere reprezentând scorul la fotbalul extraterestru. Să se afișeze în câte moduri poți ajunge la acel scor.

#1757 Sec

În timp ce-și bea sortimentul preferat de vin sec, vrăjitorului Arpsod i-a venit în minte o problemă de informatică ce are un enunț cel puțin la fel de sec și anume:
Dându-se un arbore binar cu N noduri și rădăcina în nodul 1, să se răspundă la Q întrebări de forma: “sunt cei doi fii ai nodului X identici?”

Doi fii sunt identici dacă au același număr de subarbori și aceștia sunt identici (mai exact, pentru orice i=1, 2, ..., N subarborele i al primului este identic cu subarborele i al celui de-al doilea).

Cunoscându-se arborele, să se răspundă la cele Q întrebări de forma indicată în enunţ.

Concursul EMPOWERSOFT, 2016

Se citesc doua matrice din fisier . Sa se calculeze produsul lor .

#1747 Lacusta

Se consideră o matrice dreptunghiulară cu m linii şi n coloane, cu valori naturale. Traversăm matricea pornind de la colţul stânga-sus la colţul dreapta-jos. O traversare constă din mai multe deplasări. La fiecare deplasare se execută un salt pe orizontală şi un pas pe verticală. Scrieţi un program care să determine suma minimă care se poate obţine pentru o astfel de traversare.

OJI 2005, clasa a X-a

Se dă un graf neorientat conex cu n vârfuri și număr par de muchii. Să se determine un graf parțial al celui dat care să fie conex și să fie obținut prin eliminarea a jumătate din numărul de muchii.

#1737 KSiruri

Se consideră un număr natural K și o secvență de N șiruri s[1], s[2], …, s[N]. Fiecare șir este format din cifre distincte. Pentru două șiruri s[i] și s[j] se definește operația de scădere () astfel: s[i]-s[j] va conține doar șirul de cifre care apar în s[i], dar nu apar în s[j]. De exemplu, dacă s[i]=(1,3,8) și s[j]=(2,9,3), atunci s[i]-s[j]=(1,8). Această operație nu este asociativă, (s[i]-s[j])-s[p] este diferită de s[i]-(s[j]-s[p]). De aceea, dacă se alege un subșir s[i1], s[i2], …, s[ip] din secvență, atunci convenim ca s[i1]-s[i2]-...-s[ip] să se execute de la dreapta la stânga.

Exemplu: (1,2,3)-(2,3)-(1,3)=(1,2,3)-(2)=(1,3). S-au obținut două cifre distincte.

Să se determine numărul subșirurilor nevide s[i1], s[i2], …, s[ip] din secvența s[1], s[2], …, s[N] asupra cărora, dacă se efectuează operația de scădere (adică s[i1]-s[i2]-...-s[ip]), se obțin cel puțin K cifre distincte. Pentru că numărul subșirurilor poate fi foarte mare, atunci el se va calcula modulo 123457.

Lot Juniori Magurele, 2016

#1736 Cuie

Pe o scândură se găsesc înfipte și aliniate N cuie de diverse înălțimi, măsurate în centimetri.

La fiecare ”bătaie” de ciocan într-un cui, acesta pătrunde în scândură cu 1 cm. Tâmplarul dorește să obțină cea mai lungă secvență de cuie de aceeași înălțime, după aplicarea a cel mult M ”bătăi” de ciocan.

Să se determine lungimea maximă – L a unei secvențe de cuie de aceeași înălțime în condițiile date și numărul minim de ”bătăi” – K necesare obținerii acesteia.

Lot Juniori Magurele, 2016

#1734 smax

Un muzeu al diamantelor își are sediul într-o clădire cu formă cubică cu N etaje, numerotate de la 1 la N. În fiecare camera se află un diamant cu valoarea cunoscută. Niște hoți vor sa fure diamantele si trebuie să aleagă cel mai profitabil traseu care să pornească din camera cu eticheta 1 1 1 și să ajungă în camera cu eticheta N N N și care, bineînțeles, să le permită să obțină o sumă maximă din vânzarea diamantelor furate din camerele prin care au trecut în traseu ales.

Concurs Național de Soft Grigore Moisil – Lugoj, 18-22 mai 2016, clasele 11-12.

Concursul Național de Soft Grigore Moisil - Lugoj, 2016

#1732 Para

Terenul de golf al unei persoane bogate, s-o numim P. are formă dreptunghiulară și se compune din NxM parcele de forma pătrată, aflate la intersecția celor N rânduri cu cele M coloane.

P. este paranoic. El nu suportă ideea că cineva ar putea să pătrundă neinvitat pe terenul lui și să-i calce iarba. În consecință, în fiecare noapte el își plasează toți cei K câini de pază pe câte una dintre parcelele terenului de golf. Dar câinii sunt la rândul lor paranoici și niciunul dintre ei nu suportă să vadă decât cel mult un alt câine, dacă privește de-a lungul rândului și coloanei pe care este amplasat.

P. și-a construit un punct de observație pe parcela aflată pe linia N și coloana M, iar acolo este singurul loc unde nu va plasa un câine de pază.

Cunoscând dimensiunile terenului de golf, să de determine numărul de posibilități modulo 30011 în care P. își poate plasa câinii pe terenul său de golf.

Lot Juniori Magurele, 2016

În țara lui Oblio toate lucrurile sunt sub formă de triunghi. Chiar și fotografiile sunt sub formă de triunghi. Fotografiile sunt formate din pixeli, care evident, la rîndul lor sunt triunghiuri ca în figura de mai jos.

Fotografiile sunt alb negru și fiecare pixel este identificat prin rândul pe care se găsește și prin poziție, adică al câtelea triunghi este în rândul respectiv numărând de la 1, d­e la stânga la dreapta. Fiecare pixel are culoarea alb sau negru. Fiecare pixel are dimensiunea 1, dar mai mulți pixeli vecini pot forma triunghiuri cu vârful în sus cu laturi de diferite lungimi. În figura din dreapta avem 3 triunghiuri de dimensiune 1 (rândul 2 poziția 1, rândul 3 poziția 1, rândul 3 poziția 3) și un triunghi de dimensiune 2 (cu colțurile: în rândul 2 poziția 1, rândul 3 poziția 1 și rândul 3 poziția 3).

Se știe că în fotografie sunt n rânduri și m pixeli albi, fiecare pixel fiind identificat prin rând și poziție.

Se cere să se determine, pentru p lungimi de laturi date, câte triunghiuri de culoare neagră (adică pline numai cu pixeli de culoare neagră) și cu vârful în sus se găsesc în fotografie pentru fiecare lungime.

Lot Juniori Focsani, 2016

#1716 KDS

Se consideră un șir de numere naturale a[1], a[2], …, a[n] așezate circular. Acest lucru înseamnă că a[1] are ca vecini numerele a[n] și a[2], iar a[n] are ca vecini pe a[n-1] și a[1]. Se consideră de asemenea un număr natural K.

Să se determine suma maximă care se poate obține din exact K secvențe nevide, disjuncte și ne-vecine.

Lot Juniori Focsani, 2016

Ludwig are o permutare p=(p[1],p[2],...,p[N]) a mulțimii {1,2,..,N} și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică p[1], și îl așează pe masă. Al doilea număr, p[2], îl pune fie în stânga lui p[1], fie în dreapta lui p[1]. La fiecare pas, dacă s-au așezat pe masă deja numerele p[1], p[2], …, p[i], atunci numărul p[i+1] este pus fie în stânga numerelor deja așezate, fie în dreapta lor.

Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.

Lot Juniori Focsani, 2016

#1712 Centura

Pe șoseaua care duce spre intrarea în oraș se află n autovehicule, dintre care m
sunt autovehicule de gabarit redus, pe care le vom numi în continuare autoturisme, iar restul sunt de gabarit mare și le vom numi camioane. Orașul are o șosea ocolitoare, numită popular centură. Camioanele trebuie să ocolească orașul
trecând în mod obligatoriu pe drumul de centură. Autoturismele pot continua drumul pe șoseaua care intră în oraș sau pot ocoli orașul intrând pe șoseaua de centură. Pe centură, camioanele circulă cu viteză redusă îngreunând traficul.

De aceea s-a impus restricția R: nu vor fi admise pe drumul de centură coloane formate din mai mult decât k camioane consecutive.

Cunoscând n, k și distribuția autovehiculelor pe șosea, să se determine două numere naturale V și T, unde V reprezintă numărul de variante de dirijare a traficului astfel încât să fie respectată restricția R, iar T reprezintă numărul minim de autoturisme care trebuie să fie deviate pe drumul de centură pentru a se respecta aceeași restricție R.

Lot Juniori Focsani, 2016

#1707 Retea

Se consideră o rețea formată din n servere, numerotate de la 1 la n. În rețea există m perechi de servere x y cunoscute între care există legături de comunicație directe. Între oricare două servere din rețea există legături, fie directe, fie prin intermediul altor servere.

Stabiliți pentru fiecare dintre cele n servere dacă eliminarea sa din rețea conduce la pierderea legăturii dintre cel puțin două servere rămase.

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

Orașul Kruskal are n intersecții unite prin m străzi bidirecționale. Datorită ninsorii de peste noapte, străzile sunt acoperite cu zăpadă. Administratorul orașului, Gigel, a determinat cu mari eforturi pentru fiecare stradă costul deszăpezirii ei și acum dorește deszăpezirea unor străzi astfel încât costul total al deszăpezirii lor să fie minim, și să se poată circula între oricare două intersecții pe străzi deszăpezite.

Maleficul Costel îl forțează pe Gigel să deszăpezească numite străzi, din motive doar de el știute. Ajutați-l pe Gigel să determine costul minim pentru deszăpezirea orașului, astfel încât să fie deszăpezite străzile dorite de Costel și să se poată circula între oricare două intersecții pe străzi deszăpezite.

#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

#1666 Arbrush

Eșuînd în a-și regăsi adevărata identitate, Brush se refugiază în magicul tărâm al arborilor. Arbotra o sună și îi dă următoarea problemă: se dă un arbore cu N noduri, o rădăcină fixată, și M întrebări de forma: câte perechi neordonate de noduri pot forma, luând noduri doar din subarborele nodului X (inclusiv pe X).

Tărâmul arborilor

#1652 RF

Se dă un graf orientat în care arcele au asociate costuri (numere naturale nenule). Să se determine câte arce (x,y) din graf au costul egal cu costul drumului de cost minim de la x la y.

#1651 Graf

Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică.

#318 Cerc

Se dau n numere naturale. Determinaţi o aranjare a acestor numere pe un cerc, astfel încât suma produselor de câte două numere vecine să fie maximă.

#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

#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

Înainte de a participa la Olimpiada Naționala de Informatică, Zoli s-a decis să se plimbe prin oraș. Orașul în care locuiește Zoli are forma unui arbore, fiecare nod reprezentând o locuință iar deplasarea între acestea se efectuează prin intermediul muchiilor.

Zoli dorește să determine lungimea maximă dintre oricare două locuințe din orașul său.

#1518 sudoku

Scrieţi un program care, pentru o matrice 9 x 9 dată, reprezentând un puzzle SUDOKU, determină o soluţie a unui astfel de puzzle.

Admitere Informatica Iasi, 2014

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

#1604 DMin

Se consideră un graf neorientat conex cu n vârfuri, numerotate de la 1 la n, şi m muchii. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de muchii al unui lanţ elementar care uneşte x cu y.

Se dau k perechi de vârfuri x y. Determinați pentru fiecare pereche distanța de la x la y.

Se dă lista muchiilor unui graf neorientat. Pentru fiecare componentă conexă numim cel mai mic vârf de ea reprezentant al componentei conexe.

Determinați reprezentantul componentei conexe cu cele mai multe vârfuri și câte noduri conține aceasta.

#1597 Vizita

După ce în problema Plata şi-a cumpărat biscuiţi, iar în problema Maraton şi-a făcut temele, Costy s-a hotărât să meargă în vizită la prietenul său Paul. Și pentru că Paul este prietenul său cel mai bun, bineînţeles că nu se va duce cu mâna goala. Va trece pe la magazin şi îi va cumpăra un pachet de biscuiţi. Marea problemă a eroului nostru este oraşul rău famat, la fiecare intersecţie existând pericole. Oraşul are forma de două triunghiuri dreptunghice isoscele cu un vârf comun, ca în figura următoare:

C 
X X
X X X
X X X B
      X X
      X X X
      X X X P 

C – reprezintă poziţia iniţială a lui Costy, care se va afla mereu în colţul din stânga sus.
B – reprezintă poziţia magazinului, care se va afla mereu în vârful comun al celor 2
triunghiuri.
P – reprezintă poziţia lui Paul, care se va afla mereu în colţul din dreapta jos.

Cum spuneam, la fiecare intersecţie există pericole. O intersecţie X[i][j] reprezintă intersecţia străzii orizontale i, cu strada verticală j. Gradul de periculozitate al unei intersecţii este un număr întreg X[i][j]. Definim gradul unui drum ca fiind suma gradelor intersecţiilor ce compun acel drum.

Costy poate merge de la o intersecţie X[i][j], doar la o intersecţie X[i][j + 1] (în dreapta) sau X[i + 1][j](în jos).

#1592 Plata

Eroul nostru, Costy merge la magazin pentru a-şi cumpăra biscuiţi. Vânzătorul îi spune că biscuţii costă S nasturi, şi că doreste ca plata lor să fie făcută cu n tipuri diferite de nasturi. De asemenea, vânzătorul precizează că ar dori ca numărul de nasturi din fiecare tip i să depăşească valoarea x[i], dar, să nu depăşească valoarea y[i]. Presupunând că baiatul are o infinitate de nasturi din fiecare tip şi că doreşte să rămână cu cât mai mulţi nasturi de tipurile n, n-1, n-2,.. în buzunar, ajutaţi-l să efectueze plata şi să pună cât mai repede mâna pe biscuiţi.

Info-Oltenia 2015

Se dă un şir de N numere întregi. Definim costul intervalului [x, y], unde x si y apartin {1, 2, …, N}, ca fiind suma diferenţelor dintre numărul maxim din șir, aflat în interval şi restul numerelor aflate pe pozițiile x, x+1, …, y.

De exemplu, pentru şirul 2 4 7 4 3 -1 2 4 6 costul intervalului [3, 6] este 15. (explicație: 7-7+ 7-4 + 7-3 + 7+1 = 15).

Se definesc M operaţii de forma tip x y, astfel: Dacă tip este 1, atunci elementul de pe poziţia x din șir devine y. Dacă tip este 2, atunci să se afişeze costul intervalului [x, y].

Să se determine răspunsul pentru fiecare operaţie de tipul 2.

Info-Oltenia 2015

#1551 DSLM

Se dă mulțimea V a arcelor unui graf orientat cu n vârfuri.
Să se determine drumul simplu de lungime maximă cu extremitatea inițială în vârful p din graf.

folclor

#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

Se dă o tablă de șah formată din n linii și m coloane, definind n*m zone, unele dintre ele fiind libere, altele conținând obstacole. În zona de coordonate 1 1 se află un cal care se poate deplasa pe tablă în L, ca la șah, fără a părăsi tabla, fără a trece prin zone care conțin obstacole și fără a trece de două ori prin aceeași zonă.

Determinați o modalitate prin care calul poate ajunge în zona de coordonate n m – unde se află o căpiță de fân.

Gigel participă la un concurs de informatică împreună cu echipa sa. Echipa sa este formată din n membri. Concursul este împărțit în mai multe nivele, numerotate de la 1 la n. După completarea primului nivel, următorul va fi disponibil și așa mai departe.

#1502 Virgule

Se consideră un şir de cifre zecimale (de la 0 la 9). În acest şir trebuie să inserăm virgule, separând astfel cifrele în scopul de a forma numere.

Scrieţi un program care să insereze virgule în şirul de cifre astfel încât să se obţină o secvenţă de numere strict crescătoare, iar ultimul număr din secvenţă să fie minim.

Olimpiada Municipala Informatica Iasi 2016

#1500 Nuclee

La cursul de comunicare organizat în vacanță, au participat N persoane, numerotate cu numere de ordine de la 1 la N. Fiecare persoană are la curs mai mulți prieteni apropiați, cărora le comunică orice informație imediat cum a aflat-o. Relaţiile de comunicare nu sunt bidirecţionale, cu alte cuvinte dacă persoana a îi transmite imediat informații persoanei b, nu este obligatoriu ca şi persoana b să transmită imediat informaţiile pe care le primeşte persoanei a.

Profesorul studiază relaţiile dintre participanţii la curs. El defineşte un nucleu de comunicare ca fiind un grup cu număr maxim de cursanţi cu proprietatea că oricare ar fi a şi b doi cursanţi din grup, dacă a primeşte o informaţie, aceasta va ajunge şi la cursantul b (direct sau prin intermediul altor cursanţi din grup).

Profesorul dorește să determine numărul de nuclee de comunicare existente la cursul său.

Cunoscând N, numărul de cursanţi, precum și prietenii fiecărui cursant, scrieţi un program care să determine numărul de nuclee de comunicare existente.

Olimpiada Municipala Informatica Iasi 2016

Să se determine toate submulţimile cu m elemente ale mulţimii divizorilor unui număr natural dat.

Se consideră un şir format din n numere naturale şi un număr dat k. Să se determine numărul secvenţelor din şir care au proprietatea că suma elementelor secvenţei este de cel puţin de k ori mai mare sau egală decât numărul elementelor secvenţei.

#1497 Nunta

La o nuntă sunt invitate n persoane, numerotate de la 1 la n. Se știe că o parte din ele se cunosc două câte două, fie că sunt rude, fie de la serviciu, fie sunt prieteni sau vecini. Astfel se vor forma un număr K minim de grupuri astfel încât în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pentru fiecare grup de cel puțin două persoane se stabileşte un lider – persoana cu numărul de ordine minim. Aceste grupuri vor fi numerotate de la 1 la K în ordinea crescătoare a numerelor de ordine ale liderilor. Ca sa se ivească cât mai puține situații stânjenitoare, organizatorul nunții ar dori să aranjeze o masă principală cu cel puţin n/2+1 invitaţi, la care să fie aşezate unul sau mai multe astfel de grupuri întregi numerotate cu valori consecutive.

Fiind date n, numărul de persoane, m, numărul de perechi de invitaţi care se cunosc între ei și cele m perechi, să se determine numărul minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut, precum şi numărul variantelor distincte în care se poate organiza masa cu cel puţin n/2+1 invitaţi din grupurile formate.

Olimpiada locală de Informatică, Prahova, 2016

#1488 Strazi

Gigel primeşte o nouă provocare de la prietenul său Programatorul! Cunoscând înălţimile clădirilor aflate pe o anumită stradă, Gigel trebuie să răspundă rapid la întrebarea: “Care este gradul de vizibilitate al străzii?”

Gradul de vizibilitate al unei străzi este dat de raportul dintre numărul clădirilor vizibile din capătul stâng al străzii şi numărul total al clădirilor de pe stradă, raport calculat cu trei zecimale.

Pentru o intersecţie de N străzi ajutaţi-l pe Gigel să determine gradul de vizibilitate al fiecărei străzi şi să precizeze care este strada cu grad maxim de vizibilitate.

Olimpiada locală de Informatică, Prahova, 2016

Scrieţi un program care încrucişează o mulţime de cuvinte într-un careu.

Admitere Informatica Iasi, 2013

#1462 Gasti

Să se determine câte găști există în orașul Nicăieri și în câte moduri se poate forma o nouă relație de prietenie, astfel încât, să se obțină o nouă gașcă, cu număr maxim de membri.

#1463 Tmax

Să se determine câte T-uri de sumă maximă există, precum și această sumă maximă.

#1431 Points

Fie o mulţime de n puncte diferite în plan cu coordonate naturale. Numim o submulţime nevidă ordonată a acestor puncte subșir descrescător dacă pentru oricare două puncte consecutive Ai(xi, yi) şi Ai+1(xi+1, yi+1) avem xi ≤ xi+1 şi yi ≥ yi+1.

Dându-se cele n puncte, calculaţi numărul de subșiruri descrescătoare care se pot forma.

#1370 pepeuri

Să se afle câte numere naturale cu n cifre au suma oricăror două cifre alăturate pătrat perfect.

Olimpiada Cunoaşterii

Fiind dată o matrice pătratică de dimensiune n cu valori 0 și 1, să se determine dimensiunea maximă a unei submatrice ce conține numai valori 1.

Concursul Interjudețean de Informatică „Memorial Ștefan Dârțu”, ediția a XI-a, 12 decembrie 2015, Vatra Dornei

#1427 Manager

Andrei este manager la o firmă foarte importantă, la care se lucrează în ture. Aceste ture durează un număr constant de minute (1017 minute), fiecare tură începând la minutul 1. După o tură, Andrei, fiind foarte obosit, doarme până la începutul următoarei ture.

El este foarte ocupat cu o mulțime de ședințe (S ședințe mai exact). Acestea sunt trecute în agenda lui astfel: Minutul de început Durata Minutele necesare pentru pregătire – în minutele de pregătire nu trebuie să îl deranjeze nimeni).

Agenda este foarte dezordonată, iar şedinţele nu sunt notate în ordine cronologică, şi, în plus, acestea se pot suprapune. Ca un bun manager, Andrei doreşte să participe la cât mai multe şedinţe într-o tură cu condiţia să nu se desfăşoare în acelaşi timp. Deoarece nu poate renunța la nicio ședință, el va amâna pentru turele viitoare unele dintre ședințele care se suprapun, păstrând în agendă aceleași informații despre fiecare (început, durată, timp necesar pentru pregătire).

a) Afișați numărul minim de ture în care Andrei poate participa la toate şedinţele.
b) Știind că în prima tură, Andrei poate să ajungă la toate şedinţele (nu se desfăşoară două sau mai multe şedinţe la un moment dat), determinați minutul în care se poate programa începutul pregătirii unei noi şedinţe de durată D şi timp de pregătire P, astfel încât să nu se suprapună cu o alta (dacă există mai multe soluţii se va afişa cea cu momentul de început minim).

Moisil++, 2015

Deoarece vin sărbătorile, elevii de la Liceul de informatică s-au gândit să decoreze laboratorul P1 cu ghirlande legate între ele. Ei au cumpărat N ghirlande numerotate de la 1 la N și vor să le lege împreună apoi să orneze laboratorul. Fiecare ghirlandă are doua culori distribuite astfel încât capetele să aibă culori diferite. Culorile sunt codificate prin numere naturale. Decoraţiunile cumpărate au N-1 culori care apar exact de două ori şi 2 culori care apar doar o singură dată. Pentru a face munca mai distractivă ei s-au gândit că, la legarea a două ghirlande, să unească două capete de aceeaşi culoare.

1) Pentru cerinţa 1 copiii vor să afle suma codurilor culorilor aflate la cele două capete ale lanţului format prin legarea ghirlandelor cumpărate, respectând regulile de îmbinare de mai sus.
2) Pentru cerinţa 2 ajutaţi-i să lege ghirlandele pentru a decora laboratorul P1 respectând regulile menţionate. Trebuie sa afisati numerele de ordine ale ghirlandelor în ordinea în care vor fi legate. La cele doua capete se vor afla
cele doua ghirlande care conțin o culoare ce apare o singura data. Dintre acestea prima va fi cea care are codul culorii mai mic

Moisil++, 2015

Se dau două matrice cu elemente numere întregi. Calculați diferența dintre prima și a doua matrice.

#1395 MSuma

Se dau două matrice cu elemente numere întregi. Calculați suma lor.

#550 Mere

Țăranul Ion are în livada sa N pomi, fiecare cu v[i] mere. Între pomi există N-1 cărări, astfel încât între oricare doi pomi să existe un singur drum, alcătuit eventual din mai multe cărări. Pentru că nu și-a plătit ratele la bancă, el este nevoit să vândă o parte dintre pomi. El vrea să adune merele din livadă, dar pentru că nu are foarte mult timp, el va aduna merele doar dintr-o parte din pomi.

Ion pornește din pomul lui preferat, pomul 1, și se deplasează spre unul din vecinii lui. Pentru că nu este foarte inteligent, atunci când Ion se află la un pom, el se va deplasa către pomul vecin care are cele mai multe mere, fără să ia în calcul ceilalți meri din livadă. Dacă doi pomi au același număr de mere, atunci Ion se va deplasa spre pomul cu numărul de ordine mai mic.

Ajutați-l pe Ion să afle câte mere va aduna folosind metoda sa!

#1385 Joc6

Dom’ Profesor Unu și Dom’ Profesor Doi au găsit o matrice cu n linii numerotate de la 1 la n și n coloane numerotate de la 1 la n și elemente numere naturale. Semnificativ marcați de algoritmul de determinare a celui mai lung subșir crescător, au inventat pe loc un joc:

  • liniile cu indice impar aparțin lui Dom’ Profesor Unu, cele cu indice par aparțin lui Dom’ Profesor Doi;
  • pentru fiecare linie a sa, Dom’ Profesor Unu determină lungimea maximă a unui subșir crescător;
  • pentru fiecare linie a sa, Dom’ Profesor Doi determină lungimea maximă a unui subșir descrescător;
  • scorul fiecărei linii este lungimea determinată;
  • scorul total al fiecărui Dom’ Profesor este egal cu suma scorurilor liniilor corespunzătoare;
  • jocul este câștigat de Dom’ Profesor cu scorul total mai mare.

Determinați scorului fiecărui Dom’ Profesor și stabiliți câștigătorul.

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Pentru a intra într-o cameră se plătește o sumă cunoscută, exprimată în lei. Intrarea în clădire este în camera de coordonate (1,m), iar ieșirea în camera de coordonate (n,1). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j-1), fără a părăsi clădirea.

Dom’ Profesor intră în clădire având asupra lui o sumă S, parcurge un șir de camere după regula precizată și iese din clădire, plătind în fiecare cameră taxa corespunzătoare. Determinați suma maximă pe care o poate avea persoana după ce iese din clădire.

Într-un laborator de analize chimice se utilizează N reactivi. Se ştie că, pentru a evita accidentele sau deprecierea reactivilor, aceştia trebuie să fie stocaţi în condiţii de mediu speciale. Mai exact, pentru fiecare reactiv x, se precizează intervalul de temperatură [minx, maxx] în care trebuie să se încadreze temperatura de stocare a acestuia.
Reactivii vor fi plasaţi în frigidere. Orice frigider are un dispozitiv cu ajutorul căruia putem stabili temperatura (constantă) care va fi in interiorul acelui frigider (exprimată într-un număr întreg de grade Celsius).

OJI 2004, Clasa a IX-a

#1262 subsecv

Se dau n numere naturale. Să se găsească o subsecvență, astfel încât suma elementelor din această subsecvență să fie divizibilă cu n.

#1340 Rucsac

Într-un magazin sunt n obiecte; pentru fiecare se cunoaște greutatea G și valoarea V. Un hoț intră în magazin având un rucsac ce poate transporta o greutate maximă GMax. El va fura anumite obiecte, sau porțiuni de obiecte, astfel încât suma greutăților obiectelor furate să nu depășească GMax.

Să se stabilească câștigul maxim pe care îl poate obține hoțul. Câștigul este egal cu suma valorilor obiectelor furate. Câștigul adus de o fracțiune de obiect este direct proporțional cu greutatea fracțiunii.

#1356 nsir

Să se determine toate șirurile a de k numere naturale nu neapărat distincte: 1 ≤ a1, a2,...,ak ≤ n, astfel încât:
1) 1 = 1/a1+ 1/a2+...+ 1/ak
2) n = a1 + a2 +...+ ak

La magazinul din colț au fost aduse n cutii, numerotate de la 1 la n, fiecare conținând un anumit număr de bomboane. Administratorul magazinului hotărăște, pentru bunul mers al afacerilor, că bomboanele trebuie rearanjate în cutii, astfel încât fiecare cutie să conțină același număr de bomboane. Pentru aceasta, administratorul magazinului realizează în mod repetat următoarea operație: mută un număr oarecare de bomboane din cutia cu număr maxim de bomboane în cea cu număr minim de bomboane.

Determinați un șir minim de operații prin care toate cutiile conțin același număr de bomboane.

#1354 varf

Se consideră un şir a cu n numere naturale distincte: a1, a2,..., an.

Să se genereze în ordine lexicografică toate subşirurile vârf ale şirului a, de lungime k≥3.

Fie n un număr natural.
Să se determine toate posibilitățile de alegere a semnelor + și - pentru care
n = (+|-) 12 + (+|-) 22 + ... + (+|-) n2

#1355 sirab

Să se genereze toate şirurile strict crescătoare de n numere naturale nenule cel mult egale cu S și cu proprietatea că oricare ar fi a şi b două numere dintr-un astfel de şir a-b divide a+b.

Se considera un vector cu n elemente. Sa se afle cate subsiruri strict crescatoare de lungime p se pot forma folosind numerele sale.

#1342 NrSubsirCresc C++

Se consideră un vector cu n elemente. Să se afle cate subşiruri strict crescătoare se pot forma folosind numerele sale.

#1341 Protest

În țara lui Zoli trăiesc n persoane, numerotate de la 1 la n, iar Zoli are numărul de ordine 1. Zoli s-a săturat de sistemul politic, așa că s-a decis să iasă în stradă. Deoarece Zoli este o persoană sociabilă, are prieteni din diverse cercuri pe care s-a gândit să îi cheme cu el. Zoli își va anunța prietenii, care la rândul lor își vor anunța prietenii și așa mai departe.

Știm însă că unele persoane sunt scandalagii, iar Zoli este un om pașnic și preferă să nu trimită invitația acestora.

Zoli vă cere să îi spuneți numărul de persoane cu care se va întâlni la protest.

Se dă un număr natural n. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale.

#1327 SirPIE

Se citeşte un număr natural nenul n, apoi n numere naturale distincte. Să se afişeze, în ordine lexicografică, șirurile din cele n valori cu proprietatea că oricare două valori învecinate sunt prime între ele.

Fie n un număr natural nenul și mulțimea A={1,2,3,...,n}. Să se determine toate partițiile disjuncte ale mulțimii A.

folclor

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Să se verifice dacă graful este bipartit.

Se dau două cifre a b și un număr n. Să se genereze toate numerele cu exact n cifre cuprinse între a și b.

Se dau două numere n m. Să se genereze toate numerele cu exact n cifre mai mici decât m cu proprietatea că diferența în valoare absolută dintre oricare două cifre consecutive este cel puțin 2.

Se dau două numere n m. Să se genereze toate numerele cu exact n cifre mai mici decât m cu proprietatea că prima și ultima cifră sunt egale.

Se dă un număr natural n. Să se genereze toate numerele cu exact n cifre prime.

Se dau două numere n m. Să se genereze toate numerele cu exact n cifre mai mici decât m.

Se citește un număr natural nenul n. Să se afişeze, în ordine lexicografică, toate submulțimile nevide ale mulţimii {1,2,..,n} pentru care diferența dintre oricare două elemente este mai mare decât 1.

Se dau n mulțimi. Să se genereze în ordine lexicografică elementele produsului cartezian al mulțimilor date.

Se dau două numere naturale nenule n și m. Considerăm mulțimea A={1,2,..,n}. Să se genereze în ordine lexicografică elementele produsului cartezian \( A^m=A \times A \times \cdots \times A \).

#1281 Regine1

Se consideră o tablă de șah de dimensiune n. Să se plaseze pe tablă n regine astfel încât să nu existe două regine care să se atace.

Să se calculeze câte numere naturale în intervalul [A, B] au suma cifrelor un număr prim.

#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

#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

#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

#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

#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

#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

#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

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

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

#1184 Epuras

Epur iepurașul dorește să epureze niște apă folosind stațiile de epurare aflate pe o câmpie de formă pătrată având latură n. Epur iepurașul începe să epureze de la stația de epurare aflată la coordonatele (1, 1). După ce apa epurată la stația de epurare de pe coordonatele (x, y) e pură, Epur se va deplasa la o stație care are ambele coordonate mai mari sau egale cu coordonatele curente. Epur Iepurașul este obligat de Legea Epurării pentru Iepuri să epureze și la stația situată la coordonatele (n, n).

Se știe că fiecare stație de epurare oferă un grad de puritate număr întreg. Când Epur iepurașul își epurează apa la stația aflată la (x, y), gradul de puritate ale apei sale crește cu gradul oferit de stația de epurare folosită.

Ajutați-l pe Epur Iepurașul ca, epurând apa sa la stațiile de epurare să obțină un grad de puritate maxim.

Un număr natural se numește SuperPerfect dacă cifrele sale sunt pătrate perfecte și suma oricăror două cifre alăturate este pătrat perfect. Se cere să se afle câte numere SuperPerfecte cu N cifre există.

#711 desc

Fie n un număr natural nenul, n > 1. Definim n(p) ca fiind descompunerea lui n în sumă de puteri naturale distincte ale numărului prim p.

Să se scrie un program care citeşte un număr natural n şi determină toate n(p) descompunerile numărului n.

Lot Juniori, Botosani, 2012

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

#556 Flici

Un flic este o creatură pufoasă de dimensiunea unui hamster, având trei ochi și o blană colorată. De la naștere, fiecărui flic îi place în mod deosebit un anumit număr.

Hobby-ul lor este să intre în cutii, iar în lumea flicilor, pe fiecare cutie este inscripționat un număr. Flicii sunt pretențioși și nu vor alege orice cutie. În mod ideal, ar alege cutia pentru care numărul inscripționat este cel mai apropiat de numărul lor favorit, dar pentru că flicii sunt altruiști, vor alege cutiile astfel încât ceilalți flici să nu se supere prea tare.

Astăzi s-a format un grup de n flici, fiecare cu un număr favorit, care au la dispoziție n cutii, fiecare având inscripționat un număr. Sarcina ta este să stabilești pentru fiecare flic în ce cutie va intra, astfel încât suma modulelor diferențelor dintre numărul favorit a flicului și cel inscripționat pe cutia în care intră acesta să fie minimă.

#1092 Spatrat

Să se scrie un număr natural n ca sumă de pătrate perfecte. De asemenea, numărul termenilor trebuie să fie minim.

#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

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

La o firmă de software se lucrează la un mare proiect. Proiectul constă în executarea a n (n număr natural) faze de dezvoltare, numerotate cu numerele 1, 2, …, n. Unele faze pot fi executate în paralel (în acelaşi timp), însă executarea altor faze nu poate fi începută până când nu se finalizează executarea anumitor faze.

Să se scrie un program care să se determine:

a) timpul minim t în care se poate finaliza executarea proiectului
b) pentru fiecare fază k (k din {1,2,…,n}), momentul de timp ck la care poate începe faza k cel mai devreme, respectiv momentul de timp dk la care poate începe faza k cel mai târziu, fără a influenţa durata totală de executare a proiectului.

OJI 2009, Clasele XI-XII

#962 Cerc4

Se desenează n cercuri distincte în planul P, numerotate cu numerele de la 1 la n. Pentru fiecare cerc k (k∈{1,2,...,n}) se cunosc: raza cercului, rk, şi coordonatele (xk,yk) ale centrului cercului, coordonate referitoare la reperul cartezian xOy cu originea în punctul O a planului P. Din punctul O, se desenează m drepte distincte, astfel încât pentru fiecare dreaptă, dintre cele m desenate, să existe cel puţin un cerc, dintre cele n, al cărui centru să fie situat pe aceasta şi pentru fiecare cerc desenat, să existe o singură dreaptă, dintre cele m desenate, care să treacă prin centrul lui.

Să se scrie un program care să se determine:
a) numărul m de drepte distincte;
b) cel mai mare număr q de cercuri, dintre cele n, exterioare două câte două, ale căror centre sunt situate pe o aceeaşi dreaptă care trece prin punctul O, dintre cele m desenate;
c) numărul p al dreptelor distincte, dintre cele m desenate, pe care sunt situate centrele a câte q cercuri, dintre cele n, exterioare două câte două.

OJI 2009, clasele XI-XII

Cei care au văzut filmul Nemuritorul, ştiu că fraza cu care nemuritorii încep lupta este “Nu poate să rămână decât unul singur”. Să încercăm să simulăm povestea nemuritorilor.

Într-o zonă dreptunghiulară formată din n linii (numerotate de la 1 la n) şi m coloane (numerotate de la 1 la m) se află maxim n•m-1 nemuritori. Doi nemuritori vecini se “luptă” între ei şi cel care pierde lupta este eliminat. “Lupta” constă în săritura unuia dintre nemuritori peste celălalt, dacă această săritură se poate face. Săritura se poate face pe orizontală sau verticală şi nemuritorul peste care s-a sărit dispare. Prin vecin al nemuritorului din poziţia (i,j) înţelegem un nemuritor din una dintre poziţiile (i-1,j), (i+1,j), (i,j-1), (i,j+1). Deci, după luptă nemuritorul din câmpul (i,j) se va găsi în una dintre poziţiile: (i-2,j), (i+2,j), (i,j-2) sau (i,j+2), dacă această poziţie este liberă şi este în interiorul zonei.

Se cere să se determine o succesiune a luptelor ce pot fi purtate, astfel încât la final să rămână un singur nemuritor.

OJI 2010, Clasele XI-XII

#1095 Joc4

Jocul nostru presupune parcurgerea unui tablou bidimensional cu două linii şi n coloane, format din 2•n celule pătratice. Fiecare celulă are asociată câte o valoare întreagă v care nu se modifică pe durata desfăşurării jocului. Jucătorii trebuie să găsească un drum de la celula de plecare la celula de sosire care respectă următoarele condiţii:

  • celula de plecare este cea din linia 1 şi coloana 1, iar celula de sosire este cea din linia 2 şi coloana n.
  • nu trece decât cel mult odată prin oricare celulă.
  • deplasarea se poate face din celula curentă spre oricare altă celulă învecinată cu ea pe orizontală sau verticală.
  • conţine cel mult k celule consecutive aflate pe aceeaşi linie.

Pentru un astfel de drum se calculează punctajul acestuia ca fiind egal cu suma valorilor asociate celulelor prin care trece drumul.

Cunoscând valorile asociate celulelor tabloului, scrieţi un program care determină punctajul maxim care poate fi obţinut în acest joc.

OJI 2010, Clasele XI-XII

#1093 Text

Ion Petre, ca oricare adolescent, este pasionat atât de jocuri, cât şi de informatică. Ultimul astfel de joc este acela de a elimina dintr-un text cuvinte astfel încât fiecare cuvânt rămas să fie urmat de un cuvânt care începe cu aceeaşi literă cu care se termină cuvântul precedent. Face excepţie de la această regulă numai ultimul cuvânt.

Ion Petre, ca oricare adolescent, este pasionat atât de jocuri, cât şi de informatică. Ultimul astfel de joc este acela de a elimina dintr-un text cuvinte astfel încât fiecare cuvânt rămas să fie urmat de un cuvânt care începe cu aceeaşi literă cu care se termină cuvântul precedent. Face excepţie de la această regulă numai ultimul cuvânt.

Pentru un text dat, se cere să se afişeze numărul de cuvinte din text, apoi numărul minim de cuvinte ce pot fi eliminate astfel încât în textul rămas orice cuvânt (cu excepţia ultimului) să se termine cu aceeaşi literă cu care începe cuvântul următor, iar în final să se afişeze cuvintele din text rămase după eliminare, fiecare cuvânt fiind afişat pe câte o linie.

Pentru un text dat, se cere să se afişeze numărul de cuvinte din text, apoi numărul minim de cuvinte ce pot fi eliminate astfel încât în textul rămas orice cuvânt (cu excepţia ultimului) să se termine cu aceeaşi literă cu care începe cuvântul următor, iar în final să se afişeze cuvintele din text rămase după eliminare, fiecare cuvânt fiind afişat pe câte o linie.

Considerăm un număr întreg N şi un şir de M cifre zecimale nenule. Să se determine dacă numărul N poate fi rezultatul unei expresii aritmetice simple (fără paranteze), formată exclusiv din cifrele şirului citit şi din operatorii aritmetici desemnaţi pentru operaţiile de adunare şi scădere (+, -).

Scrieţi un program care citeşte numerele N şi M de pe prima linie a fişierului de intrare şi şirul de M cifre de pe linia următoare şi determină şi afişează expresia găsită sau valoarea 0 în cazul în care nu există soluţie.

OJI 2011, Clasa a VIII-a

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

#1068 Suma5

Constructorii angajaţi de faraonul Keops au terminat construirea piramidei în trepte mult visată. Măreaţa piramidă are n camere identice de formă cubică, numerotate de la 1 la n, dispuse pe m niveluri astfel:

  • camera din vârful piramidei formează nivelul 1 şi are numărul 1;
  • nivelul 2 al piramidei este format din următoarele 4 camere care în secţiune cu un plan paralel cu baza au aspectul unei matrice cu 2 linii şi 2 coloane; camerele de pe nivelul 2 sunt numerotate de la 2 la 5 în ordinea crescătoare a liniilor matricei, iar pe aceeaşi linie în ordinea crescătoare a coloanelor matricei;
    ………………..
  • nivelul m al piramidei este format din m*m camere şi au, în secţiune cu un plan paralel cu baza, aspectul unei matrice cu m linii şi m coloane; camerele de pe nivelul m sunt numerotate în continuarea celor de pe nivelurile 1, 2,…, m-1, în ordinea crescătoare a liniilor matricei de secţiune, iar pe aceeaşi linie în ordinea crescătoare a coloanelor matricei. De exemplu, piramida din desenul de mai sus are n=30, m=4 iar camerele sunt numerotate şi dispuse pe niveluri astfel:

Nivelurile de camere sunt poziţionate astfel încât camerele de pe prima linie şi prima coloană a fiecărui nivel să se suprapună. Pentru exemplul dat, camerele 1, 2, 6 şi 15 sunt situate una sub alta, în această ordine.

Accesul în oricare din camerele piramidei, situate pe diferite niveluri, se realizează prin drumuri construite astfel:

  • intrarea în piramidă se face doar prin camera din vârful ei, cea cu numărul 1;
  • din camera cu numărul k de pe un drum se poate intra într-una din cele patru camere situate pe nivelul imediat următor al piramidei şi anume: camera situată sub cea cu numărul k sau una din cele trei camere vecine acesteia în secţiune (în direcţiile Est, Sud-Est, Sud, considerând secţiunile poziţionate ca în imaginile de mai sus). De exemplu, din camera cu numărul 10 se poate intra într-una din camerele cu numerele: 20, 21, 24 sau 25.

Faraonul priveşte cu mândrie şi tristeţe la frumoasa piramidă. Banii din visterie s-au împuţinat iar camerele piramidei trebuie finisate şi decorate. Scribul său favorit a refăcut toate calculele, a eliminat obiectele inutile şi a stabilit pentru fiecare cameră k un cost ck aferent finisării şi decorării ei (1≤k≤n).

Însă, suma totală necesară fiind încă mare, faraonul i-a cerut scribului să aleagă un drum, dintre cele construite, care să treacă prin toate nivelurile piramidei astfel încât suma s a tuturor costurilor aferente finisării şi decorării camerelor de pe acest drum să fie minimă. Deocamdată, doar aceste camere vor fi aranjate…

Scrieţi un program care să determine numărul m de niveluri ale piramidei, suma minimă s a tuturor costurilor aferente finisării şi decorării camerelor de pe un drum ce trece prin toate nivelurile piramidei, construit în modul descris în enunţ, precum şi un astfel de drum pentru care se obţine suma minimă, putând fi ales de scrib.

OJI 2011, Clasele XI-XII

Trei ubuntzei au hotărât ca anul acesta să petreacă ziua de 1 Mai pe malul Mării Negre împreună cu prietenii lor, motiv pentru care au pus la cale o excursie pe un traseu care să plece din oraşul lor Cluj-Napoca spre Vama Veche, unde nisipul îi aşteaptă.

În ţara ubuntzeilor există N localităţi, numerotate de la 1 la N, legate între ele prin M şosele bidirecţionale de diferite lungimi. Localitatea de plecare a ubuntzeilor, oraşul Cluj-Napoca, este numerotată cu 1, iar localitatea destinaţie, Vama Veche, cu N. Între oricare două localităţi există cel mult o şosea. Fiecare şosea uneşte două localităţi distincte şi se poate călători între oricare două localităţi circulând numai pe şosele.
Prietenii ubuntzeilor locuiesc în K localităţi distincte, diferite de Cluj-Napoca şi Vama Veche. Pentru a nu călători singuri, cei trei ubuntzei vor să treacă prin cele K localităţi în care locuiesc prietenii lor, şi apoi, împreună cu aceştia, să-şi continue excursia către mare.

Nerăbdători să ajungă cât mai repede la destinaţie, ubuntzeii s-au hotărât să îşi stabilească un traseu de lungime minimă care să treacă prin toate cele K localităţi.

Scrieţi un program care să determine, pentru ubuntzei, lungimea minimă L a unui traseu de la Cluj-Napoca la Vama Veche ce trece prin toate cele K localităţi.

OJI 2011, Clasele XI-XII

#1063 Arme

Vasile joacă (din nou!) jocul său preferat cu împuşcături. Personajul său are la brâu N arme, aşezate în N huse speciale, numerotate de la 1 la N. Arma din husa i are puterea pbi (1≤i≤N).

În camera armelor a găsit M arme, aşezate pe perete, în M locaţii, numerotate de la 1 la M. Pentru fiecare armă j (1≤j≤M) este cunoscută puterea sa pcj.

Vasile poate înlocui arme pe care le are la brâu cu arme aflate pe perete în camera armelor. La o înlocuire el ia arma de pe perete din locaţia j (1≤j≤M) şi o pune la brâu în husa i (1≤i≤N), iar arma din husa i o pune pe perete în locaţia j.

Scrieţi un program care să determine suma maximă a puterilor armelor pe care le va avea la brâu Vasile după efectuarea înlocuirilor.

OJI 2012, Clasa a VII-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

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

#1036 Parc1

Un parc de formă dreptunghiulară este format din zone pietonale şi piste de biciclete. Reprezentând harta parcului într-un sistem cartezian, cu coordonata colţului stânga-jos (0,0), pistele de biciclete sunt reprezentate prin dungi orizontale sau verticale colorate cu gri, iar zonele pietonale au culoarea albă, ca în figura din dreapta.

Vizitatorii parcului se pot plimba liber pe zonele pietonale în orice direcţie, însă pistele de biciclete se vor traversa, în linie dreaptă, paralel cu axele. În figura alăturată avem un parc de dimensiuni 10 x 8, cu piste de biciclete verticale între 2 şi 4 respectiv 5 şi 8, şi orizontale între 0 şi 1 respectiv între 2 şi 4. Gigel se află în punctul A(1,1) şi poate sa ajungă pe drumul cel mai scurt la prietenul lui, în punctul B(8,7) deplasându-se astfel: porneşte din punctul (1,1) şi parcurge un traseu format din segmente cu extremităţile în punctele de coordonate (1.5 , 2) (1.5, 4) (2 , 5) (4 , 5) (5 , 7) şi în final ajunge în punctul de coordonate (8 , 7).

Lungimea totală a drumului va fi aproximativ 11.4721359.

Cunoscând dimensiunile parcului, coordonatele lui Gigel, coordonatele prietenului lui şi poziţiile pistelor de biciclete, să se calculeze lungimea drumului minim şi numărul drumurilor distincte de lungime minimă.

OJI 2012, clasele XI, XII

#1035 Blis

Se consideră un şir de biţi şi un număr natural K. Şirul se împarte în secvenţe astfel încât fiecare bit din şir să aparţină unei singure secvenţe şi fiecare secvenţă să aibă lungimea cel puţin 1 şi cel mult K. După împărţire, fiecare secvenţă de biţi se converteşte în baza 10, obţinându-se un şir de valori zecimale. De exemplu, pentru şirul de biţi 1001110111101010011 şi K = 4, se poate obţine 1 0011 101 111 0 1010 011, apoi în baza 10: 1, 3, 5, 7, 0, 10, 3. O altă împărţire poate fi 1 00 1 1 10 11 110 1010 011, adică 1, 0, 1, 1, 2, 3, 6, 10, 3.

Scrieţi un program care:

  • determină valoarea maximă (în baza 10) care se poate obţine dintr-o secvenţă de cel mult K biţi
  • împarte şirul iniţial în secvenţe de cel mult K biţi astfel încât şirul zecimal obţinut să conţină un subşir strict crescător de lungime maximă posibilă.

OJI 2012, clasele XI, XII

#1004 Eureni

Pentru cadourile pe care Moş Crăciun urmează să le cumpere copiilor cuminţi, Consiliul Polului Nord a alocat suma de S eureni. Ştiind că în comerţul polar se utilizează n+1 tipuri de bancnote de valori 1, e1, e2, e3,…, en şi faptul că Moşul trebuie să primească un număr minim de bancnote pentru suma aprobată, să se determine numărul de bancnote din fiecare tip utilizat în plata sumei şi numărul total de bancnote care i s-au alocat.

La ştrandul Junior din oraşul nostru s-au construit n bazine pentru înot. Fiecare bazin a fost dotat cu câte un robinet pentru umplerea acestuia cu apă. Între m perechi distincte de bazine, a fost instalată câte o ţeavă prin care apa din cele două bazine din fiecare pereche să poată circula. Astfel, cele două bazine din pereche pot fi umplute prin deschiderea unui singur robinet.

Administratorul bazei a numerotat bazinele cu numerele distincte de la 1 la n şi a notat în registrul lui cele m perechi de numere (x1,y1), (x2,y2),…., (xm,ym) corespunzând perechilor de bazine între care a fost instalată câte o ţeavă. Pentru a umple toate bazinele cu apă, administratorul doreşte să deschidă un număr minim de robinete.

Scrieţi un program care să citească numerele naturale n şi m, şi cele 2*m numere naturale x1, y1, x2, y2,…., xm, ym, cu semnificația din enunț, şi care să afişeze cel mai mic număr k de robinete pe care trebuie să le deschidă administratorul astfel încât să fie umplute cu apă toate bazinele.

#956 sir2

Fie N și M două numere naturale nenule. Fie X un șir de M numere naturale nenule x1, x2,…, xM, cu proprietatea că
N=x1+x2+ ... +xM.

Scrieţi un program care să citească numerele N și M şi care să determine:
a) cel mai mare număr care poate să apară în șirul X cu proprietatea din enunț;
b) numărul de șirurilor distincte X cu proprietatea din enunț, modulo 104729.

Olimpiada locală, 2014

#950 Cerc3

Se consideră pe axa Ox din plan n puncte distincte reprezentând centrele a n cercuri numerotate cu numerele distincte de la 1 la n. Pentru fiecare cerc k se cunosc abscisa xk a centrului său şi raza sa rk.

Să se scrie un program care să determine numărul y maxim de cercuri exterioare două câte două dintre cele n.

Olimpiada de Informatică, etapa pe sector, Bucureşti, 2011

#954 joc2

Plictisiți de Facebook și jocuri online, Diana și Jonny s-au gândit să joace un joc nou, care să necesite și mișcare în aer liber. Astfel, cei doi au desenat pe terenul de sport din liceu un dreptunghi pe care l-au împărțit cu N-1 linii orizontale și M-1 linii verticale în NxM pătrate identice, așezate pe N rânduri și M coloane, câte N pe fiecare rând și câte M pe fiecare coloană, ca în exemplu. Apoi, în interiorul fiecărui pătrat au scris câte un număr reprezentând valoarea pătratului respectiv în joc. După ce au terminat de scris cele NxM numere, Diana și Jonny au stabilit ca jocul să se desfășoare după următoarele reguli:

  • Diana se poziționează în pătratul din colțul stânga-sus al dreptunghiului, iar Jonny se poziționează în pătratul din colțul dreapta-sus al dreptunghiului.
  • Din pătratul în care se află, Diana se va deplasa făcând un pas în pătratul din dreapta de pe aceeași linie (dacă există) sau în pătratul situat pe linia următoare în aceeași coloană (dacă există), ca în desenul de mai jos.
  • Din pătratul în care se află, Jonny se va deplasa făcând un pas în pătratul din stânga de pe aceeași linie (dacă există) sau în pătratul situat pe linia următoare în aceeași coloană (dacă există), ca în desenul alăturat.
  • Ambii concurenți vor face până la finalul jocului un număr egal de pași. Simultan, fiecare se va deplasa din pătratul curent în cel ales cu respectarea regulilor de mai sus. Concurenții se pot afla la un moment dat în același pătrat.
  • Jocul se încheie în momentul în care Diana ajunge în pătratul din colțul dreapta-jos al dreptunghiului, iar Jonny ajunge în pătratul din colțul stânga-jos al dreptunghiului.
  • Fiecare concurent alege pătratele prin care să se deplaseze conform regulilor de mai sus astfel încât să obțină suma maximă posibilă a valorilor din pătratele alese. Această sumă va reprezenta punctajul concurentului.
  • Câștigă jocul concurentul care obține punctajul cel mai mare la finalul jocului. Dacă cei doi concurenți obțin același punctaj, atunci amândoi vor câștiga jocul.

Scrieți un program care să citească numerele N, M, cele NxM valori ale pătratelor din dreptunghi și care să determine câștigătorul jocului, precum și punctajul obținut de acesta la finalul jocului.

Olimpiada de Informatică, etapa pe sector, Bucureşti, 2013

Într-un depozit foarte mare există un raft cu n+1 spații de depozitare, numerotate de la 1 la n+1. Primele n spatii de depozitare sunt ocupate cu n pachete numerotate cu valori între 1 și n, iar spațiul de depozitare n+1 este gol.

Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice i, pachetul numerotat cu i să se afle în spațiul de depozitare i. Pentru aceasta se va folosi spațiul de depozitare suplimentar, n+1, singura manevră validă fiind mutarea unui pachet dintr-un spațiu de depozitare în altul, cu condiția ca acesta să fie gol.

Determinați o succesiune de manevre prin care fiecare pachet să fie în spațiul corect.

Se dă lista muchiilor unui graf neorientat. Să se afișeze vârfurile izolate ale grafului.

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Unele camere sunt închise, accesul în ele fiind imposibil. Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j+1), dacă aceasta nu este închisă.

Determinați în câte moduri se poate ajunge din camera (1,1) în camera (n,m). Deoarece numărul de posibilități poate fi foarte mare, se cere doar restul acestui număr la împărțirea cu 9901.

Hercule trebuie sa strabată un labirint cu capcane reprezentat de o matrice cu n linii și m coloane. Pentru fiecare celula a labirintului, se cunoaște timpul exprimat în minute după care celula respectivă devine capcană. După ce o celula devine capcana, Hercule piere dacă intră în acea celulă.

Sa se afișeze numarul total de drumuri pe care le poate urma Hercule prin labirint, astfel încât Hercule să nu piară.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în nodurile neterminale ale arborelui, în ordine descrescătoare.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în nodurile terminale ale arborelui, în ordine crescătoare.

Fie n cuburi de aceeaşi mărime, cu feţe colorate. Culorile sunt codificate prin câte o literă de la A la M. Pentru fiecare cub se cunosc culorile feţelor în ordinea: bază, capac, faţă frontală, faţă laterală dreapta, faţa din spate, faţă laterală stânga. Să se determine numărul maxim de cuburi care, răsturnate şi rotite convenabil, pot fi puse unul peste altul astfel încât să formeze un turn cu toate feţele uniform colorate (fiecare faţă a turnului sa fie de aceeaşi culoare, de la primul, până la ultimul cub al turnului).

Lot Juniori, Bistrita, 2009

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine înălțimea arborelui.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule și un număr k. În arbore rădăcina se află pe nivelul 0, fii rădăcinii pe nivelul 1, fii fiilor rădăcinii pe nivelul 2, etc. Să se determine suma valorilor din nodurile aflate pe nivelul k.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile din arbore în urma parcurgerii în lățime, pornind din rădăcină.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine cele mai mici valori număr prim din subarborii stâng și drept ai rădăcinii.

#757 BiMax

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine valorile maxime din subarborii stâng și drept ai rădăcinii.

#756 NrNod

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine câte noduri din arbore au un singur descendent direct.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în arbore în urma parcurgerii în postordine.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în arbore în urma parcurgerii în inordine.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile memorate în subarborele stâng al rădăcinii în urma parcurgerii în preordine.

Se consideră un arbore binar alocat dinamic în care nodurile memorează numere naturale nenule. Să se determine valorile memorate în descendenții direcți ai rădăcinii arborelui.

#744 Rec

După strălucita victorie de la Austerlitz împotriva coaliţiei ruso-austriece, împăratul Napoleon Bonaparte doreşte să recompenseze N generali care s-au remarcat în luptă. Pentru aceasta, el dispune de o sumă în franci de valoare S. La festivităţile dedicate victoriei, cei N generali vor fi aliniaţi în ordinea descrescătoare a meritelor lor pe câmpul de luptă şi împăratul îi va chema pentru înmânarea recompensei în această ordine.

Bonaparte doreşte să împartă întreaga sumă astfel încât generalul cel mai merituos să primească suma cea mai mare şi oricare alt general să primească o sumă cel mult egală cu a generalului care a fost premiat anterior. De asemenea, generalul cu cel mai mic premiu nu trebuie să primească mai puţin de F franci.

Determinaţi numărul de variante distincte de acordare a recompenselor de către împăratul Napoleon.

Lot Juniori, Bistrita, 2009

#738 Left

Se dau L şi C două numere naturale şi o matrice cu L linii şi C coloane având elementele numere întregi. Trebuie alese elemente care să respecte următoarele proprietăţi:

  • de pe fiecare linie se alege o secvenţă de elemente aflate pe coloane cu indici consecutivi, începând cu elementul de pe prima coloană;
  • pentru orice două linii consecutive, lungimile secvenţelor alese trebuie să difere prin 1 sau să fie egale;
  • nu trebuie să existe 3 linii consecutive pentru care lungimile secvenţelor alese să fie egale, sau să fie în ordine strict crescătoare sau strict descrescătoare;

Se cere să se facă o alegere a secvenţelor de pe fiecare linie a matricei respectând restricţiile precizate, astfel încât însumând elementele acestora să se obţină suma maximă posibilă.

Lot Juniori, Alba Iulia, 2010

#723 Fibo

Maria este pasionată de matematică. Ea este interesată în special elementele şirului Fibonacci şi vrea să studieze proprietăţile elementelor acestui şir. De curând a scris elementele Fibonacci: 1, 1, 2, 3, 5, 8, 13, … şi a observat că un element, numărul 5, poate fi scris ca sumă de alte două numere Fibonacci ridicate la pătrat, 5=12+22, iar alt număr Fibonacci, numărul 144, poate fi scris ca diferenţă a altor două numere Fibonacci ridicate la pătrat, 144=132-52.

Maria a fost încântată de rezultatele pe care le-a obţinut şi ar dori să mai găsească şi alte elemente ale şirului care se pot scrie ca sumă sau ca diferenţă de alte două numere Fibonacci ridicate la pătrat.

Ajutaţi-o pe Maria, să decidă despre un element Fibonacci oarecare dacă se poate scrie ca sumă sau diferenţă de două numere Fibonacci distincte ridicate la pătrat. Datorită valorilor mari ale numerelor Fibonacci se cere restul împărţirii lor la 46337.

Lot Juniori, Focsani, 2010

  • Fișiere
  • Silviu Candale
  • Zoltan Szabo
  • concurs

Se dau două numere naturale N şi K. Determinaţi numărul de şiruri de lungime N formate doar din semnele + şi şi în care nu apar K semne pe poziţii consecutive.

Lot Juniori, Arad, 2011

#725 Rege

Cunoscând dimensiunea m*n a tablei de şah, respectiv poziţia iniţială (l1,c1) şi poziţia finală (l2,c2) a traseului regelui, să se calculeze numărul drumurilor minime distincte în care regele poate parcurge drumul.

Lot Juniori, Focsani, 2010

Matca cea tânără a decis să părăsească stupul şi să îşi facă propria familie de albine, lucru nu tocmai uşor. Ea, împreună cu albinele sale trebuie să meargă din floare în floare până la marginea plantaţiei. Plantaţia are formă dreptunghiulară cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). În fiecare punct este o floare. Florile sunt codificate cu 0 sau 1, cele codificate cu 0 putând fi ocupate doar de matcă, cele cu valoarea 1 doar de câte o albină. Roiul de albine pleacă de la marginea stângă a plantaţiei (coloana 1) şi trebuie să ajungă în marginea din dreapta (coloana M). La un pas, toate albinele (inclusiv matca) trebuie să se afle pe poziţii consecutive pe aceeaşi coloană. La pasul următor ele se pot deplasa doar pe coloana următoare, dar tot pe poziţii vecine (eventual îşi pot schimba ordinea). Efortul depus pentru deplasarea de pe o coloană pe alta este egal cu diferenţa dintre prima linie ocupată de un membru al roiului de albine (matca sau albină) la pasul anterior şi prima linie ocupată de un membru al roiului albine (matca sau albină) după mutare.

Determinaţi numărul maxim de membri ai roiului de albine (matcă + albine) care pot părăsi stupul pentru a traversa toată plantaţia în scopul formării unei noi familii. Determinaţi, de asemenea efortul total minim cu care matca poate traversa plantaţia cu numărul maxim de albine determinat.

Lot Juniori, Focsani, 2010

#716 cmin

Jocul cmin constă în a găsi o strategie pentru a deplasa un anumit număr de jetoane identice pe o tablă pătratică, în scopul obţinerii unei configuraţii finale, cu un cost minim.

Tabla are n*n celule, aflate la intersecţia a n rânduri numerotate de la 1 la n de sus în jos şi a n coloane, numerotate de la 1 la n de la stânga spre dreapta. Numărul n este întotdeauna par.

La momentul iniţial al jocului, pe tablă se găsesc k jetoane în poziţii cunoscute. Fiecare jeton poate fi deplasat doar pe verticală, din celula iniţială într-o celulă finală neocupată de un alt jeton. Un jeton poate fi deplasat chiar dacă între poziţia sa iniţială şi cea finală există celule ocupate de către alte jetoane.

Costul deplasării unui jeton pe verticală, din celula curentă într-o celulă adiacentă este 1 (o unitate). Un jeton poate fi mutat de mai multe ori. Jucătorul decide ordinea deplasării jetoanelor. Acesta poate să mute 0, 1 sau chiar toate jetoanele pentru a termina jocul cu un cost total minim. Costul total este suma costurilor deplasării tuturor jetoanelor.

Jocul cmin se termină când diferenţa în valoare absolută dintre numărul de jetoane care se află pe primele n/2 rânduri (cele de sus) şi numărul de jetoane care se găsesc pe ultimele n/2 rânduri (cele de jos), este minimă.

Cunoscând numărul n de rânduri şi de coloane ale tablei şi poziţiile iniţiale ale jetoanelor, determinaţi costul total minim necesar pentru deplasarea acestora, astfel încât diferenţa în valoare absolută dintre numărul jetoanelor care se vor găsi în final pe primele n/2 rânduri şi numărul jetoanelor care se vor găsi pe ultimele n/2 rânduri, să fie minimă.

Lot Juniori, Resita, 2012

Mircea şi Andrei sunt pasionaţi de construcţiile realizate din piese Lego. Fiecare dintre ei are un set format din N cuburi negre de latură 1 şi mai multe piese paralelipipedice de culoare albă cu care va construi o clădire de formă paralelipipedică având baza un pătrat de latură 2 şi înălţimea H.

Toate piesele de culoare albă au înălţimea 2 iar celelalte laturi egale cu 1 şi nu pot fi răsturnate în momentul în care se asamblează pentru a construi clădirea. Aceasta va conţine întotdeauna toate piesele negre din set şi atâtea piese de culoare albă cât e necesar pentru finalizarea ei.

În momentul finalizării clădirii, cei doi băieţi observă că deşi au folosit aceleaşi seturi de piese, cele două clădiri sunt diferite deoarece combinaţiile de culori alb-negru de pe faţadele (nordică, sudică, vestică sau estică) clădirilor nu arată la fel.

Scrieţi un program care să calculeze numărul T de clădiri diferite care se pot construi cu piesele date, ştiind că două clădiri sunt identice dacă sunt îndeplinite simultan următoarele condiţii:

  • faţada dinspre nord a uneia este identică cu faţada dinspre nord a celeilalte;
  • faţada dinspre est a uneia este identică cu faţada dinspre est a celeilalte;
  • faţada dinspre sud a uneia este identică cu faţada dinspre sud a celeilalte;
  • faţada dinspre vest a uneia este identică cu faţada dinspre vest a celeilalte.

Programul va afişa restul împărţirii numărului T la 666013.

Lot Juniori, Resita, 2012

#707 sumk

sumk este un joc de perspicacitate, cu N stagii numerotate de la 1 la N. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la 1 la N, toate cele N stagii ale jocului şi în fiecare stagiu a obţinut exact K puncte. Fiecare stagiu are N niveluri, numerotate de asemenea de la 1 la N. Jucătorul are posibilitatea să câştige 0, 1, …, K puncte pe oricare nivel al stagiului curent.

Dacă jucătorul se găseşte în stagiul i pe nivelul j și numărul total de puncte obţinute până în acel moment în acest stagiu este mai mic decât K, el va trece în mod obligatoriu pe nivelul j+1 al stagiului i. Dacă jucătorul primește cel puţin un punct pe nivelul j și astfel punctajul său în stagiul i devine exact K, atunci jucătorul trece în mod automat pe nivelul j al stagiului i+1 sau termină jocul cu succes dacă i=N.

Cunoscând numărul N de stagii ale jocului şi numărul K de puncte care trebuie să fie obţinute în fiecare stagiu, să se determine numărul de posibilităţi modulo 578537 pentru ca jocul să se termine cu succes.

Lot Juniori, Baia Mare, 2013

Prin fibosir(N) înţelegem un şir construit prin adăugarea la sfârşit (concatenare) a primilor N termeni nenuli ai şirul Fibonacci definit astfel:

  • F1=1
  • F2=1
  • FN = FN-1 + FN-2

Pentru N valoare naturală dată, să se elimine din fibosir-ul construit M secvenţe disjuncte de lungime K fiecare, astfel încât numărul format din cifrele rămase în fiboşir să fie maxim.

Lot Juniori, Baia Mare, 2013

#704 smsm

Notăm X ca fiind mulţimea numerelor naturale care se pot scrie sub forma 2a*3b. Se consideră doar acele numere pentru care 0 ≤ a ≤ D şi 0 ≤ b ≤ T, unde D şi T sunt date. Pentru un număr v din X, considerăm asociatul lui v ca fiind valoarea (C*P)%Q unde C este ultima cifră a lui v iar P şi Q se dau (de exemplu, pentru P = 1 şi Q = 10 asociatul lui 21*32 este 8).

Se cere determinarea valorii maxime a sumei asociatelor elementelor unei submulţimi a lui X astfel încât oricare ar fi două elemente u şi v din submulţimea respectivă, u nu divide pe v şi nici v nu divide pe u.

Lot Juniori, Baia Mare, 2013

Se dă un șir de numere întregi a[0],a[1],..a[N-1]. Fiecare valoare a[i] reprezintă mărimea maximă a unui salt ce poate fi efectuat din pozitia i. Din poziţia i, se poate ajunge printr-un salt la oricare din poziţiile i+1, i+2,…, i+a[i], dacă a[i] este pozitiv, iar dacă a[i] este negativ se poate ajunge la oricare din poziţiile i-1,i-2,…, i+a[i].

Trebuie să se ajungă, prin salturi, de la poziția 0 la o poziție mai mare decât N-1 (în afara vectorului, la dreapta).

Scrieți un program care să determine numărul minim de salturi necesare pentru a ajunge de la poziția 0 la o poziție mai mare decât N-1.

Lot Juniori, Baia Mare, 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

#692 robot

Studenţii Facultăţii de Informatică din cadrul Universităţii din Cluj, au conceput roboţi care şterg praful, plantează copaci, pun gresie, servesc masa, etc.

Botezat „Rosie“, robotul care şterge praful are două braţe ( S – stâng şi D – drept) pe care sunt montate nişte perii ce sunt învârtite cu ajutorul unui motoraş. Braţul robotului este programat să se poziţioneze în dreptul unei suprafeţe, periile învârtite de motoraş parcurg suprafaţa ştergând în acest fel praful de pe ea.

Pentru o demonstraţie, robotul este aşezat în faţa unei etajere cu N rafturi numerotate în ordine, de jos în sus, cu numere de la 1 la N. Braţul stâng ( S ) al robotului este poziţionat în dreptul primului raft iar celălat braţ ( D ) în dreptul celui de-al K-lea raft.

Pentru ştergerea prafului, deplasarea braţelor robotului este programată astfel:

  • fiecare braţ se deplasează doar de jos în sus, de la raftul în dreptul căruia este poziţionat la un moment dat, la raftul situat imediat deasupra acestuia;
  • din minut în minut, se deplasează doar unul din braţe, se poziţionează în dreptul raftului corespunzător şi şterge praful de pe acesta;
  • dacă ambele braţe ajung în dreptul aceluiaşi raft, atunci robotul se blochează şi demonstraţia se încheie fără succes.

Ştiind că demonstraţia se termină în momentul în care braţul drept ( D ) al robotului a ajuns pe ultimul raft al etajerei, scrieţi un program care calculează numărul M de modalităţi diferite în care poate fi programat robotul pentru a asigura succesul demonstraţiei.

Programul va afişa restul împărţirii numărului M la 64997.

Lot Juniori, Sovata, 2014

O tablă pătratică este formată din N x N celule pătrate, identice ca dimensiune, grupate pe N linii şi N coloane numerotate de la 1 la N. Din oricare celulă aflată la linia i şi coloana j, se poate face o deplasare doar spre celula vecină (i + 1, j) sau (i, j + 1), dacă aceasta există. În interiorul a M celule ale acestei matrice s-a așezat câte un jeton.

Numim drum pe această tablă, orice succesiune de celule parcurse conform regulii de deplasare descrisă anterior. Lungimea unui asemenea drum este egală cu numărul de celule parcurse.

Cunoscând dimensiunea tablei N, numărul total de jetoane m şi două numere naturale L şi K, să se determine un număr d, reprezentând numărul de drumuri distincte modulo 31607 de lungime L care pornesc din celula (1, 1) şi care conţin fiecare câte K jetoane.

Lot Juniori, Sovata, 2014

Domino este un joc care utilizează N piese speciale, de formă dreptunghiulară. Pe prima şi pe a doua jumătate a fiecărei piese este inscripţionată câte o cifră de la 1 la 9.

În timpul jocului cele N piese se așează pe tabla joc astfel încât toate cifrele să fie aliniate pe orizontală, iar jucătorul poate acţiona asupra unei piese în două moduri:

  • ELIMINARE – piesa este înlăturată de pe tabla de joc;
  • ROTIRE – piesa este rotită cu 180 grade, păstrându-și ordinea relativă în raport cu celelalte piese.

Ştiind că în timpul jocului pot fi efectuate cel mult K1 ROTIRI şi exact K2 ELIMINĂRI de piese, determinaţi cel mai mare număr care se poate forma prin scrierea în ordine, de la stânga la dreapta, a cifrelor de pe piesele rămase pe tabla de joc, în urma efectuării operaţiilor permise.

Lot Juniori, Sovata, 2014

Având la dispoziție n cifre, să se construiască k numere, astfel încât suma lor să fie minimă.

Lot Juniori, Sibiu 2011

#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 următoarele proprietăţi:

  • Fiecare cifră a bazei b: 0, 1, …, b – 1, apare, în total, în numerele acestui subşir de acelaşi număr de ori.
  • În orice prefix al subşirului determinat, diferenţa dintre numerele de apariţii ale oricăror 2 cifre cuprinse între 0 şi b-1 este cel mult k (un prefix al subşirului determinat reprezintă o secvenţă de valori din subşir începând cu primul element al subşirului).

Determinaţi numărul maxim de elemente ale unui astfel de subşir.

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 dă un arbore binar care conține valori numere naturale. În acest arbore rădăcina este considerată pe nivelul 0, descendenții direcți ai rădăcinii pe nivelul 1, etc. Să se determine numărul de nivele k din arbore și, pentru fiecare nivel i de la 0 la k, numărul de noduri situate pe acel nivel.

Se dă un arbore binar care conține valori numere naturale. Se dau k noduri din arbore și se cere determinarea, pentru fiecare nod, a numărului de noduri din subarborele cu rădăcina în acel nod care conțin valori prime.

Se dă un arbore binar care conține valori numere naturale. Să se afișeze frunzele acestui arbore.

Se dă un arbore binar care conține valori numere naturale. Se dau k noduri din arbore și se cere determinarea, pentru fiecare nod, a numărului de noduri din subarborele cu rădăcina în acel nod.

Se dă un arbore binar care conține valori numere naturale. Să se determine diferența în valoare absolută a sumei valorilor memorate în subarborele stâng al rădăcinii și suma valorilor memorate în subarborele drept al rădăcinii.

Se dă un arbore binar care conține valori numere naturale. Să se afișeze valorile din arbore în urma parcurgerii în postordine.

Se dă un arbore binar care conține valori numere naturale. Să se afișeze valorile din arbore în urma parcurgerii în inordine.

Se dă un arbore binar care conține valori numere naturale. Să se afișeze valorile din arbore în urma parcurgerii în preordine.

Într-o firmă sunt n angajați, numerotați de la 1 la n, organizați ierarhic, astfel că fiecare angajat are un șef direct, cu excepția directorului general, care nu are șef. Fiecare angajat al firmei are un salariu cunoscut, exprimat printr-un număr natural. În firmă funcționează un sistem de recompensare a angajaților astfel încât câștigul fiecărui salariat este egal cu salariul său la care se adaugă media aritmetică a câștigurilor subordonaților săi direcți. Excepție fac angajații care nu au subordonați direcți, pentru care câștigul este egal cu salariul.

Determinați care este câștigul directorului general al firmei.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și k noduri distincte din arbore. Afișați fiii fiecăruia dintre cele k noduri.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați nodurile p din arbore pentru care suma valorilor asociate nodurilor din subarborele cu rădăcina în p este maximă.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și o valoare k. Determinați nodurile situate pe nivelul k în arbore.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Determinați câte perechi de noduri neterminale distincte p q din arbore au proprietatea că subarborele cu rădăcina în p și cel cu rădăcina în q au același număr de noduri.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și un nod k. Determinați câte noduri conține subarborele cu rădăcina în k.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și un nod k. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați suma valorilor asociate nodurilor din subarborele cu rădăcina în k.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și un nod k. Afișați, în ordine crescătoare, nodurile terminale din subarborele cu rădăcina în k.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri n care fiecare nod are asociată o valoare numerică. Determinați drumul de la rădăcină la un nod terminal pentru care suma valorilor asociate nodurilor este maximă.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și doua noduri p q. Determinați drumul elementar de la nodul p la nodul q.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și un nod k. Determinați drumul de la rădăcina arborelui la nodul k.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și un nod k. Determinați drumul de la nodul k la rădăcina arborelui.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și un nod k. Afișați, în ordine crescătoare, nodurile din subarborele cu rădăcina în k.

#640 NrFii

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Determinați nodul din arbore cu număr maxim de fii. Dacă în arbore sunt mai multe noduri cu număr maxim de fii, afișați-le pe toate, în ordine crescătoare.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Determinați înălțimea arborelui.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și k noduri din arbore. Determinați pentru fiecare dintre cele k noduri nivelul pe care se află.

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Determinați rădăcina arborelui și frunzele acestuia.

Se dau cele n-1 muchii ale unui arbore cu n noduri și un nod k . Afișați vectorul de tați al arborelui cu rădăcina în k.

Alexandru dorește să devină expert în securitate, iar pentru aceasta s-a apucat să învete mai multe despre siguranța parolelor. El dorește să afle câte parole poate crea folosind a litere mici ale alfabetului englez și b litere mari ale alfabetului englez, c cifre si d caractere din mulțimea {!, @, #, $, %}. Totodată, el vrea să găsească parola cu numărul x în ordine lexicografică, formată din caracterele descrise mai sus.

Cunoscând a, b, c, d si x se cere:

a) A x-a parolă în ordine lexicografică, formată din caracterele menționate în enunț.
b) Numărul de parole diferite formate din caracterele menționate în enunț, modulo 666013.

Grigore Moisil, 2014

#630 Joc

Mihai, fiind un mare pasionat al jocurilor în aer liber, a inventat un joc nou în speranța că își va convinge colegii să iasă afară să se joace. Jocul lui Mihai spune că se dau N pătrate ce se află la anumite nivele iar din fiecare pătrat se poate sări doar în anumite pătrate stabilite la începutul jocului. Dacă un jucător sare dintr-un pătrat aflat la nivelul X într-un pătrat aflat la un nivel mai mare Y, acesta folosește un efort egal cu [Y/X], iar dacă sare într-un pătrat aflat la un nivel mai mic sau egal Y, efortul folosit este [X/Y]. Jucătorul se află la început în pătratul de start S și scopul jocului este să ajungă în pătratul final F, depunând un efort minim.

Cunoscând numărul de pătrate N, pătratul de start S, pătratul final F și pentru fiecare pătrat, pătratele în care jucătorul poate sări, se cere:

a) Efortul minim necesar pentru a ajunge în pătratul final.
b) Pătratele pe care jucătorul le sare până ajunge la pătratul final.

Grigore Moisil, 2014

#615 Gate

După ce a ajutat la conectarea oraşelor Nordemos şi Suderim, Negrimon s-a hotărât să-şi urmeze destinul şi să devină un programamon roşu. Pentru a-şi începe călătoria, este nevoit să părăsească Udobje Lurrak şi să treacă prin Sha’ar Azih, poarta magică de la ieşirea din oraşul Estumar. Această poartă se bazează pe un sistem de runix-uri aşezate în linie, numerotate de la 1 la N. Un runix este un pătrat pe care este înscrisă o literă mică, din mulţimea
unui alfabet restrâns, format din primele L litere ale alfabetului englez. Alfabetul restrâns este circular, astfel încât după ultima literă urmează prima, iar înainte de prima literă este ultima literă din alfabet.

În starea iniţială a sistemului, primul runix este setat pe litera a, al doilea runix este setat pe următoarea literă din alfabetul restrâns ş.a.m.d .

Când Negrimon ajunge la poartă, aceasta prinde viaţă şi se produce un şir de acţiuni de următorul tip:

1. Runix-ul cu numărul r împreună cu toate runix-urile din stânga se deplasează şi se separă de cele din dreapta (dacă există), formându-se astfel două grupuri independente (iniţial toate runix-urile formează un singur grup).
2. Toate runix-urile din grupul din care face parte runix-ul cu numărul r execută o schimbare de pas p. Aceasta constă în înlocuirea literei asociate cu următoarea a p-a literă din alfabet (p > 0) sau cu precedenta a (-p)-a literă din alfabet (p < 0). Datorită circularităţii alfabetului, oricât de mare ar fi p va exista o literă care să fie la
distanţa p faţă de litera actuală.
3. Negrimon primeşte o întrebare de tipul: pe ce literă este setat runix-ul cu numărul r?

Poarta se deschide dacă Negrimon răspunde corect la toate întrebările primite şi astfel își poate continua călătoria în Azih Lurrak.

Ajutaţi-l pe Negrimon să deschidă poarta.

Se dă un graf neorientat ponderat conex cu n vârfuri și m muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Kruskal, determinați un arbore parțial de cost minim.

#614 carti

Gigel are o bibliotecă cu T rafturi orizontale de diferite lungimi și T cutii cu cărți, câte o cutie pentru fiecare raft, în ordine. Cărţile dintr-o cutie au grosimi cunoscute și înălţimi egale cu înălţimea raftului pentru care sunt pregătite.

Gigel îşi doreşte foarte mult o bibliotecă nouă şi încearcă să o convingă pe mama sa folosind următoarea tactică: pe fiecare raft în parte el vrea să plaseze un număr minim de cărţi din cutia corespuzătoare astfel încât, așezându-le în anumite poziţii, să nu mai încapă nicio carte dintre cele rămase în acea cutie.

Ajutați-l pe Gigel să determine, pentru fiecare raft, numărul minim de cărți ce pot fi alese din cutia corespunzătoare pentru a fi plasate pe raft în condițiile de mai sus.

Urmasii lui Moisil, 2014, Clasele XI-XII

Se dă un graf orientat ponderat – în care fiecare arc are asociat un cost, număr natural strict pozitiv, și un nod p. Să se determine, folosind algoritmul lui Dijkstra, costul minim al drumului de la p la fiecare nod al grafului.

#598 Gears

Considerăm un ansamblu format din n roți dințate, numerotate de la 1 la n. Fiecare roată se poate roti spre dreapta sau spre stânga. Dacă o roată se rotește spre dreapta, toate roțile pe care le angrenează se vor roti spre stânga, și invers.
Una dintre roți este conectată la un motor și se va roti spre dreapta, iar toate roțile din ansamblu se vor roti în mod corespunzător. Ansamblul este construit astfel încât toate roțile vor fi angrenate și fiecare roată va fi angrenată de o unică altă roată.

Dându-se numărul de roți n, numărul de ordine x al roții conectate la motor și perechile de roți conectate între ele, să se determine sensul de rotație al fiecărei roți.

În imperiul maleficului Costel s-a instaurat anarhia. În imperiu sunt n orașe, numerotate de la 1 la n, unite prin m șosele unidirecționale, fiecare șosea fiind controlată de o bandă afiliată la unul dintre cele k sindicate banditești existente în imperiu, numerotate de la 1 la k. Pentru a călători prin pe șoselele din imperiu, orice călător trebuie să plătească taxe sindicatelor: plata taxei către un anumit sindicat îi permite călătorului să folosească nelimitat orice șosea controlată de o bandă afiliată acelui sindicat. Pentru toate sindicatele se plătește aceeași taxă.

Călătorul Gigel trebuie să ajungă din orașul p în orașul q. Determinați numărul minim de sindicate banditești cărora Gigel trebuie să le plătească taxe, pentru a putea realiza călătoria dorită.

#593 Parc

Parcul orașului este alcătuit din n intersecții, numerotate de la 1 la n, unite între ele prin m alei bidirecționale, fiecare având o anumita lungime. Într-o intersecție precizată C se organizează un concert; de asemenea, unele intersecții, precizate și ele, reprezintă porți de intrare în parc, accesul fiind posibil doar prin aceste porți.

Gigel poate ajunge cu mașina la oricare dintre aceste porți, dar vă roagă să alegeți pentru el acea poartă pentru care distanța până la intersecția C este minimă. Dacă există mai multe porți cu această proprietate se va determina poarta cu numărul de ordine mai mic.

#590 Prim

Se dă un graf neorientat ponderat conex cu n vârfuri și m muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Prim, determinați un arbore parțial de cost minim, cu rădăcina în vârful 1.

#591 Firma

Într-o țară sunt n orașe, numerotate de la 1 la n, unite între ele prin m șosele bidirecționale de lungimi cunoscute, între oricare două orașe existând drum, fie șosea directă, fie prin alte orașe. O firmă dorește să-și stabilească sediul în unul dintre orașe, astfel încât suma lungimilor drumurilor minime de la orașul în care se află sediul la toate celelaltele orașe să fie minimă. Determinați orașul care va fi ales pentru sediul firmei. Dacă sunt mai multe orașe care pot fi alese, se va alege cel cu numărul de ordine mai mic.

Se dă un graf orientat ponderat cu n noduri și m arce – în care fiecare arc are asociat un cost, număr natural strict pozitiv. Folosind algoritmul Roy-Floyd, construiți matricea costurilor minime.

Se dă lista arcelor unui graf orientat. Să se determine nodurile care au gradul interior nul.

#585 Orase

Într-o țară oarecare sunt n orașe, numerotate de la 1 la n, între care există șosele unidirecționale. Președintele țării vrea să facă o vizită electorală prin mai multe orașe în felul următor: aterizează cu elicopterul în orașul p, merge până în orașul q folosind rețeaua de șosele existentă, de unde pleacă cu elicopterul. Din punct de vedere politic unele orașe sunt sigure (conduse de aliați politici ai președintelui), altele sunt nesigure (conduse de adversari), iar președintele dorește să parcurgă numai orașe sigure.

Consilierii președintelui i-au propus mai multe perechi de orașe p q care pot fi alese ca punct de plecare și de sosire pentru vizită. Președintele vă cere să verificați pentru fiecare pereche dată dacă există un drum care să treacă numai prin orașe sigure.

#584 Anunt

Într-o clasă sunt n elevi, numerotați de la 1 la n, iar unii dintre ei pot cunoaște numerele de telefon ale altor elevi. Dirigintele dorește să-i anunțe pe elevi despre un eveniment deosebit și pentru aceasta vrea să transmită informația unui singur elev din clasă, urmând ca acesta să-și anunțe colegii cărora le cunoaște numărul de telefon, aceștia să-și anunțe colegii cărora le cunosc numărul de telefon etc, astfel încât toți elevii să afle informația respectivă.

Determinați care sunt elevii din clasă care pot fi anunțați inițial astfel încât, toți elevii să fie în cele din urmă informați.

Se dă lista arcelor unui graf orientat. Construiți matricea drumurilor, folosind algoritmul lui Roy-Warshall.

Se dă un graf orientat cu n noduri. Să se determine câte componente tare conexe are graful dat.

Se dă un graf turneu cu n noduri. Să se determine un drum elementar care să conțină toate nodurile grafului.

Se dă un graf orientat cu n noduri și un nod p. Să se afișeze toate nodurile q ale grafului, diferite de p, cu proprietatea că există cel puțin un drum de la p la q și lungimea drumului minim este pară.

Se dă un graf orientat cu n noduri. Determinați, dacă există, un drum hamiltonian.

Se dă lista arcelor unui graf orientat. Să se afișeze, în ordine lexicografică, toate circuitele de lungime trei.

Se dă lista arcelor unui graf orientat. Să se afișeze, în ordine lexicografică, toate ciclurile de lungime trei.

Într-un grup sunt n persoane, numerotate de la 1 la n și o persoană poate cunoaște alte persoane – relație care nu este reciprocă. Să se determine persoana cea mai cunoscută.

Să se determine câte grafuri orientate complete cu n noduri există.

Se dă lista arcelor unui graf orientat. Să se determine nodurile care au gradul exterior egal cu gradul interior.

Se dă lista muchiilor unui graf neorientat. Să se determine numărul de muchii care pot fi eliminate din graf astfel încât numărul de componente conexe ale grafului să nu se modifice.

Într-o țară locuiesc n persoane. Anumite perechi de persoane se cunosc între ele și se cunosc aceste perechi. Relația de cunoaștere între două persoane este reciprocă.

În țară izbucnește o epidemie (nu este mortală, doar foarte contagioasă). Dacă persoana A este bolnavă și cunoaște persoana B, se va îmbolnăvi și aceasta, după o perioadă de incubație a bolii de 1 zi. Inițial sunt bolnave k persoane cunoscute. Se cere să se determine după câte zile sunt bolnave toate cele n persoane.

#545 Euler

Se dă un graf neorientat cu n vârfuri care este conex și are gradele tuturor vârfurilor pare. Determinați un ciclu eulerian.

Se dă un graf neorientat cu n vârfuri. Determinați, dacă există, un ciclu hamiltonian.

Se dă lista muchiilor unui graf neorientat conex cu n vârfuri, etichetate de la 1 la n. Să se verifice dacă graful este bipartit.

#541 Lant1

Se dă lista muchiilor unui graf neorientat și trei vârfuri p q r . Să se determine un lanț cu extremitățile p q care conține vârful r.

#539 DFS

Se consideră un graf neorientat cu n vârfuri și m muchii și un vârf cunoscut X. Să se afişeze vârfurile vizitate în urma parcurgerii în adâncime a grafului pornind din vârful X.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și vârf p . Să se determine toate nodurile q ale grafului cu proprietatea că lungimea minimă a unui lanț de la q la p este L.

Se dă lista muchiilor unui graf neorientat și două vârfuri p q . Să se determine cel mai scurt lanț cu extremitățile p q.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și o succesiune de k vârfuri. Să se verifice dacă vârfurile din succesiune formează un lanț.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine cel mai lung lanț elementar cu extremitățile p și q.

#478 Ciclu

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf p. Să se determine un ciclu elementar care conține vârful p.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și trei vârfuri p q r. Să se determine toate lanțurile elementare cu extremitățile în p și q care nu conțin vârful r.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și trei vârfuri p q r. Să se determine toate lanțurile elementare cu extremitățile în p și q care conțin vârful r.

#475 Lant

Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine toate lanțurile elementare cu extremitățile p și q.

Se consideră două mulţimi nevide A şi B, cu proprietatea că formează o partiție a mulțimii {1,2,...,n}. Să se construiască un graf bipartit complet cu n vârfuri, bipartit peste partiţia formată din mulțimile A și B.

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Să se verifice dacă graful este bipartit.

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n, precum si o mulțime A de vârfuri ale grafului. Considerăm mulțimea B formată din vărfurile grafului care nu aparțin lui A. Să se verifice dacă graful este bipartit peste partiția formată din mulțimile A și B.

Se dă lista muchiilor unui graf neorientat. Să se afișeze, pentru fiecare vârf al grafului, lista vecinilor săi.

#416 Grade

Se dă lista muchiilor unui graf neorientat. Să se afișeze gradul fiecărui vârf.

Se dă lista muchiilor unui graf neorientat. Să se afișeze vârfurile de grad maxim.

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate vârfurile etichetate cu valori prime. Să se determine câte muchii va avea subgraful obținut.

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate vârfurile care au gradul minim. Să se determine câte muchii va avea subgraful obținut.

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate muchiile cu proprietatea că ambele extremități au aceeași paritate. Să se determine câte muchii va avea graful parțial obținut.

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate muchiile cu o extremitate de grad maxim și cealaltă extremitate de grad minim. Să se determine numărul de muchii eliminate și să se afișeze matricea de adiacență a grafului parțial obținut.

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate muchiile cu o extremitate într-un vârf de grad maxim. Să se determine numărul de muchii eliminate și să se afișeze matricea de adiacență a grafului parțial obținut.

#437 Conex

Se dă lista muchiilor unui graf neorientat. Să se verifice dacă graful este sau nu conex.

Se dă lista muchiilor unui graf neorientat. Să se afișeze componentele conexe ale acestui graf.

Se dă lista muchiilor unui graf neorientat. Să se determine numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex, precum și un set de asemenea muchii.

Se dă un număr natural n. Construiți toate grafurile neorientate cu n vârfuri.

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Pentru a intra într-o cameră se plătește o sumă cunoscută. Intrarea în clădire este în camera de coordonate (n,1), iar ieșirea în camera de coordonate (1,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i-1,j) sau (i,j+1), fără a părăsi clădirea.

O persoană intră în clădire, parcurge un șir de camere după regula precizată și iese din clădire, plătind în fiecare cameră taxa corespunzătoare. Determinați suma minimă care trebuie plătită.

#432 Taxe

Ali Baba și cei 40 de hoți stăpânesc un deșert de formă dreptunghiulară, împărțit în n linii și m coloane, care definesc n*m sectoare. Intrarea într-un sector se plătește cu o taxă cunoscută, exprimată în galbeni.

Un călător trebuie să traverseze deșertul de la Est la Vest, trecând dintr-un sector în altul, astfel: din sectorul (i j) se poate ajunge în unul din sectoarele (i-1,j-1), (i,j-1) sau (i+1,j-1), dar fără a părăsi deșertul (ar fi omorât de oamenii lui Ali Baba). La trecerea printr-un sector, călătorul plătește taxa aferentă acelui sector.

Determinați suma totală minimă pe care trebuie să o plătească călătorul la traversarea deșertului, știind că pleacă din orice sector al coloanei m (Est) și se oprește în orice sector al coloanei 1 (Vest), cu respectarea condițiilor de mai sus.

Se dau mai multe grafuri neorientate, prin matricea de adiacență. Să se verifice despre fiecare graf dacă este complet.

#396 SCLM

Se dă un șir n numere naturale. Determinați un cel mai lung subșir crescător al șirului.

Se dă lista muchiilor unui graf neorientat. Să se afișeze matricea de adiacență a grafului.

Se dă lista muchiilor unui graf neorientat. Să se afișeze matricea de adiacență a grafului.

Gigel este un cântăreț începător. El știe deja să cânte n piese, și pentru fiecare piesă se cunoaște durata, exprimată în minute și secunde. Gigel va participa la o emisiune de televiziune, unde va putea cânta timp de T secunde. El vrea să cânte cât mai multe piese, pentru a-și demonstra talentul deosebit.

Ajutați-l să aleagă piesele pentru emisiune, și vă va răsplăti cu un autograf.

Să se determine o modalitate de parcurgere a unei tablei de către un cal care se deplasează în maniera specifică piesei de șah, astfel încât acesta să nu treacă de două ori prin aceeaşi poziţie.

#402 Bete

Gigel a primit cadou n bețe de diferite lungimi. Neștiind ce să facă cu ele, se întreabă dacă poate alege dintre bețele date o parte, astfel încât, lipindu-le, să obțină un băț de lungime S.

Într-un depozit există un raft cu n+1 spații de depozitare, numerotate de la 1 la n+1. Primele n spatii de depozitare sunt ocupate cu n pachete numerotate cu valori între 1 și n, iar spațiul de depozitare n+1 este gol.

Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice i, pachetul numerotat cu i să se afle în spațiul de depozitare i. Pentru aceasta se va folosi spațiul de depozitare suplimentar, n+1, singura manevră validă fiind mutarea unui pachet dintr-un spațiu de depozitare în altul, cu condiția ca acesta să fie gol.

Determinați o succesiune de manevre prin care fiecare pachet să fie în spațiul corect.

De-a lungul principalei străzi din orașul nostru există n plopi, pentru fiecare cunoscându-se înălțimea. Primarul orașului dorește ca plopii să aibă înălțimile în ordine descrescătoare. Pentru aceasta, este posibilă tăierea dintr-un plop a unei bucăți – este o tehnică ecologică, nevătămătoare, în urma căreia plopul nu are de suferit. Plopii nu pot fi înălțați în nici un fel.

Determinați numărul minim de plopi din care se va tăia și lungimea totală minimă a bucăților tăiate.

De-a lungul principalei străzi din orașul nostru există n plopi, pentru fiecare cunoscându-se înălțimea. Primarul orașului dorește să taie anumiți plopi, astfel încât înălțimile celor rămași să fie în ordine strict descrescătoare.

Determinați numărul minim de plopi care trebuie tăiați astfel încât înălțimile celor rămași să fie în ordine strict descrescătoare.

Ali Baba și cei 40 de hoți stăpânesc un deșert de formă dreptunghiulară, împărțit în n linii și m coloane, care definesc n*m sectoare. În fiecare sector se află o comoară ascunsă de Ali Baba. Se cunoaște valoarea în galbeni a fiecărei comori.

Un călător trebuie să traverseze deșertul de la Nord la Sud, trecând dintr-un sector în altul, astfel: din sectorul (i j) se poate ajunge în unul din sectoarele (i+1,j-1), (i+1,j) sau (i+1,j+1), dar fără a părăsi deșertul (ar fi omorât de oamenii lui Ali Baba). La trecerea printr-un sector, călătorul colectează comoara din acel sector.

Determinați valoarea totală maximă a comorilor pe care le poate colecta călătorul la traversarea deșertului, știind că pleacă din orice sector al liniei 1 și se oprește în orice sector al linei n, cu respectarea condițiilor de mai sus.

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j+1). Determinați în câte moduri se poate ajunge din camera (1,1) în camera (n,m). Deoarece numărul de posibilități poate fi foarte mare, se cere doar restul acestui număr la împărțirea cu 9901.

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. În fiecare cameră se află o cantitate cunoscută de bomboane. Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j+1), fără a părăsi clădirea.

Un copil intră în clădire, parcurge un șir de camere după regula precizată și iese din clădire, luând din fiecare cameră în care intră toate bomboanele existente. Determinați cantitatea maximă de bomboane care poate fi culeasă precum și un traseu prin clădire în care se adună cantitatea maximă de bomboane.

Se consideră un triunghi de numere naturale format din n linii.Prima linie conține un număr, a doua linie conține 2 numere, etc. ultima linie n, conține n numere. În acest triunghi se pot calcula diverse sume cu n elemente, astfel:

  • termenul i al sumei se află pe linia i din triunghi
  • pentru un anumit termen al sumei, termenul următor se află pe linia următoare și pe aceeași coloană, sau pe coloana imediat următoare spre dreapta.

Să se determine cea mai mică sumă care se poate obține în acest mod și numerele care o alcătuiesc.

Se consideră un triunghi de numere naturale format din n linii.Prima linie conține un număr, a doua linie conține 2 numere, etc. ultima linie n, conține n numere. În acest triunghi se pot calcula diverse sume cu n elemente, astfel:

  • termenul i al sumei se află pe linia i din triunghi
  • pentru un anumit termen al sumei, termenul următor se află pe linia următoare și pe aceeași coloană, sau pe coloana imediat următoare spre dreapta.

Să se determine cea mai mare sumă care se poate obține în acest mod.

La un festival sunt programate n spectacole, pentru fiecare se cunoaşte momentul de început și momentul de sfârșit, exprimate prin numere naturale. Un spectator dorește să urmărească cât mai multe spectacole în întregime.

Determinați numărul maxim de spectacole care pot fi urmărite, fără ca acestea să se suprapună.

Generați toate șirurile de n paranteze rotunde care se închid corect.

Se dă o tablă dreptunghiulară formată din n linii și m coloane, definind n*m zone, unele dintre ele fiind libere, altele conținând obstacole. Într-o zonă precizată se află un șoarece care se poate deplasa pe tablă trecând din zona curentă în zona învecinată cu aceasta pe linie sau pe coloană. Scopul sau este să ajungă la o bucată de brânză aflată într-o zonă de asemenea precizată, fără a părăsi tabla, fără a trece prin zone care conțin obstacole și fără a trece de două ori prin aceeași zonă.

Determinați o modalitate prin care șoarecele poate să ajungă la bucata de brânză.

Se dă o tablă dreptunghiulară formată din n linii și m coloane, definind n*m zone, unele dintre ele fiind libere, altele conținând obstacole. În zona aflată la poziția is, js se află un șoarece care se poate deplasa pe tablă trecând din zona curentă în zona învecinată cu aceasta pe linie sau pe coloană. Scopul sau este să ajungă la o bucată de brânză aflată în zona de la poziția ib, jb, fără a părăsi tabla, fără a trece prin zone care conțin obstacole și fără a trece de două ori prin aceeași zonă.

Determinați câte modalități prin care șoarecele poate ajunge de la poziția inițială la cea a bucății de brânză există.

Să se determine o modalitate de parcurgere integrală a unei tablei de către un cal care se deplasează în maniera specifică calului de șah, astfel încât acesta să nu treacă de două ori prin aceeaşi poziţie.

#329 Bila

Se consideră o tablă de joc de formă dreptunghiulară, împărţită în n linii şi m coloane. Se obţin astfel n*m zone şi se cunoaște înălțimea fiecărei zone. La o poziție cunoscută – linia istart, coloana jstart se află o bilă care se poate deplasa pe o poziție vecină (sus, jos, stânga, dreapta) doar dacă înălțimea poziției vecine este strict mai mică decât înălțimea poziției curente.

Determinați numărul maxim de zone prin care poate să treacă bila pentru a ajunge pe una dintre marginile tablei de joc.

Se citesc două numere naturale nenule n și m. Să se determine toate şirurile cu m elemente din mulţimea {1,2,..,n}, ordonate strict crescător, cu proprietatea că oricare două elemente consecutive în şir au diferenţa mai mică sau egală cu cu 2.

Se dă un număr natural nenul n. Să se determine toate modalităţile distincte de descompunere a numărului n în sumă de 3 şi 5.

Se dă un număr natural n şi o mulţime cu m elemente, numere naturale nenule. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de termeni din acea mulţime.

Se dă un număr natural n şi un interval [a,b]. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale din intervalul [a,b].

Se dă un număr natural n. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale.

Se dă un număr natural n. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale distincte.

Se dă un număr natural n şi un număr m. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de cel puţin m numere naturale distincte.

Se dă o matrice pătratică cu n lini şi n coloane şi elemente numere naturale distincte. Determinaţi cea mai mare sumă a n elemente din matrice, cu proprietatea că oricare două elemente se află pe linii şi coloane distincte.

#19 BFS

Se consideră un graf neorientat cu n vârfuri și m muchii și un vârf cunoscut X. Să se afişeze vârfurile vizitate în urma parcurgerii în lățime a grafului pornind din vârful X.

Se citeşte un număr natural nenul n. Să se afişeze, în ordine invers lexicografică, permutările mulţimii {1,2,..,n}.

#146 graph

Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu N noduri şi M arce, fiecare arc având o distanţă de valoare întreagă.

Dându-se N, M şi cele M arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri.

Grigore Moisil 2013

Natasha a descoperit un nou joc pe calculator. Pe un suport se află N biluțe pe care este scris câte un număr si . Jocul constă în alegerea unei biluțe, biluță care se va ridica de pe suport și va pluti în aer pentru si secunde, apoi se va așeza din nou pe poziția ei în suport. În momentul în care o biluță atinge suportul, prima biluță bst din stânga ei și prima biluță bdr din dreapta ei (care nu s-au așezat pe suport în același moment de timp) se vor ridica în aer, fiecare plutind pentru sst , respectiv sdr secunde, după care se vor reașeza în suport, fiecare pe poziția ei. Această mișcare a biluțelor continuă până când Natasha se plictisește și închide calculatorul. Dar asta nu e tot. În timp ce Natasha urmărește mișcarea biluțelor, ea trebuie să răspundă la M întrebări de forma: “Este biluța bk la momentul de timp tk pe suport sau în aer?”.

Pentru fiecare din cele M întrebări, răspundeți cu 1 dacă biluța b este pe suport, sau cu 0 dacă biluța este în aer.

Grigore Moisil 2013

Cunoscând timpii de evaluare a n proiecte, să se stabilească ordinea de evaluare a acestora, astfel încât să se minimizeze timpul mediu de aşteptare a investitorilor care au depus aceste proiecte.

Se citeşte un număr natural nenul n. Să se afişeze, în ordine lexicografică, permutările mulţimii {1,2,..,n}.

Se citeşte un număr natural nenul n, apoi n numere naturale distincte. Să se afişeze, în ordine lexicografică, permutările mulţimii formate din cele n numere citite.

Se citeşte un număr natural nenul n şi o permutare a mulţimii M={1,2,..,n}. Să se afişeze, în ordine lexicografică, toate permutările mulţimii M care nu conţin elemente alăturate care au fost alăturate şi în permutarea dată.

Se citeşte un număr natural nenul n. Să se afişeze, în ordine lexicografică, permutările fără puncte fixe ale mulţimii {1,2,..,n}.

Se citesc două numere naturale nenule n și k. Să se afişeze, în ordine lexicografică, submulțimile de câte k elemente ale mulţimii {1,2,..,n}.

Să se genereze toate anagramele unui cuvânt citit.

Se citește un număr natural nenul n. Să se afişeze, în ordine lexicografică, toate submulțimile nevide ale mulţimii {1,2,..,n}.

Se citesc două numere naturale nenule n și k. Să se afişeze, în ordine lexicografică, aranjamentele de câte k elemente ale mulţimii {1,2,..,n}.

Urmasii lui Moisil, Iasi, 2013

#149 scara

Claudia vrea să construiască o scară cu N trepte astfel încât prima treaptă să fie la înălţimea 0 şi ultima treaptă să fie la înălţimea H. Fiind pusă pe glume, ea îi cere arhitectului să proiecteze o scară neobişnuită, în care treptele sunt dispuse astfel încât, la un moment dat, să poţi urca, coborî sau rămâne la acelaşi nivel. Pentru a fi uşor de urcat sau coborât, valoarea absolută a diferenţei dintre înălţimile la care se află oricare două trepte consecutive trebuie să fie mai mică sau egală cu o valoare dată, K. Nicio treaptă nu se poate afla la o înălţime negativă sau la o înălţime mai mare decât H.

Scrieţi un program care să determine numărul de scări diferite cu N trepte, ce pot fi construite respectând cerinţele Claudiei. Deoarece numărul de scări poate fi foarte mare, determinaţi restul împărţirii acestui număr la 666013.

Urmasii lui Moisil, Iasi, 2013

#126 DMax

Să se determine maximul distanţelor minime între nodul 1 şi celelalte noduri, într-un graf neorientat.

Cunscându-se timpii necesari reparării unor maşini, se cere să se determine numărul maxim de maşini care pot fi reparate pe rând, în timpul T.