UniLecs #Task. Считалочка
Задача: команда программистов не выполнила проект в срок! Теперь они не могут решить, кто пойдет к заказчику за новым дедлайном. Не придумали ничего лучше, как определить с помощью детской считалочки.
Определите кто из программистов пойдет к заказчику?
Входные данные:
- N — количество программистов в команде;
- Str — массив слов (считалочка);
- K — номер программиста, с которого начнется считалочка.
1 <= K <= N; N <= Str.Length <= 10⁵.
Примеры: N = 4; K = 2;
Str = [ “Вышел”, “месяц”, “из”, “тумана”,
“Вынул”, “ножик”, “из”, “кармана”,
“Буду”, “резать”, “буду”, “бить”,
“Всё”, “равно”, “тебе”, “водить”]
Answer: 1
Разбор
Обозначим Count — количество слов в считалочке.
Сначала решим задачу без сдвига, т.е. для k = 1. Заметим, что (Count%N) (% — операция остаток от деления) дает хорошие результаты, если считалочкой выбирается любой, кроме N-го участника. Если же выбор падает на него, то остаток от деления равен 0. Для этого изменим опрецию:
результат определяется формулой (Count — 1) % N + 1.
Теперь сдвиг — это по сути то же вычисление, только уже изначально было сделано еще k-1 ходов.
Поэтому прибавляя к C еще k-1 шагов и получаем финальную формулу (Count + k — 2) % N+1
Реализация
https://gist.github.com/unilecs/9ae436042a14ca3dac2173e84fd95c05
