Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-02-24 07:22:41.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:sn.in, sn.outSursăWinter Challenge 2008, Runda 2
AutorBogdan Alexandru StoicaAdăugată defireatmyselfBogdan-Alexandru Stoica fireatmyself
Timp execuţie pe test0.95 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Siguranta Nationala

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 si lansatoare de rachete sol-aer. 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 [ai,bi]. 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.

Cerinta

In calitate de Secretar General al Consiliului Suprem de Aparare a Tarii, 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.

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 ai, bi, cu semnificatia ca un dispozitiv plasat in locatia i va putea distruge orice forma de viata ce se afla in intervalul [ai,bi].

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.

Restrictii

  • 1 ≤ N, L ≤ 1 000 000
  • 1 ≤ ai ≤ bi ≤ L
  • intervalele vor fi date in ordinea crescatoare a lui ai si, in caz de egalitate, in ordinea crescatoare a lui bi
  • fiecare punct este continut de cel putin doua intervale din fisierul de intrare
  • intr-o locatie poate fi amplasat doar un singur tip de lansator de rachete

Exemplu

sn.insn.out
7 4
1 3
1 5
3 7
5 7
1
0
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?