Fișierul intrare/ieșire | nori.in, nori.out | Sursă | ONI 2016 baraj gimnaziu |
---|---|---|---|
Autor | Gelu Mustață | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 4096 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Nori (baraj gimnaziu)
Pe planeta Aret există un continent de formă dreptunghiulară împărțit în R x C pătrate identice, dispuse alăturat câte C pe fiecare rând și câte R pe fiecare coloană. Fiecare pătrat reprezintă câte o țară. Rândurile sunt numerotate de la 1 la R de sus în jos, iar coloanele de la 1 la C de la stânga la dreapta. O țară situată pe rândul X și coloana Y este identificată prin coordonatele (X,Y).
Deasupra continentului circulă N nori, de diferite tipuri, ca în figura 1, care sunt formați și ei din pătrate identice, iar suprafața unui pătrat acoperă în întregime suprafața unei țări. Norii pot intra pe continent prin vest și se deplasează pe orizontală spre est, sau pot intra pe continent prin nord și se deplasează pe verticală spre sud.
În fiecare oră, norii se deplasează cu câte o poziție în direcția de deplasare, iar atunci când norul părăsește în totalitate suprafața continentului, intră din nou pe continent deasupra aceleași țări acoperite la prima intrare (poziția inițială) și continuă deplasarea. Norii intră pentru prima dată deasupra continentului după un timp de așteptare W și se pot suprapune în timpul deplasării. Un nor se numește ”întreg”, dacă în timpul deplasării, există cel puțin o oră în care norul este situat deasupra continentului și nu depășește marginile continentului.
În exemplul din figura 2 sunt trei nori, simbolizați prin cifrele 1, 2 și 3. Norul 1 – de tip 1 – pătrunde pe continent prin țara (2,1) după 3 ore de așteptare, norul 2 – de tip 3 – pătrunde prin țara (4,1) după 0 ore de așteptare, iar norul 3 – de tip 5 – pătrunde prin țara (1,3) după 1 oră de așteptare. În acest exemplu este redată poziția fiecărui nor în primele 9 ore. În țările care nu sunt acoperite de nori cerul este senin, iar în țările peste care se suprapun cel puțin doi nori este furtună.
Cerințe
Cunoscând numerele naturale R, C, N, coordonatele țării pe unde intră fiecare nor pe continent, tipul acestuia, precum și timpul de așteptare al fiecărui nor la prima intrare pe continent, se cere:
- Să se determine numărul A al norilor întregi și timpul B minim după care toți norii întregi sunt situați deasupra continentului, fără a depăși marginile acestuia;
- Cunoscând și un timp T, să se determine numărul S de țări care au cerul senin după T ore și numărul F de țări în care este furtună după T ore.
Date de intrare
Fișierul de intrare nori.in conține:
- Pe prima linie, un număr natural P care poate avea doar valorile 1 sau 2;
- Pe linia a doua, patru numere naturale R, C, N și T, în această ordine, despărțite prin câte un spațiu, cu semnificația din enunț;
- Pe următoarele N linii se află câte patru numere naturale Xi, Yi, Zi și Wi, unde i ∈ {1, 2, 3, …, N} în această ordine, despărțite prin câte un spațiu. Numerele Xi și Yi reprezintă linia și coloana, țării prin care intră norul i pe continent, Zi reprezintă tipul norului i, iar Wi reprezintă timpul de așteptare al norului i la prima intrare deasupra continentului.
Date de ieșire
- Dacă valoarea lui P este 1, se va rezolva numai cerința 1. În acest caz, fișierul de ieșire nori.out va conține pe prima linie două numere naturale A și B, în această ordine, despărțite prin câte un spațiu. Numărul A reprezintă numărul norilor întregi, iar B este timpul minim determinat;
- Dacă valoarea lui P este 2, se va rezolva numai cerința 2. În acest caz, fișierul de ieșire nori.out va conține pe prima linie două numere naturale S și F, în această ordine, despărțite printr-un spațiu. Numărul S reprezintă numărul de țări care au cer senin după T ore, iar F reprezintă numărul de țări în care este furtună după T ore.
Restricții
- 2 ≤ R, C ≤ 200; 1 ≤ N ≤ 50; 1 ≤ T ≤ 2 000 000;
- 1 ≤ Zi ≤ 25; Zi este număr impar; Zi poate fi mai mare decât R sau C;
- 0 ≤ Wi ≤ 200;
- Pentru cerinta 1, se garantează că 1 ≤ B < 300 000;
- Pot exista mai mulți nori care intră pe continent prin aceeași țară;
- Niciun nor nu intră pe continent prin țara cu coordonatele (1,1);
- Dacă Xi = 1 atunci 2 ≤ Yi ≤ C
- Dacă Yi = 1 atunci 2 ≤ Xi ≤ R
- Pentru rezolvarea corectă a cerinței 1 se obține 30% din punctaj, iar pentru cerința 2 se obține 70% din punctaj.
Exemple
nori.in | nori.out | Explicație |
---|---|---|
1 5 3 3 9 2 1 1 3 4 1 3 0 1 3 5 1 |
2 9 |
Vezi exemplul din figura 2. Sunt 2 nori întregi și anume norul 1 și norul 2. Cei doi nori sunt situați în întregime deasupra continentului, prima dată după 9 ore. |
2 5 3 3 9 2 1 1 3 4 1 3 0 1 3 5 1 |
8 2 |
Vezi exemplul din figura 2. După T=9 ore țările cu cer senin sunt la coordonatele: (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 3), (5, 1) iar țările în care este furtună sunt la coordonatele: (4, 3) și (5, 2). |