Polish version    English version  
  Historia OI -> III OI 1995/1996 -> 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
IV OI 1996/1997
III OI 1995/1996
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
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
III Olimpiada Informatyczna 1995/96

Zadanie: MOK
Autor: Piotr Chrząstowski-Wachtel
Mokra robota

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

 

Dysponujemy n naczyniami, gdzie 1 <= n <= 4. Wszystkie naczynia są początkowo całkowicie wypełnione wodą. Pojemność i-tego naczynia oi, mierzona w litrach, jest liczbą naturalną spełniającą nierówności 1 <= oi <= 49.

Wolno wykonywać trzy rodzaje ruchów:

  1. Przelanie całej zawartości z jednego naczynia do drugiego. Ruch ten można wykonać tylko wtedy, gdy w drugim naczyniu jest wystarczająco dużo wolnego miejsca.
  2. Dolanie wody do pełna z jednego naczynia do drugiego.
  3. Wylanie całej zawartości jednego naczynia do zlewu.

Zadanie

Napisz program, który:
  • wczytuje z pliku tekstowego MOK.IN liczbę naczyń n, pojemność każdego naczynia i zadaną końcową ilość wody w każdym z naczyń,
  • bada, czy można w skończonej liczbie ruchów doprowadzić do zadanej sytuacji końcowej i jeśli tak, znajduje minimalną liczbę ruchów prowadzących do niej,
  • zapisuje wynik, tj. słowo NIE lub minimalną liczbę ruchów w pliku tekstowym MOK.OUT.

Wejście

W pierwszym wierszu pliku tekstowego MOK.IN jest zapisana jedna liczba całkowita dodatnia n <= 4 - jest to liczba naczyń.

W drugim wierszu jest zapisanych n liczb naturalnych. Koleina i-ta liczba 1 <= oi <= 49 jest pojemnością i-tego naczynia.

W trzecim wierszu jest zapisanych n liczb naturalnych. Koleina i-ta liczba 0 <= wi <= oi jest zadaną końcową ilością wody w odpowiednim i-tym naczyniu.

Liczby w wierszach drugim i trzecim są pooddzielane pojedynczym odstępem.

Wyjście

Jeśli nie można doprowadzić do zadanej sytuacji końcowej, to w pierwszym i jedynym wierszu pliku tekstowego MOK.OUT należy zapisać jedno słowo NIE, a w przeciwnym przypadku minimalną liczbę ruchów prowadzących do zadanej sytuacji końcowej.

Przykłady

Dla pliku MOK.IN:
3
3 5 5
0 0 4

poprawnym rozwiązaniem jest następujący plik MOK.OUT:
6

Dla pliku MOK.IN:
2
20 25
10 16

poprawnym rozwiązaniem jest plik MOK.OUT:
NIE

Twój program powinien szukać pliku MOK.IN w katalogu bieżącym i tworzyć plik MOK.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę MOK.???, 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 MOK.EXE.




Wersja do druku