luogu#P9195. [JOI Open 2016] JOIRIS
[JOI Open 2016] JOIRIS
题目背景
译自 JOI Open 2016 T1 「JOIRIS」
题目描述
JOIRIS 的游戏区域名叫「井」,是一个宽度为 ,高度足够大的矩形网格。位于左数第 列,从下往上数第 列的格子记作 。游戏过程中,每个格子要不有一个方块,要不没有方块。
开始时,在第 列有且仅有 有方块。
接下来, 个 的骨牌一个个下落,玩家要依次放置骨牌。每次放置骨牌按照如下方式进行:
玩家先选择骨牌是横向放置还是纵向放置。
- 若选择纵向,玩家还需再选择一个整数 ()。一个骨牌会下落到第 列最上方方块的上面一行。若第 列没有方块,骨牌会下落到井底。
- 若选择横向,玩家还需再选择一个整数 ()。一个骨牌会下落到第 列至第 列最上方方块的上面一行。若第 列至第 列没有方块,骨牌会下落到井底。
每个骨牌停止下落后,系统将从井底往上逐行检查,如果有一行格子被方块填满,该行的所有方块都会消失,且上方的所有方块向下移动 格。
此时检查井中是否有方块,如果井中没有方块,游戏结束,玩家胜利,否则玩家开始放置下一个骨牌。
保证开始时最底下一行没有被方块填满。请判断玩家能否胜利,如果可能,则输出一种方案。
输入格式
输入共 行。
第一行含有两个整数 。
在接下来的 行中,第 行()有一个整数 。
输出格式
如果玩家无法胜利,请输出一行一个 。
否则请输出 行,其中 表示消去所有棋子所需要的步数:
第一行包含一个整数 。接下来第 行()表示你的方案。
- 如果第 个下落的骨牌纵向放置,输出两个整数,第一个整数为 ,第二个整数 表示玩家放置零件的位置(如题目描述中所述)。
- 如果第 个下落的骨牌横向放置,输出两个整数,第一个整数为 ,第二个整数 表示玩家放置零件的位置(如题目描述中所述)。
4 2
1
0
1
2
4
2 2
1 1
2 3
1 2
3 2
2
0
1
3
1 2
1 3
2 1
2 2
0
1
-1
5 3
1
0
1
0
1
9
1 4
1 5
2 1
2 1
2 2
1 1
1 2
2 3
2 3
提示
样例 1 解释
数据规模与约定
本题采用捆绑测试。
对于所有数据,,,。
- Subtask 1(15 points): 且 为奇数。
- Subtask 2(15 points): 且 为偶数。
- Subtask 3(15 points): 能够整除 。
- Subtask 4(55 points):没有额外限制。