Let’s Play the Hat?

Created by LXC on Wed Apr 10 18:41:28 2024

https://codeforces.com/problemset/problem/1619/F

ranting: 2000

tag: brute force, constructive algorithms, greedy, math

problem

The Hat是一个快速解释/猜测单词的游戏(类似于Alias)。在这道题中，我们所讨论的是一种游戏变体，即玩家坐在桌旁，每个人都单独玩游戏。

有 $n$ 个人聚集在一个有 $m$ 张桌子( $n \ge m \times 2$ )的房间里。他们想玩 $k$ 次 The Hat。$k$ 次游戏将在这些桌子上进行，每个人都会玩 $k$ 次游戏。

这些玩家被分配到这些桌子上。每个玩家可以在不同的桌子上玩，但每局游戏每个玩家只能在一张桌子上玩。

玩家们希望拥有“公平”的游戏顺序。出于这个原因，他们正在寻找一个方案，要求如下:

• 在任意一场游戏中，所有桌子都有 $\lfloor \dfrac{n}{m} \rfloor$ 或 $\lceil \dfrac{n}{m} \rceil$ 个玩家。不同的桌子有不同数量的玩家，这些玩家可以玩不同的游戏。
• 每个玩家都有一个值 $b_i$，它表示第 $i$ 个玩家和 $\lceil \dfrac{n}{m} \rceil$ 个玩家在一张桌子上玩游戏的次数。任意两个玩家的 $b_i$ 值相差不会超过 $1$。换句话说，对于任意两个玩家 $i,j$，满足 $|b_i-b_j| \leq 1$。

我们称有 $\lfloor \dfrac{n}{m} \rfloor$ 个玩家的桌子为“小桌子”，称有 $\lceil \dfrac{n}{m} \rceil$ 个玩家的桌子为“大桌子”。

例如，$n=5,m=2,k=2$，那么根据第一项要求，每张桌子上应该有 $2$ 或 $3$ 名玩家。考虑这些游戏顺序：

• 第一局：玩家 $1,2,3$ 在第一张桌子上玩，玩家 $4,5$ 在第二张桌子上玩。第二局：玩家 $5,1$ 在第一张桌子上玩，玩家 $2,3,4$ 在第二张桌子上玩。这个顺序是不“公平”的，因为 $b_2=2$ (第二名玩家在大桌子上玩了两次)，$b_5=0$ (第五名玩家没有在大桌子上玩过游戏)。
• 第一局：玩家 $1,2,3$ 在第一张桌子上玩，玩家 $4,5$ 在第二张桌子上玩。第二局：玩家 $4,5,2$ 在第一张桌子上玩，玩家 $1,3$ 在第二张桌子。这是一种“公平”的顺序：$b=[1,2,1,1,1]$ (任意两个值的差都不超过 $1$)。

为 $n$ 个玩家找到所有“公平”的顺序，如果他们玩 $k$ 次游戏，在 $m$ 张桌子上。

输入格式

第一行一个整数 $t(1 \leq t \leq 10^4)$，表示数据组数。

接下来 $t$ 行，每行三个整数 $n,m,k(2 \leq n \leq 2 \times 10^5,1 \leq m \leq \lfloor \dfrac{n}{2} \rfloor,1 \leq k \leq 10^5)$，分别表示玩家个数，桌子个数以及游戏次数。

保证所有测试用例的 $n \times k$ 之和不超过 $2 \times 10^5$。

输出格式

对于每组数据，输出 $k$ 块矩阵，每块矩阵有 $m$ 行。每一块矩阵表示一次游戏，共有 $m$ 张桌子，用一行表示一张桌子，每行先输出这张桌子的玩家数，再输出这些玩家。每组数据

如果有多个“公平”的顺序，那么输出任意一个。保证至少有一个有效的解。

solution

有$n \bmod m$个大桌子，大桌子每桌人数为$\lceil \dfrac{n}{m} \rceil$，剩余的都是小桌子，每桌人数为$\lfloor \dfrac{n}{m} \rfloor$。

分配到大桌的人，下一轮要尽量分配到小桌子上去。

大桌总人数为有$(n \bmod m)\lceil \dfrac{n}{m} \rceil$，我们可以在其中轮转地选取$n - (n \bmod m)\lceil \dfrac{n}{m} \rceil$分配到小桌子上。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    ll n, m, k;
    cin >> n >> m >> k;
    // cout << n << " " << m << " " << k << endl;
    int sz1 = n%m*(n/m+1), sz2 = (m-n%m)*(n/m);
    vector<int> a(sz1), b(sz2);
    iota(a.begin(), a.end(), 0);
    iota(b.begin(), b.end(), sz1);
    // cout << sz1 << " " << sz2 << "\n";
    // cout << a << " " << b << endl;
    auto pr = [&]() {
        for (int i=0; i<sz1; i++) {
            if (i%(n/m+1) == 0) {
                cout << n/m+1;
            }
            cout << " " << a[i]+1;
            if (i%(n/m+1) == n/m) {
                cout << "\n";
            }
        }
        for (int i=0; i<sz2; i++) {
            if (i%(n/m) == 0) {
                cout << n/m;
            }
            cout << " " << b[i]+1;
            if (i%(n/m) == n/m-1) {
                cout << "\n";
            }
        }
    };
    pr();
    ll p = 0;
    while (--k) {
        if (a.size())
        for (int i=0; i<sz2; i++) {
            swap(a[(p+i)%sz1], b[i]);
        }
        p += sz2;
        pr();
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}