PROBLEM LINK:
Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Simple
PREREQUISITES:
Modulo operation
PROBLEM:
Is it possible to cut an R\times C rectangular cake into pieces with areas M, K and J? You are only allowed to cut parallel to the sides, and pieces must remain rectangular with integer sides.
QUICK EXPLANATION:
- If RC \not= M + K + J, the answer is
No, - else, if M, K and J are divisible by R, the answer is
Yes, - else, if M, K and J are divisible by C, the answer is
Yes, - else, if M is divisible by R and K is divisible by (C - M/R), the answer is
Yes, - else, if K is divisible by R and J is divisible by (C - K/R), the answer is
Yes, - else, if J is divisible by R and M is divisible by (C - J/R), the answer is
Yes, - else, if M is divisible by C and K is divisible by (R - M/C), the answer is
Yes, - else, if K is divisible by C and J is divisible by (R - K/C), the answer is
Yes, - else, if J is divisible by C and M is divisible by (R - J/C), the answer is
Yes, - otherwise, the answer is
No.
The first line checks whether the area is exactly what’s needed.
The second and third line checks for two horizontal or two vertical cuts.
The fourth to ninth lines check for one horizontal and one vertical cut.
EXPLANATION
First, for a cut to be possible, it must be the case that M + K + J constitutes the total area of the rectangle. But the total area is RC, so if RC \not= M + K + J, then the answer is immediately No. Thus, in the following, we can assume that RC = M + K + J.
Each cut splits one piece into two pieces, so that means we must perform exactly two cuts. The first cut splits the whole cake into two pieces. The second cut splits one of the pieces into two again. This means that, after the first cut, one of the pieces must have an area of exactly M, K or J. In other words, it must split the whole cake into two pieces of areas (M,K+J), (K,J+M) or (J,M+K).
When is it possible to cut an R\times C piece into two pieces with areas (A,B)? Well, you can cut either horizontally or vertically.
- If you cut horizontally, then the pieces will have dimensions r_1\times C and r_2\times C, where r_1 + r_2 = R. Thus, the following must be true: A = r_1C and B = r_2C. In other words, A and B must be divisible by C.
- If you cut horizontally, then the pieces will have dimensions R\times c_1 and R\times c_2, where c_1 + c_2 = C. Thus, the following must be true: A = Rc_1 and B = Rc_2. In other words, A and B must be divisible by R.
After that, we must split one of the pieces into two parts again, with specific areas. But since we know the dimensions of the piece, this is basically the same problem as above! Therefore, we now have all the tools required to write a complete solution.
We’ll describe it with Python. First, let’s write a function that performs the procedure above:
def possible_splits(R,C,A,B):
# returns all possible dimensions of the second piece if we split an
# R*C rectangle into pieces with areas A and B
dimensions = []
if A % C == 0 and B % C == 0:
r2 = B / C
dimension = (r2,C)
dimensions.append(dimension)
if A % R == 0 and B % R == 0:
c2 = B / R
dimension = (R,c2)
dimensions.append(dimension)
return dimensions
With this function, we can now answer a query:
def query(R, C, M, K, J):
if R*C != M + K + J: # wrong area
return False
# try three possibilities
for r, c in possible_splits(R, C, M, K+J):
if possible_splits(r, c, K, J):
return True
for r, c in possible_splits(R, C, K, J+M):
if possible_splits(r, c, J, M):
return True
for r, c in possible_splits(R, C, J, M+K):
if possible_splits(r, c, M, K):
return True
# nothing worked
return False
This first checks if RC = M + K + J, and if true, tries out all three possible initial splits: (M,K+J), (K,J+M) or (J,M+K). After that, we can simply call the query function to print the answers!
for cas in xrange(input()):
R, C, M, K, J = map(int, raw_input().strip().split())
print 'Yes' if query(R, C, M, K, J) else 'No'
Here is a more compact version:
def possible_splits(R,C,A):
B = R*C - A
if A % C == 0 and B % C == 0: yield B / C, C
if A % R == 0 and B % R == 0: yield R, B / R
def query(R, C, M, K, J):
if R*C != M + K + J: # wrong area
return False
# try three possibilities
for A, B in [(M, K), (K, J), (J, M)]:
for r, c in possible_splits(R, C, A):
if any(possible_splits(r, c, B)):
return True
# nothing worked
return False
The changes here are:
- We made use of Python’s
yieldstatement to not have to collect the dimensions in adimensionsarray. - We removed the
Bparameter inpossible_splits, because it can be extracted from the other parameters from the equation RC = A + B.
Time Complexity:
O(1)