e-olymp 8594. Между A и B

Задача

Заданы целые неотрицательные числа $a$ и $b$ [latex](a \le b)[/latex] и натуральное число $x$. Сколько существует чисел между $a$ и $b$ включительно, делящихся на $x$?

Входные данные

Три числа $a$, $b$ и $x$ [latex](0 \le a \le b \le 10^{18}, 1 \le x \le 10^{18}[/latex]).

Выходные данные

Выведите ответ на задачу.

Тесты

Вход Выход
2 6 5 1
1 200 3000 0
83 180 10 10
775 12004 312 36
13 42 7 5

 Код программы

 

Решение

Для решения данной задачи, мы должны найти длину отрезка [latex][a;b][/latex], получаем промежуток, а после, если поделим на $x$, обнаружим целую и дробную часть, как раз целая часть числа и будет являться нашим ответом. Формула оказывается таковой: [latex][\frac{b-a}{x} ][/latex]. На сию формулу я буду в основном опираться. Но эта формула не учитывает некоторые случаи.

Если $a$ или $b$ будут без остатка делится на $х$, например, [latex]a=5[/latex], [latex]b=15[/latex], [latex]x=5[/latex]. По старой формуле ответ будет $2$. Но само по себе $a$(или $b$) тоже кратно $x$.  Ещё один случай формула не видит, поэтому нужно прописать дополнительную формулу для подобных ситуаций: [latex][\frac{b-a}{x} + 1][/latex]

Первая формула также не учитывает случай, когда остаток от меньшего числа, больше остатка от большего, например, [latex]a=3[/latex], [latex]b=6[/latex], [latex]x=5[/latex]. Между $a$ и $b$ есть решение, но по старой формуле ответ равен $0$, но мы видим, что ответ есть и он $1$. Опять же, мы должны предусмотреть подобные случаи и сделать для них «исключение» от изначальной формулы, добавив забытую единицу:  [latex][\frac{b-a}{x} + 1][/latex]

Ссылки

e-olymp

ideone

 

6 thoughts on “e-olymp 8594. Между A и B

  1. Вы просматриваете три варианта и два из них имеют один и тот же результат, их можно объединить

  2. Здесь изложена куча условий, в которых довольно легко ошибиться и не очевидно, что они правильные. В то же время к данной задаче есть классический и более простой подход. «Научимся считать количество чисел, делящихся на $х$, от 1 до $k$…»
    Пока что предоставлю Вам сделать из этого посыла самостоятельные выводы.

      • Никаких претензий, только советы 🙂

        Хорошо, поясняю. Описание Вашего решения напоминает процесс блуждания: возьмем что-то похожее на ответ, зашлем на сервер, получим Wrong Answer, а точно! есть еще случай, добавим для него if, снова зашлем, снова WA… Вот, теперь ОК, так и оставим.

        Если бы у Вас под рукой не было сервера, или на сервере были бы неполные тесты, то из данного Вами описания было бы невозможно сделать вывод, что именно данный набор проверок является достаточным и почему. Вдруг Ваша формула еще какой случай «не видит» или в уже рассмотренных случаях какой-то неверно описан.

        На самом деле, проблема кроется в необоснованности самого первого утверждения «Для решения данной задачи, мы должны найти длину отрезка [a, b]». Ведь, как Вы показываете далее, всязь между длиной отрезка и количеством делящихся на x чисел неоднозначна. Я предлагаю вместо этого научиться считать сколько чисел от 1 до k делится на x. Там все однозначно. Тогда можно найти количество на отрезке, как разность количеств на двух отрезках. Этот подход проще и является традиционным для таких задач.

  3. Саша, Вы никак не реагируете на советы и замечания. Просто снова и снова ставите работу на проверку. Какой реакции с моей стороны Вы ожидаете? Что мне это надоест и я просто зачту?
    Если не понимаете сути замечаний, задавайте вопрос. Если понимаете — исправляйте.

Добавить комментарий