Lista de probleme 29

• Numărul de secvențe distincte în care fiecare literă poate să apară de maximum k ori. Două secvențe sunt considerate distincte dacă diferă fie prin poziția de început, fie prin cea de final.
• Cea mai lungă secvență care conține doar litere distincte. Dacă sunt mai multe secvențe de lungime maximă formate din litere distincte se alege prima din punct de vedere lexicografic (alfabetic).

Privită din spațiu, harta insulei din povestea noastră are forma unui caroiaj pătratic cu L linii și L coloane. Liniile și coloanele sunt numerotate de la 1 la L. În fiecare dintre cele L*L celule se află câte un far. Inițial cel de la poziția 1,1 este aprins și toate respectă regula: orice far are farurile vecine (pe linie și coloană, deci maximum 4) în starea opusă față de starea sa. În urma unei furtuni, s-au întâmplat lucruri ciudate: fulgerele au lovit unul după altul și au afectat starea unor faruri. Sunt trei tipuri de fulgere. Prin schimbarea stării unui far înțelegem că acesta se aprinde dacă este stins și se stinge dacă este aprins.
Se dau date despre fulgere, în ordinea în care acestea acționează. Se cere ca la finalul furtunii să se indice care este starea anumitor faruri, aflate la coordonate precizate de pe insulă.

Există azi mulți viruși care acționează în diferite moduri asupra informației stocate într-un calculator. Printre aceștia există și unii mai puțin periculoși, care se mulțumesc doar să simuleze o anumită alterare a informației. Să presupunem că dorim să scriem un astfel de virus care acționează doar asupra informației de tip text de pe ecranul calculatorului. În mod text, ecranul este constituit din n linii pe fiecare aflându-se câte m caractere. Caracterele sunt reținute în memoria calculatorului prin codul lor ASCII, reprezentat în binar pe 8 biți. Biții sunt numerotați de la 0 la 7 de la dreapta către stânga, cel din stânga fiind cel mai semnificativ bit. La fiecare secundă, virusul transformă simultan toate caracterele de pe ecran. Cunoscând configurația inițială a ecranului, scrieți un program care să rezolve următoarele două cerințe:
1. determină numărul de caractere inatacabile obținute în prima secundă (adică după prima transformare);
2. determină după câte secunde toate caracterele de pe ecran sunt inatacabile.

Pe un perete au fost montate n x m piese pe n rânduri (numerotate de sus în jos, de la 1 la n) și m coloane (numerotate de la stânga la dreapta, de la 1 la m). Piesele sunt tuburi sau coturi având unul dintre tipurile 1, 2, …, 6. Ionel poate introduce o bilă într-o piesă situată pe rândul 1, doar dacă piesa este de tip 2, 4 sau 6. Bila poate coborî un nivel sau se poate deplasa pe orizontală într-o piesă alăturată, dacă îmbinarea pieselor permite aceasta, dar nu poate urca, din cauza gravitației. Bila nu poate trece de două ori prin aceeași piesă și se blochează atunci când nu se mai poate deplasa într-o altă piesă.
Se citesc două numere naturale n, m și apoi n x m numere din mulțimea {1, 2, 3, 4, 5, 6} reprezentând dispunerea pieselor pe perete. Scrieți un program care să rezolve următoarele cerințe:
1. determină numărul maxim de piese prin care poate trece până la blocare o bilă introdusă în una dintre piesele de pe rândul 1, având tipul 2, 4 sau 6;
2. pentru un rând k dat, determină numerele c și t, unde c este coloana minimă pentru care, înlocuind piesa existentă pe rândul k și coloana c cu o piesă de tipul t, se obține un număr cât mai mare posibil de piese prin care poate trece, până la blocare, o bilă introdusă în una dintre piesele de pe rândul 1 având tipul 2, 4 sau 6; dacă există mai multe soluții de a înlocui piesa de pe rândul k și coloana c, se alege varianta cu t minim.

Pasionat de informatică și de puzzle-uri, Dorel a construit o matrice A de dimensiunea N × M lipind mai multe piese dreptunghiulare de diferite dimensiuni. Fiecare piesă este compusă din elemente de dimensiunea 1 × 1 și rețin o aceeași valoare. Matricea rezultată nu are spații libere, iar piesele din care este compusă nu se suprapun. Nu există două piese cu aceeași valoare.
Deși inițial părea că acest design este unul inedit, nu a durat mult până când Dorel s-a plictisit. Astfel, acum el dorește să “upgradeze” matricea construită. Dorel alege o submatrice delimitată de coordonatele (x1,y1) – colțul stânga-sus, (x2,y2) – colțul dreapta-jos (1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ M), unde crește toate valorile elementelor submatricei cu valoarea V.
Dorel efectuează în ordine Q operații de upgrade, operații numerotate de la 1 la Q. La finalizarea celor Q operații de upgrade, toate elementele din matrice au valoarea mai mare sau egală cu K. După o operație de upgrade, structura inițială a matricei se modifică.
Cum priceperea lui Dorel este proverbială, trebuie să îl ajutați în rezolvarea următoarelor cerințe:
1) determinarea coordonatelor piesei cu număr maxim de elemente înainte ca Dorel să efectueze operațiile de upgrade;
2) determinarea numărului minim de operații de upgrade după care toate elementele matricei au valoarea mai mare sau egală cu K.

Cei N elevi participanți la olimpiadă au fost invitați să admire panorama orașului din roata cu N locuri instalată în Orășelul Copiilor. Fiecare elev poartă un tricou inscripționat cu un număr natural, numerele de pe tricouri fiind diferite două câte două și având valori cuprinse între 1 și N. Inițial, ei ocupă toate cele N locuri din roată, începând cu cel mai de jos scaun și continuând cu următoarele scaune, în sensul acelor de ceasornic. Roata se mișcă circular, în sensul acelor de ceasornic, cu un număr de poziții, se oprește și elevul aflat pe scaunul cel mai de jos coboară. În continuare, ea se rotește în același sens, un număr mai mare de poziții, apoi se oprește și coboară elevul aflat pe scaunul cel mai de jos și așa mai departe până când coboară toți elevii.
Cunoscându-se numărul N de elevi, precum și numerele de pe tricouri, în ordinea în care elevii se află inițial în roată, să se determine N numere reprezentând pozițiile cu care roata se mișcă circular pentru a coborî fiecare elev, astfel încât elevii să coboare din roată în ordinea crescătoare a numerelor de pe tricou. Cele N numere de poziții trebuie să fie în ordine strict crescătoare, iar numărul total de poziții trebuie să fie minim.

Ionel are de rezolvat o nouă problemă. El trebuie să construiască un șir de N numere naturale. Numerele din șir pot avea ca divizori primi doar numere prime de o cifră. După construirea șirului, Ionel a constatat că există subsecvențe în șir pentru care produsul elementelor este cubul unui număr natural. Ionel vrea să determine numărul subsecvențelor din șirul construit care au produsul elementelor o valoare ce este cubul unui număr natural.

• este identică cu o altă piesă, dacă această piesă conține exact aceleași cifre, în aceeași ordine cu ale ei sau în ordine inversă. Astfel, piesa C1|C2|C3 este identică cu o altă piesă de forma C1|C2|C3 și cu o piesă de forma C3|C2|C1.
• este prietenă cu o altă piesă dacă aceasta conține exact aceleași cifre ca piesa dată, dar nu neapărat în aceeași ordine. Astfel, piesa C1|C2|C3 este prietenă cu piesele: C1|C2|C3, C1|C3|C2, C2|C1|C3, C2|C3|C1, C3|C1|C2 și C3|C2|C1. Se observă că două piese identice sunt și prietene!
  Un grup de piese prietene este format din TOATE piesele prietene între ele, aflate pe tabla de joc.
  1) Alegeți o piesă de pe tabla de joc, astfel încât numărul M al pieselor identice cu ea să fie cel mai mare posibil și afișați numărul M determinat;
  2) Afișați numărul grupurilor de piese prietene existente pe tabla de joc;
  3) Afișați numărul maxim de piese dintr-o secvență ce conține piese așezate una lângă alta pe tabla de joc, pentru care prima piesă și ultima piesă din secvență sunt prietene.

Maria iubește numerele prime. Ea scrie pe o foaie de hârtie, în ordine strict crescătoare, un șir format din numerele prime care au cel puțin două cifre. Apoi, din numerele care conțin mai mult de două cifre taie cifrele din stânga, astfel încât să rămână exact două cifre. Dacă după tăierea cifrelor numărul obținut nu este cuprins între 10 și 99, numărul este eliminat din șir. De exemplu, numărul prim 101, care are trei cifre, nu va fi scris, deoarece i se taie cifra din stânga, rezultând numărul 01, adică 1, care nu are exact două cifre, deci după tăiere va fi eliminat din șir.
Maria umple un tabel cu 2 * k linii și k coloane, astfel încât, parcurgându-l pe linii, de sus în jos și fiecare linie de la stânga la dreapta, se obțin numerele din șir. Studiind numerele din tabel, constată că printre acestea se află și numere care nu sunt prime. Cunoscând un număr natural k nenul și un număr natural x, ajutați-o pe Maria:
1. Să determine suma numerelor din tabel care nu sunt prime. Dacă nu există numere care nu sunt prime, suma are valoarea 0.
2. Să aleagă x coloane consecutive din tabel, astfel încât acestea să conțină, în total, un număr maxim de numere prime. Dacă există mai multe posibilități, se va alege secvența de coloane consecutive care are o valoare cât mai mare a coloanei de început din secvență. Să se determine numărul primei coloane din secvența aleasă, precum și numărul total de numere prime din secvență.

Aflat într-o vizită cu părinții, Iliuță primește un bilet la tombolă pe care este scris un număr natural S. Pentru a câștiga un premiu, Iliuță trebuie să afle, plecând de la numărul S, un număr câștigător X. Pentru a-l ajuta să ghicească numărul câștigător, mama îi spune lui Iliuță că numărul S de pe biletul său este suma dintre numărul câștigător X și toate numerele obținute plecând de la numărul câștigător X, prin ștergerea cifrei unităților numărului X, apoi, succesiv, prin ștergerea cifrei unităților numărului obținut la pasul anterior, până se ajunge la un număr de o singură cifră.

Cunoscându-se numerele naturale N, S1, A, B, C, D, scrieți un program care rezolvă următoarele cerințe:
1) pentru fiecare dintre termenii șirului S1, S2, …, SN, determină cel mai mare număr natural mai mic strict decât termenul respectiv, pentru care există un număr câștigător; programul va afișa restul împărțirii sumei numerelor obținute la 1018+31;
2) pentru fiecare dintre termenii șirului S1, S2, …, SN, determină câte numere naturale mai mici sau egale cu termenul respectiv NU au număr câștigător; programul va afișa restul împărțirii sumei rezultatelor obținute la 1018+31.