宝くじ大好きニックくんは算数ができない（Topcoder SRM 466 div2 250pt）

topcoderの過去問を解いた。

photo by Sean Molin Photography

TopCoder, Inc.TopCoder, Inc. | Home of the world's largest development community

　topcoderという競技プログラミングの過去問を解いた。頭からやっていこうと思ったが、なぜか過去問を四つしか選べなかったのでSRM466を選択。問題文を引用する。

　以下自分なりの日本語訳

ニックは宝くじが大好き。一組のくじのコストは値段（意味不）。ニックは四つの貨幣を持っていて、その値はb1,b2,b3そしてb4である（どれかの値が同じである可能性もある）。彼はおつりを出さずに一組のくじを買えるかを知りたい。言い換えるなら、彼は自分が持っている貨幣の組み合わせでくじの代金を払いたいということだ。可能なら"POSSIBLE"を返し、不可能なら"IMPOSSIBLE"を返す。（すべての相場は明確である）

定義
Class: LotteryTicket
Method: buy
Parameters: int, int, int, int, int （全て整数型）
Returns: String　（文字列）
Method signature: String buy(int price, int b1, int b2, int b3, int b4)
(be sure your method is public)

制約

くじの値段(price)は1~4000

b1, b2, b3, b4 はそれぞれ1~1000

　はじめ四つの貨幣を四種類の貨幣と勘違いし、難しそうだと思ったが和訳するうちにそうではないと気づいた。貨幣を払うパターンは
四つ全て：1通り　
三つ：4通り
二つ：6通り
一つ：4通り
　の計15通り。それほど多くないので力技で条件分岐を書くことに。

#line 41 "LotteryTicket.cpp"
#include 
#include 
#include 

using namespace std;
class LotteryTicket {
public:
	string buy(int price,int b1,int b2,int b3,int b4) {
		char output[100];
		//しらみつぶしにやってみる
		if(price > (b1+b2+b3+b4)) {goto dame;}
		if(price == (b1+b2+b3+b4)){goto ok;}
		if (price == b1+b2+b3 || price ==b1+b2+b4 
			||price == b1+b3+b4 || price == b2+b3+b4){goto ok;}
		
		if(price == b1+b2 || price == b1+b3 || price == b1+b4
		   || price == b2+b3 || price == b2+b4 || price==b3+b4){goto ok;}
		
		if(price == b1 || price == b2 || price == b3 || price == b4){goto ok;}
		
		goto dame;
	
	ok:
		sprintf(output,"POSSIBLE");goto kekka;
	dame:
		sprintf(output,"IMPOSSIBLE");goto kekka;
	kekka:
		puts(output);
		return string(output);
	}
};
int main(){
	LotteryTicket t1;
	int p,j1,j2,j3,j4;
	scanf("%d%d%d%d%d",&p,&j1,&j2,&j3,&j4);
	t1.buy(p,j1,j2,j3,j4);
	return 0;
}

（提出したコードはmain関数とputs(output)は消してある。）
248.16/250　ptを獲得した。やったー。しかしもっといいアルゴリズムがあるはず。これでは貨幣が増えた場合に大変なことになる。