Fişierul intrare/ieşire:casute.in, casute.outSursăLot Alba 2007
AutorMircea Bogdan PasoiAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test1.2 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Casute

Nargy si Fumeanu au plecat la munte. Ei au o harta a muntelui, in care sunt identificate N casute montane (numerotate cu numere distincte intre 1 si N), situate la diferite inaltimi (casuta i se afla la inaltimea Hi). Aceste casute sunt legate prin M poteci. O poteca leaga doua casute distincte si poate fi parcursa doar intr-un singur sens: de la casuta situata la o inaltime mai mica catre casuta situata la o inaltime mai mare.
La un moment dat, cei doi s-au despartit si fiecare a ajuns in dreptul unei casute, dar din fericire fiecare avea la el o copie a hartii. Cei doi si-au telefonat si au stabilit un loc de intalnire, astfel: se vor intalni la casuta situata la inaltimea minima dintre acele casute la care pot ajunge amandoi (tineti minte ca nu pot decat urca).
Pentru a evita astfel de situatii in viitor, cei doi si-au propus sa determine locul in care s-ar fi intalnit indiferent de casutele in care s-ar fi aflat cei doi. Ei vor trece aceste rezultate pe o foaie de hartie, pentru fiecare pereche i j (1 ≤ i < j ≤ N), perechile fiind considerate in ordine lexicografica. In cazul in care pentru o anumita pereche nu exista o astfel de casuta de intalnire, se va scrie pe foaie numarul 0.

Date de intrare

Fisierul de intrare casute.in contine pe prima linie numerele naturale N si M separate prin spatii. Urmatoarea linie va contine N numere naturale separate prin spatii reprezentand inaltimile la care se afla casutele, in ordine de la 1 la N. Urmatoarele M linii vor contine cate doua numere naturale i j separate prin spatii, reprezentand o poteca de la casuta i la casuta j (se garanteaza ca Hi<Hj).

Date de iesire

Cele N*(N-1)/2 valori pe care cei doi le vor scrie pe foaie pot fi considerate ca reprezinta cifrele unui numar scris in baza N+1. in fisierul de iesire casute.out se va scrie pe prima linie restul impartirii acelui numar convertit in baza 10 la numarul 666013.

Restrictii

  • 1 ≤ N ≤ 3.000
  • 1 ≤ M ≤ 30.000
  • inaltimile celor N casute sunt numere intregi distincte din intervalul [1,109]
  • Se considera ca o pereche de numere (a b) este mai mica din punct de vedere lexicografic decat o alta pereche de numere (c d), daca a<c sau a=c si b<d

Exemplu

casute.incasute.out
5 7
1 2 3 4 5
1 3
2 3
1 4
2 4
2 5
4 5
3 5
24052

Explicatie

(1 2) -> 3
(1 3) -> 3
(1 4) -> 4
(1 5) -> 5
(2 3) -> 3
(2 4) -> 4
(2 5) -> 5
(3 4) -> 5
(3 5) -> 5
(4 5) -> 5
3345345555(6) = 36654767(10) = 24052 (mod 666013)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content