Josephus Problem II

Josephus Problem II

CSES medium

يقف \(n\) طفلًا في دائرة، مرقمين \(1, 2, \ldots, n\). بشكل متكرر، يُتخطى \(k\) طفلًا ويُخرج الطفل التالي من الدائرة.

بأي ترتيب يخرج الأطفال؟

القيود:

• \(1 \le n \le 2 \cdot 10^5\)
• \(0 \le k \le 10^9\)

الإدخال:

• سطر واحد: عددان صحيحان \(n\) و \(k\).

المخرجات:

• \(n\) عددًا صحيحًا — ترتيب الخروج.

مثال:

الإدخال:

7 2

المخرجات:

3 6 2 7 5 1 4

الحل

نحفظ الأطفال الباقين في الدائرة في ordered_set، ونحفظ pos، وهو موقع (يبدأ من \(0\)) الطفل الذي يبدأ منه العد. في البداية pos يساوي \(0\).

في كل جولة نتخطى \(k\) طفلًا، لذلك موقع الطفل الذي يخرج هو \((pos + k) \bmod size\)، حيث \(size\) عدد الأطفال الباقين. الدالة find_by_order تجد هذا الطفل في \(O(\log n)\)، ثم نحذفه.

بعد الحذف ينتقل الطفل الذي كان بعد الطفل المحذوف إلى الموقع نفسه، لذلك تبدأ الجولة التالية العد من pos مرة أخرى. إذا كان الطفل المحذوف هو الأخير في الترتيب، فتبدأ الجولة التالية من الموقع \(0\)؛ وباقي القسمة في الجولة التالية يعالج ذلك.

في المثال (\(k = 2\)): من 1 2 3 4 5 6 7 نحذف الموقع \(2\) (الطفل \(3\))، ثم من 1 2 4 5 6 7 الموقع \(4\) (الطفل \(6\))، ثم من 1 2 4 5 7 الموقع \(6 \bmod 5 = 1\) (الطفل \(2\))، وهكذا.

التعقيد الزمني \(O(n \log n)\).

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

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

    int n;
    long long k;
    cin >> n >> k;

    ordered_set<int> children;
    for (int i = 1; i <= n; i++) {
        children.insert(i);
    }

    int pos = 0;  // index of the child where counting starts
    while (!children.empty()) {
        pos = (pos + k) % children.size();
        auto it = children.find_by_order(pos);
        cout << *it << ' ';
        children.erase(it);
        // the next child moves into index pos
    }
    cout << "\n";
}