問い31
イギリスの硬化を使って200ペンスを作る方法は何通りか?
解法
動的計画法の練習問題そのもので計算量はたったの1600回で終わります。
計算回数数億回以下なら1秒以内で答えが出るので何も考えることがありません。
#include<stdio.h>
int main(){
int memo[201]={1,0},coins[8]={1,2,5,10,20,50,100,200};
for(int i=0;i<8;i++){
for(int m=0;m+coins[i]<=200;m++){
memo[m+coins[i]]+=memo[m];
}
}
printf("%d",memo[200]);
}
問い32
解法
再帰関数で解いてみましたが何だかコードが綺麗ともいいがたく。
解くだけなら簡単、エレガントに解くのは難しい。
綺麗なコード思いつかないな。
再帰関数でa*bのaとbを決めて、後はaとbの桁数とa*bの桁数の合計が9ケタなら条件を満たしているか調べるだけす。
spents配列で使用済みの数字を記録し再帰関数の中で使用済み未使用を判別しながら全探索です。
c++ コード実行時間 0.032秒、普通にループ回した方が早いかも。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<set>
#include<time.h>
bool spents[10]={true};
std::set<int> memo;
void saiki(int a,int b,int multA,int multB,int aKeta,int bKeta){
if(a>b)return;
char num[30];
sprintf(num,"%d",a*b);
int keta=aKeta+bKeta+strlen(num);
if(keta>9||aKeta>=5||bKeta>=5)return;
if(keta==9){
bool oks[10];
memcpy(oks,spents,sizeof(oks));
for(int i=0;i<strlen(num);i++){
if(oks[num[i]-'0']==true)return;
oks[num[i]-'0']=true;
}
memo.insert(a*b);
}else{
for(int i=1;i<10;i++){
if(spents[i]==false){
spents[i]=true;
saiki(a+multA*i,b,multA*10,multB,aKeta+1,bKeta);
saiki(a,b+multB*i,multA,multB*10,aKeta,bKeta+1);
spents[i]=false;
}
}
}
}
int main(){
double start=clock();
for(int i=1;i<10;i++)spents[i]=false;
saiki(0,0,1,1,0,0);
int ans=0;
for(std::set<int>::iterator it=memo.begin();it!=memo.end();it++){
ans+=(*it);
}
printf("%d %lf",ans,clock()-start);
}
解法2
ループにしてみました。
そんなに速度アップした感じがしません。
いくつか計算してみると分かりますが1桁*4桁=4桁か2桁*3桁=4桁のみ考慮すればよいようです。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
int main(){
double start=clock();
char num[30];
bool spents[10];
int oks[10000]={0};
int ans=0;
for(int a=1;a<100;a++){
for(int b=100;b<10000;b++){
if(a*b>=10000)break;
sprintf(num,"%d%d%d",a,b,a*b);
if(strlen(num)==9){
memset(spents,false,sizeof(spents));
spents[0]=true;
bool ok=true;
for(int i=0;i<9;i++){
if(spents[num[i]-'0']==true){
ok=false;
break;
}
spents[num[i]-'0']=true;
}
if(ok==true)oks[a*b]=a*b;
}
}
}
for(int i=1000;i<10000;i++)ans+=oks[i];
printf("%d %lf",ans,clock()-start);
}
問い33
解法
簡単な問題ですがコードを短くしようとするとちょっとした難問になります。
コードを短くするには問題の特殊性に着目するしかありません。
検討するのもめんどくさかったので、素朴に定義通り計算して全パタンを検討してみました。
#include<stdio.h>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
int main(){
int m1,m2,ansD=1,ansU;
for(int a1=10;a1<100;a1++){
for(int a2=a1+1;a2<100;a2++){
int k=gcd(a1,a2);
if(k%10==0||a1%11==0||a2%11==0)continue;
m1=a1/k;
m2=a2/k;
if(a1%10==a2/10){
int k2=gcd(a1/10,a2%10);
if((a1/10)/k2==m1&&(a2%10)/k2==m2){
ansD*=m2;
ansU*=m1;
printf("(%d %d)",a1,a2);
}
}
if(a1/10==a2%10){
int k2=gcd(a1%10,a2/10);
if((a1%10)/k2==m1&&(a2/10)/k2==m2){
ansD*=m2;
ansU*=m1;
printf("(%d %d)",a1,a2);
}
}
}
}
printf("ans=%d",ansD/gcd(ansU,ansD));
}
問い34
各桁の階乗の和が元の数と同じになる数の和を求めよ。
解法
文字列になおして足し算していきます。
9,99,999,9999,99999,999999、、がその桁での階乗の和の最大値を与えますが、999999の各桁の階乗の和は2540160となり9999999より小さくなることが分かります。
つまり2540160より大きな数を検討する必要はありません。
なので後は全部チェックするだけです。
条件を満たす数はたった2つしかないので何か手計算か動的計画法でも答えが出そうな気もします。
#include<stdio.h>
#include<stdlib.h>
int main(){
int facts[10]={1,1,2,6,24,120,720,5040,40320,362880};
char num[20];
int ans=0;
for(int i=3;i<=2540160;i++){
sprintf(num,"%d",i);
int sum=0;
for(int j=0;num[j]!='\0';j++){
sum+=facts[num[j]-'0'];
}
if(i==sum){
printf("%d ",i);
ans+=i;
}
}
printf("\nans=%d",ans);
}
問い35
百万以下の巡回素数の数を求めよという問題。
解法
最初に百万以下の素数を全て求めisPrime[m]=mが素数ならtrueを返す配列にセットします。
後は2の場合を最初に答えに足しておいて、後は百万以下の全ての奇数で条件を満たす数をチェックして足していきます。
0を含む素数を巡回すると末尾が0になるので0を含む素数は巡回素数になりません。
これに注意して求めます。
#include<stdio.h>
#include<string.h>
const int up=1000*1000;
bool isPrime[up+1];
void setPrime(){
memset(isPrime,true,sizeof(isPrime));
isPrime[0]=isPrime[1]=false;
for(int i=4;i<=up;i+=2)isPrime[i]=false;
for(int i=3;i<=up;i+=2){
if(isPrime[i]==false)continue;
for(int j=i*3;j<=up;j+=2*i)isPrime[j]=false;
}
}
int isAllSlideOk(int n){
if(isPrime[n]==false)return false;
int mask=1;
while(mask<=n){
if((n/mask)%10==0)return false;//0を含む数をスライドすると末尾の数字が0になるので条件を満たさず
mask*=10;
}
int base=10;
int num=n;
while(base<mask){
num=(num*10)%mask+num/(mask/10);
if(isPrime[num]==false)return false;
base*=10;
}
return true;
}
int main(){
int ans=1,num;
setPrime();
for(int i=3;i<=up;i+=2){
ans+=isAllSlideOk(i);
}
printf("%d",ans);
}
問い36
解法
10進数の回文数だけ生成して後はこれが2進数でも正しいか調べれば計算量が落ちます。
その代わりコードが膨らみました。
もうちょっときれいなコードってなんでしょうね。
#include<stdio.h>
int BitRev(int num){
int rev=0;
for(int b=1;b<=num;b*=2){
rev*=2;
if((num&b)!=0)rev+=1;
}
return rev;
}
int main(){
int ans=0;
for(int a=1;a<1000;a++){
//2,4,6桁
int num,num2;
if(a>=100){
num=(a/100)+((a/10)%10)*10+(a%10)*100;
num2=num+a*1000;
}else if(a>=10){
num=a/10+(a%10)*10;
num2=num+a*100;
}else{
num=a;
num2=num+a*10;
}
if(num2==BitRev(num2)){
ans+=num2;
printf("%d ",num2);
}
//3桁、5桁
if(a<100){
for(int j=0;j<10;j++){
if(a>=10){
num2=num+j*100+a*1000;
}else{
num2=num+j*10+a*100;
}
if(num2==BitRev(num2)){
ans+=num2;
printf("%d ",num2);
}
}
}
}
for(int i=1;i<10;i++){
if(BitRev(i)==i){
ans+=i;
printf("%d ",i);//1桁
}
}
printf("\nans=%d",ans);
}
問い37
3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).
右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.
注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.
解法
小さな数字から生成しようとしたのですが、意外とルールが難しく。
もしかしたら生成に使う記憶用vectorのサイズが1億とか10億までメモする必要もあるかもしれない。
その危険性を考え素朴に小さい数から全部確かめることにしました。
#include<stdio.h>
#include<time.h>
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
bool check(int n){
int num=n;
while(num!=0){
if(isPrime(num)==false)return false;
num/=10;
}
num=n;
int mask=1;
while(mask<=num)mask*=10;
while(num!=0){
if(isPrime(num)==false)return false;
num=((num*10)%mask)/10;
mask/=10;
}
return true;
}
int main(){
int count=0,ans=0;
double start=clock();
for(int i=10;count!=11;i++){
if(check(i)==true){
printf("(%d %d)\n",count,i);
count++;
ans+=i;
}
}
printf("ans=%d time=%lf",ans,clock()-start);
}
問い38
解法
これも全部の場合を試してもわずか10万回の計算量で済みます。
なので手っ取り早くコードを書きました。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
bool check(char num[30]){
bool spents[10];
memset(spents,false,sizeof(spents));
spents[0]=true;
for(int i=0;i<9;i++){
if(spents[num[i]-'0']==true)return false;
spents[num[i]-'0']=true;
}
return true;
}
int toInt(char num[30]){
int re=0;
for(int i=0;num[i]!='\0';i++){
re*=10;
re+=num[i]-'0';
}
return re;
}
int main(){
int ans=0;
for(int a=1;a<=9999;a++){
char num[30],next[30];
num[0]='\0';
for(int i=1;strlen(num)<9;i++){
sprintf(next,"%s%d",num,a*i);
memcpy(num,next,sizeof(next));
}
int n=toInt(num);
if(strlen(num)==9&&check(num)==true&&ans<n){
ans=n;
}
}
printf("ans=%d",ans);
}
問い39
辺の長さが {a,b,c} と整数の3つ組である直角三角形を考え, その周囲の長さを p とする. p = 120のときには3つの解が存在する:
{20,48,52}, {24,45,51}, {30,40,50}
p ≤ 1000 のとき解の数が最大になる p はいくつか?
解法
原始ピタゴラス数の公式で条件を満たす周長を求め1倍以上の定数倍をカウントして集計します。
それだけです。
#include<stdio.h>
int GCD(int a, int b){
while( 1 ){
a = a % b;
if( a == 0 )return b;
b = b % a;
if( b == 0 )return a;
}
}
int main(){
int memo[1001]={0},ansCount=0,ansLen=0;
for(int m=2;m*m+1*1+m*m-1*1+2*m*1<=1000;m++){
for(int n=1;n<m;n++){
int a=m*m-n*n;
int b=2*m*n;
int c=m*m+n*n;
int l=a+b+c;
if(l>1000)break;
if(GCD(n,m)!=1 || (m-n)%2==0)continue;
while(l<=1000){
memo[l]++;
if(memo[l]>ansCount){
ansCount=memo[l];
ansLen=l;
}
l+=a+b+c;
}
}
}
printf("ans=%d %d",ansLen,ansCount);
}
問い40
正の整数を順に連結して得られる以下の10進の無理数を考える:
0.123456789101112131415161718192021...
小数第12位は1である.
dnで小数第n位の数を表す. d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 を求めよ.
解法
一ケタ目の終わりは9文字目、2桁目の終わりは90*2+9文字目、3桁目の終わりは900*3+90*2+9文字目、、。
後はこの数字をつかって何桁目の何個目の数字のどのポイントかを素朴に計算してみました。
もしかしたらこんなめんどくさいことをしなくてもモジュラ演算だけで片がつくかもしれません。
#include<stdio.h>
int mod[10]={0,0};
int base[10]={1};
int getKeta(int n){
int p=0;
while(mod[p+1]<=n-1)p++;
n=n-mod[p];
int m=(n-1)/(p+1)+base[p];
char text[20];
sprintf(text,"%d",m);
return text[(n-1)%(p+1)]-'0';
}
int main(){
int b=1,sum=0;
for(int i=1;i<=6;i++){
mod[i]=mod[i-1]+9*b*i;
b*=10;
base[i]=b;
}
int ans=1;
for(int b=1;b<=1000*1000;b*=10){
ans*=getKeta(b);
}
printf("%d",ans);
}
最終更新:2012年12月21日 03:08