Runda 3 [Basic] - Cyfry

05.12.2010 - Damian Rusak

Zadanie tygodnia

Runda 3; kategoria Basic

Limit czasowy: 1s; Limit pamięciowy: 32MB

Cyfry

Dziś wielka promocja w sklepie z cyframi!!! Okazja jedyna w swoim rodzaju - niezależnie od tego, ile cyfr kupisz, płacisz jak za jedną! Jak tu nie skorzystać? Cyfrosław postanowił powiększyć swoją kolekcję cyfr. Ma on jednak swoje specyficzne upodobanie - lubi tworzyć z cyfr liczby podzielne przez 3. Przejrzał uważnie ofertę sklepu z cyframi i teraz zastanawia się na ile sposobów mógłby dokonać zakupu.

Cyfrosław chciałby wejść w posiadanie zbioru cyfr, z których można ułożyć (wykorzystując wszystkie) liczbę podzielną przez 3. Oczywiście w takim razie ten zbiór nie może się składać z samych zer. Poza tym wszelkie kombinacje dozwolone! Przesłał Ci ofertę sklepu i poprosił o pomoc - napisanie programu, który policzy mu, na ile sposobów może to uczynić. Wie, że to może być bardzo duża liczba, zatem satysfakcjonuje go reszta z dzielenia tej liczby przez $809$ .

Wejście:

Wejście składa się z jednej linii, zawierającej dziesięć liczb $a_{0}$ , $a_{1}$ , $a_{2}$ , ..., $a_{9}$ . Oznacza to, że w ofercie sklepu znajduje się $a_{0}$ cyfr $0$ , $a_{1}$ cyfr $1$ , ..., $a_{9}$ cyfr $9$ . Cyfry są od siebie nierozróżnialne. Możesz założyć, że $1 \leq a_{0} + a_{1} + ... + a_{9} \leq 10^{5}$ .

Wyjście:

Wyjście powinno składać się z jednej liczby - liczby sposobów wyboru cyfr, tak, że da się z nich utworzyć liczbę dodatnią i podzielną przez $3$ . Liczba ta powinna być podana modulo $809$ .

Przykład:

Wejście:

2 0 0 1 1 1 0 0 0 0

Wyjście:

Wyjaśnienie: Liczbę dodatnią, podzielną przez $3$ można utworzyć z multizbiorów $\left\{3\right\}$ , $\left\{0,3\right\}$ , $\left\{0,0,3\right\}$ , $\left\{4,5\right\}$ , $\left\{0,4,5\right\}$ , $\left\{0,0,4,5\right\}$ , $\left\{3,4,5\right\}$ , $\left\{0,3,4,5\right\}$ , $\left\{0,0,3,4,5\right\}$

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Pozycja	Imię i nazwisko	Wynik	Czas	Cyfry
1	Arek Wróbel	10	35:28:18	10
2	Damian Straszak	10	38:04:59	10
3	Łukasz Hanuszczak	10	62:32:52	10
4	Przemek Komosa	10	77:17:10	10
5	Wojciech Janczewski	10	85:24:17	10
6	Piotr Bejda	10	86:54:38	10
7	Przemysław Derengowski	10	107:21:12	10
8	Maciej Szeptuch	10	108:29:53	10
9	Kamil Harasimowicz	10	127:25:17	10
10	Tomasz Richert	10	129:00:06	10
11	Maciej Kisiel	10	131:37:40	10
12	Witold Długosz	10	2080:43:19	10
13	Bartłomiej Gajewski	10	2673:33:15	10
14	Bartek Dudek	7	152:59:02	7
15	Jakub Sygnowski	1	11:00:49	1
16	Wojciech Dyżewski	1	78:09:54	1