Coins
Time limit2sMemory limit256 MB
Count ordered pairs of coin denominations (x, y) such that some combination of coins, where each coin of value y he counted as value x, sums to T while his count sums to S.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Math, Combinatorics, Number theory
- Solved
- No attempts yet
Problem
Ankh-Morpork is a huge city with brisk trade. Ships from the farthest countries call at its port. As a result, a large number of coins from different states are in circulation. To simplify trade, every coin has a fixed exchange rate against the city's official currency, the Ankh-Morpork dollar. We call this rate the denomination of the coin.
This variety means that even the most experienced citizens sometimes confuse coins with one another. The wizard Rincewind recently paid T dollars for a new hat instead of the required S. By the time he noticed, the shopkeeper was long gone.
Rincewind believes he mistook some coin for another, say a doubloon for a sterling. Each time he thought he was counting out sterlings, he was actually handing over doubloons, and he paid no real sterlings. For example, Rincewind could have thought he paid one doubloon and two sterlings when in fact he handed over three doubloons.
Rincewind wonders how many pairs of coins exist such that, mistaking the first coin for the second, he could pay exactly T dollars instead of S, as he had counted.
For example, if the coins in circulation have denominations of one, two, and three dollars, and Rincewind paid ten dollars instead of nine, he could have done this by mistaking coins of denomination two for coins of denomination one and paying, for instance, four coins of denomination two and one coin of denomination two that he mistook for a coin of denomination one. He could also have mistaken coins of denomination three for coins of denomination two and paid seven coins of denomination one and one coin of denomination three that he mistook for a coin of denomination two.
And if the coins in circulation have denominations of two, three, and four dollars, and Rincewind paid eleven dollars instead of ten, he could have done this by mistaking coins of denomination three for coins of denomination two and paying two coins of denomination four and one coin of denomination three that he mistook for a coin of denomination two.
Input
The first line contains three integers S, T, and n (1 ≤ S, T ≤ 10000; S ≠ T; 1 ≤ n ≤ 200): the price of the hat, the amount Rincewind spent, and the number of coins.
The next line contains n integers a1, a2, ..., an, the denominations of the coins (1 ≤ ai ≤ 10000). No two coins have the same denomination.
Output
Print the number of pairs of coins such that, mistaking the first coin for the second, Rincewind could pay T dollars instead of S.