Lista de probleme 3

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.