UVa Online Judge

.gitignore

*.exe
*.orig
list.txt

100.cpp

/**
 * UVa 100 3n+1
 * Author: chchwy
 * Last Modified: 2011.01.30
 * Tag: Brute Force
 */
#include<cstdio>
#include<algorithm>
using namespace std;

int cycle_length(int n)
{
    int length = 1;
    while (n != 1)
    {
        if (n % 2) //odd
            n = 3 * n + 1;
        else       //even
            n = n / 2;
        ++length;
    }
    return length;
}

int main()
{
    int a, b; //two input
    while (scanf("%d %d", &a, &b) == 2)
    {
        int max_cycle = 0; // max cycle length

        for (int i = min(a, b); i <= max(a, b); ++i)
        {
            int tmp = cycle_length(i);
            if (tmp > max_cycle)
                max_cycle = tmp;
        }
        printf("%d %d %d\n", a, b, max_cycle);
    }
    return 0;
}

10018.cpp

/**
 * UVa 10018 Reverse and Add
 * Author: chchwy (a) gmail.com
 * Last modified: 2010.07.27
 */
#include<cstdio>

unsigned long reverse(unsigned long n)
{
    unsigned long rev_n = 0; //WA : int rev_n = 0;
    while (n != 0)
    {
        rev_n = (rev_n * 10) + n % 10;
        n /= 10;
    }
    return rev_n;
}

inline int is_palindrome(unsigned long n)
{
    return (n == reverse(n)) ;
}

int reverse_and_add(unsigned long num, unsigned long& result)
{
    int counter = 0;
    do
    {
        num += reverse(num);
        counter++;
    }
    while ( !is_palindrome(num) );
    result = num;
    return counter;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10018.in", "r", stdin);
#endif

    int numOfCase;
    scanf("%d", &numOfCase);

    while (numOfCase--)
    {
        unsigned long num;
        scanf("%lu", &num);

        int iteration;        // the number of iterations
        unsigned long result; // the final palindrome, like 9339

        iteration = reverse_and_add(num, result);

        printf("%d %lu\n", iteration, result);
    }
    return 0;
}

10018.in

5
195
265
750
2
99

10033.cpp

/**
 * UVa 10033
 * Author: chchwy
 * Last Modified: 2009.3.25
 */
#include<iostream>

enum
{
    HALT = 1, MOVi = 2, ADDi = 3,
    MULi = 4, MOVr = 5, ADDr = 6,
    MULr = 7, LDW = 8,  STW = 9,
    BE = 0, RAM_MAX = 1000
};

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10033.in", "r", stdin);
#endif

    int numCase;
    scanf("%d ", &numCase);

    while (numCase--) //for each case
    {
        int reg[10] = {0};    //content of register
        int mem[1000] = {0};  //instructions

        //read instruction
        int mp = 0;
        char buf[8];
        while (fgets(buf, 5, stdin) != NULL && buf[0] != '\n' )
            mem[mp++] = atoi(buf);

        //interpret
        int halt = 0; //flag
        int pc = 0;

        int instCounter = 0;

        while (halt == 0)
        {
            instCounter++;

            //inst fetch
            int op, rd, rs;
            op = mem[pc] / 100;
            rd = (mem[pc] % 100) / 10;
            rs = mem[pc] % 10;
            pc++;

            /* inst execute */
            switch (op)
            {
            case HALT:  //100 halt
                halt = 1;
                break;
            case MOVi:  //2dn Movi d,n
                reg[rd] = rs;
                break;
            case ADDi:  //3dn Addi d,n
                reg[rd] = (reg[rd] + rs) % RAM_MAX;
                break;
            case MULi:  //4dn Muli d,n
                reg[rd] = (reg[rd] * rs) % RAM_MAX;
                break;
            case MOVr:  //5ds Mov d,s
                reg[rd] = reg[rs];
                break;
            case ADDr:  //6ds Add d,s
                reg[rd] = (reg[rd] + reg[rs]) % RAM_MAX;
                break;
            case MULr:  //7ds Mul d,s
                reg[rd] = (reg[rd] * reg[rs]) % RAM_MAX;
                break;
            case LDW:   // 8da Load d, [a]
                reg[rd] = mem[reg[rs]];
                break;
            case STW:   //9sa Store [s],a
                mem[reg[rs]] = reg[rd];
                break;
            case BE:    //0ds BE s,d
                if (reg[rs] != 0)
                    pc = reg[rd];
                break;
            };
        }
        printf("%d\n", instCounter);
        if (numCase != 0) printf("\n");

    }//for each case
    return 0;
}

10035.cpp

/**
 * UVa 10035 Primary Arithmetic
 * Author: chchwy
 * Last Modified: 2011/03/05
 * Blog: http://chchwy.blogspot.com
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

enum { MAX_LEN = 12 };

int to_big_number(char* num)
{
    // reverse
    int len = strlen(num);
    for (int i = 0; i < len / 2; ++i)
        swap(num[i], num[len - i - 1]);

    // sub ascii
    for (int i = 0; i < len; ++i)
        num[i] = num[i] - '0';

    // fill zero
    for (int i = len; i < MAX_LEN; ++i)
        num[i] = 0;
}

int count_carry(char* a, char* b)
{
    to_big_number(a);
    to_big_number(b);

    int carry_counter = 0;
    for (int i = 0; i < MAX_LEN; ++i)
    {
        a[i] = a[i] + b[i];
        if ( a[i] > 9 )
        {
            a[i] = a[i] - 10;
            a[i + 1]++;
            carry_counter++;
        }
    }
    return carry_counter;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10035.in", "r", stdin);
#endif

    char a[MAX_LEN], b[MAX_LEN];

    while (scanf("%s %s ", a, b) == 2)
    {
        if (a[0] == '0' && b[0] == '0')
            break;

        int result = count_carry(a, b);

        if ( result == 0)
            printf("No carry operation.\n");
        else if ( result == 1)
            printf("1 carry operation.\n");
        else
            printf("%d carry operations.\n", result);
    }
    return 0;
}

10035.in

123 456
555 555
123 594
1 9999
1 9
2222222222 3333333333
99999999997 3
0 0

10038.cpp

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

#define MAXSIZE 3000

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10038.in", "r", stdin);
#endif

    int length; //the length of sequence
    int seq[MAXSIZE];
    bitset<MAXSIZE> s;

    //for each case
    while ( scanf("%d ", &length) == 1 )
    {
        //read sequence
        for (int i = 0; i < length; ++i)
            scanf("%d ", &seq[i] );

        if (length == 1)
        {
            puts("Jolly");
            continue;
        }

        s.reset(); //init set

        //add into set
        for (int i = 1; i < length; ++i)
        {
            int diff = abs( seq[i] - seq[i - 1] );
            if (diff > 0 && diff < length)
                s.set(diff);
        }

        //judge
        if ( s.count() == length - 1 )
            puts("Jolly");
        else
            puts("Not jolly");
    }
    return 0;
}

10050.cpp

/**
 * UVa 10050
 * Author: chchwy
 * Last Modified: 2009.11.4
 */
#include <iostream>
#include <bitset>

#define MAX 3651

int countHartals()
{
    int numDay, numParty;
    scanf("%d %d ", &numDay, &numParty);

    std::bitset<MAX> day; //1-3650

    for (int i = 0; i < numParty; ++i)
    {
        int hartal;
        scanf("%d ", &hartal );

        for (int i = 0; i <= numDay; i += hartal )
        {
            if ( i % 7 == 0 || i % 7 == 6) //friday & saturday
                continue;
            day.set(i);
        }
    }
    return day.count();
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10050.in", "r", stdin);
    freopen("10050.out", "w", stdout);
#endif

    int numCase;
    scanf("%d ", &numCase);

    while ( numCase-- )
        printf("%d\n", countHartals() );

    return 0;
}

10050.in

2
14
3
3
4
8
100
4
12
15
25
40

10050.out

5
15

10055.cpp

#include <stdio.h>

long long myabs(long long in)
{
    return (in >= 0) ? in : -in;
}

int main()
{
    long long hashmat, enemy;

    while (scanf("%lld %lld ", &hashmat, &enemy ) == 2)
        printf("%lld\n", myabs( enemy - hashmat ) );

    return 0;
}

10071.cpp

#include <stdio.h>

int main()
{
    int v, t;
    while ( scanf("%d %d", &v, &t) == 2 )
        printf("%d\n", 2 * v * t );
    return 0;
}

10079.cpp

/**
 * 10079 - Pizza Cutting
 * Last Modified: 2009.11.25
 * Author: chchwy
 */
#include<iostream>
int main()
{
    long long int k;
    while ( scanf("%lld", &k) == 1 )
    {
        if (k < 0) break;
        printf("%lld\n", k * (k + 1) / 2 + 1);
    }
    return 0;
}

10082.cpp

/**
 * UVa 10082 WERTYU
 * Author: chchwy
 * Last Modified: 2010.04.21
 */
#include<cstdio>

int main()
{
    char key[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";

    //set mapping
    char map[256];
    for (int i = 0; key[i] != NULL; ++i)
        map[ key[i] ] = key[i - 1];
    map[' '] = ' ';
    map['\n'] = '\n';

    //run
    int c;
    while ((c = getchar()) != EOF)
        putchar(map[c]);

    return 0;
}

101.cpp

/**
 * UVa 101 The Block Problem
 * Author: chchwy
 * Last Modified: 2011.06.16
 * Blog: http://chchwy.blogspot.com
 */
#include<cstdio>
#include<cstring>
#include<list>
#include<algorithm>
using namespace std;

list<int> stk[25];  // the blocks
int pos[25];        // current position of each block

void init_block(int n)
{

    for (int i = 0; i < n; ++i)
    {
        stk[i].clear();
        stk[i].push_back(i);
    }

    for (int i = 0; i < n; ++i)
        pos[i] = i;
}

bool in_the_same_stack(int x, int y)
{
    return (pos[x] == pos[y]);
}

// clear all the blocks above 'x'
void clear_above(int x)
{

    int px = pos[x];

    while (stk[px].back() != x)
    {

        // place block 'num' to its original stack[num]
        int num = stk[px].back();
        stk[num].push_back(num);
        pos[num] = num;

        stk[px].pop_back();
    }
}

void move(int x, int y)
{

    int px = pos[x], py = pos[y];

    auto move_begin = std::find(stk[px].begin(), stk[px].end(), x);
    auto move_end   = stk[px].end();

    // append blocks (move_begin ~ move_end) to the end of stk[pos[y]]
    stk[py].insert(stk[py].end(), move_begin, move_end);

    //update pos array
    for (auto it = move_begin; it != move_end; ++it)
    {
        pos[ (*it) ] = py;
    }
    stk[px].erase(move_begin, move_end);
}

void print_result(int num_blocks)
{

    for (int i = 0; i < num_blocks; ++i)
    {
        printf("%d:", i);

        for (int j = 0; j < stk[i].size(); ++j)
            printf(" %d", stk[i][j] );
        putchar('\n');
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("101.in", "r", stdin);
#endif

    int num_blocks;
    scanf("%d", &num_blocks);

    init_block(num_blocks);

    char cmd1[10], cmd2[10];
    int a, b;

    // [move/pile] a [onto/over] b
    while (scanf("%s %d %s %d", cmd1, &a, cmd2, &b) == 4)
    {

        // ignore illegal command
        if (a == b) continue;
        if (in_the_same_stack(a, b)) continue;

        if (strcmp("move", cmd1) == 0)
            clear_above(a);

        if (strcmp("onto", cmd2) == 0)
            clear_above(b);

        move(a, b);
    }
    print_result(num_blocks);

    return 0;
}

101.in

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

10125.cpp

/**
 * UVa 10125 Sumsets (AC)
 * Author: chchwy
 * Last Modified: 2010.03.18
 */
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int find(vector<int>& set)
{
    for (int d = set.size() - 1; d >= 0; --d) // find the largest d
        for (int a = 0; a < set.size(); ++a)
            for (int b = a + 1; b < set.size(); ++b)
                for (int c = b + 1; c < set.size(); ++c)
                    if ( (set[d] == set[a] + set[b] + set[c]) &&
                            a != d && b != d && c != d )

                        return set[d];
    return INT_MAX;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10125.in", "r", stdin);
#endif

    int numElement;
    while (cin >> numElement)
    {
        if (numElement == 0)
            break;

        /* input */
        vector<int> set(numElement);

        for (int i = 0; i < numElement; ++i)
            cin >> set[i];

        sort(set.begin(), set.end());

        /* find d = a + b + c */
        int d = find(set);
        if ( d == INT_MAX )
            cout << "no solution\n";
        else
            cout << d << "\n";
    }
    return 0;
}

10125.in

5
2 3 5 7 12
5
2 16 64 256 1024
8
0 -1 1 2 -15 9 -4 5
5
-10 -5 -2 -3 4
0

10137.cpp

/**
 * UVa 10137 (AC)
 * Author: chchwy
 * Last Modified: 2009.03.26
 */
#include<iostream>

/* read expense as cent.  ex. 1.23 dollar => 123 cent */
int getExpense()
{
    int i = 0;
    char c;
    char buf[16];
    while ((c = getchar()) != '\n')
    {
        if (c != '.')
            buf[i++] = c;
    }
    buf[i] = 0;
    return atoi(buf);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10137.in", "r", stdin);
    //freopen("10137.out","w",stdout);
#endif

    int stu[1000]; //expense of each student
    int stuNum;    //number of students

    /* for each case */
    while (scanf("%d ", &stuNum) == 1)
    {
        if (stuNum == 0) break;

        //compute the average
        int sum = 0;
        for (int i = 0; i < stuNum; ++i)
        {
            stu[i] = getExpense();
            sum += stu[i];
        }
        int avg = ((double)sum / stuNum) + 0.5;

        //compute the exchange amount
        int exchg1 = 0, exchg2 = 0;
        for (int i = 0; i < stuNum; ++i)
        {
            if (stu[i] > avg)
                exchg1 += stu[i] - avg;
            else if (stu[i] < avg)
                exchg2 += avg - stu[i];
        }
        double rslt = (exchg1 < exchg2) ? exchg1 : exchg2;
        rslt /= 100;
        printf("$%.2lf\n", rslt);
    }
    return 0;
}

10142.cpp

/*
 * ACM 10142 (AC)
 * Author: chchwy
 * Last Modified: 2009.04.02
 */
#include<iostream>

enum { MAX_CAND = 20, NEED_ELIMINATE, ALL_TIED, ELECTED };

class Candidate
{
public:
    int elim;
    int vote;
    char name[80 + 1];
    Candidate();
};

Candidate::Candidate()
{
    elim = 0;
    vote = 0;
}

class Ballots
{
    int ballot[1000][MAX_CAND + 1];

public:
    int numCand;
    int numVoter;
    //func
    Ballots();
    void read();
    int judge(Candidate cand[], int& flag);
    void eliminate(Candidate cand[]);
    void getFirstChoice(Candidate cand[]);
};

Ballots::Ballots()
{
    memset(ballot, 0, sizeof(ballot));
}

void Ballots::read()
{
    char buf[1024];
    numVoter = 0;
    while (fgets(buf, 1024, stdin) != NULL && buf[0] != '\r' && buf[0] != '\n')
    {
        char* p = strtok(buf, " \t");
        for (int i = 0; i < numCand; ++i)
        {
            ballot[numVoter][i] = atoi(p);
            p = strtok(NULL, " ");
        }
        numVoter++;
    }
}

void Ballots::getFirstChoice(Candidate cand[])
{
    for (int i = 1; i <= numCand; ++i)
        cand[i].vote = 0;
    for (int i = 0; i < numVoter; ++i)
    {
        int rank = 0;
        while ( cand[ ballot[i][rank] ].elim ) ++rank; //if cand is eliminate, find next cand
        ++cand[ ballot[i][rank] ].vote;
    }
}

void Ballots::eliminate(Candidate cand[])
{
    int min = 0;
    cand[0].vote = INT_MAX;
    for (int i = 1; i <= numCand; ++i)
    {
        if (!cand[i].elim && cand[i].vote < cand[min].vote )
            min = i;
    }
    int minVote = cand[min].vote;

    for (int i = 1; i <= numCand; ++i)
        if (!cand[i].elim && cand[i].vote == minVote)
            cand[i].elim = 1;
}

int Ballots::judge(Candidate cand[], int& flag)
{
    //find winner
    int half = numVoter / 2;
    for (int i = 1; i <= numCand; ++i)
    {
        if (cand[i].vote > half)
        {
            flag = ELECTED;
            return i;
        }
    }
    //check all tied
    int key = 0;
    for (int i = 1; i <= numCand; ++i)
    {
        if (!cand[i].elim)
        {
            if (key == 0)
                key = i;
            else if (cand[key].vote != cand[i].vote)
            {
                flag = NEED_ELIMINATE;
                return 0;
            }
        }
    }
    flag = ALL_TIED;
    return 0;
}

void readCandName(Candidate cand[MAX_CAND], int numCand)
{
    for (int i = 1; i <= numCand; i++)
        fgets(cand[i].name, 80 + 1, stdin);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10142.in", "r", stdin);
#endif

    int numCase;
    scanf("%d ", &numCase);

    while (numCase--)
    {
        Ballots blt;
        Candidate cand[MAX_CAND + 1];

        scanf("%d ", &blt.numCand);

        readCandName(cand, blt.numCand); //read candidates' name
        blt.read();    //read ballots data

        //count the ballots
        int winner, flag = NEED_ELIMINATE;

        blt.getFirstChoice(cand);
        winner = blt.judge(cand, flag);
        while (flag == NEED_ELIMINATE)
        {
            blt.eliminate(cand);   //eliminate the lowest candidate

            blt.getFirstChoice(cand);
            winner = blt.judge(cand, flag);
        }

        //output
        if (flag == ELECTED)
        {
            printf("%s", cand[winner].name);
        }
        else   //ALL_TIED
        {
            for (int i = 1; i <= blt.numCand; ++i)
                if (!cand[i].elim)
                    printf("%s", cand[i].name);
        }
        if (numCase > 0) printf("\n"); //blank line between cases
    }
    return 0;
}

10154.cpp

/**
 * UVa 10154 Weights and Measures
 * Author: chchwy
 * Last Modified: 2012.01.20
 * Blog: chchwy.blogspot.com
 */
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

enum { MAX_TURTLES = 5607 + 1 };

struct Turtle
{
    int strength;
    int weight;
};


inline int carry(Turtle turtle)
{
    return turtle.strength - turtle.weight;
}

bool cmp_strength(Turtle a, Turtle b)
{
    return carry(a) > carry(b);
}

int max_stack(Turtle turtle[], int n)
{
    sort(turtle, turtle + n, cmp_strength);

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

    }
    return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10154.in", "r", stdin);
#endif

    // Turtles
    Turtle turtle[MAX_TURTLES];

    // number of turtles
    int n = 0;

    while (cin >> turtle[n].strength >> turtle[n].weight)
    {
        n++;
    }

    printf("%d\n", max_stack(turtle, n));
    return 0;
}

10154.in

300 1000
1000 1200
200 600
100 101

10189.cpp

#include<iostream>

enum {MAX = 100};

int main()
{
    int row, col;
    int map[MAX + 5][MAX + 5];
    int drct[8][2] = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };
    int field = 1;

    while (scanf(" %d %d", &row, &col) == 2)
    {
        if (row == 0 && col == 0)
            break;

        if (field != 1) //blank line between cases
            printf("\n");

        //input
        for (int i = 0; i <= row + 1; ++i)
            for (int j = 0; j <= col + 1; ++j)
                map[i][j] = 0;

        char buf[100 + 2];
        fgets(buf, 3, stdin); //eat \n
        for (int i = 1; i <= row; ++i)
        {
            fgets(buf, sizeof(buf), stdin);
            for (int j = 1; j <= col; ++j)
                map[i][j] = buf[j - 1];
        }

        //mine sweeper
        printf("Field #%d:\n", field++);

        for (int i = 1; i <= row; ++i)
        {
            for (int j = 1; j <= col; ++j)
            {
                if (map[i][j] == '*')
                    printf("%c", '*');
                else
                {
                    int numMine = 0;
                    for (int k = 0; k < 8; ++k)
                        if (map[ i + drct[k][0] ][ j + drct[k][1] ] == '*')
                            numMine++;
                    printf("%d", numMine);
                }
            }
            printf("\n");
        }
    }
    return 0;
}

10196.cpp

/*
 *  UVa 10196 (AC)
 *  Author: chchwy
 *  Last Modified: 2009.04.20
 */
#include<iostream>

enum { BLACK = 0, WHITE = 1, NONE };

/* return 1=empty board, 0=not empty */
int emptyBoard (char board[][12])
{

    for (int i = 2; i < 8 + 2; ++i)
        for (int j = 2; j < 8 + 2; ++j)
            if ( board[i][j] != '.') //not empty
                return 0;
    return 1;
}

int readBoard (char board[][12])
{
    //read data
    for (int i = 2; i <= 2 + 8; ++i) //8¦æ´Ñ½L+1¦æªÅ¦æ
        fgets(board[i] + 2, 20, stdin);

    return emptyBoard(board);
}

//WHITE=upper case BLACK=lowercase
int check(char board[][12], int king[2], int color)
{
    //check Knight
    int knight = (color) ? 'n' : 'N'; //ex. BlackKing(color=0) <=> White Knight='N'

    if ( board[king[0] + 1][king[1] + 2] == knight ||
            board[king[0] + 1][king[1] - 2] == knight ||
            board[king[0] + 2][king[1] + 1] == knight ||
            board[king[0] + 2][king[1] - 1] == knight ||
            board[king[0] - 1][king[1] + 2] == knight ||
            board[king[0] - 1][king[1] - 2] == knight ||
            board[king[0] - 2][king[1] + 1] == knight ||
            board[king[0] - 2][king[1] - 1] == knight
       )
    {
        return color;
    }

    /* check the diagonal */
    int queen  = (color) ? 'q' : 'Q';
    int bishop = (color) ? 'b' : 'B';

    int x = king[0] + 1, y = king[1] + 1;
    while (board[x][y] == '.')  x += 1, y += 1;
    if (board[x][y] == queen || board[x][y] == bishop)
        return color;

    x = king[0] - 1, y = king[1] + 1;
    while (board[x][y] == '.')  x -= 1, y += 1;
    if (board[x][y] == queen || board[x][y] == bishop)
        return color;

    x = king[0] + 1, y = king[1] - 1;
    while (board[x][y] == '.')  x += 1, y -= 1;
    if (board[x][y] == queen || board[x][y] == bishop)
        return color;

    x = king[0] - 1, y = king[1] - 1;
    while (board[x][y] == '.')  x -= 1, y -= 1;
    if (board[x][y] == queen || board[x][y] == bishop)
        return color;

    /* check the straight */
    int rook = (color) ? 'r' : 'R';

    x = king[0], y = king[1] + 1;
    while (board[x][y] == '.')  y += 1;
    if (board[x][y] == queen || board[x][y] == rook)
        return color;

    x = king[0], y = king[1] - 1;
    while (board[x][y] == '.')  y -= 1;
    if (board[x][y] == queen || board[x][y] == rook)
        return color;

    x = king[0] + 1, y = king[1];
    while (board[x][y] == '.')  x += 1;
    if (board[x][y] == queen || board[x][y] == rook)
        return color;

    x = king[0] - 1, y = king[1];
    while (board[x][y] == '.')  x -= 1;
    if (board[x][y] == queen || board[x][y] == rook)
        return color;

    /* check the Pawn */
    if (color == BLACK)
    {
        if ( board[ king[0] + 1 ][ king[1] - 1 ] == 'P' ||
                board[ king[0] + 1 ][ king[1] + 1 ] == 'P')
            return color;
        return NONE;
    }
    else   //color=White
    {
        if ( board[ king[0] - 1 ][ king[1] + 1 ] == 'p' ||
                board[ king[0] - 1 ][ king[1] - 1 ] == 'p')
            return color;
        return NONE;
    }
}

int checkTheCheck(char board[][12])
{
    int king[2][2];

    //find the position of kings
    for (int i = 2; i < 8 + 2; ++i)
    {
        for (int j = 2; j < 8 + 2; ++j)
        {
            if (board[i][j] == 'k')
                king[BLACK][0] = i, king[BLACK][1] = j;
            else if (board[i][j] == 'K')
                king[WHITE][0] = i, king[WHITE][1] = j;
        }
    }
    //BLACK=0, WHITE=1
    int result;
    for (int color = BLACK; color <= WHITE; ++color)
        if ( NONE != (result = check(board, king[color], color)) )
            return result;

    return NONE;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10196.in", "r", stdin);
#endif

    char board[8 + 4][8 + 4];
    memset(board, 0, sizeof(board));
    int counter = 1;
    int isEmpty = readBoard(board);

    while (!isEmpty) //for each case
    {
        int check = checkTheCheck(board);
        if (check == BLACK)
            printf("Game #%d: black king is in check.\n", counter);
        else if (check == WHITE)
            printf("Game #%d: white king is in check.\n", counter);
        else if (check == NONE)
            printf("Game #%d: no king is in check.\n", counter);
        ++counter;

        isEmpty = readBoard(board);
    }
}

102.cpp

/**
 * UVa 102 Ecological Bin Packing
 * Author: chchwy
 * Last Modified: 2008.09.10
 * Tag: Adhoc
 */
#include<iostream>

enum { B = 0, C = 1, G = 2 };

int main()
{
    //六種排列組合
    int binColor[][3] = { {B, C, G}, {B, G, C}, {C, B, G},
        {C, G, B}, {G, B, C}, {G, C, B}
    };

    char s[][4] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"};

    int bin[3][3];
    while (scanf("%d%d%d%d%d%d%d%d%d",
                 &bin[0][B], &bin[0][G], &bin[0][C],
                 &bin[1][B], &bin[1][G], &bin[1][C],
                 &bin[2][B], &bin[2][G], &bin[2][C]) != EOF)
    {
        int currentMove = 0;
        int totalGlasses = 0;

        for (int i = 0; i < 3; i++)
            totalGlasses += (bin[i][B] + bin[i][G] + bin[i][C]);

        int minMove = totalGlasses;
        int minNo = 0; //第minNo號排列組合move最少

        //六種排列組合都跑過一次
        for (int i = 0; i < 6; i++) //移動的次數 = 總瓶數-不用移動的瓶數
        {
            currentMove = totalGlasses
                          - bin[0][binColor[i][0]]
                          - bin[1][binColor[i][1]]
                          - bin[2][binColor[i][2]];

            if (currentMove < minMove)
            {
                minMove = currentMove;
                minNo = i;
            }
        }
        printf("%s %d\n", s[minNo], minMove);
    }
    return 0;
}

10200.cpp

/**
 * UVa 10200 (AC)
 * Author: chchwy
 * Last Modified: 2009.11.22
 */
#include<iostream>
using namespace std;

bool isPrime(int p)
{
    if (p % 2 == 0)
        return false;

    for (int i = 3; i * i <= p; i += 2)
        if (p % i == 0)
            return false;
    return true;
}

char p[10000]; //0未測 1質數 2非質數

int main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif

    int a, b;
    while (scanf("%d %d", &a, &b) == 2)
    {
        int counter = 0;
        for (int i = a; i <= b; ++i)
        {
            //look for table first
            if (p[i] == 1)
            {
                counter++;
            }
            else if (p[i] == 2)
            {
                continue;
            }
            else
            {
                int num = i * i + i + 41;
                if ( isPrime(num) )
                {
                    counter++;
                    p[i] = 1;
                }
                else
                {
                    p[i] = 2;
                }
            }
        }
        double result =  (double)counter / (b - a + 1) * 100 ;
        printf("%.2lf\n", result + 0.00000005);
    }
    return 0;
}

10267.cpp

/**
 * UVa 10267 (AC)
 * Author: chchwy
 * Last Modified: 2009.04.07
 */
#include<iostream>

enum {MAXSIZE = 250};

class Queue
{
    enum {MAX = 40000};
    int data[MAX][2];
    int front, rear;
public:
    Queue()
    {
        front = 0;
        rear = 0;
    }
    void add(int x, int y)
    {
        if (!full())
        {
            rear = (rear + 1) % MAX;
            data[rear][0] = x;
            data[rear][1] = y;
        }
    }
    void pop(int& x, int& y)
    {
        if ( !empty() )
        {
            front = (front + 1) % MAX;
            x = data[front][0];
            y = data[front][1];
        }
    }
    int full()
    {
        return ((rear + 1) % MAX == front) ? 1 : 0;
    }
    int empty()
    {
        return (front == rear) ? 1 : 0;
    }
};

void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

class Graph
{
    char buffer[MAXSIZE + 2][MAXSIZE + 2];
    int width, height;
public:
    void createGraph(int width, int height); //I
    void clear(); //C
    void drawPixel(int x, int y, int color); //L
    void drawVertical(int x, int yBeg, int yEnd, int color); //V
    void drawHorizontal(int y, int xBeg, int xEnd, int color); //H
    void fillRect(int x1, int y1, int x2, int y2, int color);//K
    void fillRegion(int x, int y, int color); //F
    void saveFile(char filename[16]); //S
};

void Graph::createGraph(int w, int h)
{
    width = w;
    height = h;
    clear();
    for (int i = 0; i <= height + 1; ++i)
    {
        buffer[i][width + 1] = 0;
        buffer[i][0] = 0;
    }
    for (int i = 0; i <= width + 1; ++i)
    {
        buffer[0][i] = 0;
        buffer[height + 1][i] = 0;
    }
}
void Graph::clear()
{
    for (int i = 0; i <= height; ++i)
        for (int j = 0; j <= width; ++j)
            buffer[i][j] = 'O';
}
void Graph::drawPixel(int x, int y, int color)
{
    buffer[y][x] = color;
}
void Graph::drawVertical(int x, int yBeg, int yEnd, int color)
{
    if (yBeg > yEnd)
        swap(yBeg, yEnd);

    for (int i = yBeg; i <= yEnd; ++i)
        buffer[i][x] = color;
}
void Graph::drawHorizontal(int xBeg, int xEnd, int y, int color)
{
    if (xBeg > xEnd)
        swap(xBeg, xEnd);

    for (int i = xBeg; i <= xEnd; ++i)
        buffer[y][i] = color;
}
void Graph::fillRect(int x1, int y1, int x2, int y2, int color)
{
    for (int i = y1; i <= y2; ++i)
        for (int j = x1; j <= x2; ++j)
            buffer[i][j] = color;
}
void Graph::fillRegion(int x0, int y0, int color)
{
    int origColor = buffer[y0][x0];
    if (origColor == color)
        return;

    int i = 1000;
    //BFS
    Queue q;
    q.add(x0, y0);
    buffer[y0][x0] = color;

    while (!q.empty())
    {
        int x, y;
        q.pop(x, y);

        if (buffer[y - 1][x] == origColor)
        {
            buffer[y - 1][x] = color;
            q.add(x, y - 1);
        }
        if (buffer[y][x + 1] == origColor)
        {
            buffer[y][x + 1] = color;
            q.add(x + 1, y);
        }
        if (buffer[y + 1][x] == origColor)
        {
            buffer[y + 1][x] = color;
            q.add(x, y + 1);
        }
        if (buffer[y][x - 1] == origColor)
        {
            buffer[y][x - 1] = color;
            q.add(x - 1, y);
        }
    }
}
void Graph::saveFile(char filename[16])
{
    printf("%s\n", filename);
    for (int i = 1; i <= height; ++i)
        printf("%s\n", buffer[i] + 1); //第一個char不輸出
}

void parseCommand(char command[32], char par[6][16])
{
    int i = 0;
    char* p = strtok(command, " \n");
    while (p)
    {
        strcpy(par[i++], p);
        p = strtok(NULL, " \n");
    }
}


int main()
{
#ifndef ONLINE_JUDGE
    freopen("10267.in", "r", stdin);
#endif

    Graph g;
    char command[64];

    while ( fgets(command, 64, stdin) )
    {
        char par[6][16];

        parseCommand(command, par);

        int op = par[0][0];

        int x, y, color, xBeg, xEnd, yBeg, yEnd, x1, x2, y1, y2;

        switch (op)
        {
        case 'I':
            x = atoi(par[1]);  y = atoi(par[2]);
            g.createGraph(x, y);
            break;
        case 'C':
            g.clear();
            break;
        case 'L':
            x = atoi(par[1]);  y = atoi(par[2]); color = par[3][0];
            g.drawPixel(x, y, color);
            break;
        case 'V':
            x = atoi(par[1]); yBeg = atoi(par[2]); yEnd = atoi(par[3]);
            color = par[4][0];
            g.drawVertical(x, yBeg, yEnd, color);
            break;
        case 'H':
            xBeg = atoi(par[1]); xEnd = atoi(par[2]); y = atoi(par[3]);
            color = par[4][0];
            g.drawHorizontal(xBeg, xEnd, y, color);
            break;
        case 'K':
            x1 = atoi(par[1]); y1 = atoi(par[2]);
            x2 = atoi(par[3]); y2 = atoi(par[4]);
            color = par[5][0];
            g.fillRect(x1, y1, x2, y2, color);
            break;
        case 'F':
            x = atoi(par[1]); y = atoi(par[2]); color = par[3][0];
            g.fillRegion(x, y, color);
            break;
        case 'S':
            g.saveFile(par[1]);
            break;
        case 'X':
            return 0;
        };
    }
    return 0;
}

103.cpp

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

enum {MAX_DIMENSION = 10, MAX_BOX = 30};

class Box
{
public:
    static int dimension;

    int no;
    int edge[MAX_DIMENSION];

    static int lexico_less(const Box& a, const Box& b);

    bool operator<(const Box& right);
    void sort_edges();
};

int Box::dimension;

int Box::lexico_less(const Box& a, const Box& b)
{
    for (int i = 0; i < dimension; ++i)
        if ( !(a.edge[i] <= b.edge[i]) )
            return false;
    return true;
}

void Box::sort_edges()
{
    sort(edge, edge + dimension);
}

bool Box::operator<(const Box& rh)
{
    for (int i = 0; i < dimension; ++i)
        if ( ! (edge[i] < rh.edge[i]) )
            return false;
    return true;
}

int main()
{

#ifndef ONLINE_JUDGE
    freopen("103.in", "r", stdin);
#endif

    int num_box;
    int dimension;
    Box box[MAX_BOX];

    /* for each case */
    while (scanf("%d %d", &num_box, &dimension) == 2)
    {
        // input
        Box::dimension = dimension;
        for (int i = 0; i < num_box; ++i)
        {
            for (int j = 0; j < dimension; ++j)
                scanf("%d", &box[i].edge[j]);

            box[i].no = i + 1;
            box[i].sort_edges();
        }

        // sort box by lexicographic order
        sort(box, box + num_box, Box::lexico_less);

        // LIS
        int length[MAX_BOX];
        int   prev[MAX_BOX];

        for (int i = 0; i < num_box; ++i) length[i] = 1;
        for (int i = 0; i < num_box; ++i) prev[i] = -1;

        for (int i = 0; i < num_box; ++i)
        {
            for (int j = i + 1; j < num_box; ++j)
            {
                if ( box[i] < box[j] )
                {
                    if (length[i] + 1 > length[j])
                    {
                        length[j] = length[i] + 1;
                        prev[j] = i;
                    }
                }
            }
        }

        int max = 0;
        for (int i = 0; i < num_box; ++i)
        {
            if (length[i] > length[max])
            {
                max = i;
            }
        }

        //print the result
        printf("%d\n", length[max]);

        int output_seq[MAX_BOX];
        int size = 0;

        int cur = max;
        do
        {
            output_seq[size++] = box[cur].no;
            cur = prev[cur];
        }
        while ( cur != -1 );

        for (int i = size - 1; i > 0; --i)
            printf("%d ", output_seq[i]);
        printf("%d\n", output_seq[0]);
    }
    return 0;
}

103.in

3 2
2 2
2 2
2 2
5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9
10 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
6 1
6
8
10
4
5
4
30 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
200 201 202 203 204 205 206 207 208 209
100 101 102 103 104 105 106 107 108 109
300 301 302 303 304 305 306 307 308 309
200 201 202 203 204 205 206 207 208 209
100 101 102 103 104 105 106 107 108 109
300 301 302 303 304 305 306 307 308 309
400 401 402 403 404 405 406 407 408 409
500 501 502 503 504 505 506 507 508 509
411 412 413 414 415 416 417 418 419 420
521 522 523 524 525 526 527 528 529 530
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5

10300.cpp

/*
 * UVa 10300
 * Author: chchwy
 * Last Modified: 2009.10.30
 */
#include <cstdio>

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10300.in", "r", stdin);
#endif

    int cases;
    scanf("%d ", &cases);

    while (cases--)
    {
        int numFarmer;
        scanf("%d ", &numFarmer);

        int sum = 0;
        int farmSize, numAnimal, efValue;
        for (int i = 0; i < numFarmer; ++i)
        {
            scanf("%d %d %d ", &farmSize, &numAnimal, &efValue);
            sum += farmSize * efValue;
        }
        printf("%d\n", sum);
    }
    return 0;
}

10301.cpp

/**
 * UVa 10301 (WA)
 * Author: chchwy
 * Last Modified: 2009.11.09
 */
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

class Ring
{
public:
    double x, y, radius;

    double distance(Ring&);
    bool  isGlued(Ring&);
    void print();
};

/* 計算兩個圓心的距離 */
double Ring::distance(Ring& r)
{
    return sqrt( (x - r.x) * (x - r.x) + (y - r.y) * (y - r.y) );
}
/* 圓心距離必須 小於半徑之和 大於半徑之差 */
bool Ring::isGlued(Ring& r)
{

    double dist = distance(r);
    return dist < (radius + r.radius) && dist > fabs( radius - r.radius );
}

void Ring::print()
{
    printf("(%.2f, %.2f, %.2f)\n", x, y, radius);
}

/* find the largest component */
int pickUpLargest( vector<Ring>& list )
{
    vector<vector<Ring> > component;
    while ( !list.empty() )
    {

        Ring r = list.back(); list.pop_back();

        for (int i = 0; i < component.size(); ++i)
        {
            if ( isGlued(component[i], r ) )
            {
                component.push_back(r);
                break;
            }
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10301.in", "r", stdin);
#endif

    int numRing;
    while ( scanf("%d", &numRing ) )
    {
        if (numRing < 0) break;

        /* read input */
        vector<Ring> rings;

        for (int i = 0; i < numRing; ++i)
        {
            Ring r;
            scanf("%lf %lf %lf", &r.x, &r.y, &r.radius );
            rings.push_back(r);
        }

        /* find the largest component */
        int max = pickUpLargest(rings);

        if ( max == 1 ) printf("The largest component contains 1 ring.\n");
        else  printf("The largest component contains %d rings.\n", max);
    }
    return 0;
}

10301.in

4
0.0 0.0 1.0
-1.5 -1.5 0.5
1.5 1.5 0.5
-2.0 2.0 3.5
3
3.0 2.0 2.0
0.0 -0.5 1.0
0.0 0.0 2.0
5
-2.0 0.0 1.0
1.0 -1.0 1.0
0.0 1.0 0.5
2.0 0.0 1.0
-1.0 1.0 1.0
6
0.0 0.0 0.5
1.0 0.0 0.5
2.0 0.0 0.5
3.0 0.0 0.5
4.0 0.0 0.5
0.5 0.0 0.5
2
0.0 0.0 3.0
0.0 0.0 1.0
-1

10315.cpp

/**
 * UVa 10315
 * Author: chchwy
 * Last Modified: 2009.11.3
 */
#include <iostream>

class Card
{
    friend class PokerHand;
    int  value, suit;
    int  convert(char);
    void setValue(char c)
    {
        value = convert(c);
    }
    static bool cmp(const Card& left, const Card& right)
    {
        return (left.value < right.value);
    }
};

/* 將牌的文字點數換成整數值 */
int Card::convert(char c)
{
    if (c <= '9') return c - '0';
    if (c == 'T') return 10;
    if (c == 'J') return 11;
    if (c == 'Q') return 12;
    if (c == 'K') return 13;
    if (c == 'A') return 14;
}

enum HANDRANK
{
    HIGH_CARD, PAIR, TWO_PAIR, THREE_KIND,
    STRAIGHT, FLUSH, FULL_HOUSE, FOUR_KIND,
    STRAIGHT_FLUSH
};

/* 一組五張牌 */
class PokerHand
{
    Card card[5];
    HANDRANK rank;
public:
    void fetchCard(char*);
    HANDRANK  getRank();
    int  isStraight();
    int  isFlush();
    int  is4Kind();
    int  is3Kind();
    int  numPairs();
    int  compareTo(PokerHand&); //win>0, lose<0, tie==0
    void fetchRankValues(int[5]);
};

int PokerHand::isStraight()
{
    for (int i = 0; i < 4; ++i)
    {
        if ( card[i].value + 1 != card[i + 1].value )
            return false;
    }
    return true;
}

int PokerHand::isFlush()
{
    int curSuit = card[0].suit;
    for (int i = 1; i < 5; ++i)
        if ( card[i].suit != curSuit)
            return false;
    return true;
}

int PokerHand::is4Kind()
{
    if (card[0].value == card[3].value ||
            card[1].value == card[3].value)
        return true;
    return false;
}

int PokerHand::is3Kind()
{
    for (int i = 0; i < 3; ++i)
        if (card[i].value == card[i + 2].value)
            return true;
    return false;
}

int PokerHand::numPairs()
{
    int counter = 0;
    for (int i = 0; i < 4; ++i)
    {
        if (card[i].value == card[i + 1].value)
            counter++, i++;
    }
    return counter;
}

void PokerHand::fetchCard(char* buf)
{
    int bufIndex = 0;
    for (int i = 0; i < 5; ++i)
    {
        card[i].setValue( buf[bufIndex++] );
        card[i].suit = buf[bufIndex++];
        bufIndex++; //空白跳過
    }
    std::sort(card, card + 5, Card::cmp);
    rank = getRank();
}

HANDRANK PokerHand::getRank()
{
    int st = isStraight();
    int fl = isFlush();

    if (st && fl) //同花順
        return  STRAIGHT_FLUSH;
    else if (st) //順子
        return STRAIGHT;
    else if (fl) //同花
        return FLUSH;

    if ( is4Kind() ) //鐵支
        return FOUR_KIND;

    int three = is3Kind();
    int pair = numPairs();

    if ( three && pair == 2 ) //葫蘆
        return FULL_HOUSE;
    if (three) //三條
        return THREE_KIND;
    if (pair == 2) //吐胚
        return TWO_PAIR;
    if (pair == 1) //胚
        return PAIR;

    return HIGH_CARD;
}

void PokerHand::fetchRankValues(int rankValues[5])
{
    memset(rankValues, 0, sizeof(int) * 5);
    switch (rank)
    {
    case STRAIGHT_FLUSH:
    case STRAIGHT:
        rankValues[0] = card[4].value;
        break;
    case FLUSH:
    case HIGH_CARD:
        for (int i = 0; i < 5; ++i)
            rankValues[i] = card[4 - i].value;
        break;
    case FULL_HOUSE:
    case FOUR_KIND:
    case THREE_KIND:
        rankValues[0] = card[2].value;
        break;
    case TWO_PAIR:
        //落單的一張只有三種位子 0 2 4
        if (card[0].value != card[1].value) //ex. 2 33 44
        {
            rankValues[0] = card[4].value;
            rankValues[1] = card[2].value;
            rankValues[2] = card[0].value;
        }
        else if (card[2].value != card[3].value) //ex.33 4 55
        {
            rankValues[0] = card[4].value;
            rankValues[1] = card[0].value;
            rankValues[2] = card[2].value;
        }
        else   //ex.55 66 7
        {
            rankValues[0] = card[2].value;
            rankValues[1] = card[0].value;
            rankValues[2] = card[4].value;
        }
        break;
    case PAIR:
        int pairValue;
        for (int i = 0; i <= 3; ++i) //search pair
            if (card[i].value == card[i + 1].value)
            {
                pairValue = card[i].value;
                break;
            }
        rankValues[0] = pairValue;
        for (int i = 4, r = 1 ; i >= 0; --i) //i for card, r for rankValues
        {
            if (card[i].value == pairValue)
                continue;
            rankValues[r++] = card[i].value;
        }
        break;
    }
}

/* 比較兩個牌組 */
int PokerHand::compareTo( PokerHand& op )
{
    //先比Rank
    if ( rank > op.rank )
        return 1;
    if ( rank < op.rank )
        return -1;

    //Rank相等 要比點數
    int myRank[5], opRank[5];
    fetchRankValues(myRank), op.fetchRankValues(opRank);

    for (int i = 0; i < 5; ++i)
    {
        if (myRank[i] > opRank[i])
            return 1; // i win.
        if (myRank[i] < opRank[i])
            return -1;//op win.
    }
    return 0; //tie
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10315.in", "r", stdin);
#endif

    char buf[64];

    while ( fgets(buf, sizeof(buf), stdin) != NULL )
    {
        PokerHand black, white;

        black.fetchCard(buf);
        white.fetchCard(buf + 15);

        int win = black.compareTo(white);

        if (win > 0)
            puts("Black wins.");
        else if (win < 0)
            puts("White wins.");
        else
            puts("Tie.");
    }
    return 0;
}

10315.in

2H 3D 5S 9C KD 2C 3H 4S 8C AH
2H 4S 4C 2D 4H 2S 8S AS QS 3S
2H 3D 5S 9C KD 2C 3H 4S 8C KH
2H 3D 5S 9C KD 2D 3H 5C 9S KH

10394.cpp

/**
 * UVa 10394 Twin Primes
 * Author: chchwy
 * Last Modified: 2011/07/21
 * Blog: http://chchwy.blogspot.com
 */
#include<cstdio>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;

enum { MAX = 20000000 + 1 };

bitset<MAX> p;

void sieve()
{
    p.flip();

    p[0] = p[1] = 0;

    for (int i = 3; i * i <= MAX; i += 2) // WA: i<=MAX  (³o¼Ë¤U­±i¥­¤è´N·¸¦ì¤F)
    {
        if ( p[i] )
            for (unsigned int j = i * i; j < MAX; j += i)
                p[j] = 0;
        /* if( j==169321 ) cout << "GOT!! i="<< i <<endl; overflow */
    }
}

int main()
{
    sieve();

    vector<pair<int, int> > twin;

    twin.push_back(make_pair(0, 0)); // skip twin[0]

    for (int i = 5; i < MAX; i += 2)
    {
        if ( p[i] && p[i - 2] )
        {
            twin.push_back(make_pair(i - 2, i));
        }
    }

    int no;
    while ( scanf("%d", &no) == 1 )
    {
        printf("(%d, %d)\n", twin[no].first, twin[no].second);
    }

    return 0;
}

104.cpp

/**
 * UVa 104 Arbitrage
 * Author: chchwy
 * Last Modified: 2011/01/30
 * Tag: Dynamic Programming, Floyd-Warshall
 */
#include<iostream>
enum {MAX = 20};

int main()
{
    int n; //the dimension of table
    double profit[MAX][MAX][MAX];
    int path[MAX][MAX][MAX]; //backtracking

    while (scanf("%d", &n) == 1)
    {
        memset(profit, 0, sizeof(profit)); // init profit

        //profit[0][i][j] = input for the program
        //profit[0][i][i] = 1, for all i
        //path[0][i][j] = i, for all i, j
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (i == j)
                    profit[0][i][j] = 1.0;
                else
                    scanf("%lf", &profit[0][i][j]);
                path[0][i][j] = i;
            }
        }

        //Floyd-Warshall
        for (int steps = 1; steps < n; ++steps)
        {
            for (int k = 0; k < n; ++k) //intermediate node k
            {
                for (int i = 0; i < n; ++i) //path from i to j
                {
                    for (int j = 0; j < n; ++j)
                    {
                        double tmp = profit[steps - 1][i][k] * profit[0][k][j];
                        if (tmp > profit[steps][i][j])
                        {
                            profit[steps][i][j] = tmp;
                            path[steps][i][j] = k;
                        }
                    }
                }
            }
        }

        //Find the shortest path to profit 1%
        int steps, targetNo = -1; //targetNo = the number of currency we want
        for (steps = 1; steps < n; steps++)
        {
            for (int i = 0; i < n; i++)
            {
                if (profit[steps][i][i] > 1.01)
                {
                    targetNo = i;
                    break;
                }
            }
            if (targetNo != -1)
                break;
        }

        //output
        if (targetNo == -1)
        {
            printf("no arbitrage sequence exists\n");
        }
        else
        {
            int outputSeq[MAX]; //for reverse sequnece
            int index = 0;

            int currentNo = targetNo;
            outputSeq[index++] = targetNo;
            for (int s = steps; s >= 0; --s) //path from targetNo to currentNo
            {
                currentNo = path[s][targetNo][currentNo];
                outputSeq[index++] = currentNo;
            }

            for (int i = index - 1; i > 0; --i)
                printf("%d ", outputSeq[i] + 1);
            printf("%d\n", outputSeq[0] + 1);
        }
    }
    return 0;
}

10405.cpp

/**
 * UVa 10405 Longest Common Subsequence
 * Author: chchwy
 * Last Modified: 2010.04.01
 */
#include<iostream>
using namespace std;

enum {MAX_LENGTH = 1000};

int LCS_save_memory(string& str1, string& str2)
{
    int path[2][MAX_LENGTH + 1];
    int cur = 0, prev = 1;

    memset(path, 0, sizeof(path));

    for (int i = 1; i <= str1.size(); ++i)
    {
        for (int j = 1; j <= str2.size(); ++j)
        {

            if ( str1[i - 1] == str2[j - 1] )
            {
                path[cur][j] = path[prev][j - 1] + 1;
            }
            else
            {
                path[cur][j] = max(path[cur][j - 1], path[prev][j]);
            }
        }
        swap(cur, prev);
    }
    return path[prev][str2.size()];
}

int LCS(string& str1, string str2)
{
    int path[MAX_LENGTH + 1][MAX_LENGTH + 1];

    for (int i = 0; i < str1.size(); ++i)
        path[i][0] = 0;
    for (int i = 0; i < str2.size(); ++i)
        path[0][i] = 0;

    for (int i = 1; i <= str1.size(); ++i)
    {
        for (int j = 1; j <= str2.size(); ++j)
        {

            if ( str1[i - 1] == str2[j - 1] )
            {
                path[i][j] = path[i - 1][j - 1] + 1;
            }
            else
            {
                path[i][j] = max(path[i][j - 1], path[i - 1][j]);
            }
        }
    }
    return path[str1.size()][str2.size()];
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10405.in", "r", stdin);
#endif

    string str1, str2;
    while ( getline(cin, str1) && getline(cin, str2) )
    {
        printf("%d\n", LCS(str1, str2) );
        // printf("%d\n", LCS_save_memory(str1, str2) );
    }
    return 0;
}

10405.in

abcdeffffff
abcdebbbb

10499.cpp

/**
 * UVa 10499 The Land of Justice (AC)
 * Author: chchwy
 * Last Modified: 2009.12.07
 */
#include<iostream>

int main()
{
    long long int n;
    while (scanf("%lld", &n) == 1)
    {
        if (n < 0) break;
        if (n == 1) printf("0%%\n");
        else
            printf("%lld%%\n", n * 25);
    }
    return 0;
}

105.cpp

/**
 * UVa 105 UVa 105 The Skyline Problem
 * Author: chchwy
 * Last Modified: 2008.11.27
 * Tag: Brute Force
 */
#include<iostream>
using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("105.in", "r", stdin);
#endif;

    int map[10000 + 1];
    int rightMax = 0; // the right most position of buildings

    memset(map, 0, sizeof(map));

    //read and brute force
    int left, height, right;
    while (scanf("%d %d %d", &left, &height, &right) == 3)
    {
        for (int i = left; i < right; ++i)
        {
            if (height > map[i])
                map[i] = height;
        }
        if (right > rightMax)
            rightMax = right;
    }

    //output
    int prev = 0;
    for (int i = 0; i < rightMax; ++i)
    {
        if (prev == map[i])
            continue;
        printf("%d %d ", i, map[i]);
        prev = map[i];
    }
    printf("%d %d\n", rightMax, 0);
    return 0;
}

105.in

1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

10533.cpp

/*
 * UVa 10533 (AC)
 * Author: chchwy
 * Last Modified: 2009.11.22
 */
#include<iostream>

enum {MAX = 1000001, SQRT_MAX = 1001};

char p[MAX]; //prime=0, not prime=1

void shieve()
{
    p[0] = p[1] = 1;
    for (int i = 2; i <= SQRT_MAX; ++i)
    {
        if (p[i] == 1)
            continue;
        for (int j = i * i; j < MAX; j += i)
            p[j] = 1;
    }
}

bool isDigitPrime(int in)
{
    int sum = 0;
    while (in)
    {
        sum += in % 10;
        in = in / 10;
    }
    if (!p[sum])
        return true;
    return false;
}

int dpCum[MAX];

void buildDigitPrime()
{
    for (int i = 2; i < MAX; ++i)
    {
        if ( p[i] == 0 && isDigitPrime(i) )
            dpCum[i] = dpCum[i - 1] + 1;
        else
            dpCum[i] = dpCum[i - 1];
    }
}

int main()
{
    shieve();
    buildDigitPrime();

    int numCase;
    scanf("%d", &numCase);

    int a, b;
    while (numCase--)
    {
        scanf("%d %d", &a, &b);
        printf("%d\n", dpCum[b] - dpCum[a - 1]);
    }
    return 0;
}

10591.cpp

/**
 * Problem: UVa 10591 Happy Number
 * Author: chchwy
 * Last Modified: 2010.01.30
 */
#include<cstdio>

char happy[1000] =
{
    0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
    0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0,
    1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0,
    0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
    1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
    0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
    0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0,
    0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
    0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
    0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
    0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0,
    0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0,
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0,
    1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
    1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,
    0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
    0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0,
    0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0,
    1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0
};

//取n的各位數平方和
int toNext(int n)
{
    int sum = 0;
    while ( n != 0 )
    {
        int tmp = n % 10;
        sum += tmp * tmp;
        n /= 10;
    }
    return sum;
}

bool isHappy(int n)
{
    while (n > 1000)
        n = toNext(n);
    return happy[n];
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10591.in", "r", stdin);
#endif

    int numCase;
    scanf("%d", &numCase );

    for (int i = 1; i <= numCase; ++i)
    {
        int n;
        scanf("%d", &n );
        if ( isHappy(n) )
            printf("Case #%d: %d is a Happy number.\n", i, n);
        else
            printf("Case #%d: %d is an Unhappy number.\n", i, n);
    }
    return 0;
}

10591.in

3
7
4
13

106.cpp

/**
 * UVa 106 Fermat vs. Pythagoras
 * Author: chchwy
 * Last Modified: 2011.03.20
 * Tag: Math, Pythagorean triples
 */
#include<cstdio>
#include<cstring>
#include<cmath>

short int p[1000001];

int gcd(int m, int n)
{
    int k;
    while (k = m % n)
    {
        m = n;
        n = k;
    }
    return n;
}

int main()
{
    int max;
    while (scanf("%d", &max) == 1)
    {
        int numTuple = 0; //number of tuple(a,b,c)
        memset(p, 0, sizeof(p));

        // 用雙層迴圈跑遍(x,y)所有可能的值
        for (int x = 1; x < 1000; ++x)
        {
            for (int y = x + 1;; y += 2)
            {
                if (gcd(x, y) != 1) continue;

                int a, b, c; //tuple(a,b,c)
                a = y * y - x * x;
                b = 2 * x * y;
                c = y * y + x * x;
                if (c > max) break;

                numTuple++;

                int ma = a, mb = b, mc = c;
                while (mc <= max)
                {
                    p[ma] = p[mb] = p[mc] = 1;
                    ma += a;
                    mb += b;
                    mc += c;
                }
            }
        }
        int numNotInTuple = max;
        for (int i = 0; i <= max; ++i)
            numNotInTuple -= p[i];

        printf("%d %d\n", numTuple, numNotInTuple);
    }
    return 0;
}

10616.cpp

/**
 * UVa 10616 Divisible Group Sum
 * Author: chchwy
 * Last Modified: 2011.08.11
 * Tag: Dynamic Programming, Subset Sum, Math Module
 */
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>

using std::vector;

enum
{
    MAX_NUM = 200,
    MAX_DIVISOR = 20,
    MAX_M = 10
};

vector<int> n;  // the number set
int D;          // the divisor
int M;          // the take number

int  c[MAX_NUM][MAX_DIVISOR + 1][MAX_M];
bool v[MAX_NUM][MAX_DIVISOR + 1][MAX_M]; // already in table or not


int mod( int s )
{
    if ( s >= 0 )
        return s % D;
    else
        return D - (abs(s) % D);
}

// Top-down Dynamic Programming
// (i,j,k) = (i+1, j+n[i], k-1)  or (i+1, j, k)

// i   : current index
// sum : current sum
// k   : numbers left to pick
int recur_subset( int i, int sum, int k )
{
    //printf("recur (%d %d %d)  , cur sum=%d\n", i, sum, k, sum);
    sum = mod(sum);

    if ( v[i][sum][k] )
    {
        return c[i][sum][k];
    }

    if ( k == 0 )
    {
        return ((sum % D == 0) ? 1 : 0 );
    }

    if ( i == n.size() )
    {
        return 0;
    }

    int ans_count = 0;

    ans_count += recur_subset(i + 1, sum + n[i], k - 1 ); // take n[i] or
    ans_count += recur_subset(i + 1, sum, k);       // not take n[i]

    c[i][sum][k] = ans_count;
    v[i][sum][k] = true;

    return ans_count;
}

int solve()
{
    memset(c, 0, sizeof(c));
    memset(v, 0, sizeof(v));

    return recur_subset(0, 0, M);
}

int main()
{
#ifndef ONLINE_JUDGE
    if ( freopen("10616.in", "r", stdin) == NULL ) puts("AHHHHH~");
#endif

    int set_no = 1;

    int num_num;    // the number of input numbers
    int num_query;  // the number of querys

    while ( scanf("%d%d", &num_num, &num_query) == 2 )
    {
        if ( num_num == 0 && num_query == 0 ) break;

        n.resize(num_num);

        for (int i = 0; i < num_num; ++i)
            scanf("%d", &n[i]);

        printf("SET %d:\n", set_no++);
        for (int i = 1; i <= num_query; ++i)
        {
            scanf("%d%d", &D, &M);
            printf("QUERY %d: %d\n", i, solve());
        }
    }
    return 0;
}

10616.in

4 1
1
2
3
4
2 3
10 2
1
2
3
4
5
6
7
8
9
10
5 1
5 2
5 1
2
3
4
5
6
6 2
3 1
1 -1
3 2
0 0

107.cpp

/**
 * UVa 107 The Cat in the Hat
 * Author: chchwy
 * Last Modified: 2010.02.28
 * Tag: Math, Recursion
 */
#include<cstdio>

void find (int initHeight, int kitten)
{
    /* iterate n to fit the answer */
    for (int n = 2; n <= initHeight; ++n)
    {
        int curHeight = initHeight;
        int nowCat = 1;

        int totalCat = 0, notWorkCat = 0;

        while ((curHeight % n) == 0)
        {
            totalCat += curHeight * nowCat;
            notWorkCat += nowCat;

            curHeight = curHeight / n;
            nowCat = nowCat * (n - 1);
        }

        if (nowCat == kitten)    // got Answer!
        {
            totalCat += nowCat;
            printf("%d %d\n", notWorkCat, totalCat);
            break;
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("107.in", "r", stdin);
#endif

    int initHeight, kitten; //initial height, number of kitten

    while (scanf("%d %d", &initHeight, &kitten) == 2)
    {
        if (initHeight == 0 || kitten == 0)
            break;

        /* special case */
        if (initHeight == 1 && kitten == 1)
            printf("0 1\n");
        else if (initHeight == 1)
            printf("1 %d\n", kitten);

        /* find n */
        find(initHeight, kitten);
    }
    return 0;
}

107.in

483736625 481890304
0 0

10751.cpp

#include<iostream<
#include<cmath<

int main()
{
    double sqrtwo = sqrt(2.0);
    double pathLength;
    int times, n;

    scanf("%d", &times);

    for (int i = 0; i < times; i++)
    {
        scanf("%d", &n);

        pathLength = (n - 1) * 4 + ( (n - 2 > 0) ? ((n - 2) * (n - 2) * sqrtwo) : (0));
        printf("%.4f\n", pathLength);
        if (i != times - 1) printf("\n");
    }
    return 0;
}

10780.cpp

/**
 * UVa 10780 Again Prime? No time. (WA)
 * Author: chchwy
 * Last Modified: 2010.01.30
 */
#include<cstdio>

int run(int m, int n)  // (n! / m^x) §ä³Ì¤jªºx
{
    int counter = 0;

    for (int i = 2; i <= n; ++i)
    {
        printf("test %d!\n", i);
        int fac = i;
        while (fac % m == 0)
        {
            ++counter;
            fac /= m;
            printf("yes devied %d, cnt=%d, remain fac=%d\n", m, counter, fac);
        }
    }
    return counter;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("10780.in", "r", stdin);
#endif

    int numCase;
    scanf("%d", &numCase);

    for (int i = 1; i <= numCase; ++i)
    {
        printf("Case %d:\n", i);

        int m, n;
        scanf("%d %d", &m, &n);

        int ret;
        if ( (ret = run(m, n)) > 0 )
            printf("%d\n", ret);
        else
            puts("Impossible to divide");
    }
    return 0;
}

10780.in

1
3123 2342
2 10
2 100
234 2343
45 789
111 2222
4999 9999
4999 2
23 6324

10783.cpp

/*
 * 10783 - Odd Sum
 * Last Modified: 2009.11.27
 * Author: chchwy
 */
#include<cstdio>

int main()
{
    int numCase;
    scanf("%d", &numCase);
    for (int i = 1; i <= numCase; ++i)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        if (a % 2 == 0)a++;
        if (b % 2 == 0)b--;
        printf("Case %d: %d\n", i, (a + b) * (b - a + 2) / 4 );
    }
    return 0;
}

108.cpp

/**
 * UVa 108 Maximum Sum
 * Author: chchwy
 * Last Modified: 2011.10.08
 * Tag: Dynamic Programming
 */
#include<cstdio>
#include<cstring>
#include<climits>

enum { MAX_DIM = 100 + 1 };

int subMatrixSum(int sumTable[][MAX_DIM], int x1, int y1, int x2, int y2)
{
    int sum = sumTable[x2][y2]
              - sumTable[x1 - 1][y2]
              - sumTable[x2][y1 - 1]
              + sumTable[x1 - 1][y1 - 1];
    return sum;
}

int main()
{
    int dimension; //the dimension of matrix
    int sumTable[MAX_DIM][MAX_DIM];

    while (scanf("%d", &dimension) == 1)
    {
        memset(sumTable, 0, sizeof(sumTable));

        // Build Sum Table
        for (int i = 1; i <= dimension; ++i)
        {
            for (int j = 1; j <= dimension; ++j)
            {
                int value;
                scanf("%d", &value);
                sumTable[i][j] = sumTable[i - 1][j]
                                 + sumTable[i][j - 1]
                                 - sumTable[i - 1][j - 1]
                                 + value;
            }
        }

        int max_sum = INT_MIN;

        //position (x1,y1)
        for (int x1 = 1; x1 <= dimension; ++x1)
        {
            for (int y1 = 1; y1 <= dimension; ++y1)
            {
                //position (x2,y2)
                for (int x2 = x1; x2 <= dimension; ++x2)
                {
                    for (int y2 = y1; y2 <= dimension; ++y2)
                    {
                        int sum = subMatrixSum(sumTable, x1, y1, x2, y2);
                        if (sum > max_sum)
                            max_sum = sum;
                    }
                }
            }
        }
        printf("%d\n", max_sum);
    }
    return 0;
}

10812.c

/**
 * UVa 10812 Beat the Spread!
 * Author: chchwy
 * Last Modified: 2011.04.05
 * Blog: http://chchwy.blogspot.com
 */
#include<stdio.h>
int main() {
    int tmp;
    scanf("%d ",&tmp);
    int sum, dif;
    while(scanf("%d %d", &sum, &dif)==2){
        if(sum<dif){
            puts("impossible");
            continue;
        } else if( sum%2 != dif%2 ){
            puts("impossible");
            continue; 
        }
 
        int a = (sum + dif)/2;
        int b = (sum - dif)/2;
        printf("%d %d\n", a, b);
    }
    return 0;
}

109.cpp

/**
 * UVa 109 SCUD Busters
 * Author: chchwy
 * Last Modified: 2011.10.07
 * Tag: Computational Geometry, Convex Hull
 */
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct point
{
    int x, y;
};

// 兩點距離
int dist (point a, point b)
{
    return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}

// 外積 (p1,p2) (p1,p3)
int cross (point p1, point p2, point p3)
{
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

bool min_y (point a, point b)
{
    if ( a.y == b.y )
        return (a.x < b.x);
    return (a.y < b.y);
}

// Graham's Scan 要將所有的點依照角度排序
point base;
bool counter_clockwise(point a, point b)
{

    int c = cross(base, a, b);
    if ( c == 0 )
        return ( dist(base, a) < dist(base, b));
    return (c > 0);
}

class kingdom
{
public:
    vector<point> house;
    bool is_destroyed;

    kingdom();
    void   convex_hull();
    void   destroy(point);
    bool   is_inside(point);
    double area();
};

kingdom::kingdom()
{
    is_destroyed = false;
}

// 計算凸包: Graham's Scan Algorithm
void kingdom::convex_hull()
{
    swap(house[0], *min_element(house.begin(), house.end(), min_y));

    base = house[0];
    sort(house.begin(), house.end(), counter_clockwise);

    house.push_back(house[0]);

    int CH = 1;
    for (int i = 2; i < house.size(); ++i)
    {

        while ( cross(house[CH - 1], house[CH], house[i]) <= 0 )
        {
            if ( CH == 1 )
            {
                house[CH] = house[i];
                i++;
            }
            else
            {
                CH--;
            }
        }
        CH++;
        house[CH] = house[i];
    }

    house.resize(CH + 1);
}

void kingdom::destroy (point missile)
{
    if (is_destroyed)
        return;

    if (is_inside(missile))
        is_destroyed = true;
}

// 計算被摧毀的王國面積 (如果沒被摧毀就回傳0)
double kingdom::area()
{
    if (!is_destroyed)
        return 0;

    double area = 0;
    for (int i = 1; i < house.size(); ++i)
        area += (house[i - 1].x * house[i].y) - (house[i].x * house[i - 1].y);
    return area / 2;
}

// 判斷飛彈落點是否擊中王國
bool kingdom::is_inside (point missile)
{
    for (int i = 1; i < house.size(); ++i)
    {
        if ( cross(house[i - 1], house[i], missile) < 0)
            return false;
    }
    return true;
}

kingdom build_kindom ( int house_count )
{
    kingdom k;

    int x, y;
    for (int i = 0; i < house_count; ++i)
    {
        cin >> x >> y;
        k.house.push_back(point{x, y});
    }

    return k;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("109.in", "r", stdin);
#endif

    // 1. build the world
    vector<kingdom> king;

    int house_count;
    while (cin >> house_count)
    {
        if (house_count == -1)
            break;

        king.push_back(build_kindom( house_count ));
    }

    // 2. do convex hull
    for (int i = 0; i < king.size(); ++i)
        king[i].convex_hull();

    // 3. missiles attack!
    double total_area = 0;

    point missile;
    while ( cin >> missile.x >> missile.y )
    {
        for (int i = 0; i < king.size(); ++i)
            king[i].destroy( missile );
    }

    // 4. calculate the sum of destroyed area
    for (int i = 0; i < king.size(); ++i)
        total_area +=  king[i].area();

    printf("%.2lf\n", total_area );

    return 0;
}

109.in

12
3 3
4 6
4 11
4 8
10 6
5 7
6 6
6 3
7 9
10 4
10 9
1 7
5
20 20
20 40
40 20
40 40
30 30
3
10 10
21 10
21 13
-1
5 5
20 12

10924.cpp

/*
 * UVa 10924 Prime Words (AC)
 * Author: chchwy
 * Last Modified: 2009.11.22
 */
#include<iostream>
#include<sstream>
#include<cctype>
using namespace std;
enum {MAX = 52 * 20 + 2};

char p[MAX]; //0=prime, 1=not prime

void shieve()
{
    p[0] = p[1] = 0;
    for (int i = 2; i * i < MAX; ++i)
    {
        if (p[i] == 1) continue;
        for (int j = i * i; j < MAX; j += i)
            p[j] = 1;
    }
}

int main()
{
    shieve();

    string line;
    while (getline(cin, line))
    {
        int sum = 0;
        //for each char
        for (int i = 0; i < line.length(); ++i)
        {
            if ( islower(line[i]) )
                sum += line[i] - 'a' + 1;
            else
                sum += line[i] - 'A' + 27;
        }
        if (p[sum] == 0)
            puts("It is a prime word.");
        else
            puts("It is not a prime word.");
    }
    return 0;
}

10929.cpp

/**
 * UVa 10929 You can say 11 (AC)
 * Author: chchwy
 * Last Modified: 2010.01.30
 */
#include<iostream>
using namespace std;

int main()
{
    string num;
    while ( getline(cin, num) )
    {
        if (num[0] == '0' && num.length() == 1 ) break;

        int sum = 0;
        for (int i = 0; i < num.length(); i += 2)
            sum += (num[i] - '0');
        for (int i = 1; i < num.length(); i += 2)
            sum -= (num[i] - '0');

        if (sum % 11 == 0)
            cout << num << " is a multiple of 11.\n";
        else
            cout << num << " is not a multiple of 11.\n";
    }
}

110.cpp

#include<iostream>

class ArrayList
{
public:
    int data[32];
    int size;
    //func
    ArrayList();
    void push_back(int);
    int pop_head();
    void clear();
    void print();
    void swap(int, int);
};

ArrayList::ArrayList()
{
    size = 0;
}
void ArrayList::clear()
{
    size = 0;
}

void ArrayList::print()
{
    for (int i = 0; i < size - 1; ++i)
        printf("%c,", data[i]);
    printf("%c", data[size - 1]);
}

void ArrayList::swap(int x, int y)
{
    int tmp = data[x];
    data[x] = data[y];
    data[y] = tmp;
}

void ArrayList::push_back(int input)
{
    data[size++] = input;
}

int ArrayList::pop_head()
{
    int head = data[0];
    for (int i = 0; i < size; ++i)
        data[i] = data[i + 1];
    size--;
    return head;
}

void printSeq(char c, int length)
{
    for (int i = 0; i < length - 1; ++i)
        printf("%c,", c + i);
    printf("%c", c + length - 1);
}

void indense(int num)
{
    for (int i = 0; i < num; ++i) printf("  ");
}

void metaSort(ArrayList& ls, int insertChar, int bound)
{

    //terminal condition
    if (insertChar == bound)
    {
        indense(insertChar - 'a');
        printf("writeln(");
        ls.print();
        printf(")\n");
        return;
    }

    ls.push_back(insertChar); //insert to tail

    indense(insertChar - 'a');
    printf("if %c < %c then\n", ls.data[ls.size - 2], ls.data[ls.size - 1]);

    metaSort(ls, insertChar + 1, bound);

    //next insert to every place
    for (int i = ls.size - 1; i > 0; --i)
    {
        ls.swap(i, i - 1);

        //-------------------------
        indense(insertChar - 'a');
        if (i == 1)
            printf("else\n");
        else
            printf("else if %c < %c then\n", ls.data[i - 2], ls.data[i - 1]);
        //-------------------------

        metaSort(ls, insertChar + 1, bound);
    }
    ls.pop_head(); //delete head
}

int main()
{
    ArrayList ls;
    int times, max;
    scanf("%d", &times);

    for (int i = 0; i < times; ++i)
    {
        scanf("%d", &max);

        //--------------------
        printf("program sort(input,output);\nvar\n");
        printSeq('a', max);
        printf(" : integer;\nbegin\n  readln(");
        printSeq('a', max);
        printf(");\n");
        //--------------------

        ls.push_back('a');
        metaSort(ls, 'b', 'a' + max);
        ls.clear();

        //--------------------
        printf("end.\n");
        if (i != times - 1) printf("\n");
        //--------------------
    }
    return 0;
}

11044.cpp

/**
 * UVa 11044 Searching for Nessy
 * Author: chchwy
 * Last Modified: 2009.12.05
 */
#include<iostream>

int main()
{
    int numCase;
    scanf("%d", &numCase);
    while (numCase--)
    {
        int m, n;
        scanf("%d %d", &m, &n);
        printf("%d\n", (m / 3) * (n / 3));
    }
    return 0;
}

111.cpp

#include<iostream>
using namespace std;

enum { MAX = 20 };

//transfer the rank to real sequence
void trans(int seq[MAX], int rank[MAX], int n)
{
    for (int i = 0; i < n; ++i)
        seq[rank[i] - 1] = i;
}

int main()
{
    int n;
    int rank[MAX];

    //read the correct answer
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &rank[i]);

    //trans the answer rank to answer seq
    int correct[MAX];
    trans(correct, rank, n);

    //build mapping
    int map[MAX];
    for (int i = 0; i < n; ++i)
        map[correct[i]] = i;

    while (scanf("%d", &rank[0]) == 1)
    {
        //read student's ans
        for (int i = 1; i < n; ++i)
            scanf("%d", &rank[i]);

        int seq[MAX], seq2[MAX];
        trans(seq, rank, n);
        for (int i = 0; i < n; ++i)
        {
            seq2[i] = map[seq[i]];
        }

        //lis
        int best[MAX];
        int length = 1; //length of best
        best[0] = seq2[0];

        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < length; ++j)
            {
                if (seq2[i] < best[j])
                {
                    best[j] = seq2[i];
                    break;
                }
            }
            if (seq2[i] > best[length - 1])
            {
                best[length++] = seq2[i];
            }
        }
        printf("%d\n", length);
    }
    return 0;
}

11172.cpp

/*
 * UVa 11172 Relational Operators
 * Author: chchwy
 * Last Modified: 2009.11.26
 */
#include<cstdio>
int main()
{
    int a, b;
    int numCase;
    scanf("%d", &numCase);
    while (numCase--)
    {
        scanf("%d %d", &a, &b);
        if (a < b) puts("<");
        else if (a > b) puts(">");
        else puts("=");
    }
    return 0;
}

11185.cpp

/**
 * UVa 11185 Ternary
 * Author: chchwy
 * Last Modified: 2010.02.03
 */
#include<iostream>
using namespace std;

inline char DigitToChar(int n)
{
    return "0123456789ABCDEF"[n];
}

/* convert int 'value' to string 'out' */
string toBase( int base2, long long value )
{
    if (value == 0) return "0";

    string out;
    while ( value > 0 )
    {
        out += DigitToChar( value % base2 );
        value /= base2;
    }
    reverse(out.begin(), out.end());
    return out;
}

int main()
{
    int n;
    while (scanf("%d", &n) == 1 && n >= 0)
        printf("%s\n", toBase(3, n).c_str() );

    return 0;
}

112.cpp

#include<iostream>
using namespace std;

enum
{
    //Types of token
    LEFT_BRACKET, RIGHT_BRACKET, NUMBER,

    //return Value
    MATCH, NOT_MATCH, EMPTY_TREE
};

static int num;

int getToken()
{
    int c = getchar();
    while (c == ' ' || c == '\n')
        c = getchar();

    num = 0;
    if (c == '(')
        return LEFT_BRACKET;
    else if (c == ')')
        return  RIGHT_BRACKET;
    else if ( (c >= '0' && c <= '9') || c == '-' )
    {
        int sign = 1;
        if (c == '-')
        {
            sign = -1;
            c = getchar();
        }
        for (; c >= '0' && c <= '9'; c = getchar())
            num = num * 10 + (c - '0');
        num = num * sign;
        ungetc(c, stdin);
        return NUMBER;
    }
    return 0;
}

int traversal(int sum, int target)
{
    int token;
    getToken(); //get Left Bracket '('

    token = getToken();
    if (token == RIGHT_BRACKET)
        return  EMPTY_TREE;
    else //if(token = NUMBER)
        sum += num;

    int lc = traversal(sum, target); //left child
    int rc = traversal(sum, target); //right child

    getToken(); //get right bracket ')'

    if (lc == EMPTY_TREE && rc == EMPTY_TREE) //leaf
        if (sum == target)
            return MATCH;

    if (lc == MATCH || rc == MATCH) //return result upwards
        return MATCH;
    return NOT_MATCH;
}

int main()
{
    int target;

    //for each test case
    while (scanf("%d", &target) == 1)
    {
        if (traversal(0, target) == MATCH) //if not ok
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

113.cpp

#include<cstdio>
#include<cmath>

int main()
{
    double n, p;
    while (scanf("%lf %lf", &n, &p) == 2)
        printf("%.0lf\n", pow(p, 1 / n));
    return 0;
}

11388.cpp

/*
 * UVa 11388
 * Author: chchwy
 * Last Modified: 2009.11.13
 */
#include<cstdio>
#include<cmath>

int main()
{
    int numCase;
    scanf("%d", &numCase);

    while (numCase--)
    {
        int gcd, lcm;
        scanf("%d %d", &gcd, &lcm);

        if (lcm % gcd != 0)
            puts("-1");
        else
            printf("%d %d\n", gcd, lcm);
    }
    return 0;
}

114.cpp

/**
 * UVa 114 Simulation Wizardry
 * Author: chchwy
 * Last Modified: 2009.02.03
 */
#include<iostream>
using namespace std;

enum
{
    MAX_SIZE = 51 + 2,
    SPACE = 0, WALL = 1, BUMPER = 2,
};

// 0=> 朝x方向增加  1=> 朝y方向增加
// 2=> 朝x方向減小  3=> 朝y方向減小
const int move[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

class Grid
{
public :
    int type;
    int cost;
    int value;

    void set (int ptype, int pvalue, int pcost )
    {
        type = ptype; value = pvalue; cost = pcost;
    }
};

int run(Grid map[MAX_SIZE][MAX_SIZE], int x, int y, int direction, int life )
{
    int point = 0;

    while ( life > 1 )
    {
        life -= 1;

        int nextX = x + move[ direction ][0];
        int nextY = y + move[ direction ][1];


        switch ( map[nextY][nextX].type )
        {
        case WALL:
        case BUMPER:
            life -= map[nextY][nextX].cost;
            point += map[nextY][nextX].value;
            direction  = (direction + 3) % 4; //turn right;
            break;
        case SPACE:
            x = nextX, y = nextY;
            break;
        }
    }
    return point;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("114.in", "r", stdin);
#endif

    /* surface size */
    int m, n;
    scanf("%d %d", &m, &n);

    /* map surface */
    Grid map[MAX_SIZE][MAX_SIZE];
    memset(map, 0, sizeof(map));

    /* set wall around the surface */
    int costWall;
    scanf("%d", &costWall);
    for (int i = 1; i <= m; ++i)
    {
        map[i][1].set(WALL, 0, costWall);
        map[i][n].set(WALL, 0, costWall);
    }
    for (int i = 1; i <= n; ++i)
    {
        map[1][i].set(WALL, 0, costWall);
        map[m][i].set(WALL, 0, costWall);
    }

    /* init bumper */
    int numBumper;
    scanf("%d", &numBumper);

    for (int i = 0; i < numBumper; ++i)
    {
        int x, y, value, cost;
        scanf("%d %d %d %d", &x, &y, &value, &cost);
        map[y][x].set(BUMPER, value, cost);
    }

    /* start simulation */
    int x, y, direction, life;

    int totalPoint = 0;
    //剩下每一行都代表一顆球 ( x, y, 方向, 生命值)
    while ( scanf("%d%d%d%d", &x, &y, &direction, &life) == 4 )
    {
        int point = run(map, x, y, direction, life);
        printf("%d\n", point );

        totalPoint += point;
    }
    printf("%d\n", totalPoint);
    return 0;
}

114.in

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

11461.cpp

/**
 * UVa 11461 Square Numbers
 * Author: chchwy
 * Last Modified: 2009.11.13
 */
#include<cstdio>
#include<cmath>


int main()
{
    int a, b;
    while (scanf("%d %d", &a, &b) == 2 )
    {
        if (!a) break;

        int counter = 0;
        int i = ceil(sqrt(a));
        while ( i * i <= b )
        {
            counter++, i++;
        }
        printf("%d\n", counter);
    }

    return 0;
}

11462.cpp

/**
 * UVa 11462 Age Sort (AC)
 * Author: chchwy
 * Last Modified: 2009.11.22
 */
#include<iostream>
#include<sstream>
using namespace std;

int p[2000000];

int main()
{
    string line;
    while (getline(cin, line))
    {
        int numPeople = atoi( line.c_str() );
        if (numPeople == 0) break;

        getline(cin, line);
        istringstream sin(line);

        int i = 0;
        while (sin >> p[i++]);

        sort(p, p + numPeople);

        for (int i = 0; i < numPeople - 1; ++i)
            printf("%d ", p[i]);
        printf("%d\n", p[numPeople - 1]);
    }
    return 0;
}

115.cpp

/**
 * UVa 115 Climbing Tree
 * Author: chchwy
 * Last Modified: 2009.12.07
 */
#include<iostream>

int main()
{



    return 0;
}

116.cpp

/**
 * UVa 116 (AC)
 * Author: chchwy
 * Last Modified: 2009.04.28
 */
#include<iostream>

enum { MAX_ROW = 15, MAX_COL = 100 };

int getInt()
{
    int i = 0, sign = 1;

    char c = getchar();
    while (c == ' ' || c == '\n' || c == '\r')
        c = getchar();

    if (c == '-')
    {
        sign = -1;
        c = getchar();
    }
    while (c > '0' - 1 && c < '9' + 1)
    {
        i = i * 10 + (c - '0');
        c = getchar();
    }
    return  i * sign;
}

void readMap(int map[][MAX_COL], int row, int col)
{
    for (int i = 0; i < row; ++i)
        for (int j = 0; j < col; ++j)
            map[i][j] = getInt();
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("116.in", "r", stdin);
#endif

    int row, col;
    int map[MAX_ROW][MAX_COL];

    while (scanf("%d %d ", &row, &col) == 2)
    {
        readMap(map, row, col);

        int path[MAX_ROW][MAX_COL]; //record the min path weight
        int next[MAX_ROW][MAX_COL]; //record the next path

        for (int i = 0; i < MAX_ROW; ++i)
        {
            path[i][col - 1] = map[i][col - 1];
            next[i][col - 1] = -1;
        }

        //DP shortest path
        for (int j = col - 2; j > -1; --j)
        {
            for (int i = 0; i < row; ++i)
            {
                int a = (i + row - 1) % row;
                int b = i;
                int c = (i + 1) % row;

                int min = a;
                if ( path[b][j + 1] < path[min][j + 1])
                    min = b;
                else if (path[b][j + 1] == path[min][j + 1] && b < min)
                    min = b;

                if ( path[c][j + 1] < path[min][j + 1])
                    min = c;
                else if (path[c][j + 1] == path[min][j + 1] && c < min)
                    min = c;

                path[i][j] = map[i][j] + path[min][j + 1];
                next[i][j] = min;
            }
        }

        //terminal place
        int min = 0;
        for (int i = 1; i < row; ++i)
            if (path[i][0] < path[min][0])
                min = i;

        int minCost = path[min][0];

        for (int i = 0; i < col - 1; ++i)
        {
            printf("%d ", min + 1);
            min = next[min][i];
        }
        printf("%d", min + 1);
        printf("\n%d\n", minCost);
    }
    return 0;
}

136.cpp

/**
 * This is not the solution of UVa 136
 * But it can help you to find it.
 *
 *  Author: chchwy
 *  Last Modified: 2009.11.25
 */
#include<iostream>

int main()
{
    int unum = 2;
    int counter = 1;

    while (counter < 1500)
    {
        int tmp = unum;
        while (tmp % 2 == 0)
            tmp = tmp / 2;

        while (tmp % 3 == 0)
            tmp = tmp / 3;

        while (tmp % 5 == 0)
            tmp = tmp / 5;

        if (tmp == 1)
        {
            counter++;
            printf("No.%d Ugly=%d\n", counter, unum);
        }
        unum += 2;
    }
}

146.cpp

/**
 * UVa 146 ID Codes
 * Author: chchwy
 * Last Modified: 2011.04.04
 * Blog: http://chchwy.blogspot.com
 */
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    string id;
    while (getline(cin, id))
    {
        if (id == "#")
            break;

        if (next_permutation(id.begin(), id.end()))
            cout << id << endl;
        else
            cout << "No Successor" << endl;
    }
    return 0;
}

147.cpp

/**
 * UVa 147 Dollars
 * Author: chchwy
 * Last Modified: 2009.12.05
 */
#include<cstdio>

enum {MAX = 30000 + 1, NUM_COIN = 11};

long long int count[MAX]; //unit is cent

int main()
{
    int coin[NUM_COIN] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

    //build dp table
    count[0] = 1;
    for (int i = 0; i < NUM_COIN; ++i)
        for (int j = coin[i]; j < MAX; j += 5) //bug: use int j=5
            count[j] += count[ j - coin[i] ];

    int dollar, cent;
    while (scanf("%d.%d", &dollar, &cent) == 2)
    {
        if (dollar == 0 && cent == 0) break;
        printf("%3d.%02d%17lld\n", dollar, cent, count[dollar * 100 + cent]);
    }
    return 0;
}

151.cpp

/**
 * UVa 151 Power Crisis
 * Author: chchwy
 * Last Modified: 2011.04.15
 * Blog: http://chchwy.blogspot.com
 */
#include<cstdio>
#include<deque>
#include<algorithm>

int end_with(int M, int total_region)
{
    std::deque<int> que;

    for (int i = 1; i <= total_region; ++i)
        que.push_back(i);

    int turn_off_region = que.front(); // pop 1
    que.pop_front();

    for (int i = 0; i < total_region - 1; ++i)
    {
        // skip M-1 element
        for (int j = 0; j < M - 1; ++j)
        {
            que.push_back(que.front());
            que.pop_front();
        }
        // turn off next M'th region
        turn_off_region = que.front();
        que.pop_front();
    }
    return turn_off_region;
}

int Min_M(int N)
{
    for (int m = 1; m < N; ++m)
    {
        if (end_with(m, N) == 13)
            return i;
    }
    return 0;
}

int main()
{
    int N = 0;
    while (scanf("%d", &N) == 1)
    {
        if (N == 0) break;
        printf("%d\n", Min_M(N));
    }
    return 0;
}

160.cpp

/**
 * UVa 160 Factors and Factorials
 * Author: chchwy
 * Last Modified: 2011.06.19
 * Blog: http://chchwy.blogspot.com
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

enum { PRIME_COUNT = 25 };

int primes[PRIME_COUNT] =
{
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
    43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
};

int count_factorial(int num, int fac)
{
    int counter = 0;
    while ( (num % fac) == 0 )
    {
        num = num / fac;
        counter++;
    }
    return counter;
}

int init( int fac_term[101][PRIME_COUNT] )
{
    for (int i = 0; i < 101; ++i)
        for (int j = 0; j < PRIME_COUNT; ++j)
            fac_term[i][j] = -1;
}

void print_result( int n, int fac_term[PRIME_COUNT])
{
    printf("%3d! =", n);

    for (int i = 0; i < PRIME_COUNT; ++i)
    {
        if ( fac_term[i] == -1 )
            break;

        if (i == 15) printf("\n      ");

        printf("%3d", fac_term[i]);
    }
    putchar('\n');
}

int main()
{
    int fac_term[101][PRIME_COUNT];
    init(fac_term);

    // build factorial terms table
    for (int i = 2; i <= 100; ++i)
    {
        for (int j = 0; j < PRIME_COUNT; ++j)
        {
            if ( primes[j] > i ) break;

            fac_term[i][j] = count_factorial(i, primes[j]);
        }

        for (int j = 0; j < PRIME_COUNT; ++j)
        {
            if ( fac_term[i - 1][j] >= 0 )
                fac_term[i][j] += fac_term[i - 1][j];
        }
    }

    // do process
    int n;
    while ( scanf("%d", &n) == 1 )
    {
        if ( n == 0 ) break;
        print_result(n, fac_term[n]);
    }
    return 0;
}

184.cpp

/**
 * UVa 184 Laser Lines
 * Author: chchwy
 * Last Modified: 2011.04.19
 * Blog: http://chchwy.blogspot.com
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using std::vector;

struct Point
{
    int x, y;
};

int cmpY(const Point& a, const Point& b )
{
    return (a.y < b.y);
}
int cmpX(const Point& a, const Point& b )
{
    return (a.x < b.x);
}

// three points on the same line
bool is_collinear(Point a, Point b, Point c)
{
    int pos = a.x * b.y + b.x * c.y + c.x * a.y;
    int neg = a.x * c.y + b.x * a.y + c.x * b.y;

    return (pos == neg);
}

void output(vector<Point>& line, int is_first_line )
{
    if ( is_first_line )
        puts("The following lines were found:");

    for (int i = 0; i < line.size(); ++i)
        printf("(%4d,%4d)", line[i].x, line[i].y);
    puts("");
}

bool is_prev_exist( Point a, Point b, vector<Point> prev_line )
{

    for (int i = 0; i < prev_line.size(); i = i + 2)
    {
        int r1 = is_collinear(a, b, prev_line[i]);
        int r2 = is_collinear(a, b, prev_line[i + 1]);

        if ( r1 && r2 ) return true;
    }
    return false;
}

void find_all_collinear( vector<Point>& points )
{
    int no_line_found = 1;
    int is_first_line = 1;

    std::stable_sort(points.begin(), points.end(), cmpY);
    std::stable_sort(points.begin(), points.end(), cmpX);

    vector<Point> prev_line;

    for (int i = 0; i < points.size(); ++i)
    {
        for (int j = i + 1; j < points.size(); ++j)
        {
            if ( is_prev_exist(points[i], points[j], prev_line) )
                continue;

            vector<Point> line;

            line.push_back(points[i]);
            line.push_back(points[j]);

            // check line pi-pj
            for (int k = j + 1; k < points.size(); ++k)
            {
                if ( is_collinear(points[i], points[j], points[k]) )
                {
                    no_line_found = 0;
                    line.push_back(points[k]);
                }
            }

            if ( line.size() > 2 )
            {
                output(line, is_first_line);
                is_first_line = 0;

                prev_line.push_back(line[0]);
                prev_line.push_back(line[1]);
            }
        }
    }

    if ( no_line_found )
        puts("No lines were found");
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("184.in", "r", stdin);
#endif

    // for each input set
    while (1)
    {
        vector<Point> point_list;

        Point p;
        while ( scanf("%d %d", &p.x, &p.y) == 2 )
        {
            if ( p.x == 0 && p.y == 0) break; // end of point set
            point_list.push_back(p);
        }

        if (point_list.size() == 0) break;

        find_all_collinear( point_list );
    }
    return 0;
}

184.in

1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 0 0
0 0

191.cpp

#include<cstdio>

struct Point
{
    float x, y;
};

bool intersect( Point start, Point end, Point left_top, Point right_bottom )
{
    //
}

int main()
{
    Point start, end, left_top, right_bottom;

    int num_case;
    scanf("%d", &num_case);

    while ( num_case-- )
    {
        scanf("%f%f", &start.x, &start.y);
        scanf("%f%f", &end.x, &end.y);
        scanf("%f%f", &left_top.x, &left_top.y );
        scanf("%f%f", &right_bottom.x, &right_bottom.y);

        if ( intersect(start, end, left_top, right_bottom) )
            puts("T");
        else
            puts("F");
    }
    return 0;
}

193.cpp

/**
 * UVa 193 Graph Coloring
 * Author: chchwy (a) gmail.com
 * Last Modified: 2010.04.13
 */
#include<iostream>
enum {MAX_NODE = 100};

void setAdjacentMatrix(bool adj[MAX_NODE][], int numEdge)
{
    memset(adj, 0, MAX_NODE * MAX_NODE);
    for (int i = 0; i < numEdge; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        adj[x - 1][y - 1] = true;
    }
}

int main()
{
    int numCase;
    scanf("%d", &numCase);

    while (numCase--)
    {
        int numNode, numEdge;
        scanf("%d%d", &numNode, &numEdge);

        bool adj[MAX_NODE][MAX_NODE];
        setAdjcentMatrix(adj, numEdge);
    }
    return 0;
}

270.cpp

/**
 * UVa 270 Lining Up
 * Author: chchwy
 * Last Modified: 2011.04.19
 * Blog: http://chchwy.blogspot.com
 */

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using std::vector;
using std::cin;

struct Point
{
    int x, y;
};

bool is_collinear(Point a, Point b, Point c)
{
    int pos = a.x * b.y + b.x * c.y + c.x * a.y;
    int neg = b.x * a.y + c.x * b.y + a.x * c.y;

    return (pos == neg);
}

bool is_line_exist(Point a, Point b, vector<Point>& prev_line)
{
    for (int i = 0; i < prev_line.size(); i = i + 2)
    {
        bool r1 = is_collinear(a, b, prev_line[i]);
        bool r2 = is_collinear(a, b, prev_line[i + 1]);

        if (r1 && r2) return true;
    }
    return false;
}

int search_lines( vector<Point>& points )
{
    int max_points = 0;

    vector<Point> prev_line;

    for (int i = 0; i < points.size(); ++i)
    {
        for (int j = i + 1; j < points.size(); ++j)
        {
            /* line pi-pj */
            if ( is_line_exist(points[i], points[j], prev_line) )
                continue;

            vector<Point> line;
            line.push_back(points[i]);
            line.push_back(points[j]);

            for (int k = j + 1; k < points.size(); ++k)
            {
                if ( is_collinear(points[i], points[j], points[k]) )
                {
                    line.push_back(points[k]);
                }
            }

            if ( line.size() > max_points )
                max_points = line.size();
        }
    }
    return max_points;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("270.in", "r", stdin);
#endif

    int num_case;
    scanf("%d\n", &num_case);

    while (num_case--)
    {
        vector<Point> points;

        char line[128];
        while ( cin.getline(line, sizeof(line)) )
        {
            if ( 0 == strlen(line) ) break; //empty line

            Point p;
            sscanf(line, "%d%d", &p.x, &p.y);

            points.push_back(p);
        }

        int max_points = search_lines(points);

        printf("%d\n", max_points);
        if (num_case != 0) putchar('\n');
    }
    return 0;
}

270.in

3

1 1
2 2
3 3    
9 10     
10 11

1 1
2 2
3 3
9 10
10 11

1 1
2 2
3 3
4 4
5 5

272.cpp

#include<cstdio>

int main()
{
    int c;
    int inQuotes = 0;

    while ((c = getchar()) != EOF)
    {
        if (c == '"')
        {
            if (inQuotes) //close quotes
            {
                putchar('\'');
                putchar('\'');
            }
            else   //start quotes
            {
                putchar('`');
                putchar('`');
            }
            inQuotes = !inQuotes;
        }
        else
        {
            putchar(c);
        }
    }
    return 0;
}

294.cpp

/**
 * UVa 294 Divisors
 * Author: chchwy
 * Last Modified: 2010.01.27
 */
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;

enum {MAX = 1000000000, SQRT_MAX = 31622}; //sqrt(1000000000) = 31622

char isPrime[SQRT_MAX] = {0};
vector<int> primeNum;

int shieve()
{
    isPrime[0] = 0;
    isPrime[1] = 0;
    isPrime[2] = 1;

    for (int i = 3; i < SQRT_MAX; ++i)
        isPrime[i] = i % 2;

    //shieve
    int sqrt_n = sqrt((int)SQRT_MAX);
    for (int i = 3; i < sqrt_n; i += 2)
    {
        if (isPrime[i] == 0) continue;

        for (int j = i * i; j < SQRT_MAX; j += i)
            isPrime[j] = 0;
    }

    //push all prime number into vector "primeNum"
    for (int i = 2; i < SQRT_MAX; ++i)
        if (isPrime[i])
            primeNum.push_back(i);
}

//回傳 num 總共有幾個divisor
int getDivisorNumber(int n)
{
    if ( n == 1 ) return 1;
    if ( n < SQRT_MAX && isPrime[n] ) return 2;

    int total = 1;

    int tmp = n;
    for (int i = 0 ; i < primeNum.size() && primeNum[i]*primeNum[i] <= n; ++i)
    {
        int div = primeNum[i];

        int exp = 1; //算這個因數總共有幾個
        for ( ; tmp % div == 0 ; exp++ )
        {
            tmp /= div;
        }
        total *= exp;

        if ( tmp == 1 ) return total;
    }
    if (total != 1) return total * 2; //還剩下一個大於sqrt(n)的因數
    return 2;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("294.in", "r", stdin );
#endif

    shieve(); //build the prime table

    int numCase;
    scanf("%d", &numCase);

    while (numCase--)
    {
        int a, b;
        scanf("%d %d", &a, &b);

        int maxi = 0, maxDiv = 0;
        for ( int i = a; i <= b; ++i)
        {
            int curDiv = getDivisorNumber(i);

            if ( curDiv > maxDiv )
            {
                maxi = i;
                maxDiv = curDiv;
            }
        }
        printf("Between %d and %d, %d has a maximum of %d divisors.\n", a, b, maxi, maxDiv);
    }
    return 0;
}

294.in

4 
1 100
1000 1000
999 999
999990000 1000000000

343.cpp

/**
 * UVa 343 What Base is This?
 * Author: chchwy
 * Last Modified: 2010.01.27
 */
#include<iostream>
using namespace std;

typedef long long big_int;

inline int CharToDigit(char c)
{
    if ( isdigit(c) )
        return c - '0';
    return c - 'A' + 10;
}

inline char DigitToChar(int n)
{
    return "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n];
}

bool checkIllegal(int base1, string& in )
{
    for (int i = 0; i < in.length(); ++i)
        if ( CharToDigit(in[i]) >= base1 )
            return true;
    return false;
}

/* convert string 'in' to int 'value'. */
big_int parseValue( int base, string& in )
{
    if ( checkIllegal(base, in) ) return -1;

    big_int value = 0;
    big_int curBase = 1;

    for (int i = in.length() - 1; i >= 0; --i)
    {

        value += CharToDigit(in[i]) * curBase;
        curBase *= base;
    }
    return value;
}

void match(string& num1, string& num2 )
{
    for (int i = 2; i <= 36; ++i)
    {
        for (int j = 2; j <= 36; ++j)
        {
            big_int value1 = parseValue(i, num1 );
            big_int value2 = parseValue(j, num2 );

            if ( value1 < 0 || value2 < 0 ) continue;

            if ( value1 == value2 )
            {
                printf("%s (base %d) = %s (base %d)\n", num1.c_str(), i, num2.c_str(), j);
                return;
            }
        }
    }
    //fail
    printf("%s is not equal to %s in any base 2..36\n", num1.c_str(), num2.c_str() );
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("343.in", "r", stdin);
#endif

    string num1, num2;

    while (cin >> num1 >> num2)
    {
        match(num1, num2);
    }
}

343.in

12   5
    10     A
12 34
  123   456
  1    2
  10   2
  10 36
  35 Z
Z                     35
0 0

352.cpp

/**
 * UVa 352 The Seasonal War
 * Author: chchwy
 * Last Modified: 2011.07.27
 * Blog: http://chchwy.blogspot.com
 */
#include<iostream>
#include<cstdio>
using namespace std;

enum {MAX = 25 + 2};

int img_size;
char img[MAX][MAX];

// pixel座標是否還在圖像內
bool is_valid(int x, int y)
{
    return ( x < img_size && x >= 0 && y < img_size && y >= 0);
}

void dfs(int x, int y)
{
    img[x][y] = '0';

    // 八個方向
    for (int dx = -1; dx <= 1; ++dx)
    {
        for (int dy = -1; dy <= 1; ++dy)
        {
            int next_x = x + dx;
            int next_y = y + dy;

            if ( is_valid(next_x, next_y) && img[next_x][next_y] == '1')
                dfs(next_x, next_y);
        }
    }
}

int solve(char img[MAX][MAX], int img_size )
{
    int war_eagles_counter = 0;

    for (int i = 0; i < img_size; ++i)
    {
        for (int j = 0; j < img_size; ++j)
        {
            if ( img[i][j] == '1' )
            {
                dfs(i, j);
                war_eagles_counter++;
            }
        }
    }
    return war_eagles_counter;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("352.in", "r", stdin);
#endif

    int caseNo = 1;
    while ( scanf("%d ", &img_size) == 1 )
    {
        for (int i = 0; i < img_size; ++i)
            scanf("%s", img[i]);

        int war_eagles = solve(img, img_size);

        printf("Image number %d ", caseNo++);
        printf("contains %d war eagles.\n", war_eagles);
    }

    return 0;
}

352.in

6
100100
001010
000000
110000
111000
010100
8
01100101
01000001
00011000
00000010
11000011
10100010
10000001
01100000
1
0
1
1
2
11
10

355.cpp

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

inline int CharToDigit(char c)
{
    if ( isdigit(c) )
        return c - '0';
    return c - 'A' + 10;
}

inline char DigitToChar(int n)
{
    return "0123456789ABCDEF"[n];
}

bool checkIllegal(int base1, string& in )
{
    for (int i = 0; i < in.length(); ++i)
        if ( CharToDigit(in[i]) >= base1 )
            return true;
    return false;
}

/* convert string 'in' to int 'value'. */
long long parseValue( int base1, string& in )
{
    if ( checkIllegal(base1, in) ) return -1;

    long long value = 0;
    long long curBase = 1;

    for (int i = in.length() - 1; i >= 0; --i)
    {

        value += CharToDigit(in[i]) * curBase;
        curBase *= base1;
    }
    return value;
}

/* convert int 'value' to string 'out' */
string toBase( int base2, long long value )
{
    if (value == 0) return "0";

    string out;
    while ( value > 0 )
    {
        out += DigitToChar( value % base2 );
        value /= base2;
    }
    reverse(out.begin(), out.end());
    return out;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("355.in", "r", stdin);
#endif

    int base1, base2;
    string in;

    while ( cin >> base1 >> base2 >> in )
    {
        long long value = parseValue(base1, in);

        if ( value < 0 ) //wrong
        {
            cout << in << " is an illegal base " << base1 << " number\n";
            continue;
        }
        cout << in << " base " << base1 << " = " << toBase(base2, value) << " base " << base2 << "\n";
    }
    return 0;
}

355.in

2 10 10101
5 3 126
15 11 A4C
10 2 1024
10 2 512
10 2 256
10 2 128
10 2 64
16 10 FFFF
16 2  FF
3 3 222222
6 7 0
2 3 0
16 16 7FFFFFFFFFF
10 16 9999999999

357.cpp

/**
 * UVa 357 The Me Count The Ways
 * Author: chchwy
 * Last Modified: 2010.03.01
 */
#include<iostream>

enum {MAX_MONEY = 30000, COIN_TYPES = 5};

int main()
{
    int coin[] = {1, 5, 10, 25, 50};

    long long int count[MAX_MONEY + 1];
    memset(count, 0, sizeof(count));

    /* DP to build count table */
    count[0] = 1;

    for (int i = 0; i < COIN_TYPES; ++i)
        for (int j = coin[i]; j <= MAX_MONEY; ++j)
            count[j] += count[j - coin[i]];

    /* just lookup table */
    int money;
    while ( scanf("%lld", &money) == 1 )
    {
        if ( count[money] == 1 )
            printf("There is only 1 way to produce %d cents change.\n", money);
        else
            printf("There are %lld ways to produce %d cents change.\n", count[money], money);
    }

    return 0;
}

369.cpp

/**
 * UVa 369 Conbinations
 * Author: chchwy
 * Last Modified: 2008/09/17
 */
//C(n,r)= n! / (n-r)!r!
#include<cstdio>

long double C(int n, int r)
{
    if (n - r < r) r = n - r; // C(5,3)==C(5,2)

    long double product = 1;
    for (int i = 1; i <= r; i++)
    {
        product = product * (n - r + i) / i;
    }
    return product;
}

int main()
{
    int n, r;
    while (scanf("%d %d", &n, &r) == 2)
    {
        if (n == 0 && r == 0) break;
        printf("%d things taken %d at a time is %.0Lf exactly.\n", n, r, C(n, r));
    }
    return 0;
}

371.cpp

/**
 * UVa 371 Ackermann function
 * Author: chchwy
 * Last Modified: 2010.03.18
 * Tag: Brute Force
 */
#include<cstdio>
#include<algorithm>

int getLength(long long n)
{
    int length = 0;
    do
    {
        length++;
        if (n % 2 == 0)
            n = n >> 1; // div 2
        else
            n = n * 3 + 1;
    }
    while (n != 1);

    return length;
}

int main()
{
    int L, H;

    while (scanf("%d %d", &L, &H))
    {
        if (L == 0 && H == 0)
            break;

        if (L > H) std::swap(L, H); //L may be greater than H

        int maxLen = 1, max = L;
        for (int i = L; i <= H; ++i)
        {
            int curLen = getLength(i);
            if (curLen > maxLen)
            {
                max = i;
                maxLen = curLen;
            }
        }
        printf("Between %d and %d, ", L, H);
        printf("%d generates the longest sequence of %d values.\n", max, maxLen);
    }
    return 0;
}

382.cpp

/**
 * UVa 382 Perfection
 * Author: chchwy
 * Last Modified: 2010.01.31
 */
#include<iostream>
#include<cmath>

int factorSum(int n)
{
    if (n == 1) return 0;

    int sum = 1; //1¥²¬°¦]¼Æ

    int sqrt_n = sqrt(n);
    for (int i = 2; i <= sqrt_n; ++i)
    {
        if ( n % i == 0 )
        {
            sum += i;
            sum += n / i;
        }
    }
    return sum;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("382.in", "r", stdin);
#endif

    puts("PERFECTION OUTPUT");

    int n;
    while (scanf("%d", &n) == 1)
    {
        if (n == 0) break;

        int sum =  factorSum(n);
        if (sum == n)
            printf("%5d  PERFECT\n", n);
        else if (sum < n)
            printf("%5d  DEFICIENT\n", n);
        else
            printf("%5d  ABUNDANT\n", n);
    }
    puts("END OF OUTPUT");
    return 0;
}

382.in

1
6
28
496
8128
15 28 6 56 60000 22 496 0

389.cpp

#include<iostream>
using namespace std;

inline int CharToDigit(char c)
{
    if ( isdigit(c) )
        return c - '0';
    return c - 'A' + 10;
}

inline char DigitToChar(int n)
{
    return "0123456789ABCDEF"[n];
}

/* convert string 'in' to int 'value'. */
long long parseValue( int base1, string& in )
{
    long long value = 0;
    long long curBase = 1;

    for (int i = in.length() - 1; i >= 0; --i)
    {
        value += CharToDigit(in[i]) * curBase;
        curBase *= base1;
    }
    return value;
}

/* convert int 'value' to string 'out' */
string toBase( int base2, long long value )
{
    if (value == 0) return "0";

    string out;
    while ( value > 0 )
    {
        out += DigitToChar( value % base2 );
        value /= base2;
    }
    reverse(out.begin(), out.end());
    return out;
}

string convert( string& in, int base1, int base2 )
{
    string out = toBase(base2, parseValue(base1, in) );
    if ( out.length() > 7)
        return "ERROR";
    return out;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("389.in", "r", stdin);
#endif

    int base1, base2;
    string in;

    while (cin >> in >> base1 >> base2)
    {
        printf("%7s\n", convert( in, base1, base2 ).c_str());
    }
}

389.in

1111000  2 10
1111000  2 16
2102101  3 10
2102101  3 15
  12312  4  2
     1A 15  2
1234567 10 16
   ABCD 16 15
    000 12 12

400.cpp

/*
 * UVa 400 (AC)
 * Author: chchwy
 * Last Modified: 2009.04.22
 */
#include <iostream>
#include <cmath>
using namespace std;

bool cmpAscii(const string& a, const string& b)
{
    int min = ( a.length() < b.length() ) ? a.length() : b.length();
    for (int i = 0; i < min; ++i)
    {
        if (a[i] < b[i])
            return true;
        else if (a[i] > b[i])
            return false;
    }
    if ( a.length() < b.length() )
        return true;
    return false;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("400.in", "r", stdin);
#endif

    string filename[100];
    int numFile;

    while (scanf("%d ", &numFile) == 1)
    {
        for (int i = 0; i < numFile; ++i)
            getline(cin, filename[i]);

        std::sort(filename, filename + numFile, cmpAscii);

        int longest = 0;
        for (int i = 0; i < numFile; ++i)
            if (filename[i].length() > longest)
                longest = filename[i].length();

        int colNum = 62 / (longest + 2);
        int rowNum = ceil((float)numFile / colNum); //無條件進位

        string row[101];

        cout << "------------------------------------------------------------\n";

        for (int i = 0; i < numFile; ++i)
        {
            int space = longest - filename[i].length();
            if (i / rowNum != colNum - 1) space += 2;

            for (int j = 0; j < space; ++j)
                filename[i] += " ";

            row[i % rowNum] += filename[i];
        }
        for (int i = 0; i < rowNum; ++i)
            cout << row[i] << endl;
    }
    return 0;
}

401.cpp

/*
 *  UVa 401 (AC)
 *  Author: chchwy
 *  Last Modified: 2009.04.22
 */
#include <iostream>

char mirror[128] =
{
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, '1',
    'S', 'E', 0, 'Z', 0, 0, '8', 0, 0, 0, 0, 0, 0, 0, 0, 'A', 0, 0, 0, '3',
    0, 0, 'H', 'I', 'L', 0, 'J', 'M', 0, 'O', 0, 0, 0, '2', 'T', 'U', 'V',
    'W', 'X', 'Y', '5', 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

bool palindrome(char str[], int len)
{
    for (int i = 0; i < len / 2; ++i)
        if (str[i] != str[len - 1 - i])
            return false;
    return true;
}

int mirrored(char str[], int len)
{
    for (int i = 0; i <= len / 2; ++i)
        if (str[i] != mirror[ str[len - 1 - i] ] )
            return false;
    return true;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("401.in", "r", stdin);
#endif

    char str[30 + 1];

    while ( fgets(str, sizeof(str), stdin) )
    {
        int len = strlen(str);
        if ( str[len - 1] == '\n' ) //overwrite '\n';
        {
            str[len - 1] = 0;
            len--;
        }

        bool isPalindrome = palindrome(str, len);
        bool isMirrored = mirrored(str, len);

        if (isPalindrome && isMirrored)
            printf("%s -- is a mirrored palindrome.\n\n", str);
        else if (isPalindrome)
            printf("%s -- is a regular palindrome.\n\n", str);
        else if (isMirrored)
            printf("%s -- is a mirrored string.\n\n", str);
        else
            printf("%s -- is not a palindrome.\n\n", str);
    }

    return 0;
}

406.cpp

/**
 * UVa 406 Prime Cuts (AC)
 * Author: chchwy
 * Last Modified: 2009.11.22
 */
#include<iostream>
#include<vector>
using namespace std;
enum {MAX = 1001};

char p[MAX]; //prime=0, not prime=1

void shieve()
{
    p[0] = 1;
    p[1] = 0; //本題1算質數
    for (int i = 2; i * i < MAX; ++i)
    {
        if (p[i] == 1)
            continue;
        for (int j = i * i; j < MAX; j += i)
            p[j] = 1;
    }
}

int main()
{
    shieve();

    int N, C;
    while (scanf("%d %d", &N, &C) == 2)
    {
        printf("%d %d:", N, C);

        vector<int> prime;
        for (int i = 1; i <= N; ++i)
            if (p[i] == 0)
                prime.push_back(i);

        int cuts = (prime.size() % 2 == 0) ? C * 2 : C * 2 - 1;
        if (cuts > prime.size())
            cuts = prime.size();

        int begin = (int)(prime.size() - cuts) / 2;
        if (begin < 0) begin = 0;


        for (int i = begin; i < begin + cuts; ++i)
            printf(" %d", prime[i]);
        printf("\n\n");
    }
    return 0;
}

414.cpp

/**
 * UVa 414 Machined Surface
 * Author: chchwy
 * Last Modified: 2010.02.06
 */
#include<iostream>
using namespace std;

int run (int numLine)
{
    int minSpace = 25;
    int totalSpace = 0;

    for (int i = 0; i < numLine; ++i)
    {
        char buf[32];
        fgets(buf, sizeof(buf), stdin);

        int curSpace = 0;
        for (int i = 0; i < 25; ++i)
        {
            if (buf[i] == ' ')
                curSpace++;
        }

        if (curSpace < minSpace)
            minSpace = curSpace;

        totalSpace += curSpace;
    }
    return totalSpace - (minSpace * numLine);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("414.in", "r", stdin);
#endif

    int numLine;
    while ( scanf("%d ", &numLine) )
    {
        if ( numLine == 0 ) break;

        printf("%d\n", run(numLine) );
    }
    return 0;
}

414.in

4
XXXX                XXXXX
XXX               XXXXXXX
XXXXX                XXXX
XX                 XXXXXX
2
XXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
1
XXXXXXXXX              XX
2
XXXXXXXXXXXXXXXXXX   XXXX
XXX    XXXXXXXXXXXXXXXXXX
0

431.cpp

/**
 * UVa 431 Trial of the Millennium
 * Author: chchwy
 * Last Modified: 2011.08.04
 * Tag: Dynamic Programming, 0/1 Knapsack
 */
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

enum {MAX_HOUR = 240 + 2, MAX_EVIDENCE = 100 + 1};

struct Evidence
{
    int score;
    int time_cost;
    char description[128];

    Evidence( string& );
};

Evidence::Evidence(string& line)
{
    stringstream sin(line);
    sin >> score >> time_cost;
    sin.getline(description, sizeof(description));
}

int  c[MAX_HOUR];
bool p[MAX_EVIDENCE][MAX_HOUR];

void solve_knapsack( int allowed_time, vector<Evidence>& ev )
{
    memset(c, 0, sizeof(c));
    memset(p, 0, sizeof(p));

    for (int i = ev.size() - 1; i >= 0 ; --i)
    {
        for (int j = allowed_time; j >= ev[i].time_cost; --j)
        {

            if ( c[j - ev[i].time_cost] + ev[i].score > c[j])
            {

                p[i][j] = true;
                c[j] = c[j - ev[i].time_cost] + ev[i].score;
            }
        }
    }
}

bool cmp_time( const Evidence& a, const Evidence& b)
{
    return (a.time_cost < b.time_cost);
}

void pretty_print( vector<Evidence>& ev )
{
    int total_score = 0;
    for (int i = 0; i < ev.size(); ++i)
        total_score  = total_score + ev[i].score;

    int total_time = 0;
    for (int i = 0; i < ev.size(); ++i)
        total_time = total_time + ev[i].time_cost;

    printf("Score  Time  Description\n");
    printf("-----  ----  -----------\n");

    for (int i = 0; i < ev.size(); ++i)
        printf("%3d    %3d  %s\n", ev[i].score, ev[i].time_cost, ev[i].description);

    printf("\n");
    printf("Total score: %d points\n", total_score);
    printf(" Total time: %d hours\n", total_time);
}

void backtrace_result(int allowed_time, vector<Evidence>& ev )
{
    vector<Evidence> selected_ev;

    int j = allowed_time;
    for (int i = 0; i < ev.size(); ++i)
    {
        if ( p[i][j] )
        {
            selected_ev.push_back(ev[i]);
            j = j - ev[i].time_cost;
        }
    }
    pretty_print( selected_ev );
}

bool is_enough_time( int allowed_time, vector<Evidence>& ev )
{
    for (int i = 0; i < ev.size(); ++i)
        if ( ev[i].time_cost <= allowed_time ) //holy sxxt bug at "<" to  "<="
            return true;
    return false;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("431.in", "r", stdin);
    freopen("431.out", "w", stdout);
#endif

    int num_case;
    cin >> num_case;

    while (num_case--)
    {
        int allowed_time;
        cin >> allowed_time;
        cin.ignore(10, '\n');

        vector<Evidence> ev;

        string line;
        while (getline(cin, line))
        {
            if ( line.size() == 0 )
                break;
            ev.push_back(Evidence(line));
        }

        if ( is_enough_time(allowed_time, ev) )
        {

            solve_knapsack(allowed_time, ev);
            backtrace_result(allowed_time, ev);
        }
        else
        {
            puts("There is not enough time to present any evidence. Drop the charges.");
        }
        if ( num_case != 0 ) putchar('\n');
    }
    return 0;
}

431.in

5

12
1 5 HAHA
1 5 KERKER

2
4 1 M
9 4 Y
7 1 E
2 2 B
6 4 W
9 1 N
6 3 F

240
5 4 Inspector supervising evidence collection at the crime scene
3 4 Crime scene photos
4 8 411 operator recording
3 8 Officer who arrested defendant in a previous incident
2 8 Victim's neighbor 2
1 8 Victim's neighbor 3
6 40 The victim's cousin
8 48 The defendant's current housemate
10 60 Coroner's report
5 16 SCSD Crime Lab technician 1
4 16 Taxi cab driver
2 16 SCSD Crime Lab technician 2
1 16 The defendant's personal trainer
5 24 Officer responsible for making the arrest
3 24 Victim's neighbor 1
2 24 The victim's supervisor at work
1 24 Pizza delivery person
3 1 A discarded plastic fork at the crime scene
5 32 The victim's brother
7 40 The victim's personal physician
1 1 An email the victim sent to his cousin the week before the incident
2 2 Bloody sock
6 64 Blood analysis results by chief criminalist of the SCSD Crime Lab

5
2 10 M
3 10 N

10
10 1 A
20 4 B
10 7 C

431.out

Score  Time  Description
-----  ----  -----------
  1      5   HAHA
  1      5   KERKER

Total score: 2 points
 Total time: 10 hours

Score  Time  Description
-----  ----  -----------
  9      1   N
  7      1   E

Total score: 16 points
 Total time: 2 hours

Score  Time  Description
-----  ----  -----------
  3      1   A discarded plastic fork at the crime scene
  1      1   An email the victim sent to his cousin the week before the incident
  2      2   Bloody sock
  5      4   Inspector supervising evidence collection at the crime scene
  3      4   Crime scene photos
  4      8   411 operator recording
  3      8   Officer who arrested defendant in a previous incident
  2      8   Victim's neighbor 2
  5     16   SCSD Crime Lab technician 1
  4     16   Taxi cab driver
  5     24   Officer responsible for making the arrest
  7     40   The victim's personal physician
  8     48   The defendant's current housemate
 10     60   Coroner's report

Total score: 62 points
 Total time: 240 hours

There is not enough time to present any evidence. Drop the charges.

Score  Time  Description
-----  ----  -----------
 10      1   A
 20      4   B

Total score: 30 points
 Total time: 5 hours

455.cpp

/**
 * UVa 455 Periodic Strings
 * Author: chchwy
 * Last Modified: 2010.04.22
 */
#include<iostream>

int findPeriod(char* buf)
{
    int len = strlen(buf);
    if (len == 1) return 1; //special case

    int i = 0, j = 1;
    while (buf[j] != NULL) //reach the end of string
    {
        if (buf[i] == buf[j])
            ++i, ++j;
        else
            ++j;
    }
    return ( len % (j - i) == 0 ) ? j - i : len;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("455.in", "r", stdin);
#endif

    int caseNum;
    scanf("%d ", &caseNum);

    while ( caseNum-- )
    {
        char buf[256];
        scanf("%s", buf);

        printf("%d\n", findPeriod(buf) );
        if ( caseNum > 0 ) putchar('\n');
    }
    return 0;
}

455.in

5

hahoha

abacabaabacaba

abcabcabcabcd

a

abcdefg

458.cpp

#include<cstdio>

int main(int c)
{
    while ((c = getchar()) != EOF && putchar((c > 31) ? c - 7 : c));
}

476.cpp

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

enum {MAX_REC = 10, X1 = 0, Y1 = 1, X2 = 2, Y2 = 3};


int main()
{
    int numRec = 0;
    double rec[MAX_REC][4];

    char c;

    while (scanf(" %c", &c))
    {
        if (c == '*')
            break;
        scanf("%lf %lf %lf %lf",
              &rec[numRec][X1], &rec[numRec][Y1], &rec[numRec][X2], &rec[numRec][Y2]);
        numRec++;
    }

    double x, y;
    int numPoint = 1;
    int outRec;
    while (scanf(" %lf %lf", &x, &y))
    {
        if (x == 9999.9 && y == 9999.9)
            break;

        outRec = 1;
        for (int i = 0; i < numRec; ++i)
        {
            if (x > rec[i][X1] && y < rec[i][Y1] &&
                    x < rec[i][X2] && y > rec[i][Y2])
            {
                printf("Point %d is contained in figure %d\n", numPoint, i + 1);
                outRec = 0;
            }
        }
        if (outRec)
            printf("Point %d is not contained in any figure\n", numPoint);
        numPoint++;
    }
    return 0;
}

482.cpp

/**
 * UVa 482 Permutation Arrays
 * Author: chchwy
 * Last Modified: 2011/03/15
 * Blog: http://chchwy.blogspot.com
 */
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;

enum { MAX = 1000 };

int    pos[MAX];
string data[MAX];

int read_pos_array()
{
    int x, index = 0;
    while ( cin >> x )
    {
        pos[x - 1] = index; //index shift (between 0 start and 1 start)
        index++;
        if ( cin.get() == '\n')
            break;
    }
    return index;
}

void read_data_array(int len)
{
    for (int i = 0; i < len; ++i)
    {
        cin >> data[i];
    }
    cin.ignore(128, '\n');
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("482.in", "r", stdin);
#endif

    int num_case;
    cin >> num_case;

    while (num_case--)
    {
        cin.ignore(128, '\n');

        int len = read_pos_array();
        read_data_array(len);

        for (int i = 0; i < len; ++i)
        {
            cout << data[ pos[i] ] << '\n';
        }
        if (num_case != 0)
            putchar('\n');

    }
    return 0;
}

482.in

3

3 1 2
32.0 54.7 -2

3 1 2
32.0 54.7 -2

3 1 2
32.0 54.7 -2

485.cpp

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

class BigInt
{
public:
    enum {MAX = 61};
    int dig[MAX];
    int size;

    BigInt();
    BigInt operator+(const BigInt& b);
    BigInt operator=(const BigInt& right);
    BigInt operator=(const char* input);
    void print();
};

BigInt::BigInt()
{
    size = 0;
    memset(dig, 0, sizeof(dig));
}

BigInt BigInt::operator+(const BigInt& b)
{
    BigInt sum;
    sum.size = max(size, b.size);
    for (int i = 0; i < MAX; i++)
    {
        sum.dig[i] += dig[i] + b.dig[i];
        if (sum.dig[i] > 9)
        {
            sum.dig[i] -= 10;
            sum.dig[i + 1]++;
        }
    }
    if (sum.dig[sum.size] != 0) ++sum.size;
    return sum;
}

BigInt BigInt::operator=(const BigInt& right)
{

    if ( &right == this ) return *this;

    size = right.size;
    for (int i = 0; i < MAX; i++)
        dig[i] = right.dig[i];

    return *this;
}

BigInt BigInt::operator=(const char* input)
{
    size = strlen(input);
    for (int i = 0; i < size; i++)
    {
        dig[i] = input[size - i - 1] - '0';
    }
    return *this;
}

void BigInt::print()
{
    for (int i = size - 1; i >= 0; i--)
        printf("%d", dig[i]);
}

int main()
{
    BigInt pascal[2][300];
    int currentLength;
    int current = 0, next = 1;

    //initial row1
    pascal[current][0] = "1";
    pascal[current][1] = "1";
    currentLength = 2;

    // output pascal triangle
    printf("1\n");
    printf("1 1\n");

    do
    {
        pascal[next][0] = "1";
        pascal[next][currentLength] = "1";

        printf("1 ");
        for (int i = 1; i < currentLength; i++)
        {
            pascal[next][i] = pascal[current][i - 1] + pascal[current][i];
            pascal[next][i].print();
            putchar(' ');
        }
        printf("1\n");

        swap(current, next);
        currentLength++;

    }
    while (pascal[current][currentLength / 2].size < 61);
    //10的60次方是61位數
    return 0;
}

488.cpp

/**
 * UVa Triangle Wave (AC)
 * Author: chchwy
 * Last Modified: 2010.02.03
 */
#include<cstdio>

void wave(int A)
{
    int curA = 1;
    while (curA < A)
    {
        for (int i = 0; i < curA; ++i)
            printf("%d", curA);
        printf("\n");

        ++curA;
    }
    while (curA > 0)
    {
        for (i = 0; i < curA; ++i)
            printf("%d", curA);
        printf("\n");

        --curA;
    }
}

int main()
{
    int caseNum;
    scanf("%d", &caseNum);

    while (caseNum--)
    {
        int A, F;
        scanf("%d %d", &A, &F);

        for (int i = 0; i < F; ++i)
        {
            wave(A);
            if (i != F - 1) printf("\n");
        }

        if (caseNum != 0) printf("\n");
    }
}

490.cpp

/**
 * UVa 490 Rotating Sentences
 * Author: chchwy
 * Last modified: 2010.04.23
 */
#include<iostream>
#include<vector>
using namespace std;

//find the max length of strings
int findMaxX(vector<string>& str)
{
    int max = 0;
    for (int i = 0; i < str.size(); ++i)
        if (str[i].size() > max)
            max = str[i].size();
    return max;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("490.in", "r", stdin);
#endif

    vector<string> str;

    //read input
    string line;
    while ( getline(cin, line) )
        str.push_back(line);

    //find the bound
    int max_y = str.size();
    int max_x = findMaxX(str);

    //output
    for (int i = 0; i < max_x; ++i)
    {
        for (int j = max_y - 1; j >= 0; --j)
        {
            char c = (i < str[j].size()) ? str[j][i] :  ' ';
            putchar(c);
        }
        putchar('\n');
    }
    return 0;
}

490.in

aaa    aaa
 bbb  bbb
  cccccc
   dddd
    ee
   f  f
  g    g
   h  h

492.cpp

/**
 * UVa 492 Pig-Latin (AC)
 * Author: chchwy
 * Last Modified: 2010.02.06
 */
#include<cstdio>
#include<cctype>
#include<cstring>

bool isVowel(char c)
{
    switch (c)
    {
    case 'A':
    case 'a':
    case 'E':
    case 'e':
    case 'I':
    case 'i':
    case 'O':
    case 'o':
    case 'U':
    case 'u':
        return true;
    default:
        return false;
    }
}
int main()
{
    char buf[4096];
    int  bufIndex = 0;
    bool isWord = false; //the state

    char c;
    while ( (c = getchar()) != EOF )
    {
        /* finite state machine */
        switch ( isWord )
        {
        case false:
            if ( isalpha(c) )
            {
                bufIndex = 0; //clear buf
                buf[ bufIndex++ ] = c;
                isWord = true;
            }
            else
                putchar(c);
            break;

        case true:
            if ( isalpha(c) )
            {
                buf[ bufIndex++ ] = c;
            }
            else
            {
                /* print word */
                if ( isVowel(buf[0]) )
                {
                    buf[bufIndex] = NULL; //NULL end
                    printf(buf);
                    printf("ay");
                }
                else
                {
                    buf[bufIndex] = NULL;
                    printf(buf + 1);
                    putchar(buf[0]);
                    printf("ay");
                }
                putchar(c);
                isWord = false;
            }
            break;
        }
    }
    return 0;
}

494.cpp

/*
 * UVa 494
 * Author: chchwy
 * Last Modified: 2009.10.30
 */
#include <iostream>
#include <cctype>

int main()
{
#ifndef ONLINE_JUDGE
    freopen("494.in", "r", stdin);
#endif

    int counter = 0;
    char cur = 0, prev = 0;
    while ( (cur = getchar()) != EOF )
    {
        if (cur == '\n')
        {
            printf("%d\n", counter);
            counter = 0;
            prev = 0;
        }
        if ( isalpha(cur) && !isalpha(prev) )
            counter++;
        prev = cur;
    }
    return 0;
}

516.cpp

/**
 * UVa 516 Prime Land
 * Author: chchwy
 * Last Modified: 2011.07.20
 */
#include<iostream>
#include<sstream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

enum { MAX = 32767 + 1 };

vector<int> prime;

// 用埃式篩法建質數表
int sieve()
{
    char map[MAX];
    memset(map, 1, sizeof(map));

    map[0] = map[1] = 0;

    for (int i = 2; i < MAX; ++i)
    {
        if ( map[i] )
            for (int j = i * i; j < MAX; j += i )
                map[j] = 0;
    }

    for (int i = 0; i < MAX; ++i)
        if ( map[i] == 1 )
            prime.push_back(i);
}

// 把質因數分解表示法轉成整數值
int to_int_value( string& line )
{
    int result = 1;

    istringstream sin(line);

    int base, exp;
    while ( sin >> base >> exp )
    {
        for (int i = 0; i < exp; ++i)
            result = result * base;
    }
    return result;
}

bool is_prime( int n )
{
    for (int i = 0; prime[i]*prime[i] <= n; ++i)
        if ( n % prime[i] == 0 )
            return false;
    return true;
}

// 把整數轉回質因數表示法
void to_prime_base_string(int num)
{
    if ( is_prime(num) )  // special case
    {
        printf("%d 1\n", num);
        return;
    }

    bool first = true;

    for (int i = prime.size() - 1; i >= 0; --i)
    {
        int factor_exp = 0;

        while (num % prime[i] == 0)
        {
            num = num / prime[i];
            factor_exp++;
        }

        if ( factor_exp == 0 ) continue;

        if ( !first )
            printf(" ");
        first = false;

        printf("%d %d", prime[i], factor_exp);
    }
    printf("\n");
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("516.in", "r", stdin);
#endif
    sieve();

    string line;
    while (getline(cin, line))
    {
        if (line == "0") break;

        int num = to_int_value(line);
        num = num - 1;
        to_prime_base_string(num);
    }
    return 0;
}

516.in

18 1 17 1 15 1
17 1 11 1
11 1 29 1 9 1
2 1 4 1 5 1 7 1 11 1
18 1 23 1 29 1
31 1 29 1
2 3 11 2 25 1
41 2
51 1 5 1
17 1 19 1 23 1
0

548.cpp

/**
 * UVa 548 Tree (AC)
 * Author: chchwy (a) gmail.com
 * Last modified: 2010.04.22
 */
#include<iostream>
#include<sstream>
#include<vector>
using namespace std;

class node
{
public:
    int value; //the value of this node
    int sum;   //the sum of path from root to current node
    node* lc, *rc;
    node()
    {
        value = 0, sum = 0;
    }
    node(int v, int s)
    {
        value = v, sum = s;
    };
};

node* External = new node(0, INT_MAX);

//parse strings to a integer vector
void parseIntLine(vector<int>& list, string& line)
{
    stringstream sin(line);
    int n;
    while (sin >> n)
        list.push_back(n);
}

/* build a tree by inorder and postorder sequence */
node* buildTree( vector<int>::iterator begin,
                 vector<int>::iterator end,
                 vector<int>& postorder)
{
    if (postorder.empty())
        return External;

    vector<int>::iterator it = find(begin, end, postorder.back());
    if ( it == end ) //not found
        return External;

    int value = postorder.back(); postorder.pop_back();

    node* root = new node();
    root->value = value;
    root->rc = buildTree(it + 1, end, postorder);
    root->lc = buildTree(begin, it, postorder);

    return root;
}

node* do_summing(node* cur, int path_sum)
{
    if (cur == External) return External;

    //往下累加path sum
    cur->sum = cur->value + path_sum;

    node* lc = do_summing(cur->lc, cur->sum);
    node* rc = do_summing(cur->rc, cur->sum);

    if (lc == External && rc == External) //leaf node
        return cur;

    //回傳最小的leaf node
    return (lc->sum < rc->sum) ? lc : rc;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("548.in", "r", stdin);
#endif

    string line1, line2;
    while ( getline(cin, line1) && getline(cin, line2) )
    {
        vector<int> inorder, postorder;

        parseIntLine(inorder, line1);
        parseIntLine(postorder, line2);

        node* root = buildTree(inorder.begin(), inorder.end(), postorder);

        printf("%d\n", dfs(root, 0)->value );
    }
    return 0;
}

548.in

3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 22
7 2 8 10 6 1 11 15 3 4
7 8 6 10 2 15 11 4 3 1
7 5 6 4 8 2 9 1 3 11 10 12
7 6 5 8 4 9 2 11 12 10 3 1
4 2 6 5 7 1 9 3 13 12 8 11
4 6 7 5 2 9 13 12 11 8 3 1
4 11 2 1 3 9 6
11 4 2 9 6 3 1
4 11 2 1 3 8 6
11 4 2 8 6 3 1
5 7 1
5 7 1

562.cpp

/**
 * UVa 562 Dividing Coins
 * Author: chchwy
 * Last Modified: 2011/08/07
 * Tag: Dynamic Programming, Subset sum
 */
#include<cstdio>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<numeric>

enum
{
    MAX_COINS = 100,
    MAX_CENTS = 500,
    MAX_SUM = MAX_COINS * MAX_CENTS
};

bool possible[MAX_SUM + 1];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("562.in", "r", stdin);
#endif

    int num_case;
    scanf("%d", &num_case);

    while ( num_case-- )
    {
        int num_coins;
        scanf("%d", &num_coins);

        int coin[MAX_COINS];
        for (int i = 0; i < num_coins; ++i)
            scanf("%d", &coin[i] );

        int sum = std::accumulate(coin, coin + num_coins, 0);

        memset(possible, 0, sizeof(possible));
        possible[0] = 1;

        for (int i = 0; i < num_coins; ++i)
        {
            for (int j = sum - coin[i]; j >= 0; --j)
            {
                if ( possible[j] )
                    possible[j + coin[i]] = true;
            }
        }

        int min = INT_MAX;

        for (int i = 0; i <= sum; ++i) // sum=0 cent is valid
            if ( possible[i] && abs(2 * i - sum) < min )
                min = abs(2 * i - sum);
        printf("%d\n", min);
    }
    return 0;
}

562.in

3
6
48 48 49 49 50 50
1
5
0

579.cpp

/**
 * UVa 579 ClockHands
 * Author: chchwy
 * Last Modified: 2011.04.06
 * Blog: http://chchwy.blogspot.com
 */
#include<cstdio>
#include<cmath>

float angle_between(float hr, float min)
{
    float hr_angle = (hr / 12 * 360) + (min / 60 * (360 / 12));
    float min_angle =  min / 60 * 360;

    float dif_angle = fabs(hr_angle - min_angle);

    return (dif_angle < 180) ? dif_angle : (360.0 - dif_angle);
}

int main()
{
    int hr, min;
    char tmp;

    while ( scanf("%d%c%d", &hr, &tmp, &min) )
    {
        if (hr == 0 && min == 0) break;
        printf("%.3f\n", angle_between(hr, min));
    }
}

583.cpp

/**
 * UVa 583 Prime Factors
 * Author: chchwy
 * Last Modified: 2011.07.21
 */
#include<cstdio>
#include<bitset>
#include<vector>
using namespace std;

enum {MAX = 46340 + 1}; // sqrt(INT_MAX)

vector<int> prime; //½è¼Æªí

void sieve()
{
    bitset<MAX> p;
    p.flip();

    p[0] = p[1] = 1;

    for (int i = 3; i * i < MAX; i += 2)
    {
        if ( p[i] )
            for (int j = i * i; j < MAX; j += i)
                p[j] = 0;
    }

    for (int i = 2; i < MAX; ++i)
        if ( p[i] )
            prime.push_back(i);

    printf("%d\n", prime.back());
}

void print_prime_based_representation(int num)
{
    //special case
    if ( num == 1 || num == -1 )
    {
        printf(" %d\n", num);
        return;
    }

    if (num < 0)
    {
        num = -num;
        printf(" -1 x");
    }

    bool first = true;

    // ¶}©l°µ¦]¦¡¤À¸Ñ
    for (int i = 0; i < prime.size(); ++i)
    {
        if ( prime[i]*prime[i] > num ) break;

        while ( num % prime[i] == 0 )
        {
            num = num / prime[i];

            (first) ? printf(" ") : printf(" x ");
            first = false;

            printf("%d", prime[i]);
        }
    }
    if ( num != 1 )
    {
        (first) ? printf(" ") : printf(" x ");
        printf("%d", num);
    }

    putchar('\n');
}

// 49999
// 99998
// 20685
int main()
{
    sieve();

    int num;
    while (scanf("%d", &num) == 1)
    {
        if (num == 0) break;

        printf("%d =", num);
        print_prime_based_representation( num );
    }
    return 0;
}

587.cpp

/**
 * UVa 587 There's treasure everywhere!
 * Author: chchwy
 * Last Modified: 2010.03.22
 */
#include<iostream>
#include<sstream>
#include<cmath>
#include<algorithm>
using namespace std;

const double EPS = 0.000000001;

class Vector2f
{
public:
    double x, y;

    Vector2f(double px, double py)
    {
        x = px, y = py;
    }

    Vector2f operator+= ( Vector2f right )
    {
        x += right.x, y += right.y;
    }

    Vector2f operator* ( int c )
    {
        return Vector2f( x * c, y * c );
    }

    double distance(double px, double py)
    {
        double dx = x - px;
        double dy = y - py;

        return sqrt( (dx * dx) + (dy * dy) );
    }
};

/* 8 directions */
const double SQRT2 = sqrt(2) / 2;
Vector2f N(0, 1);
Vector2f NE(SQRT2, SQRT2);
Vector2f E(1, 0);
Vector2f SE(SQRT2, -SQRT2);
Vector2f S(0, -1);
Vector2f SW(-SQRT2, -SQRT2);
Vector2f W(-1, 0);
Vector2f NW(-SQRT2, SQRT2);

bool isComma(char c)
{
    return (c == ',' || c == '.');
}

/* return the treasure location according to line */
Vector2f findTreasure( string line )
{
    // replace comma to white-space for stringstream extraction
    replace_if( line.begin(), line.end(), isComma, ' ');

    Vector2f loc(0, 0); //current location

    istringstream sin(line);

    string direct;
    int step;
    while (  sin >> step >> direct )
    {
        //cout<<step<<','<<direct<<endl;

        if ( direct == "N" )
            loc += N * step;
        else if ( direct == "NE" )
            loc += NE * step;
        else if ( direct == "E" )
            loc += E * step;
        else if ( direct == "SE" )
            loc += SE * step;
        else if ( direct == "S" )
            loc += S * step;
        else if ( direct == "SW" )
            loc += SW * step;
        else if ( direct == "W" )
            loc += W * step;
        else if ( direct == "NW" )
            loc += NW * step;
    }
    return loc;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("587.in", "r", stdin);
#endif

    int mapNo = 1;

    string line;
    while ( getline(cin, line) )
    {
        if ("END" == line)
            break;

        Vector2f target = findTreasure( line );

        printf("Map #%d\n", mapNo++);
        printf("The treasure is located at (%.3lf,%.3lf).\n", target.x + EPS, target.y + EPS );
        printf("The distance to the treasure is %.3lf.\n\n", target.distance(0, 0) );
    }
    return 0;
}

587.in

3N,1E,1N,3E,2S,1W.
10NW.
1N,1E,1S,1W.
3NE.
END

591.cpp

/*
 * UVa 591
 * Author: chchwy
 * Last Modified: 2009.11.19
 */
#include<cstdio>

int main()
{
    int numCase = 1;
    int numWall = 0;
    while (scanf("%d", &numWall) == 1)
    {
        if (numWall == 0) break;

        int wall[64];
        int sum = 0;
        for (int i = 0; i < numWall; ++i)
        {
            scanf("%d", wall + i);
            sum += wall[i];
        }

        int avg = sum / numWall;
        int move = 0;
        for (int i = 0; i < numWall; ++i)
            if (wall[i] > avg)
                move += wall[i] - avg;

        printf("Set #%d\n", numCase++);
        printf("The minimum number of moves is %d.\n\n", move);
    }
}

594.cpp

/**
 * UVa 594 One Little, Two Little, Three Little Endians
 * Author: chchwy
 * Last Modified: 2011.03.29
 * Blog: http://chchwy.blogspot.com
 */
#include<cstdio>
using namespace std;

int to_big(int little)
{

    char* p = (char*) &little;
    swap(p[0], p[3]);
    swap(p[1], p[2]);
    return little;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("594.in", "r", stdin);
#endif
    int little = 0;
    while (scanf("%d", &little) == 1)
    {
        printf("%d converts to %d\n", little, to_big(little));
    }
    return 0;
}

594.in

123456789
-123456789
1
16777216
20034556

624.cpp

/**
 * UVa 624 CD
 * Author: chchwy
 * Last Modified: 2011.07.30
 * Tag: Dynamic Programming, 0/1 Knapsack
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

enum {MAX_TRACK = 20, MAX_LEN = 10005};

int  c[MAX_LEN];
bool p[MAX_TRACK][MAX_LEN];

void solve_knapsack(int tape_len, int* track, int track_num )
{
    memset(c, 0, sizeof(c));
    memset(p, 0, sizeof(p));

    for (int i = track_num - 1; i >= 0; --i) // for all tracks
    {
        for (int j = tape_len; j >= track[i]; --j) // 1-d array!  //bug at j>track[i]
        {
            // «Øªíªº¤è¦V­n¹ï
            p[i][j] = ( c[j - track[i]] + track[i] > c[j] );
            c[j] = max( c[j - track[i]] + track[i], c[j] );
        }
    }
}

void print_tracks(int tape_len, int* track, int track_num)
{
    int k = tape_len;

    for (int i = 0; i < track_num; ++i)
    {
        if (p[i][k])
        {
            printf("%d ", track[i]);
            k = k - track[i];
        }
    }
    printf("sum:%d\n", c[tape_len]);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("624.in", "r", stdin);
    freopen("624.out", "w", stdout);
#endif

    int tape_len;
    while (scanf("%d", &tape_len) == 1)
    {
        int track_num;
        int track[MAX_TRACK];

        // read
        scanf("%d", &track_num);
        for (int i = 0; i < track_num; ++i)
            scanf("%d", &track[i]);

        solve_knapsack(tape_len, track, track_num);
        print_tracks(tape_len, track, track_num);
    }

}

624.in

5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2

624.out

1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
43 2 sum:45

657.cpp

/**
 * UVa 657 The die is cast
 * Author: chchwy
 * Last Modified: 2011.07.27
 * Blog: http://chchwy.blogspot.com
 */
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;

enum {MAX = 50 + 2};

int W, H; // the width and height of image
char img[MAX][MAX];

int dir[4][2] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

bool is_inside(int x, int y)
{
    return (x >= 0 && x < H && y >= 0 && y < W);
}

void print_debug()
{
    for (int i = 0; i < H; ++i)
        printf("%s\n", img[i]);

    puts("=================================");
    system("PAUSE");
}

void dfs_dot(int x, int y)
{
    img[x][y] = '*';

    for (int i = 0; i < 4; ++i)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        if ( is_inside(nx, ny) && img[nx][ny] == 'X' )
            dfs_dot(nx, ny);
    }
}

int dfs_dice(int x, int y)
{
    img[x][y] = '.';

    int dotted_count = 0;

    // 碰到黑點的話先填滿黑點，再填滿骰子表面

    for (int i = 0; i < 4; ++i)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        if ( is_inside(nx, ny) && img[nx][ny] == 'X')
        {
            dfs_dot(nx, ny);
            dotted_count++;
        }
    }

    for (int i = 0; i < 4; ++i)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        if ( is_inside(nx, ny) && img[nx][ny] == '*' )
        {

            dotted_count += dfs_dice(nx, ny);
        }
    }

    return dotted_count;
}

vector<int> find_all_dices()
{
    vector<int> dices;

    // 逐個骰子填滿
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            if ( img[i][j] == '*' )
            {
                int dot = dfs_dice(i, j);
                dices.push_back(dot);
            }
        }
    }
    sort(dices.begin(), dices.end()); // print in increase order
    return dices;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("657.in", "r", stdin);
#endif

    int case_no = 1;

    while ( scanf("%d %d ", &W, &H) == 2 )
    {
        if ( W == 0 && H == 0 ) break;

        for (int i = 0; i < H; ++i)
            scanf("%s", img[i]);

        vector<int> dices = find_all_dices();

        printf("Throw %d\n", case_no++);

        for (int i = 0; i < dices.size() - 1; ++i)
            printf("%d ", dices[i]);
        printf("%d\n\n", dices.back());
    }
    return 0;
}

657.in

30 15
..............................
..............................
...............*..............
...*****......****............
...*X***.....**X***...........
...*****....***X**............
...***X*.....****.............
...*****.......*..............
..............................
........***........******.....
.......**X****.....*X**X*.....
......*******......******.....
.....****X**.......*X**X*.....
........***........******.....
..............................
0 0

657.out

Throw 1
1 2 2 4

674.cpp

/**
 * UVa 674 (AC)
 * Author: chchwy
 * Last Modified: 2010.03.01
 */
#include<iostream>
enum {MAX_MONEY = 7489, COIN_TYPES = 5};

int main()
{
    int coin[] = {1, 5, 10, 25, 50};

    int count[MAX_MONEY + 1];
    memset(count, 0, sizeof(count));

    /* DP to build count table */
    count[0] = 1;

    for (int i = 0; i < COIN_TYPES; ++i)
        for (int j = coin[i]; j <= MAX_MONEY; ++j)
            count[j] += count[j - coin[i]];

    /* just lookup table */
    int money;
    while ( scanf("%d", &money) == 1 )
        printf("%d\n", count[money]);

    return 0;
}

706.cpp

/**
 * UVa 706
 * Author: chchwy
 * Last Modified: 2009.3.24
 */
#include <iostream>

enum { MAX_ROW = 2 * 10 + 3, MAX_COL = (10 + 2) * 9 };

char numPattern[5][32]
    = { " -     -  -     -  -  -  -  - ",
        "| |  |  |  || ||  |    || || |",
        "       -  -  -  -  -     -  - ",
        "| |  ||    |  |  || |  || |  |",
        " -     -  -     -  -     -  - "
      };

char getLCD(int num, int x, int y, int size)
{
    int maxX = (2 * size + 3) - 1;
    int midX = (size + 2) - 1;
    int maxY = (size + 2) - 1;

    int patternX, patternY;

    //set patternX
    if (x == 0)
        patternX = 0;
    else if (x > 0 && x < midX)
        patternX = 1;
    else if (x == midX)
        patternX = 2;
    else if (x > midX && x < maxX)
        patternX = 3;
    else //x==maxX
        patternX = 4;

    //set patternY
    if (y == 0)
        patternY = 0;
    else if (y == maxY)
        patternY = 2;
    else
        patternY = 1;

    int shift = num * 3;

    return numPattern[ patternX ][ shift + patternY ];
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("706.in", "r", stdin);
    freopen("706.out", "w", stdout);
#endif

    char strNumber[32];
    int size;

    scanf("%d %s", &size, strNumber);

    while (size != 0 || strcmp(strNumber, "0") != 0 )
    {
        char outputBuffer[MAX_ROW][MAX_COL];

        int width = size + 2;
        int height = 2 * size + 3;

        int columnIndex = 0;
        int len = strlen(strNumber);

        for (int k = 0; k < len; ++k)
        {
            for (int i = 0; i < height; ++i)
            {
                for (int j = 0; j < width; ++j)
                {
                    outputBuffer[i][j + columnIndex]
                        = getLCD(strNumber[k] - '0', i, j, size);
                }
            }
            columnIndex += width;

            //fill a Balnk Line
            if (k != len - 1)
            {
                for (int i = 0; i < height; ++i)
                    outputBuffer[i][columnIndex] = ' ';

                columnIndex += 1;
            }
        }
        //output
        for (int i = 0; i < height; ++i)
            outputBuffer[i][columnIndex] = 0;

        for (int i = 0; i < height; ++i)
            printf("%s\n", outputBuffer[i]);

        printf("\n");
        scanf("%d %s", &size, strNumber);
    }
    return 0;
}

897.cpp

/**
 * UVa 897 Anagramatic Primes
 * Author: chchwy
 * Last Modified: 2011.07.21
 * Blog: http://chchwy.blogspot.com
 */
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<set>
using namespace std;

enum {MAX = 1000};

bitset<MAX> p;

void sieve()
{
    p.flip();
    p[0] = p[1] = 0;
    for (int i = 2; i * i < MAX; i++)
        if ( p[i] )
            for (int j = i * i; j < MAX; j += i)
                p[j] = 0;
}

bool is_anagramatic_prime(int n)
{
    if ( !p[n] ) return false;

    char str[16];
    int len = sprintf(str, "%d", n);

    // ¹ïn°µ¥þ±Æ¦C
    sort(str, str + len);
    do
    {
        if ( !p[ atoi(str) ] )
            return false;
    }
    while ( next_permutation(str, str + len) ) ;

    return true;
}

set<int> find_all_anagramatic_primes()
{
    set<int> anag;
    for (int i = 2; i < MAX; ++i)
        if ( is_anagramatic_prime(i) )
            anag.insert(i);
    return anag;
}

int max_value( set<int>& anag)
{
    return (*anag.rbegin());
}

int next_power_of_10(int lower)
{
    int upper = 1;
    while ( upper <= lower)
    {
        upper = upper * 10;
    }
    return upper;
}

int main()
{
    sieve();

    set<int> anag = find_all_anagramatic_primes();

    int lower;
    while ( scanf("%d", &lower) == 1 )
    {
        if (lower == 0) break;

        if ( lower > max_value(anag) )
        {
            printf("0\n");
            continue;
        }
        int upper = next_power_of_10(lower);

        int next = *anag.lower_bound(lower + 1);
        if ( next < upper )
            printf("%d\n", next);
        else
            printf("0\n");
    }
    return 0;
}

900.cpp

/**
 * UVa 900 Brick Wall Patterns
 * Last Modified: 2009.11.27
 * Author: chchwy
 */
#include<cstdio>

int main()
{
    long long int fib[51];
    fib[0] = fib[1] = 1;
    for (int i = 2; i <= 50; ++i)
        fib[i] = fib[i - 1] + fib[i - 2];

    int in;
    while (scanf("%d", &in) == 1)
    {
        if (in == 0)
            break;
        printf("%lld\n", fib[in]);
    }
    return 0;
}

990.cpp

/**
 * UVa 990 Diving for gold
 * Author: chchwy
 * Last Modifed: 2011.08.07
 * Tag: Dynamic Programming, 0/1 Knapsack
 */
#include<cstdio>
#include<cstring>
#include<sstream>

enum { MAX_TREASURE = 30, MAX_DIVING_TIME = 1000 };

struct Treasure
{
    int depth, gold, time_cost;
};

// tables for dynamic programming
int  c[ MAX_DIVING_TIME + 1 ];
bool p[ MAX_TREASURE ][ MAX_DIVING_TIME + 1 ];

void solve_knapsack (int total_time, Treasure* trs, int num_trs)
{
    memset(c, 0, sizeof(c));
    memset(p, 0, sizeof(p));

    for (int i = num_trs - 1 ; i >= 0 ; --i)
    {
        for (int j = total_time; j >= trs[i].time_cost ; --j)
        {
            if ( c[j] < c[ j - trs[i].time_cost ] + trs[i].gold )
            {
                c[j] = c[ j - trs[i].time_cost ] + trs[i].gold;
                p[i][j] = true;
            }
        }
    }
}

void print_result (int total_time, Treasure* trs, int num_trs )
{
    std::ostringstream sout; // the output string

    int trs_count = 0;
    int total_gold = c[total_time];

    // count the total number of treasures
    int w = total_time;
    for (int i = 0; i < num_trs; ++i)
    {
        if ( p[i][w] )
        {
            sout << trs[i].depth << " " << trs[i].gold << "\n";
            w = w - trs[i].time_cost;

            trs_count++ ;
        }
    }

    printf("%d\n%d\n", total_gold, trs_count);
    printf("%s", sout.str().c_str());
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("990.in", "r", stdin);
#endif
    bool first_time = true;

    int total_time, speed;
    while (scanf("%d %d", &total_time, &speed) == 2)
    {
        if ( !first_time )
            putchar('\n');
        first_time = false;

        int num_trs;
        Treasure trs[MAX_TREASURE]; //treasure

        scanf("%d", &num_trs);
        for (int i = 0; i < num_trs; ++i)
            scanf("%d %d", &trs[i].depth, &trs[i].gold );

        for (int i = 0; i < num_trs; ++i)
            trs[i].time_cost = trs[i].depth * speed * 3;

        solve_knapsack(total_time, trs, num_trs);
        print_result( total_time, trs, num_trs );
    }
    return 0;
}

990.in

210 4
3
10 5
10 1
7 2

210 4
3
10 5
10 1
7 2

list-file.ps1

[array]$a = Get-ChildItem *.cpp -name
#[string]$s = $a -join " ^`n"
#Write-Host $s
#$s | Out-File list.txt

[string]$s = ""
foreach($f in $a) {
  $s += "<script src=`"https://gist.github.com/chchwy/e4343313d7ae99eb45ec80cad2f7d9f7.js?file=$f`"></script>"
  $s += "`n"
}
$s | Out-File list.txt

style.bat

AStyle.exe --style=allman --align-pointer=type -s4 --pad-oper --pad-comma --pad-header ^
	--keep-one-line-statements ^
	--convert-tabs ^
100.cpp ^
10018.cpp ^
10033.cpp ^
10035.cpp ^
10038.cpp ^
10050.cpp ^
10055.cpp ^
10071.cpp ^
10079.cpp ^
10082.cpp ^
101.cpp ^
10125.cpp ^
10137.cpp ^
10142.cpp ^
10154.cpp ^
10189.cpp ^
10196.cpp ^
102.cpp ^
10200.cpp ^
10267.cpp ^
103.cpp ^
10300.cpp ^
10301.cpp ^
10315.cpp ^
10394.cpp ^
104.cpp ^
10405.cpp ^
10499.cpp ^
105.cpp ^
10533.cpp ^
10591.cpp ^
106.cpp ^
10616.cpp ^
107.cpp ^
10751.cpp ^
10780.cpp ^
10783.cpp ^
108.cpp ^
109.cpp ^
10924.cpp ^
10929.cpp ^
110.cpp ^
11044.cpp ^
111.cpp ^
11172.cpp ^
11185.cpp ^
112.cpp ^
113.cpp ^
11388.cpp ^
114.cpp ^
11461.cpp ^
11462.cpp ^
115.cpp ^
116.cpp ^
136.cpp ^
146.cpp ^
147.cpp ^
151.cpp ^
160.cpp ^
184.cpp ^
191.cpp ^
193.cpp ^
270.cpp ^
272.cpp ^
294.cpp ^
343.cpp ^
352.cpp ^
355.cpp ^
357.cpp ^
369.cpp ^
371.cpp ^
382.cpp ^
389.cpp ^
400.cpp ^
401.cpp ^
406.cpp ^
414.cpp ^
431.cpp ^
455.cpp ^
458.cpp ^
476.cpp ^
482.cpp ^
485.cpp ^
488.cpp ^
490.cpp ^
492.cpp ^
494.cpp ^
516.cpp ^
548.cpp ^
562.cpp ^
579.cpp ^
583.cpp ^
587.cpp ^
591.cpp ^
594.cpp ^
624.cpp ^
657.cpp ^
674.cpp ^
706.cpp ^
897.cpp ^
900.cpp ^
990.cpp