[UVa] 784 - Maze Exploration

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

int dirs[10][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

char maze[100][100];
int color[100][100];

void dfs_visit(int x, int y)
{
    int i;
    color[x][y]=2;
    maze[x][y]='#';
    for (i=0 ; i<8 ; i++)
    {
        if (color[x+dirs[i][0]][y+dirs[i][1]]==0 && maze[x+dirs[i][0]][y+dirs[i][1]]!='X' && maze[x+dirs[i][0]][y+dirs[i][1]]!='#')
            dfs_visit(x+dirs[i][0],y+dirs[i][1]);
    }
}

void dfs(int x, int y, int mh, int mw)
{
    int i, j;
    for (i=0 ; i<mh ; i++)
        for (j=0 ; j<mw ; j++)
            color[i][j] = 0;

    for (i=0 ; i<8 ; i++)
    {
        if (color[x+dirs[i][0]][y+dirs[i][1]]==0 && maze[x+dirs[i][0]][y+dirs[i][1]]!='X' && maze[x+dirs[i][0]][y+dirs[i][1]]!='#')
            dfs_visit(x+dirs[i][0],y+dirs[i][1]);
    }
}


int end(char *p)
{
    int i;
    for (i=0 ; p[i] ; i++)
    {
        if (p[i]!='_') return 0;
    }
    return 1;
}
int seed(char *p)
{
    int i;
    for (i=0 ; p[i] ; i++)
    {
        if (p[i]=='*') return i;
    }
    return -1;
}
int main()
{
    int test, maze_size, i, sx, sy;

    scanf("%d",&test);
    getchar();
    while (test--)
    {
        for (i=0 ;  ; i++)
        {
            gets(maze[i]);

            if (end(maze[i]))
                break;
        }

        maze_size = i;

        for (i=0 ; i<maze_size ; i++)
        {
            if ((sy = seed(maze[i]))>=0)
            {
                sx = i;
                break;
            }
        }

        dfs(sx,sy,maze_size,80);

        for (i=0 ; i<=maze_size ; i++)
            puts(maze[i]);

    }
    return 0;
}

[UVa] 568 - Just the Facts

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

int fact[20000];

int main()
{
    int i, f, idx;
    fact[0] = fact[1] = 1;
    f = 1;

    for (i=2 ; i<=10000 ; i++)
    {
        f*=i;
        while (f%10 == 0)
            f/=10;

        f = f%100000;
        fact[i] = f%10;
    }

    while (scanf("%d",&idx)==1)
    {
        printf("%5d -> %d\n",idx,fact[idx]);
    }

    return 0;
}

[UVa] 439 - Knight Moves

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <queue>
#include <algorithm>

#define INF 9999999
#define MAXX 9
#define MAXW 9
using namespace std;
typedef struct v
{
    int row, col;
} vtx;
vtx moves[10]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

char inp[1000];

bool color[10][10];
int d[10][10];
int bfs(int srow, int scol, int drow, int dcol)
{
    int i, j;
    for (i=0 ; i<=MAXX ; i++)
        for (j=0 ; j<=MAXW ; j++)
        {
            color[i][j]=false;
            d[i][j]=INF;
        }

    color[srow][scol] = true;
    d[srow][scol] = 0;
    queue<vtx> myq;
    vtx u, t, s;
    s.row=srow;
    s.col=scol;

    myq.push(s);
    while (!myq.empty())
    {
        u = myq.front();
        myq.pop();
        for (i=0 ; i<8; i++)
        {
            t.row = u.row+moves[i].row;
            t.col = u.col+moves[i].col;
            if (t.row>=1 && t.row<MAXX && t.col>=1 && t.col<MAXW && color[t.row][t.col]==false)
            {
                //cout << "-> " << t.row << "  " << t.col << endl;
                //getchar();
                color[t.row][t.col]=true;
                d[t.row][t.col]=d[u.row][u.col]+1;
                if (t.row == drow && t.col == dcol) return d[t.row][t.col];
                myq.push(t);
            }
            //cout << "--> " << "lOOPing" << endl;
        }
        //if (myq.empty()) return d[drow][dcol];
        //myq.pop();
    }

    return d[drow][dcol];
}

int main()
{
    int scol, srow, dcol, drow;
    char sc,dc;
    while (gets(inp))
    {
        sscanf(inp,"%c%d %c%d",&sc,&srow,&dc,&drow);
        scol = sc-'a'+1;
        dcol = dc-'a'+1;
        srow; drow;

        //printf("%d %d %d %d\n",srow,scol,drow,dcol);
        //getchar();

        printf("To get from %c%d to %c%d takes %d knight moves.\n",sc,srow,dc,drow,bfs(srow,scol,drow,dcol));
    }
    return 0;
}

[UVa] 195 - Anagrams

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

char in[1000];
int cmp(const void *a, const void*b)
{
    return *(char*)a-*(char*)b;
}

bool comp(const char &a, const char &b)
{
    int delta = tolower(a) - tolower(b);
    return delta?delta<0:a<b;
}
int main()
{
    int test, len;
    scanf("%d",&test);
    getchar();
    while (test--)
    {
        gets(in);
        len = strlen(in);
        sort(in,in+len,comp);

        do
        {
            cout << in << endl;
        } while (next_permutation(in,in+len,comp));
    }
    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] 10161 - Ant on a Chess Board

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;

ll sum(ll n)
{
    return n*n;
}

int main()
{
    ll i, lev, lim, mid;

    while (cin >> i && i)
    {
        lev = (ll)ceil(sqrt(i));
        if (lev&1)
        {
            lim = lev*lev;
            mid = lim - (lev-1);
            if (i<mid)
            {
                cout << lev << " " << i-(lev-1)*(lev-1) << endl;
            } else
            {
                cout << lim-(i)+1 << " " << lev << endl;
            }
        } else
        {
            lim = lev*lev;
            mid = lim - (lev-1);
            if (i>=mid)
            {
                cout << lev << " " << lim-i+1 << endl;
            } else
            {
                cout << i-(lev-1)*(lev-1) << " " << lev << endl;
            }
        }
    }
    return 0;
}

[UVa] 12195 - Jingle Composing

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#define ERROR 1e-11
using namespace std;

char input[1000000];
int main()
{
    int counter, i;
    double sum;
    char *p;
    while (gets(input))
    {
        if (!strcmp(input,"*")) break;


        counter=0;
        p = strtok(input,"/");
        while (p!=NULL)
        {
            for (i=0, sum=0 ; p[i]>='A'&&p[i]<='Z' ; i++)
            {
                if (p[i]=='W') sum += 1.0;
                else if (p[i]=='H') sum += 1.0/2.0;
                else if (p[i]=='Q') sum += 1.0/4.0;
                else if (p[i]=='E') sum += 1.0/8.0;
                else if (p[i]=='S') sum += 1.0/16.0;
                else if (p[i]=='T') sum += 1.0/32.0;
                else if (p[i]=='X') sum += 1.0/64.0;
            }
            if (fabs(sum-1)<ERROR) counter++;
            p = strtok(NULL,"/");
        }
        printf("%d\n",counter);
    }
    return 0;
}