「オイラープロジェクト81～90」の編集履歴（バックアップ）一覧に戻る

---

「オイラープロジェクト81～90」を以下のとおり復元します。

---

*問い81
http://projecteuler.net/problem=81
正方行列の左上からスタートし右か下に移動しながら右下まで到達するときルートの総計が最小になるルートを取った時の値を答えよ。
動的計画法で瞬殺。


 #include<stdio.h>
 #include<algorithm>
 int main(){
	int a,memo[82][82];
	memset(memo,0,sizeof(memo));
	for(int i=1;i<81;i++){
		for(int j=1;j<81;j++){
			if(j==80)scanf("%d",&a);
			else scanf("%d,",&a);
			if(i==1)memo[i][j]=memo[i][j-1]+a;
			if(j==1)memo[i][j]=memo[i-1][j]+a;
			if(i!=1&&j!=1)memo[i][j]=std::min(memo[i-1][j],memo[i][j-1])+a;
		}
		printf("<%d>",i);
	}
	printf("%d",memo[80][80]);
 }





*問い87
5000万>素数^2+素数^3+素数^4と表現できる数字の個数を答えよ。
読解ミスしてかなり間違えた問題。
5000万未満の数字が何個あるかというところを何通りの式で表すことが出来るかと読解ミスして間違えた。
恥ずかしい。。。





 #include<stdio.h>
 #include<math.h>
 #include<vector>
 #include<set>
 
 const int up=50000000;
 std::vector<int> sosuu;
 
 bool so[7100];//50000000の大雑把な平方根
 
 void setSo(){
 	int i2;
 	memset(so,true,sizeof(so));
 	sosuu.push_back(2);
 	for(int i=3;i<=sqrt(up);i+=2){
 		if(so[i]==false)continue;
 		sosuu.push_back(i);
 		i2=i*2;
 		for(int j=i*3;j<sqrt(up);j+=i2){
 			so[j]=false;
 		}
 	}
 }
 int main(){
 	setSo();
 	//for(int i=0;i<sosuu.size();i++){
 		//printf("%d ",sosuu[i]);
 	//}
 	int t=8,p;
 	std::vector<int> p2,p3,p4;
 	for(int i=1;t<up;i++){
 		p3.push_back(t);
 		p=sosuu[i];
 		t=p*p*p;
 	}
 	t=16;
 	for(int i=1;t<up;i++){
 		p4.push_back(t);
 		p=sosuu[i];
 		t=p*p*p*p;
 	}
 	for(int i=0;i<sosuu.size();i++){
 		p2.push_back(sosuu[i]*sosuu[i]);
 	}
 	for(int i=0;i<p2.size();i++){
 		//printf("%d ",p2[i]);
 	}
 	
 	
 	std::set<int> ans;
 	for(int i=0;i<p4.size();i++){
 		for(int j=0;j<p3.size();j++){
 			t=up-(p4[i]+p3[j])-1;
 			for(int k=0;p2[k]<=t&&k<p2.size();k++){
 				ans.insert(p4[i]+p3[j]+p2[k]);
 			}
 		}
 	}
 	printf("%d",ans.size());
 }

---

復元してよろしいですか？