Cut the Sheet

3.3

3 votes
Math, C++, Basic Math, Observation
Problem

Bob is initially given one sheet of width W and height H. He wants to make at least N pieces from the sheet. He can cut any sheet into two equal pieces along any side of the rectangular sheet such that the value of width and height of the resultant pieces always remain an integer. For example, If the sheet has 2X2 dimensions, he can make two pieces of 1X2 dimensions or two of 2X1 dimensions.

Print Yes if Bob is able to make at least N pieces or No otherwise.

Input Format:

  • The first line contains an integer T, which denotes the number of test cases.
  • The first line of each test case contains three integers W, H, and N denoting the dimensions of the sheet and the least number of pieces Bob has to make.

Output Format:

For each test case, print Yes if Bob is able to make at least N pieces or No otherwise.

Constraints:

1T1051W,H1091N1018

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

First test case:- 
N=2, Bob has a 4X1 sheet. He can first cut the 4X1 sheet into two 2X1 sheets, and then cut each of them into two more sheets of 1X1. As a result, we get four sheets. Here, the answer is Yes as we have at least 3 sheets.

Second test case:-
N=2, Bob has a 1X1 sheet. He can't cut the sheet further. So we are not able to make more than 1 piece and the answer is No.

Editor Image

?