[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('\n');
 first = false;
 for (i=0 ; i<lst.size() ; i++) {
   printf("%lld / %lld = %lld\n",lst[i].first,lst[i].second,n);
 }
 
  }
  
  return 0;
  
}