Show all combinations of numbers from 1 to 9 that add up to 100 by adding, subtracting and concatenating

So, this week I saw a blog post somewhere where the poster claimed that if you can't solve the mentioned 5 problems each in under and hour, you ain't no programmer, dev or software engineer. So, I went in and read the problems. 1-4 were easy but number 5 got me a worrying a little. And expected, I failed to solve that in under 1 hour yesterday. But today morning I solved that in less than 30 minutes. But whatever, I can't call myself a programmer anymore :(
Here's my approach though, using recursion:
Each i (from 1 through 9) has 2 different ways of connecting to the sequence.
1. Add itself to the closest sum (1 + 23 + 4 + .......)
2. Or concatenate itself (1 + 234 + ......)
So if we either add an i to the sequence that has reached it or we concatenate. Examples: .......8 + 9
.......89
Now the part before 8 has the same behavior with 8
.......7 + 8
.......78
This goes all the way back to 1 and 2
1 + 2
12
So, the program works something like this

Each branch ultimately ends on the leftmost call.
Code:

#include <cstdio>
#include <iostream>
#include <sstream>

using namespace std;

string i2s(int i) {
    stringstream op;
    op << i;
    return op.str();
}

int solveS(int i, int sum, string p) {

    if (i >= 10) {
        if (sum == 100) {
            cout << p + " = " << sum << endl;
        }
        return 0;
    }

    int iSum = 0;
    for (int j = i ; j<=9 ; j++) {
        iSum = iSum * 10 + j;
        if (i == 1) {
            solveS(j+1, iSum, i2s(iSum));
        } else {
            solveS(j+1, sum+iSum, p + " + " + i2s(iSum));
            solveS(j+1, sum-iSum, p + " - " + i2s(iSum));
        }
    }

    return 0;
}

int main() {

    //freopen("output.txt", "w+", stdout);

    solveS(1, 0, "");

    return 0;
}

[UVa] 543 - Goldbache's Conjecture

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
#define PMAX 1000010
bool ver[PMAX];
vector<int> plist;
int sieve(int lim) {
  int i, j, k;
  plist.clear();
  plist.push_back(2);
  for (int i=3 ; i<=lim ; i+=2) {
    if (ver[i]==false) {
      plist.push_back(i);
      for (int j=3 ; i*j<=lim ; j+=2) {
        ver[i*j] = true;
      }
    }
  }
}

int main() {
  sieve(PMAX);
  int n;

  while (scanf("%d",&n)==1) {
    if (n == 0) break; // Program terminated
    int a=-1, b=-1;
    bool found = false;
    for (int i=0 ; i<plist.size() && plist[i]<=n ; i++) {
      a = n-plist[i];
      b = plist[i];
      if (a>1 && b>1 && (a&1) && (b&1) && ver[a] == false && ver[b] == false) {
        found = true;
        break;
      }
    }
    if (found == true) {
      printf("%d = %d + %d\n",n,b,a); 
    } else {
      printf("Goldbach's conjecture is wrong.\n");
    }

  }
  return 0;
}

[UVa] 12718 - Dromicpalin Substrings

#include <cstdio>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool isOdd(int val) {
    if (val & 1) return true; // bitwise checking
    else return false;
}
int counts[1000]; // only 'a' - 'z' is significant
int main( ) {

    //freopen("j.input.txt","r",stdin);
    //freopen("j.analysis.txt","w",stdout);

    int test, kase=1;
    string inputstr;

    cin >> test;

    while (test--) {

        cin >> inputstr;

        int palindromes=0;
        for (int i = 0 ; i<inputstr.size() ; i++) {
            for (int ii = 'a' ; ii<='z' ; ii++) counts[ii] = 0;
            int odds = 0;
            for (int j=i ; j<inputstr.size() ; j++) {
                counts[inputstr[j]]++;

                if ( isOdd(counts[inputstr[j]]) ) odds++;
                else odds--;
                int rangeLength = j-i+1;
                if ( isOdd(rangeLength) && odds==1 ) palindromes++;
                if ( !isOdd(rangeLength) && odds==0 ) palindromes++;
            }
        }
        cout << "Case " << kase++ << ": " << palindromes << endl;
    }

    return 0;
}

[UVa] 12712 - Pattern Locker

#include <cstdio>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define MOD 10000000000007

typedef long long lint;

int main() {

    lint test, l, m, n, kase=1;

    cin >> test;

    while (test--) {

        cin >> l >> m >> n;
        lint init = 1;
        for (lint i = l*l ; i>(l*l-m) ; i--) {
            init = ((init * i)%MOD);
        }
        lint sum = init;
        for (lint i = (l*l-m) ; i>(l*l-n) ; i--) {
            init = ((init * i)%MOD);
            sum = ((sum + init)%MOD);
        }

        cout << "Case " << kase++ << ": " << sum << endl;


    }


    return 0;
}

[UVa] 10926 - How many dependencies

#include <cstdio>
#include <iostream>

using namespace std;

#define init(n) { for (int i=0 ; i<=n ; i++) { visit[i] = false; for (int j=0 ; j<=n ; j++) adj[i][j] = adj[j][i] = false; } }

int n, dep[200], root[200], adj[200][200];
bool visit[200];

int dfs_visit(int s, int src) {

    root[s] = src;
    dep[s] = 0;
    for (int i=1 ; i<=n ; i++) {
        if (!visit[i] && adj[s][i]) {
            visit[i] = true;
            dep[s] += (dfs_visit(i,src)+1);
        }
    }
    return dep[s];
}

void dfs() {

    for (int i=1 ; i<=n ; i++) {
        for (int j=0 ; j<=n ; j++) visit[j] = false;
        dfs_visit(i,i);
    }

}

int main( void ) {

    int t, x, maxdepi, maxdep;

    while (scanf("%d",&n)==1 && n) {

        init(n);

        for (int i=1 ; i<=n ; i++) {
            scanf("%d",&t);
            for (int j=0 ; j<t ; j++) {
                scanf("%d",&x);
                adj[i][x] = true;
            }
        }


        dfs();

        maxdep = -1000;

        for (int i=1 ; i<=n ; i++) {


            if (dep[i]>maxdep) {
                maxdep = dep[i];
                maxdepi = i;

            }
        }

        printf("%d\n",maxdepi);

    }


    return 0;
}

Segment Tree [Tutorials]

Some of the links are shortened because some Google services are blocked in my country. So I have to use proxies that generate Long links.
1. Tutorial 1

[For ICPC] Links

Has some nice DP Problems : GitHUB
Has lots of links: Online Resources

[UVa] 574 - Sum It Up

Method: Backtracking
Possible optimizations: Used a map to check if a set was generated before, it takes more time than checking if the numbers were used more than they appeared in input

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<int> nlist;
vector< vector<int> > finlist;
bool used[20];
map< vector<int>, bool > mp;
int btracking(int t, int sum, vector<int> temp, int k) {
    //if (!sum) solve[i].clear();

    if (sum == t) {
        if (!mp[temp]) {
            finlist.push_back(temp);
            mp[temp] = true;
        }
        return 0;
    }

    for (k ; k<nlist.size() ; k++) {
        if (!used[k]) {
            if (nlist[k]<=(t-sum)) {
                sum+=nlist[k];
                temp.push_back(nlist[k]);
                used[k] = true;
                btracking(t, sum, temp, k);
                used[k] = false;
                temp.pop_back();
                sum-=nlist[k];
            }
        }
    }

    return 0;
}

int main( void ) {

    int t, n, i, j, x;

    //freopen("574_in.txt","r+",stdin);

    while ( scanf("%d %d",&t,&n) == 2 ) {
        if (!n) break;

        printf("Sums of %d:\n",t);

        nlist.clear();
        for (i=0 ; i<n ; i++) {
            scanf("%d",&x);
            nlist.push_back(x);
            used[i] = false;
        }
        //cout << "-----> " << nlist.size() << endl;

        finlist.clear();
        vector<int> temp;
        temp.clear();
        mp.clear();
        btracking(t, 0, temp, 0);

        if (!finlist.size()) {
            printf("NONE\n");
        }

        //printf("--> %d\n",finlist.size());
        for (i=0 ; i<finlist.size() ; i++) {
            for (j=0 ; j<finlist[i].size() ; j++) {
                if (!j) printf("%d",finlist[i][j]);
                else printf("+%d",finlist[i][j]);
            }
            printf("\n");
        }

    }

    return 0;
}

[UVa] 796 - Critical Links

Method: The core idea is behind the DFS. It uses the d[u] data. low[u] contains the index of the topmost and leftmost vertex in the tree that u resides in. It is updated in two conditions. They are
1. If a vertex that is connected with u was visited earlier has a lower d[v] (d[v] is checked because u is part of v's tree then it's low[v] is still not reliable but d[v] is it's most reliable data)
2. If a fresh vertex is visited through u, then u can use that low[v] data and update itself in case v has a higher hierarchy access.
3. If low[v] > d[u], the explanation of this is that low[v] was generated during a traversal from v. During that traversal v could not find any other edge to reach u or any of it's preceding nodes. So, to reach the tree that u resides in, v must use the edge [u,v] which makes it a bridge essentially.

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
bool visited[200];
int d[200], low[200], brcount, br[200][200];
vector<int> g[200];
int dfs(int u, int parent, int depth) {
    visited[u] = true;
    d[u] = low[u] = depth;

    for (int i=0 ; i<g[u].size() ; i++) {
        int v = g[u][i];

        if (visited[v] && v!=parent) {
            low[u] = (low[u]<d[v]?low[u]:d[v]);
        }
        if (!visited[v]) {
            dfs(v, u, depth+1);
            low[u] = (low[u]<low[v]?low[u]:low[v]);
            if (low[v]>d[u]) {
                brcount++;
                br[u][v] = br[v][u] = true;
            }
        }
    }

}


int main( void ) {

    //freopen("brg.txt","r+",stdin);

    int n, v, x, e;

    while (~scanf("%d",&n)) {

        for (int i=0 ; i<200 ; i++) {
            g[i].clear();
            visited[i] = false;
            for (int j=0 ; j<200 ; j++) {
                br[i][j] = false;
            }
        }

        for (int i=0 ; i<n ; i++) {
            scanf("%d (%d)",&v,&e);
            for (int j=0 ; j<e ; j++) {
                scanf("%d",&x);
                g[v].push_back(x);
                g[x].push_back(v);
            }
        }

        brcount = 0;

        for (int i=0 ; i<n ; i++) {
            if (!visited[i]) {
                dfs(i, 0, 0);
            }
        }

        printf("%d critical links\n",brcount);
        for (int i=0 ; i<n ; i++) {
            for (int j=i+1 ; j<n ; j++) {
                if (br[i][j]) {
                    printf("%d - %d\n",i,j);
                    br[i][j] = br[j][i] = false;
                }
            }
        }
        printf("\n");
    }

    return 0;
}

[UVa] 10199 - Tourist Guide

The problem uses the concept of Articulation Points. One critical case is when the graph is already disconnected.
Method: For each vertex, I first counted it's child count (dfscount, dfsnum). Then I counted them again after disconnecting that vertex. If both of them aren't same, I incremented the Articulation Point count, because that vertex is an articulation point.

6
sugarloaf
maracana
copacabana
ipanema
corcovado
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
corcovado sugarloaf
lapa corcovado
5
guanabarabay
downtown
botanicgarden
colombo
sambodromo
4
guanabarabay sambodromo
downtown sambodromo
sambodromo botanicgarden
colombo sambodromo
6
a
b
d
c
e
f
7
a b
a d
d c
b d
c e
c f
e f
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f g
7
g
f
e
d
c
b
a
7
a b
b c
c d
d e
e f
f g
g a
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f a
6
a
b
c
d
e
f
5
a b
a f
c d
c e
d e
3
a
b
c
2
a b
b c
0

#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <vector>


using namespace std;


bool visited[200], con[200][200];
int dfscounter;
int dfs(int v, int n) {
    visited[v] = true;
    dfscounter++;
    for (int i=1 ; i<=n ; i++) {
        if (!visited[i] && con[v][i]) {
            dfs(i, n);
        }
    }
}
map<string, int> cmap;
vector<string> lst;
int artP;
int main( ) {
    int n, e, kase=1;

    //freopen("tourist.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);

    while ( cin >> n ) {

        if (!n) break;

        if (kase>1) cout << endl;

        cmap.clear();
        lst.clear();
        artP = 0;
        for (int i=1 ; i<=n ; i++) {
            string a;
            cin >> a;
            cmap[a] = i;
        }
        cin >> e;
        for (int i=1 ; i<=n ; i++) for (int j=1 ; j<=n ; j++) con[i][j] = false;
        for (int i=1 ; i<=e ; i++) {
            string a, b;
            cin >> a >> b;
            con[ cmap[a] ][ cmap[b] ] = con[ cmap[b] ][ cmap[a] ] = true;
        }
        for (map<string, int>::iterator it=cmap.begin() ; it!=cmap.end() ; it++) {
            int rcount;
            dfscounter=0;
            for (int i=1 ; i<=n ; i++) visited[i] = false;
            dfs(it->second, n);
            rcount = dfscounter;
            for (int i=1 ; i<=n ; i++) visited[i] = false;
            visited[it->second] = true;
            dfscounter=0;
            for (int i=1 ; i<=n ; i++) {
                if (con[ it->second ][i]) {
                    dfs(i, n);
                    break;
                }
            }
            if (rcount>1 && dfscounter!=rcount-1) {
                artP++;
                lst.push_back(it->first);
            }
        }

        printf("City map #%d: %d camera(s) found\n",kase++,lst.size());
        for (int i=0 ; i<lst.size() ; i++) {
            cout << lst[i] << endl;
        }

    }

}

[UVa] 315 - Network

#Articulation Points #Graph #DFS #BFS
Method:
Turn off each node and see if all the other nodes except that are visited or not using DFS
Sample I/O:

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
5
1 2
2 3 4
4 5
0
0

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool con[200][200];
vector< pair<int, int> > edges;
bool visit[200];

void init_con(int n) {
    for (int i=0 ; i<=n ; i++)
        for (int j=0 ; j<=n ; j++)
            con[i][j] = false;
}

int dfs_visit(int s, int n) {

    int vCount = 1;

    if (visit[s]) return 0;
    visit[s] = true;

    for (int i=1 ; i<=n ; i++) {
        if (!visit[i] && con[s][i]) {
            vCount += (dfs_visit(i,n));
        }
    }
    return vCount;
}

int dfs(int s, int n) {

    int vCount = 0;

    for (int i=1 ; i<=n ; i++) {
        visit[i] = false;
    }
    visit[s] = true;

    for (int i=1 ; i<=n ; i++) {
        if (!visit[i]) {
            vCount = dfs_visit(i,n);

            return vCount;
        }
    }
    return vCount;
}

int find_bridges(int n) {
    int aps = 0, i, j;


    for (int i=1  ; i<=n ; i++) {
        if (dfs(i,n) != (n-1)) aps++;
    }


    return aps;
}
char buf[10000];
int main( void ) {


    //freopen("inp.dat","r+",stdin);

    int n, result, vtx, plc;
    char *p;

    while (scanf("%d",&n)==1 && n!=0) {
        getchar();

        init_con(n);
        edges.clear();

        while (gets(buf)) {
            if (!strcmp(buf,"0")) break;
            p = strtok(buf," ");
            sscanf(p,"%d",&plc);

            while ((p=strtok(NULL," "))) {
                sscanf(p,"%d",&vtx);

                con[plc][vtx] = con[vtx][plc] = true;
                edges.push_back(make_pair(plc,vtx));
            }
        }

        result = find_bridges(n);

        cout << result << endl;
    }


    return 0;
}

Segment Tree [ On the run ]

I'm trying to implement Segment Tree and maybe will solve some problems using it, prior to ICPC. Here's some resource that I'm using

• http://codeforces.com/blog/entry/3327
• http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
• http://apps.topcoder.com/forums/;jsessionid=2DA32E9BC12C8C331BCC8441B68E278E?module=Thread&threadID=754366&start=0&mc=4#1572259
• http://ronzii.wordpress.com/2011/07/08/segment-tree-tutorial/
• http://en.wikipedia.org/wiki/Segment_tree

The Dijkstra Algorithm for Single Source Shortest Path

Currently the code is still under development. This is just to have the track of docs that I'm using to write it
Theory : [ http://en.wikipedia.org/wiki/Dijkstra's_algorithm ]
Priority queue (STL) : [ http://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html ]
[ http://www.technical-recipes.com/2011/priority-queues-and-min-priority-queues-in-c/ ]
Till now it feels like that's all you need, I don't know for sure though. Let's see
Update : Here's a full code of a problem that I solved using this algorithm [UVA 10986]

#include <iostream>
#include <list>
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

// based on TopCoder tutorial

#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define INF 200000010

list<ii> G[30000];

int djk( int s, int t, int n ) {
 vi D(n, INF);
 
 set<ii> q;
 D[s] = 0;
 q.insert(ii(0,s));
 
 while (!q.empty()) {
 
  
  ii top = *q.begin();
  q.erase(q.begin());
  int v = top.second, d = top.first;
  
  tr(G[v], it) {
   int v2 = it->second, cost = it->first;
   if (D[v2] > D[v] + cost) {
    if (D[v2] != INF) {
     q.erase(q.find(ii(D[v2],v2)));
    }
    D[v2] = D[v] + cost;
    q.insert(ii(D[v2],v2));
   }
   
  }
 }
 return D[t];
}


int main( void ) {
 int test, n, m, s, t, x, y, v, kase=1;
 scanf("%d",&test);
 while (test--) {
  scanf("%d %d %d %d",&n,&m,&s,&t);
  for (int i=0 ; i<=n ; i++) {
   G[i].clear();
  }
  for (int i=0 ; i<m ; i++) {
   scanf("%d %d %d",&x,&y,&v);
   G[x].push_back(ii(v,y));
   G[y].push_back(ii(v,x));
  }
  int res = djk(s,t,n);
  
  printf("Case #%d: ",kase++);
  if (res == INF) printf("unreachable\n");
  else printf("%d\n",res);
 } 
 
 return 0;
}

11821 - High-Precision Number

import java.util.Scanner;
import java.math.BigDecimal;

public class Main {
  public static void main(String[] args) {
    
    Scanner input = new Scanner(System.in);
    int n;
    BigDecimal val;
    n = input.nextInt();
    
    while ( n-- > 0 ) {
      BigDecimal sum = new BigDecimal("0");
      while ( true ) {
        val = input.nextBigDecimal();
        if ( val.equals(BigDecimal.ZERO) ) break;
        
        sum = sum.add(val);
        
      }
      
      int i = new Integer(0);
      
      char out[] = sum.toString().toCharArray();
      
      int len;
      
      for (len=out.length-1 ; len>0 && out[len]=='0' ; len--);
      if (len>0 && out[len]=='.') len--;
      for (i=0 ; i<=len ; i++) {
        System.out.print(out[i]);
      }
      System.out.println();
      
    }
    
  }
}

[UVa] 11456 - Trainsorting

Method:
The problem at first glance seems too straightforward but it's not that much. Think a bit about the lines "Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, but the cars within it must be ordered by weight.". What I understand from these lines is.

1. Erin can choose to start making the train from any point of the arrivals of the cars. So she may have started to make the train from either 1st or n-1st or nth or n/2nd, any point.
2. And from the point in time where she starts this, she checks if the new car is smaller in weight than the last car of her train or higher in weight than the first car or vice versa.
3. So the sorting can start from any point and the optimal choice is at any point.
Ofcourse you have to use LIS, but you also need LDS. Why??

Because suppose she starts from position i. Since she wants to make the train as long as possible so she must make sure the train is optimal from the last till i. Then after i she wants to join the longest possible train using the cars i+1 to n. So, she wants to join the LIS(1 -> i) with LDS(i+1 -> n).

In my solution, I subtracted 1 from LIS(i)+LDS(i) because in both the i car is present. So erased it from 1 of them.

// BISMILLAHIRRAHMANIRRAHIM

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <list>
#include <iostream>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>

#define swp(type, a, b) {type x=a; a=b; b=x;}

typedef long long lint;
typedef unsigned long long ulint;

using namespace std;

int seq[10000];
int lis[10000], lds[10000];

int LIS(int n) {
 
 int i, j, mx=0;
 
 
 for (i=n-1 ; i>=0 ; i--) {
  lis[i] = 1;
  for (j=i+1 ; j<n ; j++) {
   if (seq[i]<seq[j]) {
    lis[i] = max(lis[i] , 1+lis[j]);
   }
  }
  mx = max(mx, lis[i]);
 }
 return mx;
}

int LDS(int n) {
 
 int i, j, mx=0;
 
 
 for (i=n-1 ; i>=0 ; i--) {
  lds[i] = 1;
  for (j=i+1 ; j<n ; j++) {
   if (seq[i]>seq[j]) {
    lds[i] = max(lds[i] , 1+lds[j]);
   }
  }
  mx = max(mx, lds[i]);
 }
 return mx;
}



int main ( void ) {
 
 int i, kount, kase, n, x, mx, mnn, mxx, len, res;
 
 
 
 cin >> kase;
 
 while (kase--) {
  cin >> n;
  mx = n;
  
  len = 0;
  kount = 0;
  while (mx--) {
   cin >> x;
   seq[kount++] = x;
  }
  
  LDS(n); LIS(n);
  
  res = 0;
  
  for (i=0 ; i<n ; i++) {
   res = max(res, lis[i]+lds[i]-1);
  }
  
  
  /*cout << "{ debug-start" << endl;
  for (i=0 ; i<n ; i++) {
   cout << seq[i] << " ";
  } cout << endl;
  for (i=0 ; i<n ; i++) {
   cout << lis[i] << " ";
  } cout << endl;
  for (i=0 ; i<n ; i++) {
   cout << lds[i] << " ";
  } cout << endl;
  cout << "end-debug }" << endl;*/
  
  cout << res << endl;
 }
 
 return 0;
}

[UVa] 11296 - Counting Solutions

Method:
First design a bruteforce solution with small input in mind. It should be able to compute answers for 100 101 etc. Now sequentially examine all the answers you'll find a pattern. The solution to every i-th even number is the sum of all numbers till i+1. It also applies to all odd numbers. Such as 2, 1st even number, so result is 1+2, till 2nd number And for 3, 1st odd number, it's the same. Just find the i using i = (n/2) and use i*(i+1)/2 formula for the result.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <list>
#include <iostream>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

typedef long long lint;

lint res[1000010];

int main ( void ) {
 
 lint i, j, k, n, cnt, ser;
 res[0] = 1LL;
 res[1] = 1LL;
  
 for (i=2, ser=2LL ; i<=1000001LL ; i+=2, ser++) {
  res[i] = (res[i-1]+ser);
  res[i+1] = res[i];
 }
 
 
 while ( cin >> n ) {
  cout << res[n] << endl;
 }

 return 0;
}

Backtracking Basic Code

This is one of the first things you do when you learn how to program a backtracking simulation. Generate all permutations of a given number range. When the program is at halt enter any number greater than 0 to see all numbers in that range permuted. The program terminates with the 0 input.

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

int src[100], out[100], used[100], n;

void btrack( int k ) {
 
 if (k>=n) {
  for (int i=0 ; i<n ; i++) {
   printf(" %d ",out[i]);
  }
  printf("\n");
  return;
 }
 
 for (int i=0 ; i<n ; i++) {
  if (!used[i]) {
   used[i] = 1;
   out[k] = src[i];
   btrack( k+1 );
   used[i] = 0;
  }
 }
 return;
}


int main ( void ) {
 
 while ( scanf("%d",&n) && n ) {
  for (int i=0 ; i<n ; i++) {
   used[i] = 0;
   src[i] = i+1;
  }
  btrack( 0 );
 }
 
 return 0;
}

[UVa] 437 - The Tower of Babylon

Method: LIS (Modified)
You can only see the problem as an LIS Problem but you cannot solve it using LIS principles. All the six sides of the blocks have to be considered. If you test them using the rotational if in the LIS algorithm, they are just testing one or two but all the sides. So you have to make the list with six sides. -Thanks to Rakib (My team mate for contests) for pointing this out :) Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

typedef int lint;

using namespace std;

typedef struct blk {
 int x, y, z; 
} block;


bool comp( block a, block b ) {
 if (a.x != b.x) return (a.x<b.x);
 else if (a.y!=b.y) return (a.y<b.y); 
 else return (a.z<b.z);
}

vector<block> lst;
int lis[1000];

int LIS( int n ) {

 int max_lis(-1), i, j, k;
 
 for (int i=0 ; i<n ; i++) {
  lis[i] = lst[i].z;
  for (int j=0 ; j<i ; j++) {
   if (( (lst[i].x > lst[j].x && lst[i].y > lst[j].y) || (lst[i].x > lst[j].y && lst[i].y > lst[j].x) ) ) {
    lis[i] = max ( lis[i] , lis[j]+lst[i].z );
   }
  }
  max_lis = max ( lis[i] , max_lis );
 }
 return max_lis;
}

int main( void ) {

 int n, i, x, y, z, kase=1;

 while ( scanf("%d",&n) && n ) {
 
  lst.clear();
 
  for (i=0 ; i<n ; i++) {
   scanf("%d %d %d",&x,&y,&z);
   
   lst.push_back( (block) {x,y,z} );
   lst.push_back( (block) {x,z,y} );
   lst.push_back( (block) {y,x,z} );
   lst.push_back( (block) {y,z,x} );
   lst.push_back( (block) {z,x,y} );
   lst.push_back( (block) {z,y,x} );
  }
  
  sort(lst.begin(), lst.end(), comp);
  
  int res = LIS( lst.size() );
  
  printf("Case %d: maximum height = %d\n",kase++,res);
 } 
 return 0;
}

[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] 627 - The Net

Pretty simple and somewhat forced towards the solution.
Counting number of nodes and shortest path. You have to print the path too.
It's simply BFS. The pi[ ] array comes handy to print the path.

Method: BFS (Use the pi array)

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>

#define WHITE 0
#define GREY 1
#define BLACK 3
#define INF 0
#define NIL -1

using namespace std;

bool color[400], adj[400][400];
int d[400], p[400];
char in[100000];

bool bfs( int s, int des, int n ) {
 int u, v;
 for (u=0 ; u<=300 ; u++) {
  color[u] = WHITE;
  d[u] = INF;
  p[u] = NIL;
 }
 color[s] = GREY;
 d[s] = 0;
 p[s] = NIL;
 
 queue<int> q;
 q.push(s);
 while (!q.empty()) {
  u = q.front();
  q.pop();
  for (v=1 ; v<=n ; v++) {
   if (adj[u][v] && color[v]==WHITE) {
    color[v] = GREY;
    d[v] = d[u]+1;
    p[v] = u;
    q.push(v);
    if (v == des) {
     return true;
     
    }
   }
  }
  color[u] = BLACK;
 }
 return false;
}

void print_path(int v) {
 int i, j, pr[1000];
 for (i=v, j=0 ; i>0 ; i=p[i], j++) pr[j] = i;
 for (--j ; j>0 ; j--) printf("%d ",pr[j]);
 printf("%d\n",pr[j]);  //|Last one can't have
}    //|can't have blank space
    //|after it

int main( void ) {


 int i, j, c, n, u, v, nodes, conn;
 char *p;

 while ( scanf("%d",&nodes) == 1 ) {
  getchar(); // Back off for gets()
  
  for (i=0 ; i<=300 ; i++) { 
   for (j=0 ; j<=300 ; j++) adj[i][j] = false;
  }
  
  n = nodes;
  
  while (nodes--) {
   gets(in);
   p = strtok(in,"-,");
   sscanf(p,"%d",&i);
   p = strtok(NULL,"-,");
   while (p) {
    sscanf(p,"%d",&c);
    adj[i][c] = true; //|Connections are !bidirectional
    p = strtok(NULL,"-,");
   }
  }
  
  
  scanf("%d",&conn);
  
  printf("-----\n");
  
  for (i=1 ; i<=conn ; i++) {
   scanf("%d %d",&u, &v);
   if (bfs(u,v,n)) {
    print_path( v );
   } else {
    printf("connection impossible\n");
   }
  }
 }
}