Problem B
Difference
A smallest different sequence (SDS) is a sequence of positive integers created as follows: $A_1=r \geq 1$. For $n>1$, $A_ n=A_{n-1}+d$, where $d$ is the smallest positive integer not yet appearing as a value in the sequence or as a difference between two values already in the sequence. For example, if $A_1 =1$, then since $2$ is the smallest number not in our sequence so far, $A_2=A_1+2=3$. Likewise $A_3=7$, since $1, 2$ and $3$ are already accounted for, either as values in the sequence, or as a difference between two values. Continuing, we have $1, 2, 3, 4, 6$, and $7$ accounted for, leaving $5$ as our next smallest difference; thus $A_4=12$. The next few values in this SDS are $20, 30, 44, 59, 75, 96, \ldots $ For a positive integer $m$, you are to determine where in the SDS $m$ first appears, either as a value in the SDS or as a difference between two values in the SDS. In the above SDS, $12, 5, 9$ and $11$ first appear in step $4$.
Input
Input consists of a single line containing two positive integers $A_1$ $m$ ($1 \leq r \leq 100, 1 \leq m \leq 200\, 000\, 000$).
Output
Display the smallest value $n$ such that the sequence $A_1, \ldots , A_ n$ either contains $m$ as a value in the sequence or as a difference between two values in the sequence. All answers will be $\leq 10\, 000$.
Sample Input 1 | Sample Output 1 |
---|---|
1 5 |
4 |
Sample Input 2 | Sample Output 2 |
---|---|
1 12 |
4 |
Sample Input 3 | Sample Output 3 |
---|---|
5 1 |
2 |