runtah

UVa 471 Magic Numbers

UVa 471 Magic Numbers

Method: Searching, String checking, Bruteforce Solved during ACM Workshop 2012 at my University.

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>


using namespace std;


typedef long long lint;

bool cmp(pair<lint,lint> a, pair<lint,lint> b) {
 
 return (a.first<b.first);
 
}


bool check(lint n) {
 
 bool ver[20];
 char buf[100];
 lint len;
 for (int i=0 ; i<=20 ; i++) ver[i]=false;
 
 sprintf(buf,"%lld",n);
 
 len = strlen(buf);
 
 if (len>10) return false;
 
 for (int i=0 ; i<len ; i++) {
 if ( ver[ buf[i]-0 ] == true ) return false;
 else ver[ buf[i]-0 ] = true;
 }
 return true;
}


int main( void ) {
 
 lint kase, n, i, j, numerator, x, k;
 bool first=true, dis, ver[10];
 
 vector< pair<lint,lint> > lst;
 
 scanf("%lld",&kase);
 
 while (kase--) {
 
 scanf("%lld",&n);
 
 if (n==0) continue;
 
 lst.clear();
 
 for (i=1 ; (n*i)>=0 ; i++) {
 
 numerator = n*i;
 
 x = numerator;
 
 for (k=0 ; x ; k++, x/=10) if (k>10) break; // if length of the current
 if (k>10) { break; } // numerator exceeds 10 the loop ends
 
 if (check(i) && check(numerator)) 
 lst.push_back(make_pair(numerator,i));

 }
 
 sort(lst.begin(),lst.end(),cmp);
 
 if (!first) putchar( );
 first = false;
 for (i=0 ; i<lst.size() ; i++) {
 printf("%lld / %lld = %lld ",lst[i].first,lst[i].second,n);
 }
 
 }
 
 return 0;
 
}

Go to link download