QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 512 MB Total points: 100
[+13]

# 7979. 棋盘

Statistics

小 L 作为一名 OIER,做过了广为人知的棋盘计数问题。

即,给定一个无限大的棋盘,第 i 行第 j 列记作位置 (i,j),棋盘上有若干个位置被标记,棋子只能经过被标记的地方,保证 (1,1) 被标记,有一颗棋子初始在 (1,1),每次只能向右或向下(即将某一位的坐标增加 1),对于所有位置求出有多少种方案可以走到这里。

然而小 L 觉得太简单了,记走到 (i,j) 位置的方案数为 fi,j(如果无法走到该位置则 fi,j=0),他希望选出若干个不同位置,使得它们的 f 值加起来等于给定的数 k,如果有多种方案,任意输出一种即可,小 L 会询问 Q 次。

小 L 希望每次询问选出的位置尽量的少,同时,小 L 希望棋盘上被标记的位置也尽量的少,请你构造一组方案来满足条件。

具体的,小 L 希望棋盘上被标记的位置不超过 X,每次询问选择的位置数不超过 Y

输入格式

第一行三个正整数,分别为 K,Q,X,Y,保证询问的所有 k 满足 1k<10K

接下来 Q 行,每行一个整数 k

输出格式

第一行一个正整数 n,表示棋盘上被标记的数的数量,你需要保证 nX

接下来 n 行,每行两个数 x,y,表示被标记的位置的坐标,你需要保证被标记的坐标互不相同,并且你需要注意这里的输出顺序(后续需要考虑),尽管棋盘是无限大的,你还是需要保证输出的坐标 x,y 满足 1x,yn

接下来 Q 行,每行一个长度为 n01 串,其中第 i 位为 1 表示你选择了第 i 个被标记的坐标。

你需要保证 nX,并且 01 串中 1 的数量不超过 Y

输入输出样例

样例输入
2 3 1000 340
1
2
3
样例输出
8
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3
10000000
00000110
10000001
样例解释

棋盘如下:

problem_7979_1.png

其中左上角为格子 (1,1),右下角为 (3,3),黄色格子是未被标记的格子,格子中的数为对应的 f 值,当然棋盘大小不止 3×3,这里只展示了存在被标记的格子的区域。

第一次询问选择了格子 (1,1),第二次询问选择了格子 (3,1),(3,2),第三次询问选择了格子 (1,1),(3,3)

下发文件中提供了 checker.cpp,你可以将其编译成可执行文件,其使用格式为 checker chess.in chess.out,其中 chess.in 为输入文件,chess.out 为你的输出,checker 会执行检查命令并返回错误所对应的编码:

  1. 输出格式出错(包括 n>X 但不包括 01 串中 1 的数量 >Y
  2. 01 串中 1 的数量 >Y
  3. 你所构造的方案的 f 值之和不是询问所需要的值。

如果你的构造正确,checker 会返回 correct

你可以参考或直接使用 checker 提供的高精度模板。

注意下发 checker 和实际 checker 有所不同。

数据范围
Subtask分值X=Y=K=特殊性质
151033402
21010334012
310103340100
410990310100数据随机
5101050260100
6101050240100
715980260100Q=1
830960240100

其中,数据随机的方式是:k[1,10K) 中等概率随机。

对于所有数据,保证 1Q104