TopCoder SRM 351 Div1 Easy countExchanges

問題

最初G1枚の金貨、S1枚の銀貨、B1枚の銅貨を持っている。
これを両替をして、G2枚以上の金貨、S2枚以上の銀貨、B2枚以上の銅貨を持っている状態にしたい。


両替は、1枚の金貨を出して9枚の銀貨を貰う、
1枚の銀貨を出して9枚の銅貨を貰う、
11枚の銀貨を出して1枚の金貨を貰う、
11枚の銅貨を出して1枚の銀貨を貰う、
を好きな回数だけ行うことができる。


必要な両替の回数の最小値を求めよ。
不可能な場合は-1を返せ。

制約条件

G1,S1,B1,G2,S2,B2≦1000000

方針

銀貨を金貨から両替して作り、作った銀貨で金貨を作る、
のような操作は明らかに無駄なので行う必要がない。


すると、G1がG2より少なかったら、銀貨から必ず金貨を作る必要がある。
同様に、B1がB2より少なかったら、銀貨から銅貨を作る必要がある。


最後に、銀貨が足りない分を金貨、銅貨から作る。
金貨から作れる限り金貨から両替したほうが、回数が少なくなるので、
金貨から貪欲に作れるだけ作り、足りない分を銅貨から作る。

ソースコード

class CoinsExchange {
	public:
	int countExchanges(int G1, int S1, int B1, int G2, int S2, int B2) 
	{
		int ans=0;
		while(G1<G2)S1-=11, G1++, ans++;
		while(B1<B2)S1--, B1+=9, ans++;
		while(S1<S2&&G1>G2)G1--, S1+=9, ans++;
		while(S1<S2&&B1-11>=B2)B1-=11, S1++, ans++;
		return S1>=S2?ans:-1;
	}
};