# UVa 10306

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.