Polish version    English version  
  Historia OI -> VII OI 1999/2000 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Zasady organizacji
Wskazówki
Terminarz
Statystyki
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VII Olimpiada Informatyczna 1999/2000

Zadanie: BRO
Autor: Wojciech Guzicki
Gdzie zbudować browar?

Zawody I stopnia
Plik źródłowy: BRO.??? (np. pas, c, cpp)
Plik wykonywalny: BRO.exe
Plik wejściowy: BRO.in
Plik wyjściowy: BRO.out

Mieszkańcy bajtockiej wyspy Abstynencja bardzo lubią piwo bezalkoholowe. Do tej pory piwo bezalkoholowe sprowadzano z Polski, ale w tym roku w jednym z miast na Abstynencji zostanie wybudowany browar. Wszystkie miasta wyspy leżą na wybrzeżu i są połączone autostradą obiegającą wyspę wzdłuż brzegu. Inwestor budujący browar zebrał informacje o zapotrzebowaniu na piwo, tj. ile cystern piwa trzeba codziennie dostarczyć do każdego z miast. Dysponuje także zestawieniem odległości pomiędzy miastami. Koszt transportu jednej cysterny na odległość 1 km wynosi 1 talar. Dzienny koszt transportu to suma, jaką trzeba wyłożyć, by do każdego miasta przetransportować z browaru tyle cystern, ile wynosi zapotrzebowanie w danym mieście. Jego wielkość zależy od miejsca położenia browaru. Inwestor chce zminimalizować koszty transportu piwa.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego BRO.IN liczbę miast, odległości między nimi oraz dzienne zapotrzebowania na piwo,
  • obliczy minimalny dzienny koszt transportu piwa,
  • zapisze wynik w pliku tekstowym BRO.OUT.

Wejście

W pierwszym wierszu pliku tekstowego BRO.IN jest zapisana jedna liczba całkowita n równa liczbie miast, 5 <= n <= 10 000. W każdym z kolejnych n wierszy zapisana jest para nieujemnych liczb całkowitych oddzielonych pojedynczym odstępem. Liczby zi di zapisane w (i+1)-ym wierszu to odpowiednio zapotrzebowanie na piwo w mieście nr i oraz odległość (w kilometrach) od miasta nr i do następnego miasta na autostradzie. Kolejne miasta na autostradzie mają kolejne numery, po mieście nr n leży miasto nr 1. Całkowita długość autostrady nie przekracza 1 000 000 km. Zapotrzebowanie na piwo w żadnym mieście nie przekracza 1 000 cystern.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu pliku tekstowego BRO.OUT dokładnie jedną liczbę całkowitą równą minimalnemu dziennemu kosztowi transportu piwa.

Przykład

Dla pliku wejściowego BRO.IN:

6
1 2
2 3
1 2
5 2
1 10
2 3

poprawną odpowiedzią jest plik wyjściowy BRO.OUT:

41



Wersja do druku