Lista de probleme 21

Ștefan Vodă, după bătălia de la Vaslui, și-a aliniat cei n oșteni și a dat fiecăruia câte un număr natural nenul a0, a1, … an-1. Având o bună dispoziție după strașnica victorie, voievodul face două tipuri de operații:

• 1 i x (aceasta este primeneala!): oșteanul de la poziția i primește o nouă valoare (ai devine egal cu x);
• 2 x y d (aceasta este iscoditura!): câte numere din secvența de oșteni ax, ax+1, …, ay au cel mult d divizori?

Scrieți un program care răspunde corect la toate iscoditurile și veți fi la fel de faimoși ca Ștefan cel Mare!

Spunem că un număr natural x este fibopower dacă acesta se poate descompune în produs de trei numere Fibonacci distincte. Se consideră șirul A = (A[1], A[2], ..., A[n] cu n elemente numere naturale nenule, respectiv un număr natural k cuprins între 1 și n. O secvență a șirului A este formată din valori situate pe poziții consecutive în A: A[i], A[i+1], ..., A[j], unde 1 ≤ i ≤ j ≤ n. Pe șirul A se fac q interogări de tipul x y cu semnificația: să se determine numărul secvențelor A[i], A[i+1], ..., A[j] cu x ≤ i ≤ j ≤ y care conțin exact k numere fibopower. Fiind cunoscute n, k, q și cele n elemente ale șirului A, să se determine răspunsul pentru cele q interogări date.

Octav începe din colțul stânga-sus al foii de matematică (pătrăţelul 1, 1) și merge diagonal în jos, marcând cu x fiecare pătrățel prin care trece. Când ajunge la una dintre marginile foii, el schimbă direcţia şi sensul de deplasare. El se deplasează continuu, marcând cu x pătrăţelele prin care trece, până când ajunge din nou într-un colț al foii. Octav consideră că pătrăţelele marcate cu x sunt ziduri. Pătrăţelele marcate cu x delimitează pe foaia de matematică diferite modele geometrice. p. Cunoscând numerele naturale N şi M, scrieţi un program care să rezolve următoarele cerinţe:
1. determină numărul de pătrăţele marcate cu x;
2. determină numărul total de modele obţinute;
3. determină numărul de categorii obţinute;
4. determină descrierile categoriilor de modele obţinute, ordonate crescător după pătrăţelul reprezentativ.

Pentru o listă de numere naturale vom numi reprezentant al listei numărul care apare de cele mai multe ori în aceasta. În caz de egalitate (adică mai multe valori cu număr maxim de apariții) reprezentantul este suma acestor valori. Se dă o listă inițial vidă cu două tipuri de operații codificate în felul următor:

• 1 x – adăugăm un element nou cu valoarea x la sfârșitul listei și ne întrebăm ce valoare are reprezentantul după această modificare;
• 2 x – eliminăm primul element cu valoarea x din listă, ne întrebăm care este reprezentantul listei după eliminare și punem la loc elementul pe poziția lui.

Se dă șirul A de N numere naturale nenule A = (A[1], A[2], A[3], ..., A[N]). Numim secvență snake a șirului A o secvență S = (A[L], A[L+1], A[L+2], ..., A[R]) cu 1 ≤ L < R ≤ N cu proprietatea că fiecare poziție din șirul compress(S) este minim local sau maxim local. Să se determine câte perechi de poziții (L,R) cu 1 ≤ L < R ≤ N au proprietatea că secvența S = (A[L], A[L+1], A[L+2], ..., A_R) este snake.

La un concurs de pinball, în 2026, s-a întâmplat ceva inedit. Cei n participanți la concurs au obținut punctajele v[1], v[2], ..., v[n], numere naturale nenule. Pe lângă obișnuitele aplauze, au fost recompensați la finalul concursului cu bomboane. O persoană care a obținut punctajul x a primit un număr de bomboane egal cu numărul de divizori naturali ai lui x.
1. Știind că la începutul concursului, bugetul a fost de b bomboane, să se determine numărul nr de bomboane care au rămas după concurs.
2. Să se determine ce punctaj P cu proprietatea 1 ≤ P ≤ 6.000.000.000 ar trebui să obțină al (n+1)-lea participant, astfel încât să nu mai rămână nicio bomboană.

Fiind încântat de proba de biatlon de la jocurile olimpice de iarnă, Rareș s-a gândit să inventeze propriul joc. El a așezat în linie un număr de ținte, apoi și-a propus să le doboare folosind mingea. Mingea fiind mai mare, la o lovitură se doboară două ținte aflate una lângă alta. Dacă o țintă este izolată (fără alta vecină) ea poate fi doborâtă la o lovitură cu mingea.

Fiind inventiv, el și-a stabilit câteva reguli speciale de joc:

• Dacă o țintă este vecină cu o alta, aceasta nu poate fi doborâtă singură la lovitura următoare;
• El dorește să execute un număr maxim de lovituri până reușește să doboare toate țintele, respectând regulile jocului;
• Rareș este un foarte bun executant de lovituri cu mingea, așa că el reușește să lovească mereu ținta sau țintele propuse.

Problema are două cerințe, în funcție de valoarea lui C ∈ {1, 2}.

1. C=1. Să se determine numărul maxim de lovituri pe care le poate executa pentru șirul de valori din fișierul de intrare.
2. C=2. Rareș poate să modifice configurația țintelor în felul următor: formează N − 1 grupuri prin alipirea țintelor din ultimul grup la unul dintre celelalte grupuri. Dorește să formeze un astfel de set cu N − 1 grupuri asupra căruia să poată executa un număr de lovituri strict mai mare decât cel maxim posibil pe setul inițial de N grupuri. Programul trebuie să determine grupurile la care poate fi alipit ultimul astfel încât să se îndeplinească dorința lui.

În vistieria cetății se află N lacăte așezate în linie, numerotate de la 1 la N, fiecare având inscripționat un cod numeric în baza 10. Definim amprenta unui cod ca fiind un număr format din două cifre, \( \overline{XY} \) , unde \(X\) este cea mai mare cifră a codului, iar \(Y\) este cifra cea mai mică. De exemplu pentru codul 327003 amprenta este 70.

Două lacăte din șir situate pe pozițiile i și j formează o pereche echilibrată dacă i < j și codurile lor Cod[i] și Cod[j] au aceleași cifre, indiferent de ordinea și numărul de apariții al acestora. De exemplu, dacă primul lacăt din șir și al treilea au codurile Cod[1] = 1221 și Cod[3] = 211, atunci perechea (Cod[1], Cod[3]) este echilibrată deoarece ambele sunt formate exact din cifrele {1, 2} și 1 < 3.

Scrieți un program care rezolvă următoarele cerințe, cerința de rezolvat fiind dată de C ∈ {1, 2, 3}:

C=1. Determinați câte lacăte au amprenta formată din două cifre identice.
C=2. Considerăm că din fiecare cod trebuie să eliminăm exact o apariție a unei cifre, astfel încât suma amprentelor rezultate să fie maximă. Determinați această sumă.
C=3. Determinați numărul total de perechi echilibrate din șirul inițial al celor N lacăte.

Sofia iubește șotronul și îl joacă în fiecare zi în spatele blocului. Șotronul poate fi reprezentat ca un șir de 𝑁 pătrățele așezate în linie, numerotate de la 1 la N.

Jocul Sofiei constă în mai multe ture de joc. La începutul fiecărei ture a jocului, Sofia se află în poziția de start, aflată imediat înaintea căsuței 1, și aruncă o piatră care pică pe una dintre căsuțele șotronului. Considerăm că numărul căsuței pe care a picat piatra este i. Fetița trebuie apoi să se deplaseze până la căsuța i, efectuând unul sau mai multe salturi și să ia piatra. Cum Sofia se antrenează zilnic, a învățat deja să sară peste mai multe căsuțe, din căsuța numărul i poate sări pe căsuțele i+1, i+2 respectiv i+3, însă nu poate sări pe căsuța i+4 sau mai departe.

Regula jocului spune că pentru turele de joc care urmează, Sofia nu mai are voie să calce pe căsuța i, aceasta fiind marcată ca interzisă. Dacă piatra cade din nou pe o căsuță marcată anterior ca interzisă, jocul se încheie imediat întrucât fetița nu mai poate călca pe acea căsuță.

Cunoscându-se numărul N de pătrățele ale șotronului, numărul Q de aruncări pe care le-ar putea efectua fetița și indicele căsuței pe care ar ateriza piatra la fiecare aruncare, determinați care este prima aruncare la care Sofia nu mai poate recupera piatra.

În laboratoarele Marii Ghilde, ucenicul Jean Carapace are pe masa de lucru N eprubete asezate in linie. Eprubetele sunt numerotate de la stanga la dreapta cu indici de la 1 la N. Fiecare eprubetă i conține inițial o cantitate de Esență Primordială, V[i] , număr natural nenul. Definim o „Pereche Pură” ca fiind două eprubete vecine ale căror cantități sunt reprezentate prin numere prime între ele, adică cmmdc(V[i] , V[i+1]) = 1. O proprietate esențială a configurației inițiale este că se garantează existent, a a cel puțin unei astfel de perechi.

Scopul lui este să obțină „Scara Perfectă”, adică o configurație în care cantitatea de esență din fiecare eprubetă este
egală cu indicele ei:

Eprubeta ₁ = 1, Eprubeta ₂ = 2, …, Eprubeta _N = N.

Pentru a modifica nivelul substanței, el poate folosi doar fenomenul de Rezonanță între două eprubete vecine. Mai exact, operațiile se aplică pe două eprubete situate la indicii A și B, cu condiția ca |A − B| = 1. Operațiile permise sunt:

• adun A B ⇒ V[A] ← V[A] + V[B] (Eprubeta A câștigă o cantitate de esență egală cu valoarea din eprubeta B)
• scad A B ⇒ V[A] ← V[A] − V[B] (Eprubeta A pierde o cantitate de esență egală cu valoarea din eprubeta B)

La aplicarea operațiilor, trebuie respectate următoarele reguli:

1. La fiecare operație, doar eprubeta cu indicele A își modifică valoarea. Eprubeta cu indicele B rămâne neschimbată.
2. Cantitatea de esență din orice eprubetă trebuie să se mențină în intervalul de siguranță [1, 10sup>5] în orice moment (inclusiv intermediar).
3. Numărul total de operații nu poate depăși 106.

Se cunosc C (numărul cerinței, 1 sau 2), N numărul de eprubete, precum și valorile V[i]. Determinați:

1. Secvența de lungime maximă din șir în care oricare două eprubete alăturate formează o Pereche Pură, dacă C = 1. Dacă există mai multe astfel de secvențe, se va afișa cea cu indicele de început minim.
2. O succesiune de operații care transformă șirul inițial în Scara Perfectă, respectând toate regulile de mai sus, dacă C = 2.