codingame clash of code: josephus problem
На codingame в разделе clash of code попалась задача (потом в чате более умные люди подсказали, что это модифицированная задача Иосифа Флавия
)
По кругу стоит N человек. В руках у первого человека меч, у остальных людей меча нет. Человек с мечом убивает следующего за ним (то есть, при достаточно большом числе народу в начале - второго) и передает меч следующему человеку за убитым (то есть, в примере, третьему). Далее все повторяется. В конце-концов, останется один человек. Вопрос - какая позиция этого выжившего, то есть, иными словами, где нужно встать, если предложат поиграть в такую игру.
Эта задача использовалась на clash of code, то есть надо было в условиях ограниченного времени соревноваться с другими программистами и быстренько сделать решение, которое пройдет все тесты - и сделать его раньше остальных.
Чем мне нравятся такие задания - на них можно отдохнуть от работы. Достаточно слепить говнокод, неважно какой, лишь бы работал и проходил тесты и не думать о его поддерживаемости, сопровождаемости, оптимальности, надежности и прочем.
Я сделал совершенно незамысловатое решение (не глядя в ссылку на вики, это я потом ее нагуглил) - завел массив, помечал там убитых воинов и тупо бежал по нему, симулируя все это.
В начальных условиях обещали, что количество воинов не больше 100000, поэтому я решил, что это не суперрасход памяти.
Вот моё незамысловатое решение:
В итоге я занял второе место, что, конечно, аргумент в силу говнокода! Первое место заняло решение на питоне, оно вроде попроще:
Ссылка на результаты - тут https://www.codingame.com/clashofcode/clash/report/19029482cba62c79c07c0140c40fbbbab876b0e