公交车

admin管理员组

文章数量:1122888

公交车

1009: 公交车
时间限制: 1 Sec 内存限制: 128 MB
题目描述
最近pashmak被运输公司录用了，公司有k辆车，现在有个学校n个学生要用车，学校要将这些学生送到d个不同地方，每个地方呆1天，总共要d天。每天公司要提供车运输这些学生，pashmak就要安排方案。学校为了防止这些学生太过亲密，不希望有任意两个学生d天内都是同一辆车。问pashmak能否合理安排。

注意，我们假设每辆车的容量是无限的。

输入
输入3个数,n, k, d (1 <= n, d <= 1000; 1 <= k <= 10 ^9)

输出
如果可以输出”yes”

然后输出n行，每行d个数，每行输出每个人的安排车辆(车辆编号是从1到k)

方案有多种，这里要求输出字典序最小的一种

不可以输出”no”

样例输入
3 2 2
样例输出
yes
1 1
1 2
2 1
提示
输入

3 2 1

输出

no

来源
cf459C

这道题可以简化为k^d与n的关系
如果小于，那么输出no
不然就输出yes
输出方案很简单
先将一个a数组全赋值为1
然后从尾部不断加一
维护k进制即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,k,d;
int a[1005];
int main()
{scanf("%d%d%d",&n,&k,&d);ll kd=1;for (int i=1;i<=d;i++){kd=kd*k;if (kd>=n) break;}if (kd<n){printf("no\n");return 0;}printf("yes\n");for (int j=1;j<=d;j++)a[j]=1;for (int i=1;i<=n;i++){for (int j=1;j<d;j++)printf("%d ",a[j]);printf("%d\n",a[d]);int x=d;a[x]++;while (a[x]>k){a[x--]=1;a[x]++;}}return 0;
}

本文标签： 公交车