Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | reinvent.in, reinvent.out | Sursă | ONI 2009, clasele 11-12 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Andrei Misarca •Mishu91 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Reinvent
Zăhărel şi Sică s-au gândit să se reinventeze din punct de vedere spiritual. În prima fază, vor să se mute în oraşul Sala. Oraşul Sala conţine N case (numerotate de la 1 la N) unite prin M străzi bidirecţionale de lungimi egale. Ei au la dispoziţie fonduri limitate şi pot să se mute doar într-un cartier mărginaş format din X case. Fiindcă sunt buni prieteni cei doi vor să se mute în două case distincte, cât mai apropiate între ele. Determinaţi distanţa minimă dintre două case distincte din cele X din cartier.
Date de intrare
Pe prima linie a fişierului de intrare reinvent.in se află trei numere întregi N, M si X separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii se află câte două numere întregi distincte separate printr-un singur spaţiu, reprezentând o stradă bidirecţională din oraş. Ultima linie din fişier conţine X numere naturale distincte separate prin câte un spaţiu, reprezentând casele din cartier.
Date de ieşire
În fişierul de iesire reinvent.out se află un singur număr natural, reprezentând distanţa minimă între două case distincte din cartier.
Restricţii
- 1 ≤ N, M ≤ 100.000
- 2 ≤ X ≤ N
- Pentru 30% din teste N ≤ 1024
Exemplu
| reinvent.in | reinvent.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
