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

文化祭1日目

programming 雑談

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


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


1、虫食い算
O(10^N) (N=7)なので、2重ループで全探索やるだけ。
先頭の位が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;
}

2、フィボナッチ数列に出てくる数を使って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;
}

3、お金の問題。
場合の数の問題はほぼ全部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;
}