#GYM104619C. Cutting into Monotone Increasing Sequence
Cutting into Monotone Increasing Sequence
Description
A monotone sequence is a sequence of numbers that either consistently increases or consistently decreases as you move along the sequence. In other words, it exhibits a consistent trend in either an upward or downward direction.
In a monotone increasing sequence, each term in the sequence is greater than or equal to the preceding term. Mathematically, for a sequence $a_1,\dots,a_n$, it is monotone increasing if and only if for every $1\le i< n$, $a_i \le a_{n+1}$. For example, the sequence $1, 2, 2, 4, 5$ is a monotone increasing sequence because each term is greater than or equal to the previous term.
Monotone sequences are important in various areas of mathematics, including calculus and analysis, as they often simplify the analysis of functions and their behavior. They provide a clear and consistent trend that makes it easier to understand the behavior of a sequence or a function over a range of values.
One of our problem setters is fond of big integers. Over the past few years, the Taiwan Online Programming Contest has frequently featured problems involving big integers. This time, we have a problem that combines big integers with monotone increasing sequences. Your task is to transform a big integer, denoted as $x$, into a monotone increasing sequence by inserting commas ',' into the gaps between its digits, while adhering to following constraints.
- The last term of the monotone increasing sequence is no more than $b$.
- Commas cannot be inserted before a zero.
- The number of commas is minimized.
Let's assume that $x$ is an integer with $k$ digits and is represented as $d_1d_2\cdots d_k$. For instance, if we have $x=654321=d_1d_2\cdots d_6$ and $b=1000$, we can insert commas into gaps after $d_3$ and $d_5$ to convert $x$ into the following monotone increasing sequence: $6, 54, 321$.
Please write a program to compute the minimum number of commas required to transform a given big integer $x$ into a monotone increasing sequence consisting of numbers no more than a given integer $b$. If there is no way to transform, please print 'NO WAY'.
The input contains two non-negative integers $x$ and $b$.
- $x\le 10^{100000}$
- $b< 2^{64}$
- There is no leading zero if $x>0$.
Print the minimum number of commas required to transform $x$ into a monotone increasing sequence consisting of numbers no more than $b$. If there is no way to transform, please print 'NO WAY' without quotes.
Input
The input contains two non-negative integers $x$ and $b$.
- $x\le 10^{100000}$
- $b< 2^{64}$
- There is no leading zero if $x>0$.
Output
Print the minimum number of commas required to transform $x$ into a monotone increasing sequence consisting of numbers no more than $b$. If there is no way to transform, please print 'NO WAY' without quotes.
654321 1000
654321 100
2
NO WAY