← 返回题目列表

Codeforces · 715/D

D. 创建一个迷宫

中文机器翻译题面 查看原题

编码员 ZS 喜欢迷宫。你的工作是创造一个这样他就可以玩它。迷宫由 n × m 个房间组成,房间排列为 n 行(从上到下从 1 开始编号)和 m 列(从左到右从 1 开始编号)。第i行j列的房间用(i,j)表示。玩家从房间 (1, 1) 开始,想要到达房间 (n, m)。

每个房间都有四扇门(迷宫边界的门除外),每面墙上各一扇,并且靠墙相邻的两个房间共用同一扇门。有些门是锁着的,这意味着无法通过门。例如,如果连接(i,j)和(i,j + 1)的门被锁了,那么我们就不能从(i,j)到(i,j + 1)。另外,如果相应的门未锁,则只能在房间之间向下(从房间(i,j)到房间(i + 1,j))或向右(从房间(i,j)到房间(i,j + 1))移动。

此图像代表一个迷宫,其中一些门被锁着。彩色箭头表示所有可能的路径,而红色十字表示锁着的门。

ZS 如果从房间 (1, 1) 到房间 (n, m) 正好有 x 种方式,那么编码员认为迷宫的难度为 x。如果两种方式在旅行时访问的房间顺序不同,则被认为是不同的。

你的任务是创建一个迷宫,使其难度恰好等于T。另外,编码员ZS不喜欢大迷宫,所以迷宫的大小和上锁的门的数量都是有限的。听起来很简单,对吧?

输入

输入的第一行也是唯一一行包含一个整数 T (1 ≤ T ≤ 1018),即所需迷宫的难度。

输出

第一行应包含两个整数 n 和 m (1 ≤ n, m ≤ 50)——分别是迷宫的行数和列数。

下一行应包含一个整数 k (0 ≤ k ≤ 300) — 迷宫中锁着的门的数量。

然后,应该出现描述锁门的 K 线。它们每个都应包含四个整数:x1、y1、x2、y2。这意味着连接房间(x1,y1)和房间(x2,y2)的门被锁定。请注意,房间 (x2, y2) 应与 (x1, y1) 的右侧或底部相邻,即 x2 + y2 应等于 x1 + y1 + 1。列表中不应出现两次上锁的门。

保证至少存在一个解。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3

输出 #1

3 2
0

输入 #2

4

输出 #2

4 3
3
1 2 2 2
3 2 3 3
1 3 2 3

注意

以下是示例输入和输出的样子。彩色箭头表示所有可能的路径,而红色十字表示锁着的门。

在第一个示例案例中:

在第二个示例案例中: