nori

Time limit: 0.1s
Memory limit: 4MB
Input: nori.in
Output: nori.out

Pe planeta Aret există un continent de formă dreptunghiulară împărțit în RCR \cdot C pătrate identice, dispuse alăturat câte CC pe fiecare rând și câte RR pe fiecare coloană. Fiecare pătrat reprezintă câte o țară. Rândurile sunt numerotate de la 11 la RR de sus în jos, iar coloanele de la 11 la CC de la stânga la dreapta. O țară situată pe rândul XX și coloana YY este identificată prin coordonatele (X,Y)(X, Y).

Deasupra continentului circulă NN nori, de diferite tipuri, ca în figura 11, 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 22 sunt trei nori, simbolizați prin cifrele 11, 22 și 33. Norul 11 - de tip 11 - pătrunde pe continent prin țara (2,1)(2, 1) după 33 ore de așteptare, norul 22 - de tip 33 - pătrunde prin țara (4,1)(4, 1) după 00 ore de așteptare, iar norul 33 - de tip 55 - pătrunde prin țara (1,3)(1, 3) după 11 oră de așteptare. În acest exemplu este redată poziția fiecărui nor în primele 99 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 RR, CC, NN, 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 AA al norilor întregi și timpul BB 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 TT, să se determine numărul SS de țări care au cerul senin după TT ore și numărul FF de țări în care este furtună după TT ore.

Date de intrare

Fișierul de intrare nori.in conține:

  • Pe prima linie, un număr natural PP care poate avea doar valorile 11 sau 22;
  • Pe linia a doua, patru numere naturale RR, CC, NN și TT, în această ordine, despărțite prin câte un spațiu, cu semnificația din enunț;
  • Pe următoarele NN linii se află câte patru numere naturale XiX_i, YiY_i, ZiZ_i și WiW_i, unde i{1,2,3,,N}i \in \{1, 2, 3, \dots, N\} în această ordine, despărțite prin câte un spațiu. Numerele XiX_i și YiY_i reprezintă linia și coloana, țării prin care intră norul ii pe continent, ZiZ_i reprezintă tipul norului ii, iar WiW_i reprezintă timpul de așteptare al norului ii la prima intrare deasupra continentului.

Date de ieșire

  • Dacă valoarea lui PP este 11, se va rezolva numai cerința 11) În acest caz, fișierul de ieșire nori.out va conține pe prima linie două numere naturale AA și BB, în această ordine, despărțite prin câte un spațiu. Numărul AA reprezintă numărul norilor întregi, iar BB este timpul minim determinat;
  • Dacă valoarea lui PP este 22, se va rezolva numai cerința 22). În acest caz, fișierul de ieșire nori.out va conține pe prima linie două numere naturale SS și FF, în această ordine, despărțite printr-un spațiu. Numărul SS reprezintă numărul de țări care au cer senin după TT ore, iar FF reprezintă numărul de țări în care este furtună după TT ore.

Restricții și precizări

  • 2R,C2002 \leq R, C \leq 200;
  • 1N501 \leq N \leq 50;
  • 1T2 000 0001 \leq T \leq 2 \ 000 \ 000;
  • 1Zi251 \leq Z_i \leq 25; ZiZ_i este număr impar; ZiZ_i poate fi mai mare decât RR sau CC;
  • 0Wi2000 \leq W_i \leq 200;
  • Pentru cerinta 11), se garantează că 1B<300 0001 \leq 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)(1, 1);
  • Dacă XiX_i = 11 atunci 2YiC2 \leq Y_i \leq C
  • Dacă YiY_i = 11 atunci 2XiR2 \leq X_i \leq R
  • Pentru rezolvarea corectă a cerinței 11. se obține 30%30\% din punctaj, iar pentru cerința 22. se obține 70%70\% din punctaj.

Exemplul 1

nori.in

1
5 3 3 9
2 1 1 3
4 1 3 0
1 3 5 1

nori.out

2 9

Explicație

Vezi exemplul din figura 22. Sunt 22 nori întregi și anume norul 11 și norul 22. Cei doi nori sunt situați în întregime deasupra continentului, prima dată după 99 ore.

Exemplul 2

nori.in

2
5 3 3 9
2 1 1 3
4 1 3 0
1 3 5 1

nori.out

8 2

Explicație

Vezi exemplul din figura 22. După T=9T=9 ore țările cu cer senin sunt la coordonatele:
(1,1)(1, 1), (1,2)(1, 2), (1,3)(1, 3), (2,1)(2, 1), (2,3)(2, 3), (3,1)(3, 1), (3,3)(3, 3), (5,1)(5, 1) iar țările în care este furtună sunt la coordonatele: (4,3)(4, 3) și (5,2)(5, 2).

Problem info

ID: 1085

Editor: stefdasca

Author:

Source: ONI 2016 Baraj Juniori: Problema 2

Tags:

ONI 2016 Baraj Juniori

Log in or sign up to be able to send submissions!