Polish version    English version  
  O olimpiadzie -> Zadania -> IX OI 2001/2002


 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
IX Olimpiada Informatyczna 2001/2002

Zadanie: naw
Autor: Piotr Chrząstowski-Wachtel, Wojciech Guzicki
Nawiasy

Zawody III stopnia, dzień drugi  
Plik źródłowy: naw.??? (np. pas, c, cpp)
Plik wejściowy: naw.in
Plik wyjściowy: naw.out

Działanie odejmowania nie jest łączne, np (5-2)-1=2, natomiast 5-(2-1)=4, a zatem (5-2)-1<>5-(2-1). Wynika stąd, że wartość wyrażenia postaci 5-2-1 zależy od kolejności wykonywania odejmowań. Zwykle przy braku nawiasów przyjmuje się, że wykonujemy działania w kolejności od lewej do prawej, czyli wyrażenie 5-2-1 jest równoważne wyrażeniu (5-2)-1.

Mamy dane wyrażenie postaci:

x1 +/- x2 +/- ... +/- xn

gdzie +/- oznacza + (plus) lub - (minus), a x1,x2,...,xn oznaczają (parami) różne zmienne. Chcemy w wyrażeniu postaci:

x1-x2-...-xn

tak rozstawić n-1 par nawiasów, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu. Na przykład, chcąc uzyskać wyrażenie równoważne wyrażeniu:

x1-x2-x3+x4+x5-x6+x7

możemy w:

x1-x2-x3-x4-x5-x6-x7

rozmieścić nawiasy w następujący sposób:

(((x1-x2)-((x3-x4)-x5))-(x6-x7)).

Uwaga: Interesują nas tylko wyrażenia w pełni i poprawnie ponawiasowane. Wyrażeniem w pełni i poprawnie ponawiasowanym jest

  • albo pojedyncza zmienna,
  • albo wyrażenie postaci (w1-w2), w którym w1 i w2, to w pełni i poprawnie ponawiasowane wyrażenia.

Nieformalnie mowiąc, nie interesują nas wyrażenia, w których występują na przykład konstrukcje postaci: (), (xi), ((...)) lub x1-(x2-x3) nie jest w pełni ponawiasowane, ponieważ brakuje zewnętrznych nawiasów.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego naw.in opis danego wyrażenia postaci x1 +/- x2 +/- ... +/- xn,
  • obliczy na ile różnych sposobów (modulo 1 000 000 000) można rozstawić n-1 par nawiasów w wyrażeniu x1-x2-...-xn tak, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu,
  • zapisze wynik w pliku tekstowym naw.out.

Wejście

W pierwszym wierszu pliku tekstowego naw.in zapisana jest jedna liczba całkowita n, 2<=n<=5000. Jest to liczba zmiennych w danym wyrażeniu. W każdym z kolejnych n-1 wierszy jest zapisany jeden znak, + lub -. W i-tym wierszu zapisany jest znak występujący w danym wyrażeniu między xi-1 a xi.

Wyjście

Twój program powinien zapisać w pierwszym wierszu pliku tekstowego naw.out jedną liczbę całkowitą równą ilości różnych sposobów (modulo 1 000 000 000), na jakie można rozstawić n-1 par nawiasów w wyrażeniu x1-x2-...-xn tak, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu.

Przykład

Dla pliku wejściowego naw.in:

7
-
-
+
+
-
+

poprawną odpowiedzią jest plik wyjściowy naw.out:

3



Wersja do druku