这个题纠结了好久。首先想到的是暴搜，必超时。
然后注意到题目中，天平左边的物体和右边的物体交替取，可能会使更快得到最优解，所以就根据他们的位置是否>0把他们放到两个数组里，这里有个优化就是按照到达-1.5和+1.5的力矩排序，这样如果取了前面的物体天平失去了平衡，则后面的物体也不用取了，一定会失去平衡。这样继续暴搜，还是超时。我估计这个优化没什么用，因为就算你把剩下的都取完，也不需要浪费多少时间嘛。。。平均意义上能减少一般的时间。但是A(20,20)。。这个有点大。
好吧，又继续陷入僵局了。看别人的结题报告，发现主流版本是一堆乱糟糟的代码，不懂在搞什么。。。后来偶然发现了一个版本，在暴搜的时候，写的很奇怪，参见http://blog.csdn.net/wuli2496/article/details/7284641。dfs(l,r)，l,r表示前面l-1,r-1个已经取过了，这让我煞是费解。（他的解法是把物体一个个的放到纠结的天平上），为什么不能先力矩放大的，后放力矩小的？然后我改了下他的dfs()，变成无参的，每次都从0开始找，交，超时了。作者没有说明他为什么要这么做，或许是他不想说？或者他没留意？而且这明明就不是个dfs了，如果可以证明，先放小的比先放大的好，那么这个dfs就是个DP了。和有限背包问题一样的。好吧。然后我就想着证明为何先放力矩小的比先放力矩大的好，想了很久，发现，没办法。
后来，偶然想到了一种方法，证明出如果在当前的情况中，拿掉左边力矩最大的，天平向右歪，并且拿掉右边力矩最大的，天平向左歪，那么无论以后怎么拿，都不可能成功。
这样反推一下，刚刚好是一个dp。r[i][j]表示放上去了左边前i个，右边前j个的天平状况（这种状况刚刚好依赖于0-i,0-j的质量）。它只能由r[i][j-1],r[i-1][j]推出。
额，这样就是一个完美的背包问题了，只要20*20个状态，交了，A掉了，跑的足够快，理论上应该是最快的解法了吧？肯定比搜索快，也要比状态压缩的DP快，因为状态压缩的DP需要2^20个状态。。。可能是我的代码写的太乱了，所以才跑到15名。。
好了，最重要的的问题就是证明上面一段中红色字的结论。
现在我们把天平分成3段：第一段是最左边到-1.5，中间是-1.5到1.5，右边是1.5-最右边。
左边的物体的力矩我们记为:WL(左边最大那个力矩) + Lrest(左边剩余力矩) ,中间的物体的力矩我们记为 C+Mrest(C表示中间那一段的模板质量，Mrest表示中间物体质量),右边的力矩我们记为
WR(右边最大那个力矩)+Rrest(右边剩余力矩)。我们可以简单地在左边和右边都剪掉Rrest。那么左边，中间，右边的力矩为WL+rest, C+Mrest,WR。如果拿掉左边最大的右偏，我们可以得到式子 : rest + C + Mrest < WR 。那么很显然，rest会越来越小，所以这个式子永远成立，所以红字得证。
好了，这个证明想了很久，而且中间用到了一个结论：拿掉天平左右两边等重的物体，对天平没影响。对于有两个平衡点的这只是个臆测，额好吧，谁有更好更简单的解法欢迎交流。LRJ出的题果真很神，不过也很让人纠结。代码写的比较乱，莫看。
#include <cstdio>
#include <cstdlib>
#include <cstring>
class node
{
public:
int pos,w;
};
class set
{
public:
int ll,lr,rl,rr;
int prev,ok;
};
set res[30][30];
node lefts[110],rights[110];
int lcount,rcount;
int find;
int L,W,C;
int abs(int i)
{
if(i>0) return i;
return -i;
}
void pans(int l,int r)
{
if(l == 0 && r== 0)
return;
if(res[l][r].prev == 1)
{
printf("%d %d\n",rights[r-1].pos/2,rights[r-1].w);
pans(l,r-1);
}
else
{
printf("%d %d\n",lefts[l-1].pos/2,lefts[l-1].w);
pans(l-1,r);
}
}
int cmp1(const void* a,const void* b)
{
node i = *(node*)a;
node j = *(node*)b;
return (-i.pos-3)*i.w - (-j.pos-3)*j.w;
}
int cmp2(const void* a,const void* b)
{
node i = *(node*)a;
node j = *(node*)b;
return (i.pos-3)*i.w - (j.pos-3)*j.w;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int i,c=1,j;
int ll,lr,rl,rr;
while(scanf("%d%d%d",&L,&W,&C)!=EOF && L>0)
{
memset(res,0,sizeof(res));
L *= 2;
ll = rr =0; rl = lr = 3*W;
node tmp;
lcount = rcount = 0;
for(i=0;i<C;i++)
{
scanf("%d%d",&tmp.pos,&tmp.w);
tmp.pos*=2;
if(tmp.pos<0)
lefts[lcount++] = tmp;
else
rights[rcount++] = tmp;
}
qsort(lefts,lcount,sizeof(node),cmp1);
qsort(rights,rcount,sizeof(node),cmp2);
set tmpset = {ll,lr,rl,rr,0,1};
res[0][0] = tmpset;
for(i=0;i<=lcount;i++)
for(j=0;j<=rcount;j++)
{
if(i-1>=0 && res[i-1][j].ok == 1)
{
tmpset = res[i-1][j];
//放了第i个物体
if(lefts[i-1].pos < -3)
tmpset.ll += (-3-lefts[i-1].pos)*lefts[i-1].w;
else
tmpset.lr += (lefts[i-1].pos+3)*lefts[i-1].w;
if(lefts[i-1].pos < 3)
tmpset.rl += (3 - lefts[i-1].pos)*lefts[i-1].w;
else
tmpset.rr += (lefts[i-1].pos - 3)*lefts[i-1].w;
if(tmpset.ll < tmpset.lr && tmpset.rl>tmpset.rr)
{
tmpset.ok = 1;
tmpset.prev = -1;
res[i][j] = tmpset;
}
else
{
res[i][j].ok = 0;
}
}
if(res[i][j].ok)
continue;
if(j-1>=0 && res[i][j-1].ok == 1)
{
tmpset = res[i][j-1];
if(rights[j-1].pos < -3)
tmpset.ll += (-3-rights[j-1].pos)*rights[j-1].w;
else
tmpset.lr += (rights[j-1].pos+3)*rights[j-1].w;
if(rights[j-1].pos < 3)
tmpset.rl += (3 - rights[j-1].pos)*rights[j-1].w;
else
tmpset.rr += (rights[j-1].pos - 3)*rights[j-1].w;
if(tmpset.ll < tmpset.lr && tmpset.rl>tmpset.rr)
{
tmpset.ok = 1;
tmpset.prev = 1;
res[i][j] = tmpset;
}
else
{
res[i][j].ok = 0;
}
}
}
printf("Case %d:\n",c++);
if(res[lcount][rcount].ok == 1)
pans(lcount,rcount);
else
printf("Impossible\n");
}
return 0;
}