UVa 10306

From Algorithmist
Jump to navigation Jump to search

10306 - e-Coins[edit]

Summary[edit]

Given m types of coin, each of which have two values (Xi and Yi).

You are to print the minimum number of coins to be selected (of any type and amount) such that sum(Xi)^2 + sum(Yi)^2 is equal to S^2.

Explanation[edit]

Use Dynamic Programming to find the minimum number of coins to form (X,Y).

Brute force among all possible values of (X,Y) such that X^2 + Y^2 == S^2 and dp[X][Y] is minimum.