e-olymp 8701. Кузнечик-попрыгунчик

Задача

Кузнечик-попрыгунчик долго сидел на отметке [latex]0[/latex] числовой прямой, так долго, что придумал инновационную методологию своего перемещения. Такую, что за каждую итерацию движения он выполняет ровно два прыжка, перемещаясь сначала на [latex]a[/latex], а затем на [latex]b[/latex] единичных отрезков по числовой прямой, причем, если число положительное, то он движется вправо, а если отрицательное, то влево. Продолжительность прыжка в секундах равна соответствующему количеству единичных отрезков, на которое переместится кузнечик.

Например, если [latex]a = 3[/latex], а [latex]b = — 2[/latex], то через [latex]3[/latex] сек. он будет на отметке [latex]3[/latex], а через [latex]5[/latex] сек. от начала движения попадет на отметку [latex]1[/latex]. Далее, на [latex]8[/latex] секунде переместится на отметку [latex]4[/latex], а на [latex]10[/latex] секунде вернется на [latex]2[/latex].

При заданных [latex]a[/latex] и [latex]b[/latex] найти сколько необходимо времени в секундах, чтобы допрыгать до отметки x числовой прямой или вывести [latex]-1[/latex], если это невозможно.

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

Целочисленные значения [latex]a[/latex], [latex]b[/latex], [latex]x[/latex] — в одной строке через пробел. Значение по модулю не превышают [latex]10^{9}[/latex].

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

Ответ на задачу.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 3 -2 1 5
2 100 200 0 0
3 -10 -20 -900 900
4 5 -6 3 27
5 1 3 10 -1

Код программы (с использованием условных операторов)

Решение задачи (с использованием условных операторов)

Для решения данной задачи сначала проверим не находимся ли мы уже в точке [latex]0[/latex], после проверим не равна ли сумма дистанций прыжков [latex]0[/latex], если равна, то также проверим можно ли добраться до точки x за один прыжок a. Если возможно выводим a. После проверяем возможность добраться до точки x двумя способами:

  1. Сначала добравшись до точки x-a прыжками вида a+b, а после совершив один прыжок на дистанцию a
  2. Добраться до точки x исключительно прыжками вида a+b

Если одним из способов невозможно добраться, то присваиваем переменной соответствующей потраченному времени MAX, а после выводим минимум из переменных possible_ans1, possible_ans2(в случае, если обеими способами невозможно добраться, т.е. обе переменные равны MAX выводим -1).

Код программы (без использования условных операторов)

Решение задачи (без использования условных операторов)

Заранее вычислим значения s(пройденное расстояние за один прыжок вида a+b) и t(время, потраченное на один прыжок вида a+b). После поочередно проверим выполнение всех условий, описанных ранее. При выполнении какого-либо из условий, выводим соответствующее время, если ни одно из условий не выполнилось то выводим [latex]-1[/latex].

11 thoughts on “e-olymp 8701. Кузнечик-попрыгунчик

  1. Стоит отметить то, что выход из цикла на 33 строчке — лишний, а также то, что задачу, скорее всего, нужно решить, используя массивы.

    • Николай, благодарю Вас за замечание относительно выхода из цикла на 33 строчке — он действительно был лишним. Так же я спрашивал у Игоря Евгеньевича насчёт способа решений данной задачи и он сказал, что я могу разместить решение без использования массивов, приведя аргументы в пользу невозможности их использования. Возможно, я рассмотрел не все варианты использования массивов для решения данной задачи и был бы очень Вам благодарен, если бы вы помогли мне найти какой-либо вариант.

  2. К сожалению, на тесте 1 -1 1000000000 Ваш код работает в 9 раз дольше положенного времени (проверял локально на Core i3 1.9 Ггц). Это не единственный «плохой» тест — есть еще например 1 1 1000000000. Нельзя ли избавиться от цикла в решении или хотя бы уменьшить сложность алгоритма?

  3. Я зачел, но мнене не нравится несколько мест. Например, if(a+b==0) if(x==a) return(cout << a << endl,0);
    Я бы решал так

    Ещё есть смутное ощущение, что все эти условные операторы можно свернуть в формулу, нет?
    Добавил эту же задачу в категорию «Линейные вычисления». Если даже не получится свернуть всё в формулу, всегда можно использовать трюк с вычислением составных логических выражений. Как упражнение вполне подойдет.
    Проодобавьте еще один код и категорию.

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