Editorial for Art Academy VII: A Mysterious Object

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: astrocat879

For the $10\%$ $10 %$ subtask, looping from $0$ $0$ to $K$ $K$ and checking if the number contains $10$ $10$ as a subsequence passes. Make sure the number doesn't contain $100$ $100$ as a subsequence.

For the remaining $90\%$ $90 %$ , we use dynamic programming.

The dp state should be $dp[index][state][less]$ $d p [i n d e x] [s t a t e] [l e s s]$ .

$index$ $i n d e x$ is between $0$ $0$ and the number of digits in $K$ $K$ . It represents which digit you are at in $K$ $K$ .
$state$ $s t a t e$ is either $0$ $0$ , $1$ $1$ , or $2$ $2$ . It represents zero previous occurrences of $1$ $1$ , a previous occurrence of $1$ $1$ , and a previous occurrence of a $1$ $1$ and a $0$ $0$ , respectively.
$less$ $l e s s$ is either $0$ $0$ or $1$ $1$ . It represents if the number being considered is currently less than $K$ $K$ .

The transition is left as an exercise to the reader.

Comments

There are no comments at the moment.