Fişierul intrare/ieşire:import.in, import.outSursălot 2006
AutorDan-Ionut FecheteAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.05 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Import

Ca orice tara civilizata, Romania importa diferite produse din alte tari. In acest scop se efectueaza M transporturi, fiecare transport plecand dintr-un oras din afara tarii si avand ca destinatie finala un oras din Romania. Orice transport este efectuat de un camion ce apartine fie firmei Alfatrans, fie firmei Betatrans. Putem presupune ca orasele sunt numerotate de la 1 la N, orasele 1 ... K fiind din Romania, iar orasele K+1 ... N din alte tari. Intre aceste orase exista N-1 sosele bidirectionale astfel incat intre oricare 2 orase exista exact un drum (format din una sau mai multe sosele) si orice drum de la un anumit oras din Romania catre un oras din alta tara trece prin orasul 1, in acest oras aflandu-se vama. Pe parcursul drumului oricarui transport, la trecerea printr-un oras soferul camionului trebuie sa plateasca anumite taxe si trebuie sa comercializeze o parte din produsul transportat, astfel incat sa obtina un profit fixat de primaria orasului respectiv. Guvernul Romaniei a stabilit pentru fiecare transport profitul total minim ce trebuie obtinut. Profitul total se obtine insumand profiturile obtinute in fiecare oras prin care trece camionul pe drumul de la orasul de plecare la orasul destinatie (inclusiv orasul de plecare si orasul destinatie). Patronul Alfatrans are numeroase relatii internationale si poate manipula primaria fiecarui oras. Astfel, el poate sa stabileasca pentru fiecare oras i profitul Pi care trebuie sa fie obtinut la trecerea unui camion prin orasul respectiv. Pentru a discredita firma Betatrans, patronul firmei Alfatrans doreste sa stabileasca Pi pentru fiecare oras i astfel incat orice transport executat de camioane Alfatrans sa aduca un profit mai mare sau egal cu profitul minim stabilit pentru acel transport si orice transport executat de camioane Betatrans sa aduca un profit strict mai mic decat profitul stabilit.

Cerinta

Pentru un numar considerabil de actiuni la Alfatrans si pentru a obtine 100 de puncte, trebuie sa-l ajutati pe patronul firmei Alfatrans sa stabileasca pentru fiecare oras profitul impus de primarie astfel incat firma Betatrans sa fie discreditata.

Date de intrare

Pe prima linie a fisierului de intrare import.in sunt scrise numerele naturale N M K separate prin cate un spatiu, avand semnificatia din enunt. Urmatoarele N-1 linii contin cate doua numere naturale a b separate printr-un spatiu, cu semnificatia ca exista o sosea bidirectionala de la orasul a la orasul b. Urmatoarele M linii descriu transporturile dupa cum urmeaza. Fiecare linie contine 4 numere a b c d separate prin cate un spatiu cu semnificatia "se face transport de la orasul a la orasul b executat de firma x, iar profitul minim ce trebuie asigurat pentru acest transport este c". Firma x este Alfatrans daca d=0 si respectiv Betatrans daca d=1. Se garanteaza ca pentru orice transport a este un oras din afara tarii, iar b este un oras din Romania.

Date de iesire

Fisierul import.out va contine o singura linie pe care se vor scrise N numere separate prin spatii (unul sau mai multe spatii). Cel de al i-lea numar de pe linie reprezinta Pi, profitul stabilit de patronul Alfatrans pentru orasul i. Daca aceste valori vor face ca firma Betatrans sa nu respecte cerintele guvernului, iar firma Alfatrans sa respecte in totalitate aceste cerinte veti obtine punctajul maxim pe test.

Restrictii

  • 3 ≤ N ≤ 221
  • 2 ≤ K ≤ N-1
  • 1 ≤ M ≤ K*(N-K)-1
  • profitul minim ce trebuie asigurat pentru fiecare transport este un numar intreg cuprins intre -109 si 109.
  • profiturile Pi trebuie sa fie numere intregi cuprinse intre -100 000 si 100 000
  • se garanteaza existenta unei solutii.

Exemplu

import.inimport.out
7 4 4
1 3
3 2
3 4
1 5
1 6
6 7
6 2 10 0
6 3 5 1
7 4 7 0
5 4 -2 1
0 6 -6 3 0 10 0

Explicatie

Primul transport trece prin orasele 6 1 3 si 2 obtinand un profit de 10+0-6+6=10 deci respecta conditiile din enunt.
Al doilea trece prin 6 1 3 si obtine un profit de 10+0-6=4 mai mic decat 5 si de asemenea respecta conditiile din enunt
Al treilea drum trece prin orasele 7 6 1 3 4, obtine un profit de 0+10+0-6+3=7, iar ultimul drum trece prin 5 1 3 4 cu un profit de 0+0-6+3=-3 mai mic decat -2

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content