CF1816A.Ian Visits Mary

入门

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Ian and Mary are frogs living on lattice points of the Cartesian coordinate plane, with Ian living on (0,0)(0,0) and Mary living on (a,b)(a,b).

Ian would like to visit Mary by jumping around the Cartesian coordinate plane. Every second, he jumps from his current position (xp,yp)(x_p, y_p) to another lattice point (xq,yq)(x_q, y_q), such that no lattice point other than (xp,yp)(x_p, y_p) and (xq,yq)(x_q, y_q) lies on the segment between point (xp,yp)(x_p, y_p) and point (xq,yq)(x_q, y_q).

As Ian wants to meet Mary as soon as possible, he wants to jump towards point (a,b)(a,b) using at most 22 jumps. Unfortunately, Ian is not good at maths. Can you help him?

A lattice point is defined as a point with both the xx-coordinate and yy-coordinate being integers.

伊恩和玛丽是生活在笛卡尔坐标平面上格点处的两只青蛙,其中伊恩住在 (0,0)(0,0),玛丽住在 (a,b)(a,b)。

伊恩希望借助在笛卡尔坐标平面上跳跃的方式去拜访玛丽。每一秒,他从当前位置 (xp,yp)(x_p, y_p) 跳到另一个格点 (xq,yq)(x_q, y_q),要求线段 (xp,yp)(x_p, y_p) 与 (xq,yq)(x_q, y_q) 之间(不包括端点)不经过任何其他格点。

由于伊恩希望尽快与玛丽会面,他希望最多通过 22 次跳跃就到达点 (a,b)(a,b)。遗憾的是,伊恩不擅长数学。你能帮他吗?

格点定义为横、纵坐标均为整数的点。

输入格式

The first line contains a single integer tt (1≤t≤5001 \le t \le 500) — the number of test cases. The description of test cases follows.

The first and only line of each test case contains two integers aa and bb (1≤a,b≤1091\le a,b\le 10^9) — the coordinates of the lattice point where Mary lives.

第一行包含一个整数 tt(1≤t≤5001 \le t \le 500),表示测试用例的数量。测试用例的描述如下。

每个测试用例仅有一行,包含两个整数 aa 和 bb(1≤a,b≤1091\le a,b\le 10^9),表示玛丽所居住的格点坐标。

输出格式

For each test case, print an integer nn (1≤n≤21 \le n \le 2) on the first line, denoting the number of jumps Ian uses in order to meet Mary. Note that you do not need to minimize the number of jumps.

On the ii-th line of the next nn lines, print two integers 0≤xi,yi≤1090 \le x_i,y_i \le 10^9 separated by a space, denoting Ian's location (xi,yi)(x_i,y_i) after the ii-th jump. xn=ax_n = a, yn=by_n = b must hold.

Ian's initial location and his locations after each of the nn jumps need not be distinct.

If there are multiple solutions, output any.

对于每个测试用例,在第一行输出一个整数 nn(1≤n≤21 \le n \le 2),表示 Ian 为与 Mary 相遇所使用的跳跃次数。注意:你无需最小化跳跃次数。

在接下来的 nn 行中,第 ii 行输出两个整数 0≤xi,yi≤1090 \le x_i, y_i \le 10^9,以空格分隔,表示 Ian 在第 ii 次跳跃后的位置 (xi,yi)(x_i, y_i)。必须满足 xn=ax_n = a 且 yn=by_n = b。

Ian 的初始位置以及他每次跳跃后的位置可以重复(即不必互不相同)。

若存在多个解,输出任意一个即可。

输入输出样例

  • 输入#1

    8
    3 4
    4 4
    3 6
    2 2
    1 1
    7 3
    2022 2023
    1000000000 1000000000

    输出#1

    1
    3 4
    2
    3 2
    4 4
    2
    5 3
    3 6
    2
    1 0
    2 2
    1
    1 1
    1
    7 3
    1
    2022 2023
    2
    69420420 469696969
    1000000000 1000000000

说明/提示

In the first test case:

(0,0)→(3,4)(0,0) \to (3,4)

In the second test case:

(0,0)→(3,2)→(4,4)(0,0) \to (3,2) \to (4,4)

In the third test case:

(0,0)→(5,3)→(3,6)(0,0) \to (5,3) \to (3,6)

第一个测试用例:

(0,0)→(3,4)(0,0) \to (3,4)

第二个测试用例:

(0,0)→(3,2)→(4,4)(0,0) \to (3,2) \to (4,4)

第三个测试用例:

(0,0)→(5,3)→(3,6)(0,0) \to (5,3) \to (3,6)

输入解题思路,AI测评打分。不知道怎么写?

首页