QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 512 MB Total points: 100

# 7979. 棋盘

统计

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

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

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

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

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

输入格式

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

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

输出格式

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

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

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

你需要保证 $ n\le X $,并且 $ 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\times 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= $特殊性质
$ 1 $$ 5 $$ 10^3 $$ 340 $$ 2 $
$ 2 $$ 10 $$ 10^3 $$ 340 $$ 12 $
$ 3 $$ 10 $$ 10^3 $$ 340 $$ 100 $
$ 4 $$ 10 $$ 990 $$ 310 $$ 100 $数据随机
$ 5 $$ 10 $$ 1050 $$ 260 $$ 100 $
$ 6 $$ 10 $$ 1050 $$ 240 $$ 100 $
$ 7 $$ 15 $$ 980 $$ 260 $$ 100 $$ Q=1 $
$ 8 $$ 30 $$ 960 $$ 240 $$ 100 $

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

对于所有数据,保证 $ 1\le Q\le 10^4 $。