F2 - Digitálny displejČasový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Alojzko dostal na narodeniny úžasný digitálny displej, ktorý dokáže zobrazovať ľubovoľné kladné čísla. Z toľkej radosti mu však nakoniec displej spadol na zem a všetky číslice sa rozsypali na drobné kúsky! Digitálne číslice displeja boli zložené z jednotlivých paličiek, pričom výsledné kladné celé číslo, ktoré tvorili, nezačínalo nulou. Alojzko si pamätá len to, že toto číslo bolo deliteľné tromi. Práve spočítal všetky paličky rozsypané po zemi a snaží sa zistiť, koľko rôznych čísel mohlo byť zobrazených na displeji, než sa rozbil. ÚlohaPre zadaných n paličiek zistite, koľko rôznych kladných čísel deliteľných tromi mohlo byť zobrazených na displeji.VstupNa prvom riadku sa nachádza číslo p, počet testovacích sád. Nasleduje p, riadkov, pričom každý obsahuje jediné číslo n.VýstupVypíšte p riadkov, každý s jediným číslom - hľadaným počtom možností pre danú sadu. Keďže toto číslo môže byť veľmi veľké, vypíšte jeho zvyšok po delení 1 000 000 009.F11 ≤ p, n ≤ 15 F21 ≤ p ≤ 100, 1 ≤ n ≤ 100 000 PríkladVstup:3 4 5 6 Výstup:0 1 3Pri 6 paličkách máme 3 rôzne možnosti - jednociferné čísla 6 a 9 zložené zo šiestich paličiek a trojciferné číslo 111, pričom číslica 1 je zložená z dvoch paličiek. Všetky tieto tri čísla sú deliteľné troma. |