| Historia OI -> III OI 1995/1996 -> Zadania |  |
|
III Olimpiada Informatyczna 1995/96
|
|
Zadanie: MOK
|
Autor: Piotr Chrząstowski-Wachtel
|
| 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:
- 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.
- Dolanie wody do pełna z jednego naczynia do drugiego.
- 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.