Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Ułamki łatwe (ulamki-latwe) Limit pamięci: 32 MB Limit czasu: 1.00 s Kapral Jasio z bardzo dobrym przybliżeniem oszacował ostatnio liczbę niemieckich czołgów. Zauważył, że na każdym z czołgów jest numer seryjny, a numery przyznawane są sekwencyjnie: 1, 2, 3, … i tak dalej. Jeśli więc wśród dwudziestu wytropionych czołgów największy numer był 95, to całkiem niezłym przybliżeniem liczby wszystkich czołgów jest 100. Kapitan Bajtazar pochwalił kaprala Jasia i obiecał mu awans jeżeli rozwiąże ten problem (kolejnych numerów seryjnych) w bajtockiej armii. Jasio postanowił, że numery seryjne bajtockich czołgów powinny być ułamkami zwykłymi. Aby było łatwiej, ułamki te muszą być nieskracalne. Dla niepoznaki, numery czołgów będą wprowadzane do ściśle tajnego cybernetycznego systemu w postaci liczb dziesiętnych. Przykładowo: czołg o numerze seryjnym $\frac{1}{2}$ będzie figurował w systemie pod nazwą 0.5. System ten jednak przyjmuje numery o skończonej precyzji. Wyklucza to więc niektóre numery seryjne czołgów, takie jak $\frac{1}{3} = 0.333\ldots$. Jasio postanowił więc używać ułamków najprostszych: ułamków zwykłych nieskracalnych, które zapisane jako ułamki dziesiętne mają skończone nieokresowe rozwinięcie. Takie ułamki Jasio nazwał łatwymi. Przykładowo więc, ułamki $\frac{1}{2}$ oraz $\frac{97}{50}$ są łatwe, zaś ułamki $\frac{1}{3}$ oraz $\frac{5}{20}$ nie są. Dodatkowo, Jasio nie uznaje za łatwe ułamków z mianownikiem 1, ani ułamków z licznikiem 0. Są to liczby całkowite, nie ma sensu zapisywać ich w nienormalny sposób. W wojsku dysponują jedynie skończoną i bardzo niewielką liczbą szablonów cyfr, które można odmalować na czołgach. Każdej cyfry można użyć tylko jeden raz: jako cyfrę licznika ułamka, jako cyfrę mianownika ułamka albo nie użyć jej wcale. Cyfry, zarówno w liczniku jak i w mianowniku, można wstawiać w dowolnej kolejności. Niedopuszczalne jest uzyskanie zer wiodących: ani w liczniku ani w mianowniku. Pomóż Jasiowi zasłużyć na awans w armii. Ile różnych numerów seryjnych czołgu (łatwych ułamków) Jasio może stworzyć ze swojego zbioru cyfr? Napisz program, który: wczyta (multi)zbiór dostępnych cyfr, wyznaczy liczbę łatwych ułamków jakie możliwe są do uzyskania z dostępnego zbioru i wypisze wynik na wyjście. Wejście W pierwszym (jedynym) wierszu wejścia znajduje się ciąg cyfr, bez żadnych odstępów. Wyjście W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita – reszta z dzielenia przez 109 + 7 liczby możliwych do uzyskania łatwych ułamków. Ograniczenia Długość ciągu cyfr nie przekracza 18 znaków. Przykład Wejście Wyjście Wyjaśnienie 1230 14 Czołg mógłby mieć jeden z następujących numerów seryjnych: $\frac{1}{320} = 0.003125, \frac{1}{32} = 0.03125, \frac{1}{20} = 0.05, \frac{3}{20} = 0.15, \frac{3}{10} = 0.3, \frac{1}{2} = 0.5, \frac{13}{20} = 0.65, \frac{3}{2} = 1.5, \frac{31}{20} = 1.55, \frac{23}{10} = 2.3, \frac{13}{2} = 6.5, \frac{31}{2} = 15.5, \frac{103}{2} = 51.5, \frac{301}{2} = 155.5$.

Wejście	Wyjście	Wyjaśnienie
`1230`	`14`	Czołg mógłby mieć jeden z następujących numerów seryjnych: $\frac{1}{320} = 0.003125, \frac{1}{32} = 0.03125, \frac{1}{20} = 0.05, \frac{3}{20} = 0.15, \frac{3}{10} = 0.3, \frac{1}{2} = 0.5, \frac{13}{20} = 0.65, \frac{3}{2} = 1.5, \frac{31}{20} = 1.55, \frac{23}{10} = 2.3, \frac{13}{2} = 6.5, \frac{31}{2} = 15.5, \frac{103}{2} = 51.5, \frac{301}{2} = 155.5$.