308997: CF1610A. Anti Light's Cell Guessing

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Anti Light's Cell Guessing

题意翻译

蓝邀请你和她玩一个游戏: 有一个 $n\times m$ 的网格。她在心里想了网格中的一个坐标 $(x,y)$。 为了猜出坐标 $(x,y)$,你可以选出 $k$ 个坐标 $(x_1,y_1),(x_2,y_2),\dots,(x_k,y_k)$,然后蓝会算出并告诉你一个长度为 $k$ 的数组 $b$,满足 $b_i=|x-x_i|+|y-y_i|$。 现在你对于 $k$ 的最小值很感兴趣。对于给出的 $n,m$,试着求出最小的 $k$,使得存在一种选出 $k$ 个坐标的方案,使得无论蓝心中想的 $(x,y)$ 是什么样的,你都能将其猜出。 本题多组数据,数据组数为 $t$,会在输入的开头给出。对于每组数据,蓝会依次告诉你 $n$ 和 $m$。你需要输出最小的 $k$。 题目数据满足:$1 \leq t \leq 10^4$,$1 \leq n,m \leq 10^9$。

题目描述

You are playing a game on a $ n \times m $ grid, in which the computer has selected some cell $ (x, y) $ of the grid, and you have to determine which one. To do so, you will choose some $ k $ and some $ k $ cells $ (x_1, y_1),\, (x_2, y_2), \ldots, (x_k, y_k) $ , and give them to the computer. In response, you will get $ k $ numbers $ b_1,\, b_2, \ldots b_k $ , where $ b_i $ is the manhattan distance from $ (x_i, y_i) $ to the hidden cell $ (x, y) $ (so you know which distance corresponds to which of $ k $ input cells). After receiving these $ b_1,\, b_2, \ldots, b_k $ , you have to be able to determine the hidden cell. What is the smallest $ k $ for which is it possible to always guess the hidden cell correctly, no matter what cell computer chooses? As a reminder, the manhattan distance between cells $ (a_1, b_1) $ and $ (a_2, b_2) $ is equal to $ |a_1-a_2|+|b_1-b_2| $ .

输入输出格式

输入格式


The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows. The single line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 10^9 $ ) — the number of rows and the number of columns in the grid.

输出格式


For each test case print a single integer — the minimum $ k $ for that test case.

输入输出样例

输入样例 #1

2
2 3
3 1

输出样例 #1

2
1

说明

In the first test case, the smallest such $ k $ is $ 2 $ , for which you can choose, for example, cells $ (1, 1) $ and $ (2, 1) $ . Note that you can't choose cells $ (1, 1) $ and $ (2, 3) $ for $ k = 2 $ , as both cells $ (1, 2) $ and $ (2, 1) $ would give $ b_1 = 1, b_2 = 2 $ , so we wouldn't be able to determine which cell is hidden if computer selects one of those. In the second test case, you should choose $ k = 1 $ , for it you can choose cell $ (3, 1) $ or $ (1, 1) $ .

Input

题意翻译

蓝邀请你和她玩一个游戏: 有一个 $n\times m$ 的网格。她在心里想了网格中的一个坐标 $(x,y)$。 为了猜出坐标 $(x,y)$,你可以选出 $k$ 个坐标 $(x_1,y_1),(x_2,y_2),\dots,(x_k,y_k)$,然后蓝会算出并告诉你一个长度为 $k$ 的数组 $b$,满足 $b_i=|x-x_i|+|y-y_i|$。 现在你对于 $k$ 的最小值很感兴趣。对于给出的 $n,m$,试着求出最小的 $k$,使得存在一种选出 $k$ 个坐标的方案,使得无论蓝心中想的 $(x,y)$ 是什么样的,你都能将其猜出。 本题多组数据,数据组数为 $t$,会在输入的开头给出。对于每组数据,蓝会依次告诉你 $n$ 和 $m$。你需要输出最小的 $k$。 题目数据满足:$1 \leq t \leq 10^4$,$1 \leq n,m \leq 10^9$。

加入题单

上一题 下一题 算法标签: