当前位置: 首页 > 工具软件 > Friends > 使用案例 >

Problem: Cards for Friends

蒋健
2023-12-01

Description
For the New Year, Polycarp decided to send postcards to all his n friends. He wants to make postcards with his own hands. For this purpose, he has a sheet of paper of size w×h, which can be cut into pieces.
Polycarp can cut any sheet of paper w×h that he has in only two cases:
If w is even, then he can cut the sheet in half and get two sheets of size w2×h;
If h is even, then he can cut the sheet in half and get two sheets of size w×h2;
If w and h are even at the same time, then Polycarp can cut the sheet according to any of the rules above.After cutting a sheet of paper, the total number of sheets of paper is increased by 1.Help Polycarp to find out if he can cut his sheet of size w×h at into n or more pieces, using only the rules described above.
Input
The first line contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.Each test case consists of one line containing three integers w, h, n (1≤w,h≤104,1≤n≤109) — the width and height of the sheet Polycarp has and the number of friends he needs to send a postcard to.
Output
For each test case, output on a separate line:
“YES”, if it is possible to cut a sheet of size w×h into at least n pieces;
“NO” otherwise.
You can output “YES” and “NO” in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).
Sample Input
5
2 2 3
3 3 2
5 10 2
11 13 1
1 4 4
Sample Output
YES
NO
YES
YES
YES
Hint
In the first test case, you can first cut the 2×2 sheet into two 2×1 sheets, and then cut each of them into two more sheets. As a result, we get four sheets 1×1. We can choose any three of them and send them to our friends.
In the second test case, a 3×3 sheet cannot be cut, so it is impossible to get two sheets.
In the third test case, you can cut a 5×10 sheet into two 5×5 sheets.
In the fourth test case, there is no need to cut the sheet, since we only need one sheet.
In the fifth test case, you can first cut the 1×4 sheet into two 1×2 sheets, and then cut each of them into two more sheets. As a result, we get four sheets 1×1.
这题呢,就是只要是将w,h分奇偶讨论;
当两个都为奇数的时候,h只能等于1;
当一奇一偶时,就相当于长度为w或h的绳子被剪断,注意考虑每次剪断之后,一半还是不是偶数,最后对所有的小绳子进行计数,如果比n大或等于n,就能送出去,否则就不够了;
当两个都是偶数时,即将w和h分别剪断,然后相乘即可;
废话不多说,直接上代码:

#include<stdio.h>
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int w,n,h,flag;
		scanf("%d%d%d",&w,&h,&n);
		if(w%2!=0&&h%2!=0)
		{
			if(n==1) flag=1;
			else flag=0;
		}
		else if(w%2==0&&h%2!=0)
		{
			int a=w,c=1;;
			for(int i=1;;i++)
			{
				a=a/2;
				c*=2;
				if(a%2!=0)	break;
			}
			
			if(c>=n) flag=1;
			else  flag=0;
		}
		else if(w%2!=0&&h%2==0)
		{
			int b=h,d=1;;
			for(int i=1;;i++)
			{
				b=b/2;
				d*=2;
				if(b%2!=0)	break;
			}
			
			if(d>=n) flag=1;
			else  flag=0;
		}
		else if(w%2==0&&h%2==0)
		{
			int p=w,q=1;;
			for(int i=1;;i++)
			{
				p=p/2;
				q*=2;
				if(p%2!=0)	break;
			}
			
			int x=h,y=1;;
			for(int i=1;;i++)
			{
				x=x/2;
				y*=2;
				if(x%2!=0)	break;
			}
			
			if(q*y>=n) flag=1;
			else       flag=0;
		}
		if(flag==1) printf("YES\n");
		else printf("NO\n"); 
	}
	return 0;
}
 类似资料:

相关阅读

相关文章

相关问答