codeforces ラウンド #261(div2) C の問題解決 report_html/css_WEB-ITnose

C. パシュマックとバス

テストごとの制限時間

テストごとのメモリ制限

入力

出力

最近パシュマク運送会社に就職しました。同社は k 台のバスを所有しており、生徒がいる学校と契約を結んでいます。学校は、生徒たちを d 日間 (毎日 1 か所で) さまざまな場所に連れて行くことを計画しました。同社は毎日、旅行に必要なすべてのバスを提供します。パシュマクは生徒をバスに手配しなければなりません。彼は、2 人の生徒が親しい友達にならないように生徒を配置したいと考えています。彼のばかばかしいアイデアでは、2 人の生徒が同じバスに一日中乗っている場合に限り、親友になれるというものです。

パシュマクの奇妙なアイデアを手伝ってください。各バスの容量は無制限であると仮定します。

入力

入力の最初の行には、スペースで区切られた 3 つの整数 n,?k,?d(1?≤?n,?d?≤?1000; 1? ≤?k?≤?109).

出力

有効な配置がない場合は、単に -1 を出力します。それ以外の場合は、d 行を出力し、各行に n 個の整数を出力します。 i 行目の j 番目の整数は、j 番目の生徒が i 日目にどのバスに乗らなければならないかを示します。バスには 1 から k までの番号が付いていると想定できます。

サンプル テスト

入力

3 2 2

出力

1 1 2 1 2 1 

入力

3 2 1

出力

-1

注意

2 人の生徒が毎日バスに乗り合わせた場合にのみ親しい友達になることに注意してください。ただし、共有するバスは日によって異なります。

题目大意：

n个人、k个公交、出去游玩d天、每天每个人可以选择いずれか一辆公交乘坐、最后你求每天每每个每人人选择的的公交并要求要求要求的的的的天、不不能至少有有有两个一直一直在同公交公交。

さらに要約すると、各人の個人空間共有のシーケンスは、最大で d ビット k 個の数になります。割り当て可能なシーケンスの数は k^d です。 n

最初の人のシーケンス: 0, 0, 0, 0

第二人物の配列： 0, 0, 0, 1

第三人物の配列： 0, 0, 0, 2

第四人物の配列： 0, 0, 1, 0

第五个人のシーケンス： 0, 0, 1, 1

第八人物の配列： 0, 0, 2, 1

代コード：

#include <cstdio>#include <iostream>#define LL long long#define N_max 1234using namespace std;int d, n, k;int f[N_max][N_max];void init() {	cin >> n >> k >> d;}bool check() {	LL cnt=1;	for (int i = 1; i <= d; i++) {		cnt *= k;		if (n <= cnt)			return true;	}	return false;}void solve() {	if (check()) {		for (int i = 2; i <= n; i++) {			int tmp=0;			f[i][1] = 1;			for (int j = 1; j <= d; j++) {				f[i][j] = f[i-1][j] + f[i][j] + tmp;				if (f[i][j] >= k) {					f[i][j] -= k;					tmp = 1;				}				else					tmp = 0;			}		}		for (int j = 1; j <= d; j++) {			for (int i = 1; i <= n; i++)				printf("%d ", f[i][j]+1);			printf("\n");		}	}	else		printf("-1\n");}int main() {	init();	solve();}