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 1 5 5
5 1 3 10 -1

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

Решение задачи

Для того, чтобы найти время которое нужно кузнечику чтобы добраться до необходимой точки, запустим цикл, отображающий процесс его передвижения. В переменной cur_pos будем хранить текущую позицию кузнечика, а в переменной cnt — время, которое понадобилось кузнечику чтобы добраться до cur_pos. Перед запуском цикла, с помощью условных операторов, проверим возможность кузнечика добраться до необходимой ему точки. Запустим цикл for, состоящий из [latex]x[/latex] итераций(за [latex]x[/latex] прыжков кузнечик определенно должен добраться до необходимой точки, так как расстояния, которые он преодолевает с помощью прыжков целочисленные, соответственно, расстояние минимального прыжка — 1). На каждой итерации цикла сначала перемещаем кузнечика на [latex]a[/latex] единичных отрезков, и проверяем добрался ли он до необходимой точки, а после перемещаем на [latex]b[/latex] единичных отрезков и проверяем то же условие. После выхода из цикла, в зависимости от значения переменной found выводим [latex]-1[/latex] или cnt, в случае если кузнечик все же добрался до необходимой точки.

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

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

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

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

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

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