Olimpiada Informatyczna

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: [a₁,a₂,...,a_n] 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 |a_k-a_n| =1 oraz
a₁=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
4

poprawnym rozwiązaniem jest plik wyjściowy SUM.OUT o zawartości:

Twó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