Analysis of the problem about Francis Xavier

If you haven't solved the problem about St. Francis Xavier's Day from the contest "Advanced Conditional Operator problems", then don't read on, solve the problem first.

-
-
-
-
-
-
-
-
-
-
-
-
-
-

How can this task be solved? Of course, you can solve stupidly: run the cycle from the year of birth to the year of death and check every year. According to the condition, the years do not exceed 2000, so such a decision will be quite in time.

But these are tasks for a conditional operator, so I will not solve the solution with cycles here. Moreover, in principle, it is immediately clear that the problem can be solved simply by doing a few calculations, without cycles — so the program will work very quickly regardless of the input data. (And a solution with a loop can work very slowly if the years in the input data can be very large — for example, on the test 0 1000000000.) (Nevertheless, this all applies to our training course. If you had such a task at the Olympics, then, of course, you would just have to write a cycle.)

How to write such a solution? In principle, you can work with the data "as is", just write several if's, and in each immediately calculate and count the answer. An example of such a solution:

{$mode delphi}
var r,s:integer;
begin
read(r,s);
if (s<1605) then writeln(0)
else if ((r=1605) or (r mod 10=5)) then writeln((s-r) div 10)
else if (r>1605) then
	if (r mod 10<5) then writeln((s-(r-r mod 10 +5))div 10 +1)
	else writeln((s-(r-r mod 10 +15))div 10 +1)
else writeln((s-1605) div 10 +1);
end.

But it's quite difficult to write such a solution (and in general, I'm not 100% sure that the solution above is correct — it, of course, passes all the tests, but I'm not sure that the tests there are complete enough).

It is easier to do the following — and in fact this is an approach found in many tasks. It should be understood that you do not have a goal to write one big formula (well, or several formulas with case analysis). The computer is capable of more complex actions, and this should be taken advantage of.

So, let's say we counted the data:

s, f = map(int, input().split())

(s and f from start and finish).

First of all, let's shift the start of the countdown to 1605, i.e. subtract 1605 from all the years:

s = s - 1605
f = f - 1605

This will greatly simplify the task: now we are interested in years divisible by 10, it is much easier to work with this than with years that give a remainder of 5 when divided by 10. In addition, then we will have to make comparisons not with 1605, but with zero, which allows us not to make a mistake with the year.

Already now formulas and if's will be easier. But we will go further and instead of the years of birth and death, we will count and use the first year when he could touch the relics, and the last such year.

How to determine the first year when he could touch the relics? It would seem that this is the first year, a multiple of ten, after the year of birth. The corresponding formula is easy to come up with:

s = s - s % 10 + 10

However, as soon as you wrote this expression (or even as soon as you thought about it), you should immediately think: does it always work? Four considerations should immediately arise:

• And if s is a multiple of 10 at once?
• And if the year received is more than the year of death?
• And if the resulting year is less than zero?
• Does this work correctly for negative s?

The answer to the first question is simple: our formula will work correctly. Indeed, according to the condition in the year of birth, the peasant could not touch the relics, so if the year of birth was a multiple of 10, then the first year when he could touch the relics would be 10 years later — this is our formula and gives.

We will remember the second question for now, we will consider it later; in addition, we will immediately remember that it will be necessary to check such a test — for example, test 3 5, more precisely, taking into account the fact that we subtracted 1605 from all years, then the test 1608 1610.

The fourth question is not really a question: in python, taking the remainder for negative numbers works reasonably (for example, (-3) % 10 == 7, think about why this is reasonable). As a result, if initially it was s = -3, then we will get s = 0, which is to be expected. Here in other programming languages, this should be handled carefully.

And finally, the third question is handled easily: if the resulting year is less than zero, then in fact the first time a peasant could touch the relics in the zero year:

if s < 0:
    s = 0

Let's do the same with the year of death: we need to determine the last year, a multiple of 10, which was no later than the year of death. The formula is even simpler:

f = f - f % 10

Here, too, the same four questions arise, or rather, two questions already, because we have already figured out the behavior of the remainder of the division for negative numbers, and the questions "the resulting year is less than the year of birth" and "the resulting year is less than zero" are now the same situation. We will consider it later, and the answer to the remaining question "if f is a multiple of 10 at once" is the same: our code works correctly, because in the year of death it could touch the relics.

Now we know the first and last year when a peasant could touch the relics. The answer to the problem is already calculated quite easily: (f-s) // 10 + 1 just don't forget the questions we've been putting off. It is not difficult to see that they are all combined into one if f < s, and as a result we get a simple output of the answer:

if f < s: 
    print(0)
else:
    print((f-s) // 10 + 1)

That's all. Final program:

s, f = map(int, input().split())
s = s - 1605
f = f - 1605

s = s - s % 10 + 10
if s < 0:
    s = 0

f = f - f % 10

if f < s: 
    print(0)
else:
    print((f-s) // 10 + 1)

The program is much simpler than the one given at the beginning. It is also much easier to look for errors in it, because you can check it in parts; we perfectly understand what the physical meaning of each piece is.

(In particular, if it were not python, then you would have the problems discussed above with residuals for negative numbers. For example, in c++, in pascal it turns out (-3) %10 == -3 (c++) and (-3) mod 10 == -3 (pascal), so the corrections s and f will be incorrect. It is necessary to take such cases into account especially, but in any case, as soon as you find such a bug, you immediately understand where it is and how to fix it. In a solution with a bunch of nested if's, it would be much more difficult to look for such an error.

So, and it is useful not only in this task, but also in many others. If you understand that the problem is solved by a formula, do not immediately rush to write this formula. The computer can do additional actions, you can perform some calculations, for example, simplifying the input data, or calculating some additional variables, etc. Don't be afraid to do it.

And the second moral: if you see that you can simplify the input data to the task, it is often useful to do so. By consistently simplifying the data, you make the solution simpler and simpler.