Fişierul intrare/ieşire:	eprubeta.in, eprubeta.out	Sursă	Stelele Informaticii 2007-2008, Clasele 11-12
Autor	Alexandru Mosoi	Adăugată de	Alexandru Mosoi •alexandru.mosoi
Timp execuţie pe test	0.95 sec	Limită de memorie	128000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Eprubeta

Bubu e la ora de chimie si are in fata un suport in forma de patrat pentru NxN eprubete. Eprubeta aflata pe coloana x si linia y contine un volum fixat de lichid a_x,y. Tocilar fiind, Bubu inventeaza un joc de o singura persoana. Intai fixeaza doua numere i ≤ j, iar asupra patratului cu coltul stanga-sus (i, i) si coltul dreapta (j, j) efectueaza operatii care pot fi de urmatoarele doua tipuri:

1. roteste patratul cu 180 grade
2. calculeaza cat lichid se afla in eprubetele din patratul delimitat

Vi se cere sa scrieti un program care, dandu-se cat de mare e suportul si cat lichid este initial in fiecare eprubreta sa simuleze M operatii date. In final se va determina cat lichid este in fiecare eprubeta.

Date de intrare

Fisierul de intrare eprubeta.in are urmatorul format:

• Pe prima linie se vor afla cinci numere numere N, M, Z, A, si B. N este descris din enunt, iar M este numarul de operatii. Pentru a nu avea un fisier de intrare de dimensiuni prea mari, valorile volumelor de lichid din fiecare eprubeta vor fi generate dupa formula: a_{x, y} = ((y + A) * (x + B) / 4) % Z.
• Pe urmatoarele M linii se vor afla trei numere descriind codul operatiei (1 sau 2, ca mai sus), i, respectiv j, unde i si j au semnificatiile din cerinta.

Date de iesire

Fisierul de iesire eprubeta.out va avea urmatorul format:

• Pentru fiecare operatie de tipul 2 se va afisa un numar reprezentand volumul total de lichid aflat in patratul descris in operatie.
• Pentru a evita un fisier de iesire de dimensiune mare, pe ultima linie se va scrie un numar T. T va fi egal cu suma dupa linia u (0 ≤ u < N) din (suma elementelor de pe linia u)² * (u + 1). T va fi scris modulo 2³².

Restrictii si precizari

• 0 < N ≤ 2000
• 0 < M ≤ 2000
• 0 ≤ x, y < N
• 0 < A, B ≤ 30000
• 0 < Z ≤ 100000
• 0 ≤ a_{x, y} < Z
• Se garanteaza ca suma volumelor de lichid din toate eprubetele e strict mai mica decat 2³¹
• Pentru a evita orice explozie continutul eprubetelor nu va fi alterat.
• Liniile si coloanele sunt indexate de la 0.
• Daca rezultatul fiecarei operatii de tipul 2 este corect se va acorda 60% din punctajul testului.
• Daca nu doriti sa calculati sumele intermediare, atunci pentru fiecare operatie de tipul 2 se va afisa 0.
• Daca numarul T este corect se va acorda 40% din punctajul testului.
• Pentru 20% din teste N ≤ 400
• Pentru a nu avea probleme cu depasirea limitei de memorie, evitati alocarea dinamica a multor obiecte de acelasi fel prin folosirea unui vector alocat static.

Exemplu

Explicatie

• Patratul rezultat este
  8 10 0 1 2
  10 1 2 4 5
  1 3 4 6 8
  3 5 7 9 0
  4 7 9 0 2
• Pentru prima operatie, (1 0 0), trebuie sa rotim coltul din stanga sus. Nu afecteaza patratul.
• Pentru a doua operatie, (2 1 3), valoarea corecta este: 1+2+4 + 3+4+6 + 5+7+9 = 41
• Pentru a treia operatie, (2 1 1), valoarea corecta este 1
• Ultima operatie, (1 1 2), transforma patratul initial in:
  8 10 0 1 2
  10 4 3 4 5
  1 2 1 6 8
  3 5 7 9 0
  4 7 9 0 2
• Valoarea lui T este 21² * 1 + 26² * 2 + 18² * 3 + 24² * 4 + 22² * 5 = 441 + 1352 + 972 + 2304 + 2420 = 7489

Cum se trimit solutii?