P2041 分裂游戏

    • 240通过
    • 375提交
  • 题目提供者 yechenaia
  • 评测方式 云端评测
  • 标签 数论,数学 高性能
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有一个无限大的棋盘,棋盘左下角有一个大小为 n 的阶梯形区域,其中最左下角的那个格子里有一枚棋子。你每次可以把一枚棋子“分裂”成两枚棋子,分别放在原位置的上边一格和右边一格。(但如果目标位置已有棋子,则不能这样做)你的目的是通过有限次的操作,让整个阶梯里不再有任何棋子。下图所示的是 n = 2 时的一种解法。

    我们用从下往上数的方式标记行,从左往右数的方式标记列,以(行,列)来标记棋子,并且都从1开始。

    例如,第三步中的三个棋子坐标分别为(3,1),(2,2),(1,2)

    现在已知n,你需要做的是给出合适的操作序列。

    输入输出格式

    输入格式:

    输入只有一行,这一行只包含一个正整数n,其意义如题目所述。

    输出格式:

    如果有解,第一行应包含一个正整数m,表示总共需要的操作步数。

    以下m行,每行包括两个正整数xi,yi,表示第i步操作分裂的是处于第xi行第yi列的棋子。

    如果无解,只需在第一行输出-1。

    输入输出样例

    输入样例#1: 复制
    输入样例1
    1
    
    
    输入样例2
    2
    输出样例#1: 复制
    输出样例1
    1
    1 1
    
    
    输出样例2
    4
    1 1
    2 1
    2 2
    1 2
    

    说明

    ↖(^ω^)↗加油!

    对于40%的数据:N≤8;

    对于100%的数据:N≤1000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。