| O olimpiadzie -> Zadania -> V OI 1997/1998 |  |
|
V Olimpiada Informatyczna 1995/96
|
|
Zadanie: SUM
|
Autor: Grzegorz Jakacki
|
Suma ciągu jedynkowego
| Zawody I stopnia |
| Plik źródłowy: | SUM.??? (np. pas, c, cpp) |
| Plik wykonywalny: | SUM.exe |
| Plik wejściowy: | SUM.in |
| Plik wyjściowy: | SUM.out |
Ciąg liczbowy o wartościach będących liczbami całkowitymi nazywamy jedynkowym jeżeli dwa dowolne jego sąsiednie wyrazy różnią się od siebie dokładnie o jeden oraz jego pierwszy wyraz jest równy 0. Bardziej precyzyjnie: [a1,a2,...,an] będzie ciągiem o wartościach całkowitych; powiedzmy, że ten ciąg jest jedynkowy, jeżeli
- Dla dowolnej liczby całkowitej k spełniającej nierówność 1 <= k < n zachodzi warunek |ak-an| =1 oraz
- a1=0
Zadanie
Napisz program, który:
- wczyta z pliku tekstowego SUM.IN dwie liczby całkowite długości ciągu i sumę elementów ciągu;
- wyznaczy ciąg jedynkowy o zadanej długości i sumie elementów lub stwierdzi, że taki ciąg nie istnieje;
- zapisze rezultat w pliku tekstowym SUM.OUT
Wejście
W pliku tekstowym SUM.IN są zapisane
- w pierwszym wierszu - liczba n elementów ciągu, spełniająca nierówność 1<=n<=10 000
- w drugim wierszu - liczba S będąca żądaną sumą elementów ciągu, spełniająca nierówność |S| <= 50 000 000
Wyjście
W pierwszych n wierszach pliku tekstowego SUM.OUT należy zapisać n liczb
całkowitych (po jednej w wierszu) będących kolejnymi wyrazami ciągu
jedynkowego (k-ty wyraz w k-tym wierszu) o zadanej sumie S lub słowo NIE,
jeżeli taki ciąg nie istnieje.
Przykład
Dla pliku wejściowego SUM.IN o zawartości:
8 4poprawnym rozwiązaniem jest plik wyjściowy SUM.OUT o zawartości:
0 1 2 1 0 -1 0 1Twój program powinien szukać pliku SUM.IN w katalogu bieżącym i tworzyć plik SUM.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę SUM.???, 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 SUM.EXE