Diferente pentru problema/sn intre reviziile #20 si #4

Diferente intre titluri:

Siguranta Nationala
sn

Diferente intre continut:

== include(page="template/taskheader" task_id="sn") ==
Pentru ca a fost batut de prea multe ori la 'Jocul pe grid' de catre Presedinte, Primul Ministru planuieste o lovitura de stat. Din fericire, Dubluveu, a fost informat la timp de intentiile Sefului Guvernului si are de gand sa-si organizeze o aparare temeinica. Palatul Prezidential este plasat strategic, neputandu-se ajunge la acesta decat pe o singura sosea de lungime $L$ kilometri. Pe marginea sa Dubluveu cere amplasarea, in $N$ locatii fixe, a exact unul dintre urmatoarele doua tipuri de dispozitive: lansatoare de rachete "sol-sol":http://en.wikipedia.org/wiki/Surface-to-surface_missile si lansatoare de rachete "sol-aer":http://en.wikipedia.org/wiki/Surface-to-air_missile. Daca un dispozitiv (nu conteaza de ce tip) este plasat in locatia $i$, acesta va putea distruge orice forma de viata aflata intr-un interval $[a{~i~},b{~i~}]$. Pentru a fi sigur ca Primul Ministru nu va putea ajunge la el, Dubluveu vrea ca fiecare punct al soselei sa fie pazit de +ambele+ tipuri de dispozitive.
Pentru ca a fost batut de prea multe ori la 'Jocul pe grid' de catre Presedinte, Primul Ministru planuieste o lovitura de stat. Din fericire, Dubluveu, a fost informat la timp de intentiile Sefului Guvernului si are de gand sa-si organizeze o aparare temeinica. Palatul Prezidential este plasat strategic, neputandu-se ajunge la acesta decat pe o singura sosea de lungime $L$ kilometrii. Pe marginea sa Dubluveu cere amplasarea, in $N$ locatii fixe, a doua tipuri de dispozitive: lansatoare de rachete "sol-sol":http://en.wikipedia.org/wiki/Surface-to-surface_missile si lansatoare de rachete "sol-aer":http://en.wikipedia.org/wiki/Surface-to-air_missile (cate un tip in fiecare locatie). Daca un dispozitiv (nu conteaza de ce tip) este plasat in locatia $i$, acesta va putea distruge orice forma de viata doar intr-un interval $[a{~i~},b{~i~}]$. Pentru a fi sigur ca Primul Ministru nu v-a putea ajunge la el, Dubluveu vrea ca fiecare punct al soselei sa fie pazit de +ambele+ tipuri de dispozitive.
h2. Cerinta
In calitate de Secretar General al "Consiliului Suprem de Aparare a Tarii (CSAT)":http://csat.presidency.ro/csat/, trebuie sa dispuneti amplasarea a cate unui tip de lansator de rachete in fiecare din cele $N$ locatii. Daca exista mai multe solutii, puteti afisa oricare dintre ele.
Ca sef al Departamentului de Siguranta Nationala, sunteti insarcinat sa amplasati in fiecare din cele $N$ locatii unul din cele doua tipuri de lansatoare de rachete.
h2. Date de intrare
Pe prima linie a fisierului de intrare $sn.in$ se afla doua numere $L$ si $N$. Pe urmatoarele $N$ linii se afla doua numere $a{~i~}$, $b{~i~}$, cu semnificatia ca un dispozitiv plasat in locatia $i$ va putea distruge orice forma de viata ce se afla in intervalul $[a{~i~},b{~i~}]$.
Pe prima linie a fisierului de intrare $sn.in$ se afla doua numere $L$ si $N$. Pe urmatoarele $N$ linii se afla doua numere $a{~i~}$, $b{~i~}$, cu seminifcatia ca un dispozitiv plasat in locatia $i$ va putea distruge orice forma de viata ce se afla in intervalul $[a{~i~},b{~i~}]$.
h2. Date de iesire
Fisierul de iesire $sn.out$ va contine $N$ linii, pe linia $i$ se va indica tipul de lansator de racheta amplasat in respectiva locatie (se va afisa $0$ daca in $i$ se amplaseaza un lansator de rachete sol-sol, respectiv $1$ in celalalt caz). Se garanteaza ca pentru datele de test va exista intotdeauna solutie.
Fisierul de iesire $sn.out$ va contine $N$ linii, pe linia $i$ se va indica tipul de lansator de racheta amplasat in respectiva locatie ('sol-sol' daca in $i$ se amplaseaza un lansator de rachete sol-sol, respectiv 'sol-aer' in celalalt caz). Se garanteaza ca pentru datele de test va exista intotdeauna solutie.
h2. Restrictii
* $1 ≤ N, L ≤ 1 000 000$
* $1 ≤ a{~i~} ≤ b{~i~} ≤ L$
* intervalele vor fi date in ordinea crescatoare a lui $a{~i~}$ si, in caz de egalitate, in ordinea crescatoare a lui $b{~i~}$
* fiecare punct este continut de cel putin doua intervale din fisierul de intrare
* $0 ≤ N, L ≤ 1 000 000$
* $0 ≤ a{~i~} ≤ b{~i~} ≤ L$
* intervalele vor fi date in ordinea crescatoare a lui a{~i~}, iar daca a{~i~} = a{~i+1~}, atunci b{~i~} ≤ b{~i+1~}
* intr-o locatie poate fi amplasat +doar un singur tip de lansator de rachete+
table(example). |_. sn.in |_. sn.out |
| 7 4
1 3
1 5
0 3
0 5
3 7
5 7
| 1
  0
  1
  0
| sol-aer
sol-sol
sol-aer
sol-sol
|
== include(page="template/taskfooter" task_id="sn") ==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

2752