Разбор задачи про Франциска Ксавьера

Если вы еще не решили задачу про день святого Франциска Ксавьера из контеста "Продвинутые задачи на условный оператор", то не читайте дальше, сначала решите задачу.

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

Как можно решать эту задачу? Конечно, можно решить тупо: прогнать цикл от года рождения до года смерти и каждый год проверить. По условию годы не превосходят 2000, поэтому такое решение вполне успеет по времени.

Но это — задачи на условный оператор, поэтому решение с циклами разрешать я тут не буду. Тем более что в принципе понятно сразу, что задачу можно решить, просто сделав немного вычислений, без циклов — так что программа будет работать очень быстро независимо от входных данных. (А решение с циклом может очень медленно работать, если годы во входных данных могут быть очень большими — например, на тесте 0 1000000000.) (Тем не менее, это все относится к нашему учебному курсу. Если бы такая задача вам попалась бы на олимпиаде, то, конечно, надо было бы просто написать цикл.)

Как написать такое решение? В принципе, можно работать с данными «как есть», просто написать несколько if'ов, и в каждом сразу вычислять и считать ответ. Пример такого решения:

{$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.

Но такое решение писать довольно сложно (и вообще, я на 100% не уверен, что решение выше верное — оно, конечно, проходит все тесты, но я не уверен, что тесты там достаточно полные).

Проще поступить следующим образом — и на самом деле это подход, встречающийся во многих задачах. Надо понимать, что у вас нет цели написать одну большую формулу (ну или несколько формул с разбором случаев). Компьютер способен на более сложные действия, и этим надо воспользоваться.

Итак, пусть мы считали данные:

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

(s и f от start и finish).

Давайте, во-первых, сдвинем начало отсчета времени на 1605 год, т.е. вычтем из всех годов 1605:

s = s - 1605
f = f - 1605

Это уже существенно упростит задачу: теперь нас интересуют года, делящиеся на 10, с этим работать намного проще, чем с годами, которые дают остаток 5 при делении на 10. Кроме того, дальше нам сравнения надо будет делать не с 1605, а с нулем, что позволяет не ошибиться с годом.

Уже теперь формулы и if'ы будут проще. Но мы пойдем далее и вместо годов рождения и смерти посчитаем и будем использовать первый год, когда он мог коснуться мощей, и последний такой год.

Как определить первый год, когда он мог коснуться мощей? Казалось бы, это первый год, кратный десяти, после года рождения. Соответствующую формулу несложно придумать:

s = s - s % 10 + 10

Правда, как только вы написали это выражение (или даже как только подумали про это), надо тут же подумать: а всегда ли это работает? Тут же должны возникнуть четыре соображения:

• А если s кратно 10 сразу?
• А если полученный год больше года смерти?
• А если полученный год меньше нуля?
• А верно ли это работает для отрицательных s?

На первый вопрос ответ простой: наша формула сработает верно. Действительно, по условию в год рождения крестьянин не мог касаться мощей, поэтому если год рождения был кратен 10, то первый год, когда он мог коснуться мощей, будет на 10 лет позже — это наша формула и дает.

Второй вопрос пока запомним, его рассмотрим позже; кроме того, запомним сразу, что надо будет проверить такой тест — например, тест 3 5, точнее, с учетом того, что мы вычитали 1605 из всех годов, то тест 1608 1610.

Четвертый вопрос на самом деле не вопрос: в питоне взятие остатка для отрицательных чисел работает разумно (например, (-3) % 10 == 7, подумайте, почему это разумно). В результате если изначально было s = -3, то у нас получится s = 0, что и следовало ожидать. Вот в других языках программирования с этим надо аккуратно обойтись.

И наконец третий вопрос обрабатывается легко: если полученный год меньше нуля, то на самом деле первый раз крестьянин мог коснуться мощей в нулевом году:

if s < 0:
    s = 0

Аналогично поступим с годом смерти: нам надо определить последний год, кратный 10, который был не позже года смерти. Формула еще проще:

f = f - f % 10

Здесь тоже возникают те же четыре вопроса, точнее уже два вопроса, потому что с поведением остатка от деления для отрицательных чисел мы уже разобрались, а вопросы "полученный год меньше года рождения" и "полученный год меньше нуля" — это теперь одна и та же ситуация. Ее мы рассмотрим позже, а на оставшийся вопрос "если f кратно 10 сразу" ответ такой же: наш код работает правильно, т.к. в год смерти он мог коснуться мощей.

Теперь мы знаем первый и последний год, когда крестьянин мог коснуться мощей. Ответ на задачу уже вычисляется совсем легко: (f-s) // 10 + 1, только надо не забыть те вопросы, которые мы откладывали. Несложно видеть, что они все объединяются в один if f < s, и в итоге получаем простой вывод ответа:

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

Вот и все. Итоговая программа:

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)

Программа намного проще, чем та, что приведена в начале. Ошибки в ней искать тоже намного проще, т.к. можно проверять ее по частям; мы прекрасно понимаем, в чем физический смысл каждого куска.

(В частности, если бы это был бы не питон, то у вас возникли бы обсуждаемые выше проблемы с остатками для отрицательных чисел. Например, что в c++, что в паскале получается (-3) % 10 == -3 (c++) и (-3) mod 10 == -3 (паскаль), поэтому коррекции s и f будут неверными. Надо такие случаи учитывать особо, но в любом случае как только вы находите такой баг, вы сразу понимаете, где он и как его исправить. В решении с кучей вложенных if'ов искать такую ошибку было бы намного сложнее.

Итак, и это полезно не только в этой задаче, но и во многих других. Если вы понимаете, что задача решается формулой, не надо сразу бросаться эту формулу писать. Компьютер может сделать дополнительные действия, вы можете провести какие-то вычисления, например, упростив входные данные, или вычислив какие-нибудь дополнительные переменные, и т.д. Не бойтесь этого делать.

И вторая мораль: если вы видите, что вы можете упростить входные данные к задаче, это зачастую полезно сделать. Последовательно упрощая данные, вы делаете решение проще и проще.