Lista de probleme 20

Stadionul pe care Taylor Swift concertează în cadrul Turului Eras poate fi reprezentat cu ajutorul unei matrice cu N linii și M coloane, numerotate începând de la 1. În fiecare celulă (i, j), de pe linia i și coloana j (1 ≤ i ≤ N și 1 ≤ j ≤ M), se află câte un scaun pe care pot fi așezate brățări ale prieteniei. Înainte de concert, pe fiecare dintre dintre cele N x M scaune, nu se află nicio brățară. Pe durata concertului, Steven efectuează, în ordine, U modificări, care pot fi de două tipuri:

• tipul (L, a, v) cu semnificația că pe fiecare dintre cele M scaune de pe linia a sunt așezate câte v brățări noi (1 ≤ a ≤ N);
• tipul (C, a, v) cu semnificația că pe fiecare dintre cele N scaune de pe coloana a sunt așezate câte v brățări noi (1 ≤ a ≤ M).

După ce toate modificările au fost efectuate, Caroline îi pune lui Steven, în ordine, Q întrebări. Pentru fiecare întrebare, se consideră un număr natural K și descrierile a K submatrice. Steven trebuie să determine câte brățări sunt, în total, pe scaunele ce se află în cel puțin una dintre cele K submatrice considerate. Ajutați-l pe Steven să răspundă corect la toate cele Q întrebări puse de Caroline!

Yamada, cel mai bun jucător al jocului Forest of Savior, se pregătește pentru a participa într-o bătălie împreună cu coechipierii săi. Pentru a câștiga această luptă, Yamada trebuie să se folosească de diverse obiecte magice pe care le-a obținut de-a lungul timpului. Ajutați-l pe Yamada să determine:
1. Dintre toate obiectele avute la dispoziție, care este cea mai puternică carte de vrăji, care este cea mai puternică poțiune și care este cea mai puternică nestemată.
2. În ce ordine ar trebui să se folosească de obiectele magice astfel încât, la final, puterea personajului său să fie maximă.
3. Care este puterea maximă pe care o poate atinge personajul său. Fiindcă acest număr poate fi foarte mare, Yamada vrea doar să afle care ar fi restul împărțirii acestui număr la 1.000.000.007.

Se consideră un număr natural format din n cifre. Inserând între cifrele numărului dat p operatori + şi q operatori - se obţine o expresie aritmetică. Un operator poate fi inserat doar între două cifre, deci înaintea primei cifre a numărului nu se poate plasa un operator.
Scrieţi un program care, pentru un număr dat, determină valoarea maximă a unei expresii aritmetice care se poate obţine inserând p operatori + şi q operatori - între cifrele numărului dat.

Paftenie trăiește într-un oraș pătratic, împărțit în n x n regiuni pătratice, așezate pe n linii, numerotate de la 1 la n, și n coloane, numerotate de la 1 la n. Cum Paftenie este prea distras de micul său dejun englezesc cu cârnăciori și fasole fiartă, apelează la voi pentru a determina:

1) Numărul maxim de cetățeni care iau micul dejun împreună în cea de-a doua zi.
2) Gradul de fericire al orașului său.

O matrice pătratică A_{ij} de dimensiuni N x N cu N impar se numește matrice spirală dacă respectă următoarele proprietăți când este parcursă în spirală.

• Pentru oricare celulă (i, j) din matrice, fie A[i, j] = 0, fie A[i,j] nu conține cifra 0.
• Fie (i, j) oricare celulă mai puțin cea din centru și (k, l) celula parcursă anterior din matrice, și fie c oricare cifră nenulă, adică de la 1 la 9:
  a) Dacă c divide i + j, atunci A[i, j] conține cifra c dacă și numai dacă A[k, l] nu conține cifra c.
  b) Dacă c nu divide i + j, atunci A[i, j] conține cifra c dacă și numai dacă A[k, l] conține cifra c.
  c) Pentru numărul aflat în celula din centru, fiind prima parcursă, nu avem astfel de restricții.

• Un element din matrice va fi 0 dacă și numai dacă acesta nu are voie să conțină nicio cifră de la 1 la 9 conform regulilor de mai sus.

Dându-se o matrice pătratică A de dimensiune N, trebuie să determinați care este numărul minim de elemente din matrice care ar trebui înlocuite (în celulele respective pot fi scrise orice alte numere naturale) pentru ca A să devină o matrice spirală.

Maria a primit cadou de ziua ei o cutie cu piese de puzzle, etichetate cu numere naturale. Pentru a-l rezolva trebuie să lipească între ele, în ordinea în care le extrage din cutie, cât mai multe piese, formând astfel grupuri de piese. Cunoscând cele N numere naturale care se găsesc pe etichetele pieselor de joc, în ordinea în care aceste se extrag din cutie, să se determine:
1. Numărul de grupuri pe care le obține Maria după ce rezolvă jocul de puzzle;
2. Cele K numere înscrise pe etichetele grupurilor alese de Maria.

Robin Hood și Little John au hotărât să stabilească care dintre ei este cel mai bun arcaș. Pentru aceasta au construit n ținte așezate în linie dreaptă și numerotate de la 1 la n. Au stabilit apoi distanța de tragere. Cei doi se deplasează prin fața țintelor în linie dreaptă la distanța stabilită de comun acord. Cei doi pot trage simultan în aceeaşi țintă sau într-una deja atinsă. Concursul se încheie în momentul în care fiecare țintă a fost atinsă cel puțin o dată.
1. Se cere să se determine timpul în care se termină concursul.
2. Care sunt țintele atinse exact o dată în timpul concursului.
3. Care sunt țintele atinse de cele mai multe ori în timpul concursului.

Spunem că o secvență de numere (a[i], a[i + 1], ..., a[j]) este esm dacă are cel puțin 3 elemente și există cel puțin o pereche de numere (a[x], a[y]) în acea secvență, cu i ≤ x < y < j, astfel încât a[x] * a[y] = a[j]. Se dă un șir a[1], a[2], ..., a[n] de numere naturale. Să se determine:

• Numărul de secvențe esm din șir de lungime 3.
• Numărul de secvențe esm din șir care se termină cu elementul de la ultima poziție, a[n].
• Numărul de secvențe esm din șir.

Fie x[1], x[2], ..., x[N] un șir de N numere naturale. Două poziții i și j, cu 1 ≤ i ≤ j ≤ N, definesc secvența [i, j] care va conține numerele x[i], x[i + 1], ..., x[j]. O secvență [i, j] cu proprietatea că suma tuturor elementelor din secvență are cifra de control egală cu 9 o vom denumi secv9. Scrieţi un program care, cunoscând N, numărul de elemente din șir, respectiv x[1], x[2], ..., x[N], elementele din șir, rezolvă următoarele două cerințe:

• afișează lungimea maximă a unei secvențe secv9;
• afișează numărul de secvențe secv9 din șir.

Se dă un șir A cu N elemente, numere naturale nenule, și un număr natural K. O subsecvență a șirului este un șir format din unul sau mai multe elemente aflate pe poziții consecutive în șirul inițial. Spunem că o valoare x se numește element majoritar al unei secvențe de lungime m, dacă ea apare în aceasta de cel puțin \( \left[ \frac{m}{2} \right] + 1\) ori. Să se afișeze valorile care sunt elemente majoritare pentru cel puțin o subsecvență de lungime mai mare sau egală cu K a șirului A.