[UVa] 12024 - Hats

A good explaination on this problem can be found here [ https://gist.github.com/Tafhim/b5705901e33017205a3b ]
I used the formula for the DP implementation

D(n) = n D(n-1) + (-1)^n

Solution:

#include <bits/stdc++.h>
using namespace std;

map<int, pair<int, int> > precalc;
int main() {
 int kase, n, ai;
 int de[100], f[100];
 de[0] = 1;
 f[0] = 1;
 de[1] = 0;
 f[1] = 1;
 ai = -1;
 for (int i = 2 ; i<=12 ; i++) {
  ai *= (-1);
  de[i] = i * de[i-1] + ai;
  f[i] = f[i-1]*i;
 }

 cin >> kase;

 while (kase--) {
  cin >> n;
  cout << de[n] << "/" << f[n] << endl;
 }

 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] 116 - Unidirectional TSP

#include <stdio.h>

int dir[100][100];
int mtx[100][100];
int path[100];

int main()
{
 int a, b, c, min;
 int i, j, row, col, a_dir, c_dir;

 while (scanf("%d %d",&row,&col)==2)
 {
     for (i=1 ; i<=row ; i++)
            for (j=1 ; j<=col ; j++)
                scanf("%d",&mtx[i][j]);

        for (j=col-1 ; j>=1 ; j--)
        {
            for (i=1 ; i<=row ; i++)
            {
                if (i-1<1)
                {
                    a_dir = -1;
                    a = mtx[i][j] + mtx[row][j+1];
                } else
                {
                    a_dir = 0;
                    a = mtx[i][j] + mtx[i-1][j+1];
                }
                if (i+1>row)
                {
                    c_dir = -1;
                    c = mtx[i][j] + mtx[1][j+1];
                } else
                {
                    c_dir = 0;
                    c = mtx[i][j] + mtx[i+1][j+1];
                }
                b = mtx[i][j] + mtx[i][j+1];

                if (a<=b && a<=c)
                {
                    mtx[i][j] = a;

                    if (a_dir<0)
                    {
                        if (a==b) { dir[i][j] = i; }
                        else if (a==c) { dir[i][j] = i+1; }
                        else { dir[i][j] = row; }
                    } else {
                        if (a==c && c_dir<0) dir[i][j] = 1;
                        else dir[i][j] = i-1;
                    }
                }
                else if (b<=a && b<=c)
                {
                    mtx[i][j] = b;


                    if (b==a)
                    {
                        if (a_dir<0)
                        {
                            dir[i][j] = i;
                        } else
                        {
                            dir[i][j] = i-1;
                        }
                    } else if (b==c)
                    {
                        if (c_dir<0)
                        {
                            dir[i][j]=1;
                        } else
                        {
                            dir[i][j]=i;
                        }
                    } else
                    {
                        dir[i][j] = i;
                    }

                }
                else if (c<=a && c<=b)
                {
                    mtx[i][j] = c;
                    if (c_dir<0)
                    {
                        dir[i][j] = 1;
                    } else {
                        if (c==a) { dir[i][j]=i-1; }
                        else if (c==b) { dir[i][j]=i; }
                        else { dir[i][j]=i+1; }
                    }
                }

            }
        }

        for (i=1, min=mtx[1][1], path[1]=1 ; i<=row ; i++)
        {
            if (mtx[i][1]<min)
            {
                min = mtx[i][1];
                path[1] = i;
            }
        }
        printf("%d",path[1]);
        for (j=2 ; j<=col ; j++)
        {
            path[j] = dir[path[j-1]][j-1];
            printf(" %d",path[j]);
        }


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

 }

 return 0;
}

[UVa] 147 - Dollars

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

typedef long long ll;


ll table[30000][100];

ll change(ll n, ll m, int *S)
{

    if (n==0) return 1;
    else if (n<0) return 0;
    else if (m<0 && n>=1) return 0;

    //cout << n << " -- " << table[n][m]<< endl;
    //getchar();

    if (table[n][m]!=-1) return table[n][m];

    return (table[n][m] = change(n,m-1,S)+change(n-S[m],m,S));
}

ll parse(string n)
{
    int len = n.length(), i, j;
    char stor[100];
    for (i=0, j=0 ; i<len ; i++)
    {
        if (n[i]>='0' && n[i]<='9')
            stor[j++]=n[i];
    }
    stor[j]='\0';
    return (ll)atol(stor);
}


int main()
{
    int i, j;
    ll n, m, val;
    string inp;

    int S[100];

    for (i=0 ; i<=30000 ; i++)
    {
        for (j=0 ; j<=20 ; j++)
        {
            table[i][j]=-1;
        }
    }

    S[0] = 5;
    S[1] = 10;
    S[2] = 20;
    S[3] = 50;
    S[4] = 100;
    S[5] = 200;
    S[6] = 500;
    S[7] = 1000;
    S[8] = 2000;
    S[9] = 5000;
    S[10] = 10000;

    for (i=0 ; i<=30000 ; i++)
    {
        for (j=0 ; j<=20 ; j++)
        {
            table[i][j]=-1;
        }
    }

    while (cin >> inp)
    {
        if (inp=="0.00") break;

        n = parse(inp);
        val = change(n,10,S);
        cout.width(6);
        cout << inp;
        cout.width(17);
        cout << val << endl;
    }
    return 0;
}

[UVa] 10190 - Divide but not quite conquer

Critical point:
If n<2 or m<2, it's "Boring!"
If at some point (n%m != 0), it's "Boring!" to the limit :P
Method:
I store the result in a string (char arrray) when the division is taking place. If the sequence is found to be not boring, print the string.

#include #include <stdio.h>
#include <string.h>

char output[1000000], temp[1000000];
int addStr(char *des, int val, int len)
{

    if (!len)
        sprintf(des,"%d",val);
    else
    {
        int i, j;
        sprintf(temp," %d",val);
        int ln = strlen(temp);
        for (i=len, j=0 ; j<ln ; i++, j++)
        {
            des[i]=temp[j];
        }
        des[i]='\0';
        return (len+j);
    }
    return strlen(des);
}

int main()
{
    int n, m;
    while (scanf("%d %d",&n,&m)==2)
    {
        int lnt = 0;
        int b=0;
        if (n<2 || m<2)
        {
            printf("Boring!\n");
            continue;
        }
        while (n>1)
        {
            lnt=addStr(output,n,lnt);
            if (n%m != 0)
                b=1;
            n/=m;
        }
        lnt=addStr(output,n,lnt);


        if (b)
            printf("Boring!\n");
        else
            printf("%s\n",output);
    }
    return 0;
}