Hide

1234

Forestil dig følgen $C$ af cifre, der fremkommer ved at skrive de naturlige tal $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$, $11$, $12$, $13$, $14$, $15$, $\ldots $, ved siden af hinanden uden komma eller mellemrum. Cifferfølgen $C$ begynder altså med »123456789101112131415…« og er uendelig lang.

Givet et mønster $M$ af cifre, hvor mange tegn skal der springes over i $C$, før $M$ optræder første gang?

\includegraphics[width=.9\textwidth ]{img/samples.pdf}

For eksempel optræder mønstret »$3456$« på position $2$. Det gør mønstret »$3$« også. Mønstret »$12$« optræder på position $0$. Læg mærke til, at »$12$« optræder igen på position $13$, men vi er udelukkende interesserede i den første forekomst. Mønstret »8128« forekommer første gang på position $733$, når sifferfølgen er nået til $280$, $281$, $282$, $283$:

\includegraphics[width=.65\textwidth ]{img/sample8128.pdf}

Indlæsning

Mønstret $M$ på en enkelt linje med $k$ cifre, hvor $1\leq k\leq 17$.

Udskrift

Et enkelt heltal: hvor mange cifre i $C$ skal springes over inden $M$ optræder første gang?

Pointsætning

Der er to testgrupper, hver med 50 point. I den første testgruppe er $k\leq 4$.

Sample Input 1 Sample Output 1
3
2
Sample Input 2 Sample Output 2
1112
11
Sample Input 3 Sample Output 3
1113
3341
Sample Input 4 Sample Output 4
0000
38890
Sample Input 5 Sample Output 5
3142
4584
Sample Input 6 Sample Output 6
8128
733
Sample Input 7 Sample Output 7
72185000
136889471
CPU Time limit 1 second
Memory limit 1024 MB
Author
Troels Bjerre Lund
Source D-Pop 2022
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in