読者です 読者をやめる 読者になる 読者になる

マトリョーシカ的日常

ワクワクばらまく明日のブログ。

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

topcoder

topcoderの過去問を解いた。

</eyes bleeding> - 無料写真検索fotoq
photo by Sean Molin Photography


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

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

TopCoder Statistics - Problem Statement



 以下自分なりの日本語訳

ニックは宝くじが大好き。一組のくじのコストは値段(意味不)。ニックは四つの貨幣を持っていて、その値は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を獲得した。やったー。しかしもっといいアルゴリズムがあるはず。これでは貨幣が増えた場合に大変なことになる。