| Fişierul intrare/ieşire: | pitici2.in, pitici2.out | Sursă | Grigore Moisil 2008, clasa a 9-a |
| Autor | Csaba Patcas | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pitici2
In satul piticilor sunt N case, numerotate de la 1 la N. Vrajitorul satului a aflat de la zana cea buna ca satul urmeaza sa fie atacat. Folosind un ingredient magic, el poate face invizibile casele piticilor pana trece pericolul si astfel satul ar fi salvat. Din pacate vrajitorul nu are suficient ingredient magic, necesar ascunderii intregului sat si nu mai are nici timp sa mai aduca ierburi din padure. Datorita felului in care actioneaza vrajile lui, el va putea face invizibile doar case care se situeaza de-a lungul a trei drepte (nu neaparat distincte).
Stabiliti daca satul va putea fi salvat. In caz afirmativ indicati dreptele de-a lungul carora se afla casele piticilor. Altfel spus, trebuie sa determinati dreptele care "acopera" casele piticilor.
Date de intrare
Pe prima linie a fisierului pitici2.in se afla un numar natural N, reprezentand numarul caselor. Pe urmatoarele N linii se afla cate doua numere intregi, reprezentand coordonatele caselor.
Date de iesire
- In cazul in care casele piticilor nu pot fi "acoperite" de cel mult trei drepte, pe prima linie a fisierului pitici2.out se va scrie propozitia 'Piticii sunt in pericol.'.
- Daca satul va fi salvat, pe prima linie a fisierul de iesire se va scrie propozitia 'Piticii se vor salva.'. Pe urmatoarele trei linii se vor scrie cate doua numere naturale, reprezentand numere de ordine de case, separate prin cate un spatiu, care determina dreptele de-a lungul carora se situeaza casele din sat.
Restrictii
- 2 ≤ N ≤ 5000
- Coordonatele caselor vor fi din intervalul [-30 000, 30 000]
- Daca exista mai multe solutii, in fisier se va scrie una singura
- Doua case nu se vor afla in acelasi punct
Exemplu
| pitici2.in | pitici2.out |
|---|---|
| 7 0 0 0 1 0 2 1 1 2 2 2 0 1 0 | Piticii se vor salva. 1 2 1 4 1 7 |
Explicatie
Dreapta care uneste casa 1 cu casa 2 acopera si casa 3. Dreapta care uneste casa 1 cu casa 4 acopera si casa 5. Dreapta care uneste casa 1 cu casa 7 acopera si casa 6.
