I came across this question here while practising for an upcoming competition.
The problem is as follows:
Petr stands in the line of n people, but he doesn't know exactly which position he occupies. He can say that there are no less than a people standing in front of him and no more than b people standing behind him. Find the number of different positions Petr can occupy.
Input
The only line contains three integers n, a and b $(0 ≤ a, b < n ≤ 100)$.
Output
Print the single number — the number of the sought positions.
Examples
input
3 1 1
output
2
input
5 2 3
output
3
And the editorial explanation is as follows:
Let's iterate through each item and check whether it is appropriate to the conditions $a ≤ i - 1$ and $n - i ≤ b$ (for i from 1 to n). The first condition can be converted into $a + 1 ≤ i$, and the condition $n - i ≤ b$ in $n - b ≤ i$, then the general condition can be written $max(a + 1, n - b) ≤ i$ and then our answer can be calculated by the formula $n - max(a + 1, n - b) + 1$.
Unfortunately, going through the editorial, I am not able to get an intuitive understanding of how the mathematical expression $n - max(a + 1, n - b) + 1$ was arrived.
Could someone please give an intuitive explanation of the solution to this problem?
Thanks in advance.
Best Answer
We know there are at least $a$ positions before Petr and at most $b$ positions after Petr.
Let $i$ be a possible position for Petr. Then $1,2,...,i-1$ are the positions in front of Petr and this number, $i-1$, must be at least $a$, i.e. $i-1\ge a\implies i\ge a+1$ which is equivalent to $a+1\le i$.
The positions after Petr are $i+1, i+2, ..., n$ and the number of these is $n-i$ which must be at most $b$. Therefore, $n-i\le b\implies n-b\le i$.
Since both $a+1$ and $n-b$ are less than or equal to $i$, the maximum of the two is less than or equal to $i$. We take this number $m=\text{max}(a+1,n-b)$ to be the minimum position that Petr can occupy.
Now Petr can occupy positions $m,m+1,...,n$ and the number of these is $n-(m-1)=n-m+1$ which is the formula you asked about.