Polish version    English version  
  O olimpiadzie -> Zadania -> II OI 1994/1995


 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
II Olimpiada Informatyczna 1994/95

Zadanie: KOD
Autor: Krzysztof Diks
Kodowanie permutacji

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

 

Każdą permutację A = (a1, ..,an) liczb 1, ... , n można zakodować za pomocą ciągu B = (b1, ..,bn), w którym bi jest równe liczbie wszystkich aj takich, że: (j < i oraz aj > ai), dla każdego i = 1,...,n.

Przykład

Kodem permutacji A = (1, 5, 2, 6, 4, 7, 3) jest ciąg: B = (0, 0, 1, 0, 2, 0, 4).

Zadanie

Napisz program, który:
  • wczytuje z pliku tekstowego KOD.IN długość n i kolejne wyrazy ciągu liczb B,
  • sprawdza, czy jest on kodem jakiejś permutacji liczb 1,..., n,
  • jeżeli tak, to znajduje tę permutację i zapisuje ją w pliku tekstowym KOD.OUT,
  • w przeciwnym przypadku zapisuje w pliku KOD.OUT jedno słowo NIE.

Wejście

  • W pierwszym wierszu pliku tekstowego KOD.IN jest zapisana dodatnia liczba całkowita n <= 30000. Jest to liczba wyrazów ciągu B.
  • W każdym z kolejnych n wierszy jest zapisana jedna liczba całkowita nieujemna nie większa niż 30000. Jest to kolejny wyraz ciągu B.

Wyjście

W pliku tekstowym KOD.OUT należy zapisać:
  • w każdym z kolejnych n wierszy jeden wyraz permutacji A, której kodem jest dany ciąg B, zapisany w pliku KOD.IN
  • jedno słowo NIE, jeśli ciąg B nie jest kodem żadnej permutacji.

Przykłady

Dla pliku KOD.IN:
7
0
0
1
0
2
0
4

w pliku KOD.OUT należy zapisać:

1
5
2
6
4
7
3

Dla pliku KOD.IN:

4
0
2
0
0

w pliku KOD.OUT należy zapisać:

NIE

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




Wersja do druku