Polish version    English version  
  O olimpiadzie -> Zadania -> IV OI 1996/1997


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
IV Olimpiada Informatyczna 1996/97

Zadanie: TAN
Autor: Stanisław Waligórski
Tanie podróże

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

Pasażerowie autokarów turystycznych, przewożących wycieczki transkontynentalną autostradą, spędzają w drodze wiele dni, zatem opłaty za noclegi stanowią poważną część kosztów podróży. Ze względu na bezpieczeństwo jazdy i wygodę pasażerów każdy autokar jedzie tylko w ciągu dnia i nie może przejechać więcej niż 800 km dziennie. Noce na trasie (poza jej początkiem i końcem) pasażerowie i kierowca spędzają w hotelach. Dotychczas planowano przejazdy tak, by liczba noclegów na trasie była jak najmniejsza. Dążąc do obniżki kosztów, przedsiębiorstwo przewozowe zdecydowało zbadać, czy opłaci się układanie planów podróży tak, by suma opłat za noclegi była możliwie najniższa, nawet gdyby to miało przedłużyć podróż. W tych obliczeniach można korzystać z ofert hoteli położonych przy autostradzie. W każdej ofercie jest podana odległość hotelu od początku trasy i cena jednego noclegu jednej osoby. Podróż jest tylko w jedną stronę. Trasa nie ma rozgałęzień. Przez każdy punkt trasy autokar przejeżdża jeden raz. Nigdzie na trasie nie ma dwóch hoteli w jednym punkcie, więc dla zidentyfikowania hotelu wystarczy podać jego odległość od początku trasy. Nie planuje się noclegu na początku ani na końcu trasy. Liczba osób w autobusie nie zmienia się i w każdym hotelu wszyscy (łącznie z kierowcą) płacą za nocleg jednakowo - zgodnie z ofertą. Pojemność hoteli jest na tyle duża, że nie istnieje problem braku miejsc. Zawsze można liczyć na to, że w dowolnej chwili w każdym hotelu będzie wystarczająco dużo wolnych miejsc, by przenocować wszystkich pasażerów autobusu. Na każdym odcinku trasy o długości 800 km jest przynajmniej jeden hotel, co oznacza, że przejechanie trasy z zachowaniem podanych wyżej warunków jest możliwe.

Zadanie

Napisz program, który:
  • wczytuje z pliku tekstowego TAN.IN dane: długość trasy, liczbę hoteli oraz oferty hoteli;
  • znajduje dwa plany podróży:
    • najtańszej, tzn. takiej, żeby suma opłat za hotele była najmniejsza, a jeśli takich rozwiązań jest wiele, wybiera jedno z najmniejszą liczbą noclegów,
    • najszybszej, tzn. takiej, żeby liczba noclegów była najmniejsza, a jeśli takich rozwiązań jest wiele, wybiera jedno z najmniejszą sumą opłat za noclegi;
  • zapisuje wyniki, tj. dwa plany podróży - najtańszej i najszybszej, w pliku tekstowym TAN.OUT.

Wejście

W pierwszym wierszu pliku tekstowego TAN.IN są zapisane dwie liczby całkowite dodatnie, oddzielone pojedynczym odstępem: długość trasy d w kilometrach oraz liczba hoteli h, gdzie dŁ16000 i hŁ1000. W kolejnych h wierszach są zapisane oferty hoteli - każda oferta w osobnym wierszu. Są one uporządkowane według rosnącej odległości hoteli od początku trasy. Każda oferta jest zapisana w postaci dwóch liczb całkowitych dodatnich oddzielonych pojedynczym odstępem, pierwsza liczba - to odległość hotelu od początku trasy w kilometrach, a druga - to cena jednego noclegu w tym hotelu nie większa niż 1000.

Wyjście

W pierwszym wierszu pliku tekstowego TAN.OUT należy zapisać plan podróży najtańszej - odległości kolejnych miejsc noclegu od początku trasy. W drugim wierszu należy - w taki sam sposób - zapisać plan podróży najszybszej. Liczby w wierszu powinny być pooddzielane pojedynczym odstępem.

Przykład

Dla pliku TAN.IN

2000 7
100 54
120 70
400 17
700 38
1000 25
1200 18
1440 40
poprawnym rozwiązaniem jest plik TAN.OUT mający dwa identyczne wiersze:
400 1200
400 1200

Twój program powinien szukać pliku TAN.IN w katalogu bieżącym i tworzyć plik TAN.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę TAN.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku TAN.EXE




Wersja do druku