Хакерранк: спасти пленника - Математика
0 голосов
/ 04 мая

У меня проблема в модуле r арифмети c.

Упрощенная формулировка проблемы:

n: целое число r, число r заключенных

m: целое число r, число r конфет

s: intege r, chai r numbe r, чтобы начать раздавать сладости от

Заключенные сидят вокруг стола Cirla ​​r на последовательно пронумерованных стульях (начинается нумерация) из 1).

Найдите призона r, который получает последний сладкий.

Я могу придумать множество возможных решений, но решил попробовать одно line r:

m % n + s - 1

Мои рассуждения:

  1. Раздайте m конфет равномерно n заключенным. Остаток r будет частью последнего раунда распределения.

  2. Добавьте начальное смещение s для достижения последнего места.

  3. Мне пришлось вычесть 1 из результата, чтобы пройти несколько тестов (я не знаю причину) .

Howeve r, формула не проходит для r других r тестовых случаев.

Что не так в логи c? Как мне исправить формулу?

Ответы [ 2 ]

1 голос
/ 04 мая

Причина, по которой вы должны вычесть $1$, состоит в том, чтобы избежать так называемого fencepost erro r o r "off-by-one" erro r. Предположим, что есть только $1$ сладкое. Затем, начиная с места $s$, вы знаете последнюю (и единственную) сладкую волю go к пирсону r на месте $s$. Но $m\%n+s$ дает результат $s+1$. Вам необходимо настроить $-1$ в $m\%n+s-1$ для учета r того факта, что сладкий $1$ дается призону r в сетате $s$, а не в сиденье $s+1$.

* * * * * * * * * * r, что вы должны помнить r, - то, что $m\%n$ дает результат между $0$ и $n-1$, поэтому $m\%n+s-1$ будет между $s-1$ и $n+s-2$. Но номера сидений go от $1$ до $n$. Вы можете настроить r формулу на $(m+s-1)\%n$, что является правильным в большинстве случаев, но дает неправильный ответ r $0$, когда $m+s-1$ кратно $n$. Я оставлю вас подумать о том, как еще r настроить это выражение, чтобы получить ответ r, который является правильным во всех случаях.

0 голосов
/ 04 мая

У меня (m + s - 1) % n ? (m + s - 1) % n : n; по объяснениям Джона и Гандала.

Howeve r, я смог сократить его до r, используя концепцию Fencepost Erro r представил мне Гандал.

  1. Теперь это очевидно:

    (m + s - 1) % n

  2. % выходы в диапазоне:

    [0, n-1]

  3. Итак, преобразуйте все количества в операнде относительно подсчета от нуля :

    ((m - 1) + (s - 1)) % n

  4. Затем преобразовать этот ответ r относительно , считая от одного :

    (((m - 1) + (s - 1)) % n) + 1

Окончательное решение прошло все тестовые случаи.

Он по-прежнему короткий и однолинейный r:

(m + s - 2) % n + 1

Добро пожаловать на сайт Математика, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...