CF2273B.Robot Championship
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Fran and Sofia have become huge fans of robot aura fights, so they have decided to create their own robot aura tournament. Since Sofia is a great expert on robots, Fran will need your help to win the championship.
A match of the tournament takes place on an n×n board. The rows are numbered from bottom to top and the columns from left to right, so (1,1) is the bottom-left corner and (n,n) is the top-right corner. The opponent's robot is hidden at some unknown cell (i,j) and moves once every second, but you do not see it.
At the beginning of each second s, before the robot moves, you must choose an integer v with 2≤v≤2n and shoot a laser along the diagonal
(r,c)∣r+c=v. The laser touches the robot if the robot is currently on a cell of that diagonal, in which case you win immediately. Otherwise, after your shot, suppose the robot is currently at (r,c), the robot moves to one of the following cells, provided the move stays inside the board:
- up: (r+1,c);
- right: (r,c+1);
- down-left: (r−1,c−1).
The robot is at cell (3,2) (its diagonal is r+c=5). The green laser is the diagonal v=7, which does not touch the robot.
The robot is adversarial: it may start on any cell, and it may choose any valid sequence of moves. You have to output a fixed sequence of at most 3n diagonals v1,v2,…,vk such that, no matter where the robot starts and no matter how it moves, at least one of the lasers is guaranteed to touch it at some second during the tournament.
弗兰和索菲亚已成为机器人灵能对决的超级粉丝,因此她们决定举办一场属于自己的机器人灵能锦标赛。由于索菲亚是机器人领域的顶级专家,弗兰需要你的帮助才能赢得冠军。
锦标赛的一场比赛在一个 n×n 的棋盘上进行。行从下到上编号,列从左到右编号,因此 (1,1) 是左下角,(n,n) 是右上角。对手的机器人隐藏在某个未知格子 (i,j) 上,并且每秒移动一次,但你无法看到它的位置。
在每一秒 s 开始时(即机器人移动前),你必须选择一个整数 v(满足 2≤v≤2n),并沿对角线
{(r,c)∣r+c=v}
发射一道激光。若此时机器人恰好位于该对角线上的某个格子,则激光击中机器人,你立即获胜。否则,在你射击之后,假设机器人当前位于 (r,c),它将向以下三个方向之一移动(前提是移动后仍在棋盘内):
- 向上:(r+1,c);
- 向右:(r,c+1);
- 左下:(r−1,c−1)。
机器人位于格子 (3,2)(其所在对角线为 r+c=5)。绿色激光对应对角线 v=7,未击中机器人。
该机器人具有对抗性:它可从任意格子出发,且可任意选择合法的移动序列。你需要输出一个长度至多为 3n 的固定对角线序列 v1,v2,…,vk,使得无论机器人从何处出发、如何移动,都必定在比赛过程中的某一秒被至少一道激光击中。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤44). The description of the test cases follows.
The only line of each test case contains a single integer n (2≤n≤100) — the size of the board.
It is guaranteed that the sum of n3 over all test cases does not exceed 106.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤44)。随后是各测试用例的描述。
每个测试用例仅有一行,包含一个整数 n(2≤n≤100)—— 表示棋盘的大小。
保证所有测试用例的 n3 之和不超过 106。
输出格式
For each testcase, print two lines. The first line contains an integer k (1≤k≤3n) — the number of lasers.
The second line contains k integers v1,v2,…,vk (2≤vi≤2n) — the diagonals in the order they are shot.
You may print any valid sequence.
对于每个测试用例,输出两行。
第一行包含一个整数 k(1≤k≤3n)—— 激光的数量。
第二行包含 k 个整数 v1,v2,…,vk(2≤vi≤2n)—— 按发射顺序排列的对角线编号。
你可以输出任意一个合法的序列。
输入输出样例
输入#1
2 2 3
输出#1
3 3 3 3 3 4 4 4
说明/提示
For n=2, the sequence 3,3,3 works. The first laser 3 removes the diagonal r+c=3 (cells (1,2) and (2,1)). Cell (1,1) must move onto that same diagonal on the next turn, and cell (2,2) is forced to follow the path (2,2)→(1,1)→ the same diagonal. The second and third lasers catch both.
For n=3, the sequence 4,4,4 works. A robot on the diagonal r+c=4 is hit by the first laser. From the diagonal r+c=3 or from cell (3,3), every move leads onto r+c=4, so the second laser hits it. From cell (1,1) or from the diagonal r+c=5, every move leads onto r+c=3 or to cell (3,3), so the third laser hits it.
当 n=2 时,序列 3,3,3 可行。第一束激光 3 清除对角线 r+c=3(即格子 (1,2) 和 (2,1))。格子 (1,1) 必须在下一步移动到同一条对角线 r+c=3 上;而格子 (2,2) 则被迫沿路径 (2,2)→(1,1)→ 同一条对角线移动。第二束与第三束激光可成功击中二者。
当 n=3 时,序列 4,4,4 可行。位于对角线 r+c=4 上的机器人会被第一束激光击中;从对角线 r+c=3 或从格子 (3,3) 出发,任何一步移动都将抵达 r+c=4,因此第二束激光可击中它;从格子 (1,1) 或从对角线 r+c=5 出发,任何一步移动都将抵达 r+c=3 或格子 (3,3),因此第三束激光可击中它。
输入解题思路,AI测评打分。不知道怎么写?