Z2 - Zápalky 2Časový limit: 10s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Melanka riešila rôzne matematické úlohy o zápalkách. Po dlhom trápení vyriešila ťažkú úlohu a našla riešenie - veľké číslo. Keď však vošla do jej izby jej sestra Paulínka, tak Melanka sa k nej otočila a nechtiac zhodila zápalky na zem. Melanka si teraz pamätá len to, že číslo (nezačínajúce nulou) bolo deliteľné tromi. Pozbierala spadnuté zápalky a spočítala ich. Teraz sa snaží zistiť, koľko rôznych čísel mohlo byť vytvorených z týchto zápaliek. Číslice boli ukladané ako na LCD displejoch (viď obrázok). ÚlohaPre zadaných počet n zápaliek zistite, koľko rôznych kladných čísel deliteľných tromi mohlo byť z nich vytvorených.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.Z11 ≤ p, n ≤ 15 Z21 ≤ p ≤ 100, 1 ≤ n ≤ 100 000 PríkladVstup:3 4 5 6 Výstup:0 1 3Pri 6 zápalkách máme 3 rôzne možnosti - jednociferné čísla 6 a 9 zložené zo šiestich zápaliek a trojciferné číslo 111, pričom každá číslica 1 je zložená z dvoch zápaliek. Všetky tieto tri čísla sú deliteľné troma. |