|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 01-1. Задача Иосифа Флавия
(Разбор)
Рассмотрим два способа решения задачи. Давайте повторим в памяти компьютера события, происходившие в легенде.
Способ первый. Будем хранить в массиве имена (то есть номера) всех живых на текущий момент воинов. Причем удобно, чтобы номера людей были записаны в элементах массива с 0 по N-1 (чуть позже станет ясно, почему так). Когда воин будет умирать, будем удалять его из массива, и тех, кто стоял за ним, "сдвигать" на один элемент влево.
Заметим, что если мы уже убили L человек, то в живых осталось M=N-L. Пусть мы только что (на L-ом шаге) убили человека, который был записан в нашем массиве в элементе с номером j (и сдвинули людей, которые были записаны в массиве в элементах с j+1 по M на один элемент влево). Тогда следующим нужно убивать человека, который записан в этом массиве в элементе с номером (j+k-1) mod M. (Запись a mod b обозначает остаток от деления числа a на b).
Взятие остатка от деления на M нужно затем, чтобы как бы "замкнуть" наш массив в круг (то есть как только мы достигаем конца массива, мы оказываемся в его начале). Вот тут как раз и важно, что люди в массиве у нас расположены начиная с 0-го элемента - операция взятия остатка от деления на M может дать в качестве результата числа от 0 до M-1. Конечно, можно изначально расположить людей и начиная с 1-го элемента, однако тогда в этом месте формула окажется несколько сложнее.
Способ второй. Заведем массив, где будем помечать мертвых воинов (т.е. в i-м элементе хранится, жив воин i, или уже нет). Пусть у нас на текущем шаге M живых людей и на предыдущем шаге умер воин j. Чтобы найти следующего, будем бежать по массиву, отсчитывая живых и пропуская мертвых. Тот человек, на котором мы насчитаем k mod M и должен умереть следующим. Почему k mod M, а не k? Считалочка сначала проидет k div M полных кругов, а затем остановится на человеке k - (k div M) * M = k mod M. Если k mod M оказалось равно 0, то нужно найти ближайшего живого, считая назад, либо (что то же самое) M-го, считая вперед. Через N - 1 шаг останется один человек.