文化祭１日目

文化祭１日目おわた。
午前中に囲碁２局打って、スーパーカップ食って、数研の懸賞問題をプログラミングで解いてた。
さすがに図形とかは無理っぽいから景品はもらえないだろうけどね。

1,2,3を解いたからそのソースを。
合ってるかどうかは知らん。
3は絶対間違ってる。

１、虫食い算
O(10^N) (N=7)なので、２重ループで全探索やるだけ。
先頭の位が0の場合を排除するのはめんどくさかった（難しくはないが）のでさぼった。

#include<cstdio>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;

int main(){
	int x, y[5], z[5];
	
	y[0] = 1;
	
	rep(i,10000){
		x = i/100*1000 + 100 + i%100;
		rep(j,1000){
			y[1] = j/100;
			y[2] = j/10%10;
			y[3] = j%10;
			y[4] = j+1000;
			
			rep(k,5){
				z[k] = x*y[k];
			}
			
			if(z[0]%10 == 7 && z[1]/100%10 == 6 && z[2]%10 == 3 && z[2]/10000%10 == 2 &&
			   z[3]/10%10 == 2 && z[3]/10000%10 == 0 && z[4]/100%10 == 1){
				printf("%d*%d=%d\n",x,y[4],z[4]);
			}
		}
	}
		
	return 0;
}

２、フィボナッチ数列に出てくる数を使って2011を何通り作れるかっていう問題。
DPやるだけ。
数字は複数回使用不可なのでさらに簡単。
ちょっとムダがあるが、どうせ一瞬で処理終わるので問題なし。

#include<cstdio>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;

vector<int> f;
int dp[5000];

int main(){
	int m = 0;
	dp[0] = 1;
	
	f.pb(1); f.pb(2);
	
	for(int i = 1; f[i] <= 2011; i++){
		f.pb(f[i]+f[i-1]);
	}
	
	
	rep(i,f.size()-1){
		for(int j = m; j >= 0; j--){
			dp[j+f[i]] += dp[j];
		}
		m += f[i];
	}
	
	printf("%d\n",dp[2011]);
	
	return 0;
}

３、お金の問題。
場合の数の問題はほぼ全部DP。
300円300円300円1000円500円500円ってやられるとおつり払えなくなるはずなのに、払えることになってるので、不正解。
じゃあなんでソース載せたんだよっていうね。

#include<cstdio>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;
typedef long long ll;

ll dp[7][6][3];

int main(){
	int x, h;
	
	dp[0][0][0] = 1;
	
	rep(i,13){
		rep(j,i+2){
			rep(k,i-j+2){
				h = i-k-j+1;
				x = h*7 - min(k,h)*5;
				if(h >= 0 && x+k*2 <= j*3){
					if(j) dp[j][k][h] += dp[j-1][k][h]*(7-j);
					if(k) dp[j][k][h] += dp[j][k-1][h]*(6-k);
					if(h) dp[j][k][h] += dp[j][k][h-1]*(3-h);
				}
				if(dp[j][k][h] > 10000000000ll) puts("over.");
			}
		}
	}
	
	printf("%lld\n",dp[6][5][2]);
	
	return 0;
}