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

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

   C++

   int main() { unsigned long long a,b,x; cin>>a>>b>>x; cout<<( b-a ) / x + ( a%x==0 || b%x==0 || a%x > b%x ); return 0; }

   1 2 3 4 5 6

   int main() {     unsigned long long a,b,x;     cin>>a>>b>>x;     cout<<( b-a ) / x + ( a%x==0 || b%x==0 || a%x > b%x );     return 0; }

   Войдите, чтобы ответить

   • k = ( b-a ) / x +( a%x==0 || b%x==0 || a%x > b%x );

   • Действительно, это вариант короче, но мне кажется, что мой вариант более наглядный, хоть и больше. Спасибо за совет.

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

   Войдите, чтобы ответить

   • Мне не ясны ваши претензии объясните поподробнее, пожалуйста.

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

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

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

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

   • Спасибо за совет. Учёл ваше предложение в новой редакции.

   • Почти все хорошо. Вы все-таки не избежали одной проверки, а могли бы, если бы заметили, что нам из отрезка [1; b] нужно выбросить в точности отрезок [1; a-1]

   • На комментарий 20.11.18.
     Я пробовал рассмотреть вариант, когда отрезок [1; а-1]. Но на сервере он не проходит полностью. Возможно, я что то сделал не так.

   • Проблема может возникнуть с отрезком, начинающимся с 0. Потому что -1/x обрезается вверх (к 0), а не вниз. Если бы a-1 всегда были неотрицательными, все бы работало правильно.

     Можно a и b предварительно увеличить на х. Тогда их остатки от деления на х не изменятся, а требование неотрицательности будет выполнено. Но с другой стороны, это решение годится для a >= 0 и не годится для a >= -10^18, т.е. не является универсальным.

     Более универсальным было бы прибавить к границам что-то в духе (-a / x + 1) * x. Но не уверен, что в данной задаче стоит так заморачиваться.

     Еще можно делить всегда в меньшую сторону.
     int myDiv(int p, int q) {p -= (p % q + q) % q;return p / q;}

     Интересно, какой вариант больше нравится Игорю Евгеньевичу.

   • Я разделяю Ваш интерес в поиске универсального решения. Вы дали мне тему для размышления. Благодарю.
     Также я поддерживаю ваши сомнения, касательно того, нужно ли модифицировать правильное решение, занимаясь преждевременной оптимизацией.

   • Поясню причину своих сомнений. Данная задача не является самостоятельной. Она демонстрирует распространенный прием, который в качестве вспомогательного применяется во многих куда более сложных задачах. Это важно уметь писать с минимально возможным количеством ифов. т.к. если у Вас будет не отрезок, а 4-мерный гиперкуб чисел и в нем еще надо будет применять формулу включения-исключения, то каждый +иф это потенциальный +баг. Так что я задумался, какой подход позволил бы писать максимально универсальный и при этом не слишком усложненный код. Пока что это не очевидно.

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

   Войдите, чтобы ответить

   • Игорь Евгеньевич, учёл вышеизложенные советы комментаторов.

   • Пришлось помучиться. Зато выучили полезный приём и попали в таблицу рекордов по этой задаче.
     Кстати, по ссылке на ideone лежит старый вариант кода. Исправьте, пожалуйста.

4. Посмотрел своё решение. Я тоже, как советует Олег, отдельно обрабатывал случай с нулевой левой границей.

   C++

   #include <iostream> int main() { long a, b, x; std::cin >> a >> b >> x; std::cout << b/x - (a > 0? (a-1)/x : -1); }

   1 2 3 4 5 6

   #include <iostream> int main() {     long a, b, x;     std::cin >> a >> b >> x;     std::cout << b/x - (a > 0? (a-1)/x : -1); }

   Конечно, можно выкрутиться и сразу исключить 0, если сдвинуть всю шкалу вправо так, чтобы это не влияло на ответ:

   C++

   #include <iostream> int main() { long long a, b, x; std::cin >> a >> b >> x; std::cout << (b+x)/x - (a+x-1)/x; }

   1 2 3 4 5 6

   #include <iostream> int main() {     long long a, b, x;     std::cin >> a >> b >> x;     std::cout << (b+x)/x - (a+x-1)/x; }

   Войдите, чтобы ответить

5. Действительно… это действительно работает без ветвлений. Спасибо. Надеюсь вы не злитесь, за то, что я проверил ваш код на сервере?

   Войдите, чтобы ответить

   • Нет 🙂
     Я тоже его проверил 🙂