Условие задачи:
Иван Петрович хранит свои важные документы в сейфе с механическим кодовым замком, который представляет собой поворачивающийся диск с нанесенными на него делениями, каждому из которых назначен порядковый номер, начиная с единицы. Все деления, кроме первого, имеют номер на единицу больший, чем у предыдущего при движении по часовой стрелке. Рядом с диском на сейфе нанесена стрелка, которая указывает на некоторое деление и не сдвигается при повороте диска. Изначально стрелка указывает на первое деление. При наборе кода Иван Петрович несколько раз повторяет комбинацию из двух поворотов: сначала поворачивает диск на A делений против часовой стрелки (стрелка на сейфе «перемещается» относительно диска по часовой стрелке), затем на B делений в обратную сторону. Определите, сколько раз повторяется эта комбинация поворотов, если стрелка на сейфе указывала на последнее N-е деление, то есть «проходила» мимо него или меняла свое направление на нем, K раз.
Примеры тестов:
1 3 5 0
ответ: 0
1 2 4 2
ответ: 2
2 3 3 1
ответ: -1
Если кто-то знает как это можно решить максимально рационально, прошу расскажите способ решения(алгоритм) не прошу код!
mayton2019, Alexandroppolus, -1, очевидно, означает, что ответа на задачу нет. Например, даже один повтор A-B два раза пересечет искомую точку, а введено K=1.
Но без полного условия задачи с форматом ввода не все понятно.
Какая-то запутанная формулировка задачи, да и тесты представлены последовательностью каких-то чисел - без пояснений: что хочешь, то и думай...
если стрелка на сейфе указывала на последнее N-е деление, то есть «проходила» мимо него или меняла свое направление на нем, K раз
Взрыв мозга, если честно.
Если речь идет о том, что из начального положения комбинацией "влево-вправо" поочереди выставляются указанные в виде последовательности значения, то при некоторых ограничениях, действительно: в первом варианте 0 проходов, во втором 2 прохода, однако, в третьем варианте 1 проход по-любому, потому что начальное положение всегда 0 по условиям задачи и первый же поворот влево всегда будет увеличивать значение, то есть пройдет от 0 к 2 (и далее, чтобы вернуться именно на 2-ку) через 1 (единицу). Просто без вариантов.
Итак, начальное положение 0, первый поворот диска (влево) будет увеличивать значения под указателем от 0 к 9 (вот ОНО - важное ограничение), а второй поворот (вправо) - обратно. Тогда в каждом из трех вариантов произойдет следующее:
Смещение от 0 к 1 комбинацией "круть-верть": сначала ставим рандомное число больше 1, но меньше или равно 9, затем скручиваем до 1. Затем, смещение от 1 до 3 аналогичным способом. Далее, смещение от 3 до 5. После чего, смещение от 5 до 0, где "обратный" поворот будет длиннее. В итоге, диск вернулся в начальное положение не проходя через него, а значит и проходов нету ни одного.
Смещение от 0 к 1 выше уже описано. Затем, смещение от 1 до 2 аналогичным способом (заметь те, мы прошли 2-ку). Далее, смещение от 2 до 4 (здесь происходит "как бы" разворот на 2-ке, ведь предыдущее движение диска было вправо, а предстоит вращать его влево, чтобы выкрутить за пределы 4-ки). После чего, смещение от 4 до 2, то есть снова "обратный" поворот будет длиннее. В итоге, диск остановился 2-кой под указателем, совершив один проход и один "как бы" разворот, то есть 2 события.
Смещение от 0 к 2 по аналогии с предыдущими пунктами (вот и прошли через 1-ку). Затем, смещение от 2 до 3. Далее, смещение из 3 в 3 - "круть-верть". После чего, смещение от 3 до 1, то есть снова "обратный" поворот будет длиннее. В итоге, диск остановился 1-кой под указателем, совершив всего 1 проход через это деление.
В коде, полагаю, было бы проще всего запомнить ВСЕ "пройденные" в сторону увеличения числа в виде последовательности, добавляя к ней каждую новую цепочку вместе с той цифрой, на которой остановились на данном шаге, а потом пробегал бы с последним числом по всей последовательности на предмет совпадений, начиная со второго по счету элемента, чтобы отбросить вариант с возвратом в исходное положение. Поправьте, если не прав.
п.с. смею обратить общее внимание на тот факт, что в задаче не ограничивается количество делений, на которое можно провернуть диск за один раз и количество оборотов тоже не фиксировано - "вращайся пока не надоест". Поэтому, если диск ничем не сдерживается, то задача имеет бесконечное количество решений. Крутанул влево и завращалось колесо, схватил его и крутанул обратно - и снова вращается... Прошу прощения за придирки.
Если код не важен, а нужно именно решение, то вот на привычном для меня C#
Идея в том, что мы просто симулируем поворот замка и смотрим что происходит.
int A = 2;
int B = 3;
int N = 3;
int K = 1;
int maxPos = N;
int currentPos = 1;
int countReachK = 0;
int countPairs = 0;
while (countReachK < K)
{
//Если надо приводим к нулю чтобы не считать пересечение два раза.
if ((currentPos == maxPos) && (A>0))
currentPos = 0;
currentPos += A;
//Проверка на пересечение или остановку.
while (currentPos >= maxPos)
{
currentPos -= maxPos;
countReachK++;
}
//Если надо приводим к максимуму чтобы не считать пересечение два раза.
if ((currentPos == 0) && (B>0))
currentPos = maxPos;
currentPos -= B;
//Проверка на пересечение или остановку.
while (currentPos <=0)
{
currentPos += maxPos;
countReachK++;
}
countPairs++;
}
if (countReachK != K)
countPairs = -1;
// countPairs и есть искомый результат.
Простой
