luogu#P9195. [JOI Open 2016] JOIRIS

[JOI Open 2016] JOIRIS

题目背景

译自 JOI Open 2016 T1 「JOIRIS」

题目描述

JOIRIS 的游戏区域名叫「井」,是一个宽度为 NN,高度足够大的矩形网格。位于左数第 ii 列,从下往上数第 jj 列的格子记作 (i,j)(i,j)。游戏过程中,每个格子要不有一个方块,要不没有方块。

开始时,在第 ii 列有且仅有 (i,1),(i,2),,(i,Ai)(i,1), (i,2),\cdots, (i, A_i) 有方块。

接下来,10410^41×K1 \times K 的骨牌一个个下落,玩家要依次放置骨牌。每次放置骨牌按照如下方式进行:

玩家先选择骨牌是横向放置还是纵向放置。

  • 若选择纵向,玩家还需再选择一个整数 xx1xN1 \le x \le N)。一个骨牌会下落到第 xx 列最上方方块的上面一行。若第 xx 列没有方块,骨牌会下落到井底。
  • 若选择横向,玩家还需再选择一个整数 xx1xNK+11 \le x \le N-K+1)。一个骨牌会下落到第 xx 列至第 x+K1x+K-1 列最上方方块的上面一行。若第 xx 列至第 x+K1x+K-1 列没有方块,骨牌会下落到井底。

每个骨牌停止下落后,系统将从井底往上逐行检查,如果有一行格子被方块填满,该行的所有方块都会消失,且上方的所有方块向下移动 11 格。

此时检查井中是否有方块,如果井中没有方块,游戏结束,玩家胜利,否则玩家开始放置下一个骨牌。

保证开始时最底下一行没有被方块填满。请判断玩家能否胜利,如果可能,则输出一种方案。

输入格式

输入共 N+1N + 1 行。

第一行含有两个整数 N,KN,K
在接下来的 NN 行中,第 ii 行(1iN1 \le i \le N)有一个整数 AiA_i

输出格式

如果玩家无法胜利,请输出一行一个 1-1

否则请输出 X+1X+1 行,其中 XX 表示消去所有棋子所需要的步数:

第一行包含一个整数 XX。接下来第 ii 行(1iX1 \le i \le X)表示你的方案。

  • 如果第 ii 个下落的骨牌纵向放置,输出两个整数,第一个整数为 11,第二个整数 xx 表示玩家放置零件的位置(如题目描述中所述)。
  • 如果第 ii 个下落的骨牌横向放置,输出两个整数,第一个整数为 22,第二个整数 xx 表示玩家放置零件的位置(如题目描述中所述)。
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 解释

数据规模与约定

本题采用捆绑测试

对于所有数据,2N502\le N\le 501KN1\le K\le N0Ai500\le A_i \le 50

  • Subtask 1(15 points):K=2K=2NN 为奇数。
  • Subtask 2(15 points):K=2K=2NN 为偶数。
  • Subtask 3(15 points):KK 能够整除 NN
  • Subtask 4(55 points):没有额外限制。