「CF509B」Painting Pebbles

2015年1月31日3,1410

There are n piles of pebbles on the table, the i-th pile contains a_i pebbles. Your task is to paint each pebble using one of the k given colors so that for each color c and any two piles i and j the difference between the number of pebbles of color c in pile i and number of pebbles of color c in pile j is at most one.

In other words, let’s say that b_i, c is the number of pebbles of color c in the i-th pile. Then for any 1 ≤ c ≤ k, 1 ≤ i, j ≤ n the following condition must be satisfied |b_i, c - b_j, c| ≤ 1. It isn’t necessary to use all k colors: if color c hasn’t been used in pile i, then b_i, c is considered to be zero.

Input

The first line of the input contains positive integers n and k (1 ≤ n, k ≤ 100), separated by a space — the number of piles and the number of colors respectively.

The second line contains n positive integers a₁, a₂, …, a_n (1 ≤ a_i ≤ 100) denoting number of pebbles in each of the piles.

Output

If there is no way to paint the pebbles satisfying the given condition, output “NO” (without quotes) .

Otherwise in the first line output “YES” (without quotes). Then n lines should follow, the i-th of them should containa_i space-separated integers. j-th (1 ≤ j ≤ a_i) of these integers should be equal to the color of the j-th pebble in thei-th pile. If there are several possible answers, you may output any of them.

Sample test(s)

input

4 4
1 2 3 4

1 2	4 4 1 2 3 4

output

YES

1 4

1 2 4

1 2 3 4

input

5 2
3 2 4 1 3

1 2	5 2 3 2 4 1 3

output

NO

input

5 4
3 2 4 3 5

1 2	5 4 3 2 4 3 5

output

YES

1 2 3

1 3

1 2 3 4

1 3 4

1 1 2 3 4

题解

得出mn=min{ai}

每堆前mn+1个染色为1

然后2-k给每一堆染色1个

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define mod 30031
#define inf 1000000000
#define rad 100000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,k,mn=inf;
int a[105],c[105][105];
int now[105];
void color(int num,int id)
{
	for(int i=1;i<=n;i++)
	{
		int t=num;
		for(;now[i]<a[i]&&t;now[i]++,t--)
			c[i][now[i]+1]=id;
	}
}
int main()
{
	n=read();k=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		mn=min(mn,a[i]);
	}
    color(mn+1,1);
	for(int i=2;i<=k;i++)
		color(1,i);
	for(int i=1;i<=n;i++)
		if(now[i]!=a[i]){puts("NO");return 0;}
	puts("YES");
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=a[i];j++)
			printf("%d ",c[i][j]);
		puts("");
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define mod 30031

#define inf 1000000000

#define rad 100000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,k,mn=inf;

int a[105],c[105][105];

int now[105];

void color(int num,int id)

{

for(int i=1;i<=n;i++)

{

int t=num;

for(;now[i]<a[i]&&t;now[i]++,t--)

c[i][now[i]+1]=id;

}

int main()

{

n=read();k=read();

for(int i=1;i<=n;i++)

{

a[i]=read();

mn=min(mn,a[i]);

}

color(mn+1,1);

for(int i=2;i<=k;i++)

color(1,i);

for(int i=1;i<=n;i++)

if(now[i]!=a[i]){puts("NO");return 0;}

puts("YES");

for(int i=1;i<=n;i++)

{

for(int j=1;j<=a[i];j++)

printf("%d ",c[i][j]);

puts("");

}

return 0;

}

« 「CF508C」Anya and Ghosts 「CF509C」Sums of Digits »

hzwer.com _ Home | http://hzwer.com

「CF509B」Painting Pebbles

分类目录

热门文章

Myfriends

近期评论