#B. 造迷宫

    Type: Default 1000ms 512MiB

造迷宫

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小 M 喜欢玩迷宫。一个迷宫被定义为一个 n×mn\times m 的网格图,每个格子 (x,y)(x,y) 都能通过一扇门走到 (x+1,y),(x,y+1)(x+1,y),(x,y+1)。有一些门坏了,打不开。

小 M 痴迷于找出所有可能的从 (1,1)(1,1)(n,m)(n,m) 的路径,假设数目为 tt

现在小 M 忘记了网格图的具体形状,但是他仍然记得 tt。他告诉了你 tt,要你任意构造一个合法的迷宫。

因为小 M 不擅长记忆,你需要保证 1n,ml1\leq n,m\leq l,坏掉的门的个数不超过 pp

输入格式

本题多测

第一行三个正整数 T,l,pT,l,p 表示测试点数目,n,mn,m 的最大限制,坏掉的门的个数限制。

接下来 TT 行,每行一个正整数 tt 表示一次询问。

输出格式

对于每一组数据,首先输出三个数 n,m,kn,m,k 表示迷宫的两边边长,坏掉的门的个数。

然后 kk 行,每行四个正整数 x1,y1,x2,y2x_1,y_1,x_2,y_2 表示 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2) 之间的门坏掉了。你需要保证 x1x2+y1y2=1|x_1-x_2|+|y_1-y_2|=1

测试样例

样例输入 样例输出
2 100 100 100001004 1 100 03 3 21 2 1 32 1 2 2

数据范围

对于所有数据,T500T\leq 500l50l\geq 50p300p\geq 300t1018t\leq 10^{18}

测试点编号 TT\leq l=l= p=p= tt\leq
11 100100 100100 300300 100100
22 10410^4 10910^9
33 300300 10310^3 101810^{18}
44 5050
55 500500 300300

时间限制:1s\tt 1s

空间限制:512MB\tt 512MB

Odoo 省选模拟赛

Not Attended
Status
Done
Rule
OI
Problem
3
Start at
2024-2-29 8:00
End at
2024-2-29 12:00
Duration
4 hour(s)
Host
Partic.
4