Frog

Problem Statement Summary N stones (N 10^5) are arranged in a circle, numbered 1 through N. A frog sits on stone 1. Each jump, the frog advances exactly D stones clockwise. After each jump, the stone the frog lands on...

Updated May 21, 2026

Track IOI

Year 2002

Statement Not mirrored

TeXC++

Problem statement

Problem Statement

No standalone statement file is available for this entry.

Open TeX section

A separate statement file is not available for this entry, so the page focuses on the editorial and implementation.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Problem Statement Summary

$N$ stones ($N \le 10^5$) are arranged in a circle, numbered $1$ through $N$. A frog sits on stone 1. Each jump, the frog advances exactly $D$ stones clockwise. After each jump, the stone the frog lands on is removed. The frog then adjusts to the nearest remaining stone (with specific tie-breaking rules).

Simulate the process and output the order in which stones are removed.

Solution: Fenwick Tree for Order Statistics

Key Idea

Maintain the set of remaining stones in a Fenwick tree, where $\text{bit}[i] = 1$ if stone $i$ is present and $0$ otherwise. This supports:

Finding the $k$-th remaining stone in $O(\log N)$ (binary lifting on the BIT).
Removing a stone in $O(\log N)$.

Circular Jump

If there are $R$ stones remaining and the frog is at rank $r$ (1-indexed among remaining stones), after removing the current stone ($R$ becomes $R - 1$), the stones after the removed one shift down in rank. The frog's new target rank is: \[ r' = \bigl((r - 1) + (D - 1)\bigr) \bmod R' + 1 \qquad\text{where } R' = R - 1. \] This accounts for the fact that the current stone is removed before jumping.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int n;
    vector<int> tree;

    BIT(int n) : n(n), tree(n + 1, 0) {}

    void update(int i, int val) {
        for (; i <= n; i += i & (-i))
            tree[i] += val;
    }

    int query(int i) {
        int s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }

    // Find the k-th element (1-indexed) via binary lifting.
    int kth(int k) {
        int pos = 0;
        for (int bm = 1 << __lg(n); bm > 0; bm >>= 1) {
            int next = pos + bm;
            if (next <= n && tree[next] < k) {
                k -= tree[next];
                pos = next;
            }
        }
        return pos + 1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, D;
    cin >> N >> D;

    BIT bit(N);
    for (int i = 1; i <= N; i++)
        bit.update(i, 1);

    int remaining = N;
    int curRank = 1; // rank of stone 1 among remaining stones

    for (int step = 0; step < N; step++) {
        int stone = bit.kth(curRank);
        cout << stone << "\n";

        bit.update(stone, -1);
        remaining--;

        if (remaining == 0) break;

        // After removing the stone at curRank, compute new rank.
        // Ranks >= curRank shift down by 1, so the "next" stone
        // is now at curRank (if it exists). We advance D-1 more.
        curRank = ((curRank - 1 + D - 1) % remaining) + 1;
    }

    return 0;
}

Complexity Analysis

Time: $O(N \log N)$. Each of the $N$ steps performs one $k$-th element query ($O(\log N)$) and one update ($O(\log N)$).
Space: $O(N)$.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 2002 - Frog
// N stones in a circle, frog on stone 1. Frog jumps D positions clockwise,
// removing the departure stone after each jump.
// Uses a Fenwick tree for O(log N) k-th element queries and updates.
// Complexity: O(N log N) time, O(N) space.

#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int n;
    vector<int> tree;

    BIT(int n) : n(n), tree(n + 1, 0) {}

    void update(int i, int val) {
        for (; i <= n; i += i & (-i))
            tree[i] += val;
    }

    int query(int i) {
        int s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }

    // Find the k-th element (1-indexed) using binary lifting on the BIT
    int kth(int k) {
        int pos = 0;
        int bitMask = 1;
        while (bitMask <= n) bitMask <<= 1;
        bitMask >>= 1;

        for (; bitMask > 0; bitMask >>= 1) {
            int next = pos + bitMask;
            if (next <= n && tree[next] < k) {
                k -= tree[next];
                pos = next;
            }
        }
        return pos + 1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, D;
    cin >> N >> D;

    BIT bit(N);
    for (int i = 1; i <= N; i++) {
        bit.update(i, 1);
    }

    int remaining = N;
    int currentRank = 1; // rank of current stone among remaining stones

    vector<int> order;
    order.reserve(N);

    while (remaining > 0) {
        int stone = bit.kth(currentRank);
        order.push_back(stone);

        // Remove current stone
        bit.update(stone, -1);
        remaining--;

        if (remaining == 0) break;

        // After removing the stone at currentRank, the stone that was at
        // currentRank+1 shifts down to currentRank. The frog needs to advance
        // D-1 more positions from there (since the departure stone is gone).
        // New rank (0-indexed): (currentRank - 1 + D - 1) % remaining
        currentRank = ((currentRank - 1 + D - 1) % remaining + remaining) % remaining + 1;
    }

    for (int x : order) {
        cout << x << "\n";
    }

    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/2002/frog/solution.texC++ implementationcompetitive_programming/ioi/2002/frog/solution.cpp