Skip to content

Instantly share code, notes, and snippets.

@nyuichi
Created June 12, 2012 14:12
Show Gist options
  • Save nyuichi/2917777 to your computer and use it in GitHub Desktop.
Save nyuichi/2917777 to your computer and use it in GitHub Desktop.
/*
@utatakiyoshi: 友達がSkypeで「0~9を1回ずつ使い,?????/?????=1/9となるように?を埋めよ」って算数パズルを出してきたからC++でサクッと書いてドヤ顔してやった
ちなみにこうなった
result: 6381 57429
result: 6471 58239
result: 8361 75249
result: 10638 95742
result: 10647 95823
result: 10836 97524
*/
#include <cstdio>
#include <cstdlib>
int gcd(int a,int b){
if(b==0)return a;
if(a<b)return gcd(b,a);
else return gcd(b,a%b);
}
int d[10];
int r[10];
void solve(int n){
if(n==10){
int A=0,B=0;
for(int i=0;i<5;i++) A=A*10+r[i];
for(int i=5;i<10;i++) B=B*10+r[i];
int G=gcd(A,B);
if(A/G==1&&B/G==9){
printf("result: %d %d\n",A,B);
}
return;
}
for(int i=0;i<10;i++){
if(d[i]==0){
r[n]=i;
d[i]=1;
solve(n+1);
d[i]=0;
}
}
}
int main(){
solve(0);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment