[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;
  
}

[UVa] 167 - The Sultan's Successors

One thing's for sure, Backtracking is damn fun!!! :D
I liked this one a lot. Though I had to take some help for this one. But it still increased a lot of knowledge about Backtracking.

#include <cstdio>
#include <iostream>
#include <iomanip>
using namespace std;

bool col[100], d1[100], d2[100];

class c
{
    public:
    int x, y;
};

c crd[100];

int knt=0, board[100][100];

c lst[1000];

int qplace(int n)
{
    if (n>8)
    {
        for (int i=1 ; i<=8 ; i++)
        {
            lst[knt++]=crd[i];
        }
        return 0;
    }
    for (int k=1 ; k<=8 ; k++)
    {
        if (!col[k] && !d1[n+k] && !d2[n-k+8])
        {
            col[k]=d1[n+k]=d2[n-k+8]=true;
            crd[n].x = n;
            crd[n].y = k;
            qplace(n+1);
            col[k]=d1[n+k]=d2[n-k+8]=false;
        }
    }
    return 0;
}

int main()
{
    int test, i, j, sum, max;
    knt = 0;
    for (i=0 ; i<=100 ; i++)
        col[i]=d1[i]=d2[i]=false;
    qplace(1);
    //cout << knt << endl;



    scanf("%d",&test);
    while (test--)
    {
        for (i=1 ; i<=8 ; i++)
        {
            for (j=1 ; j<=8 ; j++)
            {
                scanf("%d",&board[i][j]);
            }
        }
        max = 0;
        for (i=0 ; i<knt ; i+=8)
        {
            for (j=i, sum=0 ; (j-i)<8 ; j++)
            {
                sum += board[lst[j].x][lst[j].y];
            }
            if (sum>max)
                max = sum;
        }
        cout << setw(5) << max << endl;
    }
    return 0;
}