Inverseaza reviziile

Diferente pentru problema/hvrays intre reviziile #6 si #1

Diferente intre titluri:

Hvrays

hvrays

Diferente intre continut:

== include(page="template/taskheader" task_id="hvrays") ==

Se dau $H$ raze orizontale si $V$ raze verticale. O raza orizontala este o linie dreapta care are originea intr-un punct si se extinde la infinit spre dreapta (spre coordonate $X$ crescatoare). O raza verticala este o linie dreapta ce are originea intr-un punct si se extinde la infinit in jos (catre coordonate $Y$ descrescatoare). O raza orizontala a carei origine este $(X{~h~},Y{~h~})$ atinge o raza verticala a carei origine este $(X{~v~},Y{~v~})$ daca $X{~h~} ≤ X{~v~}$ si $Y{~h~} ≤ Y{~v~}$.
 
Determinati o submultime $S$ constand dintr-un numar minim de raze verticale astfel incat fiecare raza orizontala sa fie atinsa de cel putin o raza verticala din $S$. Se garanteaza ca pe testele folosite va exista o astfel de submultime.

Poveste si cerinta...

h2. Date de intrare

Prima linie a fisierului de intrare $hvrays.in$ contine un numar intreg $T$, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine $2$ numere intregi: $H$ si $V$. Urmatoarele $H$ linii contin cate $2$ numere intregi: $X$ si $Y$, reprezentand coordonatele $(X,Y)$ ale originilor razelor orizontale. Urmatoarele $V$ linii contin cate $2$ numere intregi: $X$ si $Y$, reprezentand coordonatele $(X,Y)$ ale originilor razelor verticale.

...

h2. Date de iesire

Pentru fiecare din cele $T$ teste date, in ordinea din fisierul de intrare, afisati in fisierul de iesire $hvrays.out$ o linie continand numarul minim de raze verticale ale submultimii $S$.

...

h2. Restrictii

* $1 ≤ T ≤ 12$
* $1 ≤ H ≤ 100 000$
* $1 ≤ V ≤ 100 000$
* Coordonatele originilor tuturor razelor sunt numere intregi din intervalul $[0,50 000 000]$.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. hvrays.in |_. hvrays.out |

|1
3 3
1 6
4 4
6 2
3 8
5 7
9 4
|2|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicatie

Solutia poate consta din a doua si a treia raza verticala. O alta solutie poate fi formata din prima si a treia raza verticala.
!problema/hvrays?hvrays.jpg!

...

== include(page="template/taskfooter" task_id="hvrays") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

2182