TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

podela.cpp    21,226 b      izvorni kod rešenja
podela.tests.rar    336,081 b      test primeri

zadatak: Podela

Data je povezana mapa n gradova sa m dvosmernih puteva. Samo dva od n gradova A i B imaju fabriku čokolade. Posle kraćih dogovora, ljudi su odlučili da naprave dve disjunktne povezane mreže koristeći postojećih m puteva, tako da grad A distribuira čokoladu u svom delu, a grad B u svom delu. Svaki grad mora da pripada tačno jednoj mreži. Ako sa WA i WB označimo ukupnu dužinu puteva u mrežama koje sadrže A i B, potrebno je minimizirati veću od ukupnih dužina mreža, odnosno minimizirati izraz max(WA, WB).
Za ovaj zadatak potrebno je da predate izlazne datoteke za 10 ulaznih datoteka podela.01.in, podela.02.in, ..., podela.10.in, koji se nalaze u arhivi na računaru. Izlazi se pamte u datoteke podela.01.out, podela.02.out, ..., podela.10.out, pri čemu broj u nazivu izlazne datoteke odgovara broju u nazivu ulazne datoteke.

Ulaz.

U prvom redu ulaza se nalaze dva prirodna broja n i m. U drugom redu se nalaze indeksi gradova A i B, dok se u sledećih m redova nalaze opisi puteva: u svakom redu se nalaze tri broja x, y i z, koji označavaju da postoji put između gradova x i y dužine z.

Izlaz.

U prvom redu izlaza se nalate dva realna broja, koji predstavljaju težine mreža koje sadrže grad A i grad B, redom. Zatim slede kompletni opisi mreža: u sledećem redu štampati broj gradova i broj puteva koji pripadaju mreži koja sadrži grad A, a zatim i sve puteve iz mreže; u sledećem redu štampati broj gradova i broj puteva koji pripadaju mreži koja sadrži grad B, a zatim i sve puteve iz mreže.

Ograničenja.

  • 1 < n ≤ 500
  • mapa gradova je uvek povezana
  • dužine puteva su realni brojevi strogo veći od nule, a manji od 10.000

Primer 1.

podela.in      podela.out
6 8
1 6
1 2 3.0
1 3 3.0
2 4 2.0
2 5 2.0
3 4 1.0
4 5 3.0
4 6 1.0
5 6 4.0
        
5.0 2.0
3 2
1 2
2 5
3 2
3 4
4 6

Ocenjivanje.

Broj bodova za svaki test primer se odrešuje na sledeći način. Neka je maksimalna dužina puteva u mrežama u vašem rešenju VAL = max(WA, WB), a OPT je minimalna vrednost među svim takmičarskim rešenjima, uključujući i komisijsko rešenje. Broj bodova koje dobijete se računa po formuli (zaokrugljivanje se vrši na najmanji ceo broj koji nije manji):

1011-10·VALOPT.

Drugim rečima, ako je vaše rešenje identično sa najboljim dobijate 10 poena. U slučaju da je rešenje 10 ili više puta veće (lošije) od najboljeg rešenja - dobićete 1 poen. Ako je dužina puteva koju navedete u izlaznom fajlu različita od stvarne dužine puteva za izlazne mreže - dobijate 0 poena za taj test primer.