比赛 2022级数学专题练习赛3 评测结果 AAAAAAAAAA
题目名称 纸牌问题 最终得分 100
用户昵称 op_组撒头屯 运行时间 0.181 s
代码语言 C++ 内存使用 3.58 MiB
提交时间 2022-12-26 21:06:07
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200+5;
const int M=10000+5;
int n;
int a[N][N],b[N],c[N];
struct sdf{
	int x,y;
}ans[M];
int calc(int i){
	if (i==1||i==n){
		if (b[i]>=c[i])return c[i];
		else return b[i];
	}
	else{
		if (b[i]>=2*c[i])return 2*c[i];
		else return b[i]-b[i]%2;
	}
}
int main(){
	freopen ("flat.in","r",stdin);
	freopen ("flat.out","w",stdout);
	scanf("%d",&n);
	int tot=0;
	for (int i=1;i<=n;i++)scanf("%d",&b[i]),tot+=b[i];
	tot/=n;
	for (int i=1;i<=n;i++){
		if (i!=1)a[i][i-1]=1;
		if (i!=n)a[i][i+1]=1;
		a[i][i]=(i==1||i==n)?-1:-2;
		a[i][n+1]=tot-b[i];
	}
	for (int i=1;i<=n;i++){
		int pos=0;
		for (int j=i;j<=n;j++){
			if (a[j][i]){
				pos=j;break;
			}
		}
		if (!pos)continue;
		swap(a[i],a[pos]);
		for (int j=1;j<=n;j++){
			if (i==j||!a[j][i])continue;
			int p=a[j][i]/a[i][i];
			for (int k=1;k<=n+1;k++){
				a[j][k]-=a[i][k]*p; 
			}
		}
	}
	int mx=0;
	for (int i=1;i<n;i++){
		mx=max(mx,a[i][n+1]);
	}
	c[n]=mx;
	for (int i=1;i<n;i++){
		c[i]=mx-a[i][n+1];
	}
	int cnt=0;
	while(true){
		int mx=0,pos=0;
		for (int i=1;i<=n;i++){
			int p=calc(i);
			if (p>mx){
				mx=p;pos=i;
			}
		}
		if (!pos)break;
		if (pos==1||pos==n)ans[++cnt]={pos,mx};
		else ans[++cnt]={pos,mx/2};
		if (pos==1)b[2]+=mx,b[1]-=mx,c[1]-=mx;
		else if (pos==n)b[n-1]+=mx,b[n]-=mx,c[n]-=mx;
		else b[pos+1]+=mx/2,b[pos-1]+=mx/2,b[pos]-=mx,c[pos]-=mx/2;
	}
	printf("%d\n",cnt);
	for (int i=1;i<=cnt;i++){
		printf("%d %d\n",ans[i].x,ans[i].y);
	}
	return 0;
}