/*
会场由N*M个摊点组成
* * * * *
* * * * *
* * * * *
* * * * *
* * * * *
* * * * *
* * * * *
* * * * *
* * * * *
要使每一行感兴趣的摊点一样多,只能调整相邻两个点(同行或者同列)
点的总和位为T
如果T不能整除N,则不能通过row达到
如果T不能整除M,则不能通过column达到
由于左右调整和上下调整不改变行/列的个数,
因此我们讨论如何通过左右调整使得每一列的数量相等;
1.记录每一列的数量并记录前缀和
如果X可以整除先考虑某一列,每一列最终的个数将是T/M个
因此对于第C[i]个点将要调整|C[i]-T/M|次
准确来说,从第一个点开始,一共需要调整∑(1,m)|i*T/M-G[i]| (G[i]为前缀和)
相当于我们取A[i]=C[i]-T/M,S[i]=∑A[i]
而如果把它当作一个环来处理,就是选取第k个位置断开,每个位置的变化:
i+k<=M:
A[k+i]->S[k+1]-S[k]
i<k:
A[i]->S[i]+S[M]-S[k]
因此最后的总和是∑|S[i]-S[k]|
这个便是仓库选址这一道题目的中位数思想:
https://www.acwing.com/problem/content/106/
AC 代码:
*/
#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n,m,t,x,y;
long long res_row,res_column;
int row[MAXN]={0},column[MAXN]={0},r[MAXN],c[MAXN];
int main(){
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=t;i++){
scanf("%d%d",&x,&y);
row[x]++,column[y]++;
}
if(t%n==0||t%m==0){
if(t%m==0&&t%n!=0){
printf("column ");
//处理前缀和
for(int i=1;i<=m;i++){
c[i]=c[i-1]+column[i]-t/m;
}
//排序,计算∑|S[i]-S[k]|
sort(c+1,c+1+m);int u=c[(m+1)/2];
for(int i=1;i<=m;i++) res_column+=abs(c[i]-u);
printf("%lld",res_column);
}
else if(t%n==0&&t%m!=0){
printf("row ");
for(int i=1;i<=n;i++){
r[i]=r[i-1]+row[i]-t/n;
}
sort(r+1,r+1+n);
int u=r[(n+1)/2];
for(int i=1;i<=n;i++) res_row+=abs(r[i]-u);
printf("%lld",res_row);
}
else{
printf("both ");
//列
for(int i=1;i<=m;i++){
c[i]=c[i-1]+column[i]-t/m;
}
//排序,计算∑|S[i]-S[k]|
sort(c+1,c+1+m);
int u=c[(m+1)/2];
for(int i=1;i<=m;i++) res_column+=abs(c[i]-u);
//行
for(int i=1;i<=n;i++){
r[i]=r[i-1]+row[i]-t/n;
}
sort(r+1,r+1+n);
u=r[(n+1)/2];
for(int i=1;i<=n;i++) res_row+=abs(r[i]-u);
printf("%lld",res_row+res_column);
}
}
else printf("impossible\n");
return 0;
}