[CF459C] Pashmak and Buses

[CF459C] Pashmak and Buses

Description

有 n 个学生用车，有 k 辆车，容量无限，总共 d 天，不希望有任意两个学生 d 天内都是一辆车，问能否合理安排。(n,d le 1000, k le 10^9)

Solution

构造 n 个不同的 d 位 k 进制数

如果 n>pow(k,d) 则无解

否则，将 0,1,2,...,n-1 转 k 进制数即可

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

#define int long long

signed main()
{
    ios::sync_with_stdio(false);

    int n, k, d;
    cin >> n >> k >> d;

    int pw = 1;
    for (int i = 1; i <= d && pw < 1e9; i++)
        pw *= k;
    if (n > pw)
    {
        cout << "-1";
        return 0;
    }

    vector<vector<int>> ans(n, vector<int>(d));
    for (int i = 0; i < n; i++)
    {
        int t = i;
        for (int j = 0; j < d; j++)
        {
            ans[i][j] = t % k + 1;
            t /= k;
        }
    }

    for (int j = 0; j < d; j++)
    {
        for (int i = 0; i < n; i++)
            cout << ans[i][j] << " ";
        cout << endl;
    }
}