Lista de probleme 1921

Fermierul Petrică deține o livadă de formă dreptunghiulară, împărțită în N×M sectoare, dispuse pe N linii și M coloane, in fiecare sector fiind plantat un arbore dintr-o anumită specie, identificată printr-o literă mare a alfabetului englez.

Vecinul său, fermierul Ion dorește să cumpere o zonă dreptunghiulară din livada lui Petrică, care să aibă suprafața S și pentru fiecare specie prezentă în acea zonă numărul de arbori să fie același.

Determinați în câte moduri se poate alege zona dorită de Ion, precum și o modalitate de alegere.

Vrăjitorul Amaric a găsit un șir cu N numere, pe care vrea să-l transforme astfel încât să conțină o secvență de valori egale de lungime cât mai mare. Pentru aceasta, Amaric a pregătit două feluri de magii:

- magia de tip 1: alege două numere din șir și le schimbă între ele în șir. Această magie se poate aplica de oricâte ori.
- magia de tip 2: alege un număr din șir și îl mărește cu o valoare care este divizor al acestuia. Această magie se poate aplica cel mult o dată pentru fiecare număr din șir.

De exemplu, dacă șirul contine numerele (6, 8, 4, 8), aplicând magia de tip 1 pentru numerele 4 și 8, șirul devine (6, 8, 8, 4). Dacă aplicăm magia de tip 2 pentru numărul 4, el poate deveni 5 sau 6 sau 8.

Scrieți un program care să determine lungimea maximă a unei secvențe de numere egale dacă:

1. Amaric aplică doar magii de tipul 1;
2. Amaric aplică doar magii de tipul 2;
3. Amaric aplică magii de tipul 1 și de tipul 2.

Se consideră șirul v, care conține n elemente.

Scrieți un program care să determine în câte moduri se pot selecta patru numere din șir, de pe poziții diferite, ale căror sumă este egală cu s.

Gigel are un șir cu N beculețe, numerotate de la 1 la N, inițial toate stinse. Cu acest șir Gigel face M operații, de două tipuri:

• 1 i j: toate beculețe numerotate cu valori între i și j își schimbă starea
• 2 k: se determină starea beculețului numerotat cu k.

Scrieți un program care să determine citește N M și cele M operații și determină rezultatul fiecărei operații de tipul 2.

Se dau n dulapuri, numerotate de la 1 la n, pentru fiecare dulap cunoscându-se numărul de mingi care pot fi plasate în dulap. Se dau m mingi numerotate de la 1 la m. Toate mingile se pun în dulapuri. Pentru fiecare din cele k mingi solicitate să se precizeze în ce dulap au fost repartizate.

Un elev dispune de n cuburi, pentru fiecare cub cunoscându-se latura sa ci. El dorește să construiască m turnuri, fiecare turn conținând doar cuburi de aceeași dimensiune. Să se determine înălțimea maximă care se poate obține pentru fiecare din cele m turnuri.

Se dau coordonatele a n puncte în plan și razele a m cercuri cu centrul în originea sistemului de coordonate. Scrieți un program care determină numărul de puncte conținut de fiecare cerc.

Marele dramaturg BONIFACCI a uimit lumea teatrului cu noua sa capodoperă, Dada?!. Pentru că teatrul modern este un pic minimalist, piesa are un singur actor. Pentru că teatrul modern este un pic absurd, Actul 1 constă doar din replica A, iar Actul 2 constă doar din replica D. La repetiție, actorul și-a propus să recite, cu intonație, L replici alăturate din actul al N-lea, începând cu replica numărul P, până la replica cu numărul P+L-1. Determinați secvența de caractere rostite de actor la repetiție.

Kida vă oferă două numere N și M. Ea vă mai oferă și un șir, A, de N numere naturale cuprinse între 0 și M inclusiv. Șirul A conține două tipuri de valori: valori cuprinse între 1 și M, care nu pot fi schimbate, respectiv valori de 0, care pot fi înlocuite cu orice număr cuprins între 1 și M. Pentru un șir V, cu valori între 1 și M, vom nota cu count(V) numărul de perechi (V[i], V[j]) de pe pozițiile i și j astfel încât i < j și cmmdc(V[i], V[j]) = 1. Se cere suma count(V) pentru toate șirurile distincte V care se pot obține din șirul A, înlocuind toate valorile de 0 cu numere cuprinse între 1 și M. Deoarece acest număr poate să fie foarte mare, se cere restul împărțirii sale la 1.000.000.009.

Se dă un tablou bidimensional cu N linii și N coloane. Există Q poziții distincte, etichetate cu numere naturale distincte de la 1 la Q, unde în tablou există valoarea 1, la toate celelalte poziții din tablou există valoarea 0. Pentru o poziție oarecare, dintre cele Q date, numim “forța” acelei poziții numărul subtablourilor din tabloul dat care conțin doar o singură valoare 1, cea aflată la acea poziție, restul elementelor din subtablouri fiind egale cu 0. Pentru un șir format din P etichete distincte, dintre cele corespunzătoare celor Q poziții date, se cere să se calculeze suma “forțelor” acestora.