Eci-peci-pec

Na početku igre “Eci-peci-pec” \(n\) igrača sedi u krugu, pri čemu se može smatrati da su igrači numerisani brojevima od 1 do \(n\) u smeru kretanja kazaljke na satu. Nakon toga brojanje kreće od igrača sa rednim brojem 1 i odbrojava se \(k\) igrača u smeru kazaljke na satu. Igrač na kom se završi brojanje izlazi iz kruga, a brojanje ponovo počinje od igrača koji je bio sledeći u smeru kazaljke na satu. Pobednik je igrač koji poslednji ostane u krugu.

Napisati program koji za dato \(n\) i \(k\) proverava koji igrač će pobediti u igri.

Opis ulaza

Sa standardnog ulaza se učitavaju prirodni brojevi \(n\) (\(1 \leq n \leq 10^5\)) i \(k\) (\(1 \leq k \leq 10^6\)).

Opis izlaza

Na standardni izlaz ispisati redni broj igrača koji je pobedio u igri.

Primer

Ulaz

5 2

Izlaz

3

Objašnjenje

• Brojanje kreće od igrača broj 1 i završava se na igraču broj 2 koji izlazi iz kruga.
• Brojanje sada kreće od igrača broj 3 i završava se na igraču broj 4 koji izlazi iz kruga.
• Brojanje sada kreće od igrača broj 5 i završava se na igraču broj 1 koji izlazi iz kruga.
• Brojanje sada kreće od igrača broj 3 i završava se na igraču broj 5 koji izlazi iz kruga.
• U krugu ostaje samo igrač broj 3.

Rešenje

#include <iostream>

using namespace std;

/* n\k 1 2 3 4 ...
 *   1 0 0 0 0
 *   2 1 0 1 0
 *   3 2 2 1 1
 *   4 3 0 0 1
 *   ...
 */

int josephus(int n, int k) 
{
    if (n == 1) return 0;
    return (josephus(n - 1, k) + k) % n;
}

int josephus_iter(int n, int k)
{
    int res = 0;
    for (int N = 1; N <= n; N++) {
        res = (res + k) % N;
    }
    return res;
}

int main() 
{
    int n, k; cin >> n >> k;

    cout << josephus_iter(n, k) + 1 << endl;

    return 0;
}

#include <iostream>

using namespace std;

/* n\k 1 2 3 4 ...
 *   1 0 0 0 0
 *   2 1 0 1 0
 *   3 2 2 1 1
 *   4 3 0 0 1
 *   ...
 */

int josephus(int n, int k) 
{
    if (n == 1) return 0;
    return (josephus(n - 1, k) + k) % n;
}

int main() 
{
    int n, k; cin >> n >> k;

    cout << josephus(n, k) + 1 << endl;

    return 0;
}