Algoogle

Algorithm for Programming Contest

Codeforces 459C Pashmak and Buses

Category: Codeforces Tag: math

Pashmak and Buses

問題概要


n人をk台のバスに割り当てるのをd日分考えるとき, どの2人もd日間ずっと一緒に割り当てられることがないように割り当てろ.
無理なら−1

解法


n人にそれぞれ0からn-1の番号を割り当てる.
またバスに割り当てる方法はある.
つまりn-1までがk進法でd桁以内で全て区別可能ならそのような割り当てが存在して, それはk進数で表現した番号になる.
表現出来ない場合はとなるとき.
両辺logを取れば

コード


(459C.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

int n, k, d, kad[1024][1024];

void solve()
{

        if(d*log(k) < log(n-1)+1e-8) {
                puts("-1");
                return;
        }

        for (int i = 0; i < n; i++) {
                int res = i;
                for (int j = 0; j < d; j++) {
                        kad[i][j] = res%k;
                        res /= k;
                }
        }
        for (int j = 0; j < d; j++) {
                for (int i = 0; i < n; i++) {
                        printf("%d ", kad[i][j]+1);
                }
                puts("");
        }
}

void input()
{
        scanf("%d%d%d", &n, &k, &d);
}

int main()
{
        input();
        solve();
        return 0;
}

Comments