305719: CF1080D. Olya and magical square

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

Description

Olya and magical square

题意翻译

# 题目描述 最近 Olya 收到了一个边长为 $2^n$ 的魔法正方形。 她的姐姐认为一个正方形太无趣了,于是要求 Olya 进行 $k$ 次分割操作。 每次操作,Olya 会选择一个边长不为 $1$ 的正方形,并把这个正方形分割为四个等大的小正方形。 Olya 很开心能满足姐姐的请求,但是她自己也要开心。 Olya 是开心的,当且仅当能从左下角到右上角找到一条正方形边长相同,四联通的路径。 请你输出在这 $k$ 次切割后,路径上正方形的边长。 如果不论怎么切都不能找出一条四联通的正方形边长相同的路径,或者这个正方形不能被切割 $k$ 次,输出 `NO` # 输入格式 第一行一个整数 $t$,表示有 $t$ 组数据。 接下来 $t$ 行,一行两个整数 $n,k$,意义如上文所述。 # 输出格式 对于每组数据,输出一行。 若 $k$ 次切割后能找出一种可行的路径,输出 `YES` 和路径上正方形的边长,如果有多种可能的路径上的正方形的边长,输出任意一种。因为这个边长可能很大,请输出这个边长取关于 2 的对数。 (即,若 $2^k = \text{边长}$,请输出 $k$) 若不能,或者不能切割 $k$ 次,输出 `NO` 所有输出中 `YES` 和 `NO` 的大小写任意。 # 数据范围 $1 \leq t \leq 10^3$ $1 \leq n \leq 10^9$ $1 \leq k \leq 10^{18}$

题目描述

Recently, Olya received a magical square with the size of $ 2^n\times 2^n $ . It seems to her sister that one square is boring. Therefore, she asked Olya to perform exactly $ k $ splitting operations. A Splitting operation is an operation during which Olya takes a square with side $ a $ and cuts it into 4 equal squares with side $ \dfrac{a}{2} $ . If the side of the square is equal to $ 1 $ , then it is impossible to apply a splitting operation to it (see examples for better understanding). Olya is happy to fulfill her sister's request, but she also wants the condition of Olya's happiness to be satisfied after all operations. The condition of Olya's happiness will be satisfied if the following statement is fulfilled: Let the length of the side of the lower left square be equal to $ a $ , then the length of the side of the right upper square should also be equal to $ a $ . There should also be a path between them that consists only of squares with the side of length $ a $ . All consecutive squares on a path should have a common side. Obviously, as long as we have one square, these conditions are met. So Olya is ready to fulfill her sister's request only under the condition that she is satisfied too. Tell her: is it possible to perform exactly $ k $ splitting operations in a certain order so that the condition of Olya's happiness is satisfied? If it is possible, tell also the size of the side of squares of which the path from the lower left square to the upper right one will consist.

输入输出格式

输入格式


The first line contains one integer $ t $ ( $ 1 \le t \le 10^3 $ ) — the number of tests. Each of the following $ t $ lines contains two integers $ n_i $ and $ k_i $ ( $ 1 \le n_i \le 10^9, 1 \le k_i \le 10^{18} $ ) — the description of the $ i $ -th test, which means that initially Olya's square has size of $ 2^{n_i}\times 2^{n_i} $ and Olya's sister asks her to do exactly $ k_i $ splitting operations.

输出格式


Print $ t $ lines, where in the $ i $ -th line you should output "YES" if it is possible to perform $ k_i $ splitting operations in the $ i $ -th test in such a way that the condition of Olya's happiness is satisfied or print "NO" otherwise. If you printed "YES", then also print the $ log_2 $ of the length of the side of the squares through space, along which you can build a path from the lower left square to the upper right one. You can output each letter in any case (lower or upper). If there are multiple answers, print any.

输入输出样例

输入样例 #1

3
1 1
2 2
2 12

输出样例 #1

YES 0
YES 1
NO

说明

In each of the illustrations, the pictures are shown in order in which Olya applied the operations. The recently-created squares are highlighted with red. In the first test, Olya can apply splitting operations in the following order: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1080D/89bc3c86a78536f9d1b61fef81bfdb403a8001e2.png) Olya applies one operation on the only existing square.The condition of Olya's happiness will be met, since there is a path of squares of the same size from the lower left square to the upper right one: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1080D/cd53b9729624bc071dac2ed0c057589be03095ee.png)The length of the sides of the squares on the path is $ 1 $ . $ log_2(1) = 0 $ . In the second test, Olya can apply splitting operations in the following order: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1080D/df1d6e948d0345fb71762d3c12c1e30364985c65.png) Olya applies the first operation on the only existing square. She applies the second one on the right bottom square.The condition of Olya's happiness will be met, since there is a path of squares of the same size from the lower left square to the upper right one: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1080D/30f32350a25d720053ea3a26e869142689d6dc53.png)The length of the sides of the squares on the path is $ 2 $ . $ log_2(2) = 1 $ . In the third test, it takes $ 5 $ operations for Olya to make the square look like this: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1080D/0d23223ff71c3d3fee015cd0e5ef0cde7dde50d6.png)Since it requires her to perform $ 7 $ splitting operations, and it is impossible to perform them on squares with side equal to $ 1 $ , then Olya cannot do anything more and the answer is "NO".

Input

题意翻译

# 题目描述 最近 Olya 收到了一个边长为 $2^n$ 的魔法正方形。 她的姐姐认为一个正方形太无趣了,于是要求 Olya 进行 $k$ 次分割操作。 每次操作,Olya 会选择一个边长不为 $1$ 的正方形,并把这个正方形分割为四个等大的小正方形。 Olya 很开心能满足姐姐的请求,但是她自己也要开心。 Olya 是开心的,当且仅当能从左下角到右上角找到一条正方形边长相同,四联通的路径。 请你输出在这 $k$ 次切割后,路径上正方形的边长。 如果不论怎么切都不能找出一条四联通的正方形边长相同的路径,或者这个正方形不能被切割 $k$ 次,输出 `NO` # 输入格式 第一行一个整数 $t$,表示有 $t$ 组数据。 接下来 $t$ 行,一行两个整数 $n,k$,意义如上文所述。 # 输出格式 对于每组数据,输出一行。 若 $k$ 次切割后能找出一种可行的路径,输出 `YES` 和路径上正方形的边长,如果有多种可能的路径上的正方形的边长,输出任意一种。因为这个边长可能很大,请输出这个边长取关于 2 的对数。 (即,若 $2^k = \text{边长}$,请输出 $k$) 若不能,或者不能切割 $k$ 次,输出 `NO` 所有输出中 `YES` 和 `NO` 的大小写任意。 # 数据范围 $1 \leq t \leq 10^3$ $1 \leq n \leq 10^9$ $1 \leq k \leq 10^{18}$

加入题单

上一题 下一题 算法标签: