Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-03SRM350, SRM351, SRM352 (Practice)

SRM 351 CoinsExchange

|  SRM 351 CoinsExchange - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 351 CoinsExchange - hama_DU@TopCoderへの道

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

  • 貪欲法
    • 足りないGold、Silver、Bronzeの順に両替を行いながら埋め合わせる
  • 通ったのがいいがきれいな実装ができなかったので後で確認する。
public class CoinsExchange {
	public int countExchanges(int G1, int S1, int B1, int G2, int S2, int B2) {
		int req = 0;
		if (G2 > G1) {
			int gneed = G2 - G1;
			if (S1 >= 11 * gneed) {
				req += gneed;
				S1 -= 11 * gneed;
			} else {
				int sneed = 11 * gneed - S1;
				if (B1 >= 11 * sneed) {
					req += sneed;
					req += gneed;
					B1 -= 11 * sneed;
					S1 += sneed;
					S1 -= 11 * gneed;
				} else {
					return -1;
				}
			}
		}
		
		if (S2 > S1) {
			int sneed = S2 - S1;
			if (G1 - G2 > 0) {
				int lgold = G1 - G2;
				int needgold = (sneed + 8) / 9;
				if (lgold >= needgold) {
					req += needgold;
					G1 -= needgold;
					S1 += needgold * 9;
				} else {
					req += lgold;
					G1 = G2;
					S1 += lgold * 9;
				}
			}
			if (S2 > S1) {
				sneed = S2 - S1;
				if (B1 >= 11 * sneed) {
					req += sneed;
					B1 -= 11 * sneed;
					S1 += sneed;
				} else {
					return -1;
				}
			}
		}
		
		
		if (B2 > B1) {
			int needbronze = B2 - B1;
			int reqsilver = (needbronze + 8) / 9;
			req += reqsilver;
			if (S1 - S2 >= reqsilver) {
			} else {
				reqsilver -= (S1 - S2); 
				int reqgold = (reqsilver + 8) / 9;
				if (G1 - G2 >= reqgold) {
					req += reqgold;
				} else {
					return -1;
				}
			}
		}	
		return req;
	}
}