Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-03-22 09:20:34.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:pesaptecarari.in, pesaptecarari.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorCarabet Cosmin AndreiAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test1.25 secLimită de memorie36480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pe sapte carari

<Insert name>, mare iubitor de alcool si olimpic la informatica tocmai a descoperit conceptul de pub crawling (https://en.wikipedia.org/wiki/Pub_crawl). Foarte entuziasmat, s-a informat si a aflat de N puburi care sunt conectate intre ele prin strazi uni-directionale. El s-a hotarat sa porneasca intr-un pub crawl din barul identificat cu numarul 1 care este langa scoala sa, pana la barul N, situat langa Strada Cramei, unde protagonistul nostru locuieste. In urma unei atente analize el a aflat un indice alcoolic pentru fiecare pub. Stiind un coeficient de siguranta K, el vrea sa-si planifice traseul astfel incat produsul indicilor alcoolici de pe drum sa contina K la o putere cat mai mica. Daca reuseste sa determine un astfel de drum optim eroul nostru va ajunge acasa cu success. Se garanteaza ca isprava este posibila. <Insert Name> nu poate dezlega acest mister singur, motiv pentru care va cere ajutorul.

Date de intrare

Fişierul de intrare pesaptecarari.in va contine pe prima linie 3 numere N, M, K reprezentand numarul de baruri, numarul strazilor ce leaga baruri intre ele, respectiv coeficientul de siguranta K. Urmatoarea linie contine N valori, Ai reprezentand indicele alcoolic pentru fiecare pub din cele N. Urmatoarele M linii contin cate 2 numere: x, y aratand ca exista un drum cu sens unic de la x la y.

Date de ieşire

Fişierul de ieşire pesaptecarari.out va contine pe prima linie puterea minima la care apare K in produsul indicilor alcoolici pentru drumul optim intre barul 1 si N.
Pe urmatoarea linie se va afisa un drum de la barul 1 la barul N.

Restricţii

  • 1N105
  • 1M7 * 105
  • 1K1012
  • 0Ai1012
  • 1xN
  • 1yN
  • In caz ca exista mai multe drumuri optime, se poate afisa oricare.

Exemplu

pesaptecarari.inpesaptecarari.out
5 5 4
3 2 8 2 2
1 2
1 3
2 4
3 5
4 5
1
1 2 4 5

Explicaţie

Exista doua drumuri intre 1 si 5:
1. Primul este 1 -> 2 -> 4 -> 5, cu produsul 3 * 2 * 2 * 2 = 24 => puterea maxima la care apare 4 este 1
2. Al doilea este 1 -> 3 -> 5, cu produsul 3 * 8 * 2 = 48 => puterea maxima la care apare 4 este 2

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?