TopCoder problem "SolvingEquation" used in TCHS SRM 45 (Division I Level One)



Problem Statement

    You are given the following equation:

A * x + B * y + C * z = W

where x, y and z are integers greater than or equal to 0. Return the minimal possible sum x + y + z, or -1 if a solution does not exist.
 

Definition

    
Class:SolvingEquation
Method:solve
Parameters:int, int, int, int
Returns:int
Method signature:int solve(int A, int B, int C, int W)
(be sure your method is public)
    
 

Constraints

-A, B, C and W will each be between 1 and 100, inclusive.
 

Examples

0)
    
1
2
3
5
Returns: 2
The solution that minimizes x + y + z is x = 0, y = 1 and z = 1. 1*0 + 2*1 + 3*1 = 5. The return value is x + y + z = 0 + 1 + 1 = 2.
1)
    
1
2
3
10
Returns: 4
The best solution here is x = 1, y = 0 and z = 3.
2)
    
3
3
5
7
Returns: -1
There is no solution for the equation 3*x + 3*y + 5*z = 7.
3)
    
1
1
1
100
Returns: 100
4)
    
1
10
20
99
Returns: 14
5)
    
100
100
1
1
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8141

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10799&pm=8141

Writer:

Relja

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Simple Search, Iteration