Runda 3 [Basic] - Cyfry

05.12.2010 - Damian Rusak
Trudność

 

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:

9

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.
PozycjaImię i nazwiskoWynikCzasCyfry
1Arek Wróbel1035:28:1810
2Damian Straszak1038:04:5910
3Łukasz Hanuszczak1062:32:5210
4Przemek Komosa1077:17:1010
5Wojciech Janczewski1085:24:1710
6Piotr Bejda1086:54:3810
7Przemysław Derengowski10107:21:1210
8Maciej Szeptuch10108:29:5310
9Kamil Harasimowicz10127:25:1710
10Tomasz Richert10129:00:0610
11Maciej Kisiel10131:37:4010
12Witold Długosz102080:43:1910
13Bartłomiej Gajewski102673:33:1510
14Bartek Dudek7152:59:027
15Jakub Sygnowski111:00:491
16Wojciech Dyżewski178:09:541
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com