Polish version    English version  
  Historia OI -> V OI 1997/1998 -> 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
VI OI 1998/1999
V OI 1997/1998
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Terminarz
Statystyki
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
V Olimpiada Informatyczna 1997/98

Zadanie: PLE

Płetwonurek

II ETAP, DRUGI DZIEŃ ZAWODÓW - SOBOTA 14 LUTEGO 1998 r.  
Plik źródłowy: PLE.??? (np. pas, c, cpp)
Plik wykonywalny: PLE.exe
Plik wejściowy: PLE.in
Plik wyjściowy: PLE.out

Płetwonurek do nurkowania używa butli, w której są dwa zbiorniki: z tlenem i z azotem. W zależności od czasu przebywania pod wodą i głębokości nurek potrzebuje różnych ilości tlenu i azotu. Płetwonurek ma do dyspozycji pewną liczbę butli. Każda butla charakteryzuje się wagą oraz objętością zawartego w niej tlenu i azotu. Do wykonania zadania nurek potrzebuje określonych ilości tlenu i azotu. Jaka jest najmniejsza sumaryczna waga butli, które nurek musi zabrać ze sobą, żeby mógł wykonać zadanie?

Przykład

Nurek ma do dyspozycji 5 butli o następujących charakterystykach (odpowiednio: objętość tlenu w litrach, objętość azotu w litrach, waga butli w dekagramach):

3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
Jeżeli do wykonania zadania nurek potrzebuje 5 litrów tlenu i 60 litrów azotu, to musi zabrać ze sobą dwie butle o łącznej wadze 249, np. pierwszą i drugą lub czwartą i piątą.

Zadanie

Napisz program, który:

  • wczytuje z pliku tekstowego PLE.IN zapotrzebowanie nurka na tlen i azot, liczbę dostępnych butli oraz ich charakterystyki;
  • oblicza najmniejszą sumaryczną wagę butli, które nurek musi zabrać ze sobą, żeby wykonać zadanie;
  • zapisuje wynik w pliku tekstowym PLE.OUT.
Uwaga: dany zestaw butli zawsze gwarantuje wykonanie zadania.

Wejście

W pierwszym wierszu pliku wejściowego PLE.IN znajdują się dwie liczby całkowite t i a, oddzielone pojedynczym odstępem, 1<=t<=21 i 1<=a<=79. Są to, odpowiednio, ilości tlenu i azotu potrzebne do wykonania zadania. Drugi wiersz pliku wejściowego zawiera tylko jedną liczbę n. 1<=n<=1000. Jest to liczba dostępnych butli. Kolejne n wierszy zawiera charakterystyki butli. Wiersz i+2 pliku PLE.IN zawiera trzy liczby całkowite ti, ai, wi, pooddzielane pojedynczymi odstępami (1<=ti<=21, 1<=ai<=79, 1<=wi<=800). Są to kolejno: objętości tlenu i azotu w i-tej butli oraz waga tej butli.

Wyjście

Twój program powinien zapisać jedną liczbę całkowitą w pierwszym i jedynym wierszu pliku wyjściowego PLE.OUT. Tą liczbą powinna być najmniejsza sumaryczna waga butli, które nurek musi zabrać ze sobą, żeby mógł wykonać zadanie.

Przykład

Dla pliku tekstowego PLE.IN:

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
poprawnym rozwiązaniem jest plik wyjściowy PLE.OUT:
249





Wersja do druku