Lista de probleme 4

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.

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 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.

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.