Fișierul intrare/ieșire nori.in, nori.out Sursă ONI 2016 baraj gimnaziu
Autor Gelu Mustață Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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:

  1. 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;
  2. 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

  • 2R, C200; 1N50; 1T2 000 000;
  • 1Zi25; Zi este număr impar; Zi poate fi mai mare decât R sau C;
  • 0Wi200;
  • Pentru cerinta 1, se garantează că 1B < 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 2YiC
  • Dacă Yi = 1 atunci 2XiR
  • 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).

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii