思路
因为交换同一列的相邻两行，这一列的总数不变；交换同一行的相邻两列，这一行的总数不变。
那么如果可以平均分配的话，可以先将所有行都分配好，然后再将所有列分配好。
这样就变成了做两次环形纸牌分配问题，
给一个数列，最后一位和第一位相邻，问能否平均分配，最少需要传递多少次。
首先考虑普通纸牌均分问题：
有 (n) 个人坐成一排，每个人 (a[i]) 张牌，每个人只能和旁边的人交换纸牌，问最好交换几次能使所有人的手牌数相等。
这是一个经典问题，答案等于 (sum_{i=1}^n|s[i]-frac{t}{n}cdot i|)，其中 (s[i]=sum_{j=1}^ia[i],t=sum[n])。
这个结论是很好证明的，前 (i) 个人现在有的牌总共为 (s[i]) 张，而他们最终的状态是总共 (frac{t}{n}cdot i) 张，所以他们需要通过第 (i) 个人向第 (i+1) 个人给出或者索取 (|s[i]-frac{t}{n}cdot i|) 张牌。
环形纸牌均分问题：
刚刚是 (n) 个人做成一行，现在是 (n) 个人做成一圈，第 (1) 个人和第 (n) 个人也可以交换纸牌了，问题相同。
不管怎么说，它总有一个起点，一个终点，我们现在只是不清楚怎样选取起点终点可以使得答案更小而已，不妨先设将第 (k+1) 个人设为起点，第 (k) 个人设为终点。
设 (A[i]=a[i]-frac{t}{n})，(S[i]=sum_{j=1}^iA[i])，从第 (k) 个人断开看成一行。列出现在的排列和前缀和：
因为 (S[i]=sum_{j=1}^iA[i])，所以 (S[n]=0)，那么可以发现对于不同的 (k)，答案是 (sum_{i=1}^n|S[i]-S[k]|)，这个式子又涉及到了一个经典问题。
货舱选址
x 轴上有 (n) 个厂房，给出每个的地址 (a[i])，要求选一个厂房地址建货舱使所有厂房到这里的路程总和最小。
答案也是很简单的，是 (a) 数列的中位数，证明：设在最优位置仓库左边有 (q) 个仓库，总距离 (Q)，右边有 (p) 个仓库，总距离 (P)，则满足以下关系：
回到环性纸牌均分问题
(sum_{i=1}^n|S[i]-S[k]|) 的最小值就是 (S[k]) 取 (S) 的中位数时
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e5+10;
int n,m,t;
LL r[MAXN],c[MAXN];
LL calc(LL *a,int n){
for(int i=1;i<=n;i++) a[i]-=t/n;
for(int i=1;i<=n;i++) a[i]+=a[i-1];
sort(a+1,a+n+1);
LL ans=0;
for(int i=1;i<=n;i++) ans+=abs(a[i]-a[n/2+1]);
return ans;
}
int main(){
scanf("%d%d%d",&n,&m,&t);
for(int i=1,x,y;i<=t;i++){
scanf("%d%d",&x,&y);
r[x]++;c[y]++;
}
if(t%n==0&&t%m==0) printf("both %lld
",calc(r,n)+calc(c,m));
else if(t%n==0) printf("row %lld
",calc(r,n));
else if(t%m==0) printf("column %lld
",calc(c,m));
else printf("impossible
");
return 0;
}