No.2393 Bit Grid Connected Component
Problem Statement
There is a grid with $2^{60}-1$ rows and $60$ columns, in which each row is colored black and white according to the binary representation of its row number, as follows.
The cell $(x,y)$ at row number $x$ and column number $y$ is a black cell if the $2^y$ place in the binary representation of $x$ is $1$, and a white cell if it is $0$.
Here, the connected component containing a black cell $(x, y)$ is the set of all black cells that can be reached from $(x, y)$ by moving only through black cells that are adjacent vertically or horizontally.
For each of the $T$ test cases, find the number of black cells belonging to the connected component containing the black cell $(x, y)$.
Input
The input is given from standard input in the following format.$ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $Here, $ case_i $ is the $i$-th test case. Each test case is given in the following format.
$ x\ y $
- $ 1 \le T \le 10^5 $
- $ 1 \le x < 2^{60} $
- $ 0 \le y < 60 $
- $ (x, y) $ is a black cell. That is, the $2^y$ place in the binary representation of $x$ is $1$.
Output
Print $ T $ lines to standard output. On the $ i $-th line ($ i \leq T $), print the answer to the $ i $-th test case. Print a newline at the end.
Sample
Input
2 2 1 7 0
Output
3 7
The connected component containing $(2, 1)$ is $ (2,1),(3,0),(3,1) $, so its size is 3.
The connected component containing $(7, 0)$ is $ (7,0),(6,1),(7,1),(4,2),(5,2),(6,2),(7,2) $, so its size is 7.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。