Analysis of the "Lines in the book" problem
The first idea that arises in this problem is to write N mod K
and N div K+1
. But unfortunately, this doesn't work when N
is divisible by K.
If the conditional operator (if) could be used in this task, then everything would be simple. If this task would have been at a real Olympiad, then, of course, write if. But here you can't use if for educational purposes.
The following idea will come to the rescue. Let's first try to solve a slightly different problem: let's assume that everything in this problem — lines in the book, pages and lines on the page — is numbered from scratch. (And the number of lines on the page, of course, is counted from 1 as before.) Then, if, for example, K=3
, then on the zero page there are lines 0, 1, 2; on the first page there are lines 3 4 5, etc. And it's easy to see that just in this case, it's enough to simply divide N
by K
; the answer will be N div K
and N mod K
; this works in all cases.
Now let's get back to our task. We enter the line number, if we count from one. Let's try to reduce our problem to the one we just solved; to do this, we subtract one from N
— we get the number of the line in the book as if the numbering started from zero. Next, divide the resulting number with the remainder by K
and get the correct page number and line number on the page, only the numbering of everything is still going from zero. Add 1 to the answers to get the numbering from one.
Total solution of the problem: (N-1) div K + 1
and (N-1) mod K + 1
.
In general, this is a very useful idea — if the problem is poorly solved when numbering from one, sometimes it turns out to be much easier to switch to numbering from zero. Especially in such tasks, where you clearly need to divide into equal parts.