Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-02-19 19:56:15.
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 kilometrii. Pe marginea sa Dubluveu cere amplasarea, in N locatii fixe, a doua tipuri de dispozitive: lansatoare de rachete sol-sol si lansatoare de rachete sol-aer (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 [ai,bi]. 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.

Cerinta

In Secretar General al Consiliul Suprem de Aparare a Tarii, trebuie sa dispuneti amplasarea a cate unui tip de lansator de rachete in fiecare din cele N locatii.

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 seminifcatia 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 ('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.

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 un interval din fisierul de intrare
  • intr-o locatie poate fi amplasat doar un singur tip de lansator de rachete
  • !ATENTIE! din cauza volumului mare de date din fisierul de intrare este recomandata citirea cu gets sau fgets

Exemplu

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

Cum se trimit solutii?