Джозефус для больших русских (Facebook Hacker Cup) - PullRequest
Новая
       23

Джозефус для больших русских (Facebook Hacker Cup)

11 голосов
/ 30 января 2011

На прошлой неделе я участвовал в 1-м раунде кубка Facebook Hacker.

Одной из проблем была в основном проблема Иосифа

Я изучал проблему Иосифараньше, как дискретная математическая задача, поэтому я в основном понимаю, как получить повторение: 

f(n,k) = (f(n-1,k) + k) mod n, with f(1,k) = 0

Но это не сработало в Facebook Hacker Cup, потому что максимальное значение n было 10 ^ 12.Значение mak k было 10 ^ 4.

В Википедии упоминается подход, когда k мало, а n велико.В основном удаляют людей из одного раунда, а затем перенумеровывают.Но он не очень описан, и я не понимаю, почему работает перенумерация.

Я посмотрел пример рабочего исходного кода для решения, но я все еще не понимаю эту последнюю часть. 

long long joseph (long long n,long long k) {
    if (n==1LL) return 0LL;
    if (k==1LL) return n-1LL;
    if (k>n) return (joseph(n-1LL,k)+k)%n;
    long long cnt=n/k;
    long long res=joseph(n-cnt,k);
    res-=n%k;
    if (res<0LL) res+=n;
    else res+=res/(k-1LL);
    return res;
}

Часть, которую я действительно не понимаю, начинается с res-=n%k (и последующих строк).Как вы узнали, что так можно скорректировать результат?

Может ли кто-нибудь показать причины, по которым это получается?Или ссылка, которая выводит это?(Я не нашел никакой информации на форумах UVA или topcoder)

1 Ответ

4 голосов
/ 31 января 2011

Правильно, я думаю, что взломал это.

Давайте посмотрим, как идут итерации с n = 10, k = 3: 

0 1 2 3 4 5 6 7 8 9    n=10,k=3
1 2   3 4   5 6   0    n=7,k=3

Наблюдаем, как элементы второй итерациисопоставьте с первым: они транспонированы на n%k, потому что круг оборачивается.Вот почему мы исправляем результат, вычитая 10%3.Числа во втором ряду появляются в группах k-1, следовательно, поправка на res/(k-1).

В другом случае происходит дальнейшее повторение по итерациям 

0 1 2 3 4     n=5,k=3
2 3   0 1     n=4,k=3

Теперь j (4, 3) возвращает 0, который с поправкой на 5%3 оказывается -2.Это происходит только в том случае, если результат второй строки находится в последней группе, и в этом случае добавление n к результату даст нам наш исходный индекс.

...