2.23. Helping Deroro

Deroro wants to construct a very wide 2d geometric shape, whose width is \(W\). He has an infinite number of rectangle blocks that have \(A\) width and \(B\) height. He can only use these blocks to construct the shape he wants.

Deroro will put the rectangle blocks he has next to each other to construct the shape he wants. There are 2 ways Deroro can add blocks to the shape:

• Vertically: Construction’s width will be increased by the block’s height \(B\).

• Horizontally: Construction’s width will be increased by the block’s width \(A\).

For instance, when Deroro’s rectangle block’s width is 2 (\(A=2\)) and height is 3 (\(B=3\)) as in the figure above. He can put one block horizontally, and 5 blocks vertically next to each other to construct a shape whose total width is 13 (\(W=1*3+5*2\)) like the following figure:

Write a program that takes 3 integers as width of the shape, height and width of the given blocks in consecutive 3 lines and determines whether the shape can be constructed or not. If the shape can be built, the program must output “YES”, otherwise the output must be “NO”.

Hint: You can try all the possible permutations to find the answer.

Sample I/O:

Input:
19
5
3

Output:
YES

Input:
97
12
17

Output:
YES

Input:
97
12
18

Output:
NO

Input:
1000000
3
6

Output:
NO

Show the Answer

W = int(input())
A = int(input())
B = int(input())

result = False

for i in range(0, W+1, A):    # notice the 3rd argument as step-size in the range function
    for j in range(0, W+1, B):
        if(i + j == W):
            result = True

if result == True:
    print("YES")
else:
    print("NO")