题解 P2041 【分裂游戏】

任弈凡 · 2019-03-15 16:01:21 · 题解

我们先给出结论：

1. 当n=1时，显然，我们只需1步，移动(1,1)即可
2. 当n=2时，题目已经给了我们答案
3. 当n=3时,此题无解

然而，这是为什么呢？

• 假设我们的原数为1,不难发现，每一次分裂即是一次将原数变成一个原数的\frac{1}{2}

我们来画一个图：

额，好像表格出不来

我们容易发现，第一行这无限个数的和应是1+\frac{1}{2}+\frac{1}{4}+······这些数的和无限接近于2,在数学上，我们默认为2(我已经找到了一种绝佳的证明方法，可惜空间太短，写不下)!

同理,第2行的和即是1,第三行为\frac{1}{2},第四行为\frac{1}{4}······

所以,这无限个数之和为4

而我们已知我们无限分类的和应为1

所以，当n=4,ans=1+\frac{1}{2}*2+\frac{1}{4}*3+\frac{1}{8}*4=\frac{13}{4},所以剩下的和为4-\frac{13}{4}=\frac{3}{4}<1所以n>4无解

那么，当n=3时，依照我们的方法,结果应是\frac{5}{4}>1所以可以，但是，我们发现,第一行和第一列最多只能有一个数(在第一列时，每一个操作都只会在上和右增加数，而第一列数/第一行最多只能由第一个数得到),所以n=3时,的最大值为\frac{5}{4}-\frac{1}{8}* 2=1，然而，在有限的操作中，我们不可能使我们填满所有的格子，所以我们的ans会严格<1

综上，结论成立

代码(刚刚都解释过了) ：

#include<iostream>
using namespace std;
int n;
int main() {
    cin>>n;
    if(n==1) {
        cout<<1<<endl;
        cout<<1<<" "<<1<<endl;
    }
    else if(n==2) {
        cout<<4<<endl;
        cout<<1<<" "<<1<<endl;
        cout<<2<<" "<<1<<endl;
        cout<<2<<" "<<2<<endl;
        cout<<1<<" "<<2<<endl;
    }
    else cout<<-1;
}