My ACM Solved Problem List

Volumn I

100 - The 3n + 1 problem
101 - The Blocks Problem
102 - Ecological Bin Packing
103 - Stacking Boxes
104 - Arbitrage
105 - The Skyline Problem
106 - Fermat vs. Pythagoras
108 – Maximum Sum
109 – SCUD Buster
110 - Meta-Loopless Sorts

111 – History Grading
112 – Tree Summing
113 – Power of Cryptography
114 – Simulation Wizardry
115 – Climbing Trees
116 – Unidirectional TSP
117 - The Postal Worker Rings Once
118 - Mutant Flatworld Explorers
119 - Greedy Gift Givers
120 - Stacks of Flapjacks

121 - Pipe Fitters
122 – Trees on the level
123 – Searching Quickly
124 – Following Orders
125 – Numbering Paths
126 - The Errant Physicist
127 - "Accordian" Patience
128 - Software CRC
129 – Krypton Factor
130 – Roman Roulette

131 - The Psychic Poker Player
132 - Bumpy Objects
133 – The Dole Queue
134 - Loglan-A Logical Language
135 – No Rectangles
136 – Ugly Numbers
137 – Polygons
138 – Street Numbers

147 – Dollars

166 – Making Change

Volumn III

357 – Let Me Count The Ways

Volumn V

562 – Dividing Coins

Volumn VI

624 – CD

674 – Coin Change

Volumn IX

990 – Diving for Gold

list: 2010年看的戲劇

last update: 2010.10.31

港
＊＊＊＊＊	公主嫁到(2010)
＊＊＊＊＊	疑情別戀(2008)
＊＊＊	古靈精探B(2009)
台
＊＊	轉角遇到愛(2007)
韓
＊＊＊＊+	Air City(2007)
＊＊＊	Pasta
＊＊	拜託小姐
日
＊＊＊＊	四個謊言/四謊記(2008)

list: 2010年看的電影

last update: 2010.11.1

＊＊＊＊	Shoot ‘Em Up (2007)
＊＊＊	21 (2008)
＊＊	The Da Vinci Code (2006)
＊＊＊+	賭神3之少年賭神 (1996)
＊＊＊	雀聖2自摸天后 (2005)
＊＊	獨家試愛 (2006)
＊＊＊＊	Inception (2010)
Jul
＊＊＊＊	District 9 (2009)
＊＊	The Bounty Hunter (2010)
＊＊＊＊	72家租客 (2010)
＊＊＊＊	Couples Retreat (2009)
＊＊＊	Cloudy with a Chance of Meatballs (2009)
Jun
＊＊＊	Date Night (2010)
＊＊＊＊＊	Up in the Air (2009)
＊＊＊	重慶森林 (1994)
＊＊＊＊	下弦之月 (2004)
May
＊＊＊＊＋	Breakfast at Tiffany's (1961)
Mar
＊＊＊＊	螢火蟲之墓 (火垂るの墓) (1988)
＊＊＊＊	Alice in Wonderland (2010) (3D Version)
＊＊＊＊	Modern Times (1936)
＊＊+	The Lovely Bones (2009)
＊＊＊＊＋	Artificial Intelligence: AI (2001)
＊＊＊	Lilo & Stitch 2: Stitch  Has a Glitch (2005)
＊＊＊	Lilo & Stitch (2002)
＊＊＊	Monster Inc. (2001)
＊＊＋	老港正傳
Jan
＊＊＊＋	2012 (2009)
＊＊	(500) Days of Summer (2009)
＊＊	得閒飲茶 (2006)
＊＊＊	天水圍日與夜 (2008)

Regex Hero

http://regexhero.net/tester/

Great tool to play with and practice regular expression.

ACM: 674 – Coin Change

Another coin change problem, much the same as 357. I experimented replacing cin/cout by scanf/printf, and the runtime do reduced dramatically!

CODE

#include <iostream>

enum { MAX = 7489, COINS = 5 };

int main(){

    const int coin[] = {1, 5, 10, 25, 50};

    long long w[MAX+1] = {};

    w[0] = 1;

    for(int i=0; i<COINS; ++i)

        for(int j=coin[i]; j<=MAX; ++j)

            w[j] += w[j-coin[i]];

    int n;

    while( scanf("%d", &n) != EOF )

        printf("%d\n", w[n]);

    return 0;

}

ACM: 357 – Let Me Count The Ways

Straightforward DP coin change problem. To find the number of possible ways that make up certain amount of money.

My runtime is 0.012. Maybe the way to further reduce runtime is reducing times of i/o?

CODE

#include <iostream>

enum { MAX = 30000 };

int main(){

    const int coin[] = {1, 5, 10, 25, 50};

    long long w[MAX+1] = {};

    w[0] = 1;

    for(int i=0; i<5; ++i)

        for(int j=coin[i]; j<=MAX; ++j)

            w[j] += w[j-coin[i]];

    int n;

    while( scanf("%d", &n) != EOF )

        if( w[n] == 1 )

            printf("There is only 1 way to produce %d cents change.\n", n);

        else

            printf("There are %lld ways to produce %d cents change.\n", w[n], n);

    return 0;

}

ACM: 166 – Making Change

換零錢的問題，要使用有限量的錢幣去支付一個商品，要找出支付和找錢(假設商家錢幣為無限量)所使用的總錢幣數量為最小。我的做法是，先找出在每一個金額，商家找錢使用的最少錢幣數量。然後根據買家的錢幣組合，找出所有可以支付的金額所使用的最少錢幣數量。最後找出支付+找錢總使用最少的錢幣數量。

在計算支付的部分，似乎怪怪的，應該有更有效率的做法，但是還想不到怎麼改，繼續研究。

CODE

#include <iostream>

#include <climits>

using namespace std;

enum { COINS = 6, MAX_CHANGE = 10000 };

int main(){

    const int coin[] = {1, 2, 4, 10, 20, 40};

    int p, q, //price

        w[COINS], //wallet

        change[MAX_CHANGE+1]; //change

    int i, j, k, m, sum;

    change[0] = 0;

    for(i=1; i<=MAX_CHANGE; ++i)

        change[i] = INT_MAX;

    for(i=0; i<COINS; ++i)

        for(j=coin[i]; j<=MAX_CHANGE; j++)

            change[j] = min(change[j-coin[i]]+1, change[j]);

    while(1){

        sum = 0;

        for(i=0; i<COINS; ++i){

            scanf("%d", &w[i]);

            sum += w[i] * coin[i];

        }

        if( sum == 0 ) break;

        scanf("%d.%d", &p, &q);

        p = (p*100+q)/5;

        int* pay = (int*)malloc((sum+1) * sizeof(int));

        int* use = (int*)malloc((sum+1) * sizeof(int));

        if( pay == NULL || use == NULL ) exit(1);

        pay[0] = 0;

        for(i=1; i<=sum; ++i)

            pay[i] = INT_MAX;

        for(i=0; i<COINS; ++i){

            for(j=1; j<=coin[i]; ++j){

                m = w[i];

                for(k=j; k<=sum; k+=coin[i]){

                    if( pay[k] != INT_MAX ){

                        m = w[i];

                    }

                    else if( k < coin[i] ){ break; }

                    else if( m > 0 ){

                        pay[k] = pay[k-coin[i]] + 1;

                        --m;

                    }

                }//k

            }//j

            memset(use, 0, (sum+1) * sizeof(int));

            for(j=coin[i]; (j<=sum) && (use[j-coin[i]] < w[i]) ; ++j){

                if( (pay[j-coin[i]] != INT_MAX) && (pay[j-coin[i]]+1 <= pay[j]) ){

                    pay[j] = pay[j-coin[i]] + 1;

                    use[j] = use[j-coin[i]] + 1;

                }

            }

        }//i: coins

        int total = INT_MAX;

        for(i=p; i<=sum; ++i)

            if( pay[i] != INT_MAX )

                total = min(pay[i]+change[i-p], total);

        printf("%3d\n", total);

        free(pay);

        free(use);

    }

    return 0;

}

ACM: 147 - Dollars

也是一直想學的DP換零錢問題，很有趣。

NOTE

注意浮點數誤差的問題

REFERENCE

Coin Change

CODE

#include <iostream>

enum { MAX = 300 * 100 / 5, COINS = 11 };

int main(){

    const int coin[] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000}; //value*100/5

    long long r[MAX+1];

    int i, j;

    for(i=0; i<=MAX; ++i)

        r[i] = 1;

    for(i=1; i<COINS; ++i)

        for(j=coin[i]; j<=MAX; ++j)

            r[j] = r[j-coin[i]] + r[j];

    while( (scanf("%d.%d", &i, &j) != EOF) && (i+j != 0) )

        printf("%3d.%02d%17lld\n", i, j, r[(i*100+j)/5]);

    return 0;

}

ACM: 624 - CD

Straightforward 0/1 Knapsack problem. Tried malloc, memset, free in 2D array.

CODE

#include <iostream>

enum { TRACK = 30 };

int main(){

    int n, t, d[TRACK];

    int i, j;

    while( scanf("%d%d", &n, &t) != EOF ){

        for(i=0; i<t; ++i)

            scanf("%d", &d[i]);

        //malloc

        bool** pick = (bool**)malloc(t * sizeof(bool*));

        for(i=0; i<t; ++i)

            pick[i] = (bool*)malloc((n+1) * sizeof(bool));

        int* tape = (int*)malloc((n+1) * sizeof(int));

        if( pick == NULL || tape == NULL )

            exit(1);

        for(i=0; i<t; ++i)

            memset(pick[i], 0, (n+1)*sizeof(bool));

        memset(tape, 0, (n+1)*sizeof(int));

        for(i=t-1; i>=0; --i){

            for(j=n; j>=d[i]; --j){

                if( tape[j-d[i]]+d[i] > tape[j] ){

                    tape[j] = tape[j-d[i]] + d[i];

                    pick[i][j] = 1;

                }

            }//j

        }//i

        for(i=0, j=n; i<t; ++i){

            if( pick[i][j] ){

                printf("%d ", d[i]);

                j -= d[i];

            }

        }

        printf("sum:%d\n", tape[n]);

        //free

        for(i=0; i<t; ++i)

            free(pick[i]);

        free(pick);

        free(tape);

    }

    return 0;

}