「オイラープロジェクト31～40」の編集履歴（バックアップ）一覧に戻る
オイラープロジェクト31～40 - (2012/09/04 (火) 14:11:23) のソース
*問い31
1,5,10,20,50,100,200の硬貨を使って200を作る方法はいくつあるか？
簡単な問題なので楽々。
#include<stdio.h>
int main(){
int memo[201]={0};
int coins[]={1,2,5,10,20,50,100,200},coin;
memo[0]=1;
for(int i=0;i<8;i++){
coin=coins[i];
for(int j=0;j<=200-coin;j++){
memo[j+coin]+=memo[j];
}
}
printf("%d\n",memo[200]);
}
*問い32
7254は面白い性質を持っている. 39 × 186 = 7254と書け, 掛けられる数/掛ける数/積に1から9の数が1回ずつ出現する.
掛けられる数/掛ける数/積に1から9の数が1回ずつ出現するような積の総和を求めよ.
HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.
条件を満たす組み合わせが１桁*４桁=４桁か
２桁*３桁=４桁しかないのでこの範囲を全探索してチェック関数で条件を満たしているか調べるだけです。
#include<stdio.h>
#include<set>
bool check(int a,int b){
int count[10]={1,0};
int c=a*b;
while(a!=0){
count[a%10]++;
a/=10;
}
while(b!=0){
count[b%10]++;
b/=10;
}
while(c!=0){
count[c%10]++;
c/=10;
}
bool ok=true;
for(int i=0;i<10;i++){
if(count[i]!=1)ok=false;
}
return ok;
}
int main(){
std::set<int> memo;
std::set<int>::iterator it;
for(int a=1;a<10;a++){
for(int b=1000;b<10000;b++){
if(check(a,b)==true){
printf("%d %d %d\n",a,b,a*b);
memo.insert(a*b);
}
}
}
for(int a=10;a<100;a++){
for(int b=100;b<1000;b++){
if(check(a,b)==true){
printf("%d %d %d\n",a,b,a*b);
memo.insert(a*b);
}
}
}
int ans=0;
for(it=memo.begin();it!=memo.end();it++){
ans+=(*it);
}
printf("%d",ans);
}
*問い33
http://projecteuler.net/problem=33
親切なヒントだらけの簡単な問題。
条件を満たす答えが4つとか親切すぎると思う。
ルールが恣意的なせいかコードが膨らんでしまった。
条件を満たす削除を探して無理やり約分して比較。
ルール上数字を二つとも消すというのはないので分岐は楽。
Ｌｉｓｐで書けばもっと簡単？
#include<stdio.h>
int main(){
int ansA=1,ansB=1,aa,bb,aaa,bbb;
for(int a=10;a<100;a++){
for(int b=10;b<a;b++){
if(a%10+b%10==0)continue;
// b/a
if(a%10==b%10){
// bb/aa
aa=a/10;
bb=b/10;
}else if(a/10==b%10){
aa=a%10;
bb=b/10;
}else if(a%10==b/10){
aa=a/10;
bb=b%10;
}else if(a/10==b/10){
aa=a%10;
bb=b%10;
}else{
continue;
}
//if(a==98&&b==49)printf("(%d/%d)",bb,aa);
aaa=a;
bbb=b;
for(int i=2;i<100;i++){
while(aaa%i==0&&bbb%i==0){
aaa/=i;
bbb/=i;
}
while(aa%i==0&&bb%i==0){
aa/=i;
bb/=i;
}
}
if(aaa==aa&&bbb==bb){
printf("<%d/%d>",b,a);
ansA*=a;
ansB*=b;
}
}
}
printf("(%d/%d)",ansB,ansA);
for(int i=2;i<=ansA;i++){
while(ansA%i==0&&ansB%i==0){
ansA/=i;
ansB/=i;
}
}
printf("(%d/%d)",ansB,ansA);
}
*問い34
各桁の階乗の和が元の数と同じになる数の合計値を求める問題。
階乗の和を求める関数をf(n)とするとf(n)は２５０万あたりでｎより小さい値しか返さなくなるので後は力づくでもとめます。
#include<stdio.h>
int last=0;
int p[10];
int calc(int n){
int ans=0;
while(n!=0){
ans+=p[n%10];
n/=10;
}
return ans;
}
int main(){
int i=1;
p[0]=1;
int ans=0,last;
for(int i=1;i<10;i++){
p[i]=p[i-1]*i;
}
for(int i=3;i<6000000;i++){
if(i==calc(i)){
ans+=i;
last=i;
}
}
printf("%d %d",ans,last);
}
*問い35
ある数字の並びを右から左へ巡回させて出来る数を巡回数と呼び、巡回数が全部素数である巡回数を巡回素数という。
１００万以下の巡回素数の数を求めよ。
std::setにsosuuを保管して後は全探索で片が付きました。
#include<stdio.h>
#include<set>
#include<algorithm>
const int up=1000000;
std::set<int> sosuu;
bool so[up];
void setSo(){
int i2;
memset(so,true,sizeof(so));
sosuu.insert(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.insert(i);
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
int main(){
setSo();
int size,n,ans=0,m;
for(std::set<int>::iterator it=sosuu.begin();it!=sosuu.end();it++){
bool ok=true;
n=(*it);
size=0;
m=1;
while(n!=0){
size++;
n/=10;
m*=10;
}
m/=10;
n=(*it);
for(int i=0;i<size;i++){
//printf("%d ",n);
if(sosuu.find(n)==sosuu.end())ok=false;
n=n/10+n%10*m;
}
ans+=ok;
//printf("\n");
}
printf("%d\n",ans);
}
*問い36
１００万以下の2進数で表しても１０進数で表しても左右対称な数の和を求めよ。
１００点満点でいえば多分60点くらいの平凡なコードでクリア。
#include<stdio.h>
#include<iostream>
int rev(int n){
int re=0;
//２０回もビットシフトするとか贅沢だな
while(n!=0){
re<<=1;
re|=(n&1);
n>>=1;
}
return re;
}
int main(){
//この処理も贅沢に
int n,m;
__int64 ans=0;
for(int i=1;i<1000000;i++){
n=i;
m=0;
while(n!=0){
m*=10;
m+=n%10;
n/=10;
}
if(i==m&&rev(i)==i){
printf("%d ",i);
ans+=i;
}
}
std::cout<<"\n"<<ans;
}
*問い37
3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).
右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.
とりあえず100万以下の素数で条件を満たすかチェックする関数で試したところ１１個目が１００万以下で見つかったので答えとしました。
何故１１個しかないと証明できるのか少し不思議です。
上限があると教えるのは何だか親切な問題ですね。
#include<stdio.h>
#include<set>
#include<algorithm>
const int up=1000000;
std::set<int> sosuu;
bool so[up];
void setSo(){
int i2;
memset(so,true,sizeof(so));
sosuu.insert(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.insert(i);
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
bool check(int n){
int r=n,l=n,ten=1;//右から削除、左から削除
while(r>=10){
r/=10;
ten*=10;
if(sosuu.find(r)==sosuu.end()||sosuu.find(l%ten)==sosuu.end())return false;
//printf("(%d %d)",r,l%ten);
}
return true;
}
int main(){
setSo();
int ans=0;
for(std::set<int>::iterator it=sosuu.begin();it!=sosuu.end();it++){
if((*it)<10)continue;
if(check((*it))==true){
printf("(%d)",(*it));
ans+=(*it);
}
}
printf("%d\n",ans);
}
*問い38
192を1, 2, 3で掛けてみよう.
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
積を連結することで1から9のPandigital数 192384576 が得られる. 192384576を 192と(1,2,3)の連結積と呼ぶ.
同じようにして, 9を1,2,3,4,5と掛け連結することでPandigital数918273645が得られる. これは9と(1,2,3,4,5)との連結積である.
整数と(1,2,...,n) (n > 1) との連結積として得られる9桁のPandigital数の中で最大のものを答えよ.
解法
条件を満たす数を全探索してチェック条件を満たしたものをアウトプット、出てきた表をＥｘｃｅｌで処理すれば完了です。
#include<stdio.h>
#include<string.h>
int check(int a,int count[10]){
while(a!=0){
count[a%10]++;
a/=10;
}
//出てきている数の種類を数えて返す関数,条件を満たさなければ-1を返す
int sum=-1;//0をカウントしないようにする
for(int i=0;i<10;i++){
if(count[i]>1)return -1;
sum+=count[i];
}
return sum;
}
int main(){
int count[10],c;//0～9までをカウントする
for(int i=1;i<10000;i++){
//5桁*1=5桁
//5桁*2>=5桁より１０ケタを超えるのでi<10000までしか試す必要がない
memset(count,0,sizeof(count));
count[0]=1;//0は出てきてはならない
for(int j=1;j<10;j++){
c=check(i*j,count);
if(c>9){
break;
}else if(c==9){
printf("%d %d ",i,j);
for(int k=1;k<=j;k++){
printf("%d",i*k);
}
printf("\n");
}
}
}
}
*問い39
辺の長さが{a,b,c}と整数の3つ組である直角三角形を考え, その周囲の長さをpとする. p = 120のときには3つの解が存在する:
{20,48,52}, {24,45,51}, {30,40,50}
p ≦ 1000 で解の数が最大になる p を求めよ.
#include<stdio.h>
int calc(int p){
int ans=0;
for(int a=1;a<=p/3;a++){
for(int b=a;b<=p;b++){
int c=p-a-b;
if(c<=b)break;
if(a*a+b*b==c*c){
printf("(%d %d %d)",a,b,c);
ans++;
}
}
}
if(ans>0)printf("\n");
return ans;
}
int main(){
int ans=0,mymax=0,t;
for(int i=4;i<=1000;i++){
t=calc(i);
if(mymax<t){
mymax=t;
ans=i;
}
}
printf("\n<%d %d>",ans,mymax);
}
*問い40
正の整数を順に連結して得られる以下の10進の無理数を考える:
0.123456789101112131415161718192021...
小数第12位は1である.
dnで小数第n位の数を表す. d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 を求めよ.
コードに落とし込むのに苦労した問題。
我流で到達した方法なのでもっと賢い方法がありそう。
#include<stdio.h>
int main(){
int ups[10];
int base[10];
int calc[10];
int ten=100;
ups[0]=10;
base[0]=10;
for(int i=1;i<7;i++){
ups[i]=ups[i-1]+(ten-ten/10)*(i+1);
base[i]=ten;
ten*=10;
//printf("%d %d\n",ups[i],base[i]);
}
int k,t,point,ans=1;//ans=d1
for(int ten=10;ten<=1000000;ten*=10){
k=ten;
//for(int i=98;i<103;i++){
//k=i;
for(int j=6;j>=0;j--){
if(k>=ups[j]){
k-=ups[j];
t=k/(j+2)+base[j];
point=k%(j+2);
break;
}
}
printf("(%d %d)",t,point);
k=0;
while(t!=0){
calc[k]=t%10;
t/=10;
k++;
}
ans*=calc[k-1-point];
}
printf("%d\n",ans);
}
