Задача
Кузнечик-попрыгунчик долго сидел на отметке [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 |
Код программы (с использованием условных операторов)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<iostream> using namespace std; #define MAX 1000000000000000000 int main() { long long a, b, x; cin >> a >> b >> x; // ввод переменных if (!x) return (cout << 0 << endl, 0); // проверяем, не равен ли x 0(тогда не нужно совершать никаких прыжков) if(a+b==0) if(x==a) return(cout << a << endl,0); // так же проверяем не будет ли суммой дистанций прыжков 0, // если будет, то проверяем, можно ли за первый прыжок добраться до точки x long long possible_ans1 = MAX, possible_ans2 = MAX; // объявляем две переменные, соответветствующие двум способам добраться до точки x if (!((x - a) % (a + b)))// проверяем первый способ, если можно добраться за n(a+b) + a прыжков, где n - количество совершенных прыжков possible_ans1 = ((x - a) / (a + b)) * (abs(a) + abs(b)) + abs(a); if (!(x % (a + b))) // проверяем второй способ, если до x можно добраться n(a+b) прыжков possible_ans2 = x / (a + b) * (abs(a) + abs(b)); // если невозможно добраться каким-либо из способов, то присваиваем соответствующей переменной значение MAX if (possible_ans1 < 0) possible_ans1 = MAX; if (possible_ans2 < 0) possible_ans2 = MAX; if (possible_ans1 == MAX && possible_ans2 == MAX) // если невозможно добраться никаким из способов, то выводим -1, в отличном случае return (cout << -1 << endl, 0); // выводим минимум из возможных ответов cout << min(possible_ans1, possible_ans2) << endl; return 0; } |
Решение задачи (с использованием условных операторов)
Для решения данной задачи сначала проверим не находимся ли мы уже в точке [latex]0[/latex], после проверим не равна ли сумма дистанций прыжков [latex]0[/latex], если равна, то также проверим можно ли добраться до точки x за один прыжок a. Если возможно выводим a. После проверяем возможность добраться до точки x двумя способами:
- Сначала добравшись до точки x-a прыжками вида a+b, а после совершив один прыжок на дистанцию a
- Добраться до точки x исключительно прыжками вида a+b
Если одним из способов невозможно добраться, то присваиваем переменной соответствующей потраченному времени MAX, а после выводим минимум из переменных possible_ans1, possible_ans2(в случае, если обеими способами невозможно добраться, т.е. обе переменные равны MAX выводим -1).
Код программы (без использования условных операторов)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <cmath> using namespace std; int main() { long long a,b,x,s,t,ans=-1; cin >> a >> b >> x; s=a+b; t=abs(a)+abs(b); (!x) && cout << 0 || (x==a) && cout << abs(a) || !((x - a) % (s)) && ((x - a) / (s)) * (t) + abs(a) >= 0 && cout << ((x - a) / (s)) * (t) + abs(a) || !(x % (s)) && x / (s) * (t) >= 0 && cout << x / (s) * (t) || cout << -1; return 0; } |
Решение задачи (без использования условных операторов)
Заранее вычислим значения s(пройденное расстояние за один прыжок вида a+b) и t(время, потраченное на один прыжок вида a+b). После поочередно проверим выполнение всех условий, описанных ранее. При выполнении какого-либо из условий, выводим соответствующее время, если ни одно из условий не выполнилось то выводим [latex]-1[/latex].
Стоит отметить то, что выход из цикла на 33 строчке — лишний, а также то, что задачу, скорее всего, нужно решить, используя массивы.
Николай, благодарю Вас за замечание относительно выхода из цикла на 33 строчке — он действительно был лишним. Так же я спрашивал у Игоря Евгеньевича насчёт способа решений данной задачи и он сказал, что я могу разместить решение без использования массивов, приведя аргументы в пользу невозможности их использования. Возможно, я рассмотрел не все варианты использования массивов для решения данной задачи и был бы очень Вам благодарен, если бы вы помогли мне найти какой-либо вариант.
Спасибо за ответ, исчерпывающее объяснение.
К сожалению, на тесте 1 -1 1000000000 Ваш код работает в 9 раз дольше положенного времени (проверял локально на Core i3 1.9 Ггц). Это не единственный «плохой» тест — есть еще например 1 1 1000000000. Нельзя ли избавиться от цикла в решении или хотя бы уменьшить сложность алгоритма?
Олег прав, цикл здесь ненужен. Задача была ошибочно помещена в категорию задач на массивы. Исправил.
Только условный оператор.
И остаток от деления 🙂
Олег прав, цикл здесь не нужен. Задача была ошибочно помещена в категорию задач на массивы. Исправил.
Только условный оператор.
И остаток от деления 🙂
Ссылка указывает на другой код.
Спасибо, исправил.
Я зачел, но мнене не нравится несколько мест. Например, if(a+b==0) if(x==a) return(cout << a << endl,0);
Я бы решал так
Ещё есть смутное ощущение, что все эти условные операторы можно свернуть в формулу, нет?
Добавил эту же задачу в категорию «Линейные вычисления». Если даже не получится свернуть всё в формулу, всегда можно использовать трюк с вычислением составных логических выражений. Как упражнение вполне подойдет.
Проодобавьте еще один код и категорию.
В формулу свернуть не получилось, добавил новый вариант решения с использованием составных логических выражений.
Ну, тогда хоть пробел перед открывающей скобкой поставьте 🙂