Fişierul intrare/ieşire:nori.in, nori.outSursăONI 2016 baraj gimnaziu
AutorGelu MustataAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.innori.outExplicaţ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 sa te autentifici pentru a trimite solutii. Click aici