Разбор задачи про Франциска Ксавьера (читать только тем, кто решил саму задачу!)

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

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

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

Как можно решать эту задачу? Конечно, можно решить тупо: прогнать цикл от года рождения до года смерти и каждый год проверить. По условию годы не превосходят 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'ов искать такую ошибку было бы намного сложнее.

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

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