Državno natjecanje 2015. / Osnovna škola (7. razred) - 3. zadatak

Mladi Matej prodaje ulaznice za koncert Kiše metaka. Nažalost, pronašao je ulaznicu na podu, nekome je ispala!

Ulaznica se sastoji od 2N znamenki, ali neke od znamenki nečitljive su iz razloga poznatih samo vlasniku ulaznice.

Ulaznica može započeti i znamenkom 0.

Matej želi vratiti ulaznicu njezinom originalnom vlasniku.

S obzirom da na mjestu znamenke koja se ne može pročitati može pisati bilo koja znamenka, njega zanima koliko ima mogućih ulaznica danog oblika.

Matej je preko svojih tajnih kanala saznao sljedeće dvije informacije o ulaznici:

1. zbroj prvih N znamenaka jednak je zbroju zadnjih N znamenaka,
2. broj parnih znamenaka u prvih N znamenaka jednak je broju parnih znamenaka u zadnjih N znamenaka.

Mateja sada zanima koliko postoji različitih ulaznica danog oblika za koje vrijedi prvo svojstvo, te koliko postoji različitih ulaznica za koje vrijede oba svojstva. Pomozi mu!

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 5) iz teksta zadatka.

U drugom retku nalazi se niz od 2N znakova koji predstavljaju poznate i nepoznate znamenke ulaznice.

Nepoznata znamenka bit će označena znakom ‘?’.

IZLAZNI PODATCI

U prvom retku ispiši broj ulaznica koje zadovoljavaju prvo svojstvo.

U drugom retku ispiši broj ulaznica koje zadovoljavaju oba svojstva.

PRIMJERI TEST PODATAKA

Ulaz

1
0?

Izlaz

3
1 2
1 2

Objašnjenje

Opis prvog test primjera: Jedina kombinacija s jednakim zbrojem obje polovice je (00). To je i jedina kombinacija s jednakim brojem parnih znamenaka na obje polovice.

Ulaz

2
1??3

Izlaz

8
8

Objašnjenje

Opis drugog test primjera: Kombinacije s jednakim zbrojem obje polovice su (1203, 1313, 1423, 1533, 1643, 1753, 1863, 1973). To su i jedine kombinacije s jednakim brojem parnih znamenaka na obje polovice.

Ulaz

2
4?33

Izlaz

1
0

Objašnjenje

Opis trećeg test primjera: Jedina kombinacija s jednakim zbrojem obje polovice je (4233). Kombinacija u kojoj je jednak i broj parnih znamenaka na obje polovice ne postoji.