比赛 |
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;
}