10774. Повторяющийся Иосиф

По кругу стоят n людей, занумерованных от 1 до n. Начиная отсчет с первого и двигаясь по кругу, будем казнить каждого второго человека до тех пор пока не останется один. Пусть этот выживший имеет номер x. Расставим по кругу x людей и повторим процедуру, после которой выживет человек с номером y. И так далее до тех пор, пока номер выжившего не станет равным первоначальному количеству людей в текущем раунде.

Например, при n = 5 последовательно будут казнены 2, 4, 1, 5. Выживет номер 3. Он не равен 5 (количеству людей в раунде), поэтому следует повторить процедуру. Для n = 3 казнены будут 2, 1. Выживет человек с номером 3, равным n. Процедура заканчивается.

Вход. Входные данные состоят из нескольких тестов. Каждый тест в одной строке содержит одно число n (0 < n £ 30000)

Выход. Для каждого теста вывести в отдельной строке его номер как указано в примере, количество повторений процедуры казни после первой итерации и номер выжившего в конце процедуры.

Пример входа

2

13

23403

Пример выхода

Case 1: 2 7

Case 2: 8 1023

РЕШЕНИЕ

рекуррентное соотношение

Анализ алгоритма

Пусть n – количество людей в круге. Обозначим через f(n) номер последнего уцелевшего. Положим f(1) = 1.

Если n = 2 * k – четное, то после прохода первого круга будут удалены люди с четными номерами: 2, 4, ..., 2 * k. Останутся люди с нечетными номерами, а отсчет продолжаем с номера 1. Это все равно, что если бы у нас было k людей, а номер каждого удвоился и уменьшился на 1. То есть получим соотношение f(2 * k) = 2 * f(k) – 1.

Если n = 2 * k + 1 – нечетное, то после прохода первого круга будут удалены люди с четными номерами 2, 4, ..., 2 * k, а жертва с номером 1 уничтожается сразу же после жертвы с номером 2 * k. Остается k людей с номерами 3, 5, 7, …, 2 * k + 1. Это все равно, что люди занумерованы от 1 до k, только номер каждого удвоился и увеличился на 1. Получаем соотношение: f(2 * k + 1) = 2 * f(k) + 1.

Объединяя полученные соотношения, получим рекуррентность:

f(1) = 1

f(2 * k) = 2 * f(k) – 1, k ³ 1

f(2 * k + 1) = 2 * f(k) + 1, k ³ 1

Теорема. Значение f(n) получается путем циклического сдвига двоичного представления n влево на один бит. Например, f(100) = f(1100100₂) = 1001001₂ = 73.

Многократное применение функции f порождает последовательность убывающих значений, достигающих неподвижной точки n такой что f(n) = n. Число n будет состоять из одних единиц со значением 2^v(n) – 1, где v(n) – количество единиц в бинарном представлении числа n.

Пример

Рассмотрим входные данные для второго теста. При n = 13 последовательно будут казнены 2, 4, 6, 8, 10, 12, 1, 5, 9, 13, 7, 3. Выживет номер 11. Он не равен 13 (количеству людей в раунде), поэтому следует повторить процедуру. Для n = 11 казнены будут 2, 4, 6, 8, 10, 1, 5, 9, 3, 11. Выживет человек с номером 7, равным n. При n = 7 выживет номер 7. После первой итерации проведено еще 2 повторения процедуры казни.

Реализация алгоритма

Функция last по первоначальному количеству людей n в круге возвращает номер уцелевшего согласно рекуррентному соотношению.

int last(int n)

{

if (n == 1) return 1;

if (n%2 == 0) return 2 * last(n / 2) - 1;

else return 2 * last((n - 1) / 2) + 1;

}

Переменная r содержит количество повторений процедуры казни (изначально r = 0). По заданному входному n ищем номер уцелевшего k. Если он не равен n, то повторяем в цикле процедуру казни.

scanf("%d",&tests);

for(i = 1; i <= tests; i++)

{

scanf("%d",&n); r = 0;

while ((k = last(n)) != n) r++, n = k;

printf("Case %d: %d %d\n",i,r,n);

}