ACM 10074 Take the Land

同ACM836。
1跟0要互轉。

/* ACM 10074 Take the Land
 * mythnc
 * 2012/04/04 17:16:52
 * run time: 0.012
 */
#include <stdio.h>
#include <string.h>

#define MAXN 100

void input(int (*)[]);
int findsubsum(int (*)[]);
int subsum(int *, int *, int);

int maxrow, maxcol;

int main(void)
{
    int matrix[MAXN][MAXN];

    while (scanf("%d %d", &maxrow, &maxcol) && maxrow != 0) {
        input(matrix);
        printf("%d\n", findsubsum(matrix));
    }

    return 0;
}

/* input: receive input data. */
void input(int (*matrix)[MAXN])
{
    int i, j, tmp;

    for (i = 0; i < maxrow; i++)
        for (j = 0; j < maxcol; j++) {
            scanf("%d", &tmp);
            /* exchange 0 and 1 */
            if (tmp == 1)
                matrix[i][j] = 0;
            else
                matrix[i][j] = 1;
        }
}

/* findsubsum: find sub sum and return it */
int findsubsum(int (*matrix)[MAXN])
{
    int max, sum, i, j;
    int line[MAXN];

    /* from row 1 to N, 2 to N, ... , calculate each
     * subsum */
    for (i = max = 0; i < maxrow; i++) {
        /* init line */
        memset(line, 0, sizeof(int) * maxcol);
        for (j = i; j < maxrow; j++) {
            sum = subsum(line, matrix[j], j - i + 1);
            if (max < sum)
                max = sum;
        }
    }

    return max;
}

/* subsum: use Kadane's algorithm to find the subsum */
int subsum(int *line, int *matrix, int rown)
{
    int i, sum, max;
    /* add each column to line */
    for (i = 0; i < maxcol; i++)
        line[i] += matrix[i];

    for (i = sum = max = 0; i < maxcol; i++) {
        if (line[i] != rown) {
            sum = 0;
            continue;
        }
        sum += line[i];
        if (sum > max)
            max = sum;
    }

    return max;
}

ACM 836 Largest Submatrix

Maximum Sum。同ACM108。
因為只有1跟0，所以n個row的和，最大值必為n。
只要判斷該field的值是否是n，
就能判斷Maximum Sum。

/* ACM 836 Largest Submatrix
 * mythnc
 * 2012/04/03 16:01:37   
 * run time: 0.004
 */
#include <stdio.h>
#include <string.h>

#define MAXN 25

int input(char (*)[]);
int findsubsum(char (*)[], int);
int subsum(int *, char *, int, int);
void ctoi(int *, char *, int);

int main(void)
{
    int n, i, len;
    char matrix[MAXN][MAXN + 1];

    scanf("%d", &n);
    /* eat '\n' */
    getchar();
    for (i = 0; i < n; i++) {
        if (i > 0)
            putchar('\n');
        /* eat blank line */
        getchar();
        len = input(matrix);
        printf("%d\n", findsubsum(matrix, len));
    }

    return 0;
}

/* input: receive input data.
 * return its len */
int input(char (*matrix)[MAXN])
{
    int len, i;

    scanf("%s", matrix[0]);
    len = strlen(matrix[0]);
    for (i = 1; i < len; i++)
        scanf("%s", matrix[i]);

    return len;
}

/* findsubsum: find sub sum and return it */
int findsubsum(char (*matrix)[MAXN], int len)
{
    int max, sum, i, j;
    int line[MAXN];

    /* from row 1 to N, 2 to N, ... , calculate each
     * subsum */
    for (i = max = 0; i < len; i++) {
        /* init line */
        memset(line, 0, sizeof(int) * len);
        for (j = i; j < len; j++) {
            sum = subsum(line, matrix[j], len, j - i + 1);
            if (max < sum)
                max = sum;
        }
    }

    return max;
}

/* subsum: use Kadane's algorithm to find the subsum */
int subsum(int *line, char *row, int len, int rown)
{
    int i, sum, max;

    /* add row to line */
    ctoi(line, row, len);

    for (i = sum = max = 0; i < len; i++) {
        if (line[i] != rown) {
            sum = 0;
            continue;
        }
        sum += line[i];
        if (sum > max)
            max = sum;
    }

    return max;
}

/* ctoi: transform char to int */
void ctoi(int *line, char *row, int len)
{
    int i;

    for (i = 0; i < len; i++)
        line[i] += row[i] - '0';
}

ACM 507 Jill Rides Again

maximum sum problem。
一樣用kadane去解。
不過不太一樣的是要注意sum == max的情況，
要找最大範圍的起始點 + 終點。

/* ACM 507 Jill Rides Again
 * mythnc
 * 2012/01/18 11:15:29   
 * run time: 0.136
 */
#include <stdio.h>

#define MAXS 20001

void input(void);
void kadane(void);
void output(int);

int list[MAXS];
int n, maxstart, maxend;

int main(void)
{
    int set, i;

    scanf("%d", &set);
    for (i = 1; i <= set; i++) {
        input();
        kadane();
        output(i);
    }

    return 0;
}

/* input: receive input data */
void input(void)
{
    int i;

    scanf("%d", &n);
    for (i = 1; i < n; i++)
        scanf("%d", &list[i]);
}

/* kadane: use kadane algorithm to find the maximum sum */
void kadane(void)
{
    int max, start, end;
    int sum;

    max = 0;
    maxstart = maxend = sum = 0;
    start = 1;
    for (end = 1; end < n; end++) {
        sum += list[end];
        if (sum > max) {
            max = sum;
            maxstart = start;
            maxend = end;
        }
        else if (sum == max && end - start > maxend - maxstart) {
            maxstart = start;
            maxend = end;
        }
        if (sum < 0) {
            sum = 0;
            start = end + 1;
        }
    }
}

/* output: out put result */
void output(int set)
{
    if (maxstart == 0)
        printf("Route %d has no nice parts\n", set);
    else
        printf("The nicest part of route %d is between stops %d and %d\n",
               set, maxstart, maxend + 1);
}

ACM 11137 Ingenuous Cubrency

DP。
同ACM674。

/* ACM 11137 Ingenuous Cubrency
 * mythnc
 * 2012/01/17 21:40:44   
 * run time: 0.032
 */
#include <stdio.h>

#define MAXN 10000
#define MAXC 21

int main(void)
{
    int coin[MAXC] = {1, 8, 27, 64, 125, 216,
                    343, 512, 729, 1000, 1331, 1728,
                    2197, 2744, 3375, 4096, 4913, 5832,
                    6859, 8000, 9261};
    long long dp[MAXN] = { 1 };
    int i, j, money;

    for (i = 0; i < MAXC; i++)
        for (j = coin[i]; j < MAXN; j++)
            dp[j] += dp[j - coin[i]];

    while (scanf("%d", &money) == 1)
        printf("%lld\n", dp[money]);

    return 0;
}

ACM 497 Strategic Defense Initiative

一樣是Longest Increasing Subsequence……
結果用ACM481的方法去解竟然WA，囧rz。
用正常O(n ^ 2)解就AC……大概是我方法哪裡不對吧，
然後ACM481剛剛好AC……無解！

/* ACM 497 Strategic Defense Initiative
 * mythnc
 * 2012/01/16 20:42:20   
 * run time: 0.016
 */
#include <stdio.h>

#define MAXN    100000
#define LINEMAX 50

void input(void);
void lis(void);

int n;
int seq[MAXN], len[MAXN], pre[MAXN];

int main(void)
{
    int set, i;

    scanf("%d", &set);
    getchar();
    getchar();
    for (i = 0; i < set; i++) {
        input();
        if (i > 0)
            putchar('\n');
        lis();
    }

    return 0;
}

/* input: receive input data */
void input(void)
{
    char line[LINEMAX];

    n = 0;
    while (fgets(line, LINEMAX, stdin) && line[0] != '\n')
        sscanf(line, "%d", &seq[n++]);
}

/* lis: find lis and output */
void lis(void)
{
    int i, j, maxi;
    int out[MAXN];
    /* init */
    for (i = 0; i < n; i++) {
        len[i] = 1;
        pre[i] = -1;
    }

    for (i = 0; i < n; i++)
        for (j = i + 1; j < n; j++)
            if (seq[j] > seq[i] && len[j] < len[i] + 1) {
                len[j] = len[i] + 1;
                pre[j] = i;
            }

    for (i = 1, maxi = 0; i < n; i++)
        if (len[i] > len[maxi])
            maxi = i;

    /* output */
    printf("Max hits: %d\n", len[maxi]);
    i = 0;
    while (1) {
        out[i++] = seq[maxi];
        if (pre[maxi] == -1)
            break;
        maxi = pre[maxi];
    }
    for (j = i - 1; j > -1; j--)
        printf("%d\n", out[j]);
}

ACM 481 What Goes Up

Longest Increasing Subsequence問題。
用正常的O(n ^ 2)的演算法去解竟然會TL，傻眼……
結果只好開始看別人是怎麼AC的。
結果AC一定要用O(nlogn)的演算法……
就開始看……我發現我看不懂 ToT。

反正就是找了一堆資料，然後寫法都很數學式，又是英文，
而且又沒範例 = =，只能說GG啊。

最後還是在這裡，
找到範例碼，真是揪甘心～

重點就是要了解Patience sorting的運作原理即可。
Patience sorting大概是這樣：
1.如果沒有pile，就做一個pile。
2.每次把x值與pile最上的值相比，若x值 < pile的top值，
就把x放到該pile上。
若無，就再做一個pile。
3.反覆，到沒有x值為此。

這樣講可能很複雜，直接舉實例說明：
-7 10 9 2 3 8 8 1。
一開始是-7，沒pile，所以給-7一個pile：
-7，
接著是10，10 > -7，所以make a new pile：
-7
10，
再來是9， 9 > -7，所以不能放在pile1，
但9 < 10，所以放在pile2上，
-7
10 9，
反覆此動作我們最後可以得到：
-7
10 9 2 1
3
8
（因為Patience sorting是針對撲克牌做sort，
所以有重複的數字，我們就不再處理第二次）
如此，我們得到4個pile。
也就是lis為4。
第1到第4個位置分別可以放-7、10 9 2 1、3、8。
注意，上面這個例子並不表示，所有lis為4的組合……
也就是每個數字其實是獨立的，不能放在一起看，
除非我們找到一組順序，使得此子序列的對應關係合於本來的序列。
好吧，其實我不是很懂Patience sorting……
總之pile數 = lis數就對了！
那這樣要怎麼找到一組lis呢？
現在我們已經知道，每個位置能放的值了，
所以按照題目要求，我們只要從最末的值開始往前找即可。
這部份就跟O(n ^ 2)的方法是一樣的。

接著談實作，實作非常之令我苦惱……
所謂懂還不一定寫得出程式碼，就是這回事，囧。
首先要做出一個pile，所以讓seq[0]為第一個pile，
然後我們可以發現，Patience sorting其實是一個遞增數列（這應該是重點）。
也就是說，每個pile最上面的值，排在一起，一定為遞增數列。
既然是遞增，那我們可以用binary search去做search的動作。
（因為已經sort，所以可以用bin search）
兩種情況：
(1)seq[x]的值，比最後一個pile 的top值還大，就增加一個pile。
因為我們已知所有pile的top為一遞增數列，
那如果seq[x] > 最後一個pile的top值，
勢必seq[x]，大於所有pile的tope值，
所以這時候就要增加一個pile。
(2)非(1)的情況，表示seq[x] <= 最後一個pile的top值。
這時候，seq[x]這個值，可能跟前面某個pile的top值一樣，
或是介於某兩個pile值之間的情況。
如果是前者，那我們找到seq[x] == pile top時，任務就結束了。
如果是後者，那我們會得到pile[i] top < seq[x] < pile[i + 1] top。
這時，需把pile[i + 1]的top換成seq[x]才行。
如此才符合Patience sorting的第二個定義。

所以我們可以得到一種資料結構：stack包含stack，
但是實作上不用這麼麻煩，只要用stack + 取代就好了。
其實更好的作法是再用一個空間，去紀錄每個seq[x]的在lis位置，
就是紀錄他在哪個pile啦！用空間換取時間！

這樣，我們已經知道了pile數（lis長度），
也紀錄了每個seq[x]所在lis長度的位置，
那麼這題就有解了！
從最後一個seq[x]往前到seq[0]，去尋找符合lis長度的值，
找到該值後記錄下來，再把lis長度 - 1，同樣做找值的動作，
一直找到第一個lis為止。
如此，就是答案了。

另外為什麼是O(n * log(n))呢，
因為binary search是O(log(n))，
而有n個值，最慘的情況就是每個值都去做binary search，
那就會得到O(n * log(n))。

再一次感謝DJWS~
有興趣可以再看一些參考資料
wiki跟algorithmist都有。

/* ACM 481 What Goes Up
 * mythnc
 * 2012/01/16 09:58:36   
 * run time: 0.044
 */
#include <stdio.h>

#define MAXN 100000

void lis(int);
void binsearch(int, int, int);

int n;
int seq[MAXN], pos[MAXN], v[MAXN];

int main(void)
{

    n = 0;
    while (scanf("%d", &seq[n]) == 1)
        n++;

    lis(n);

    return 0;
}

/* lis: return the last max len position */
void lis(int n)
{
    int len, i, j;
    int out[MAXN];

    len = 0;
    v[len++] = seq[0];
    pos[0] = 0;

    for (i = 1; i < n; i++) {
        if (seq[i] > v[len - 1]) {
            v[len] = seq[i];
            pos[i] = len++;
        }
        else
            binsearch(0, len, i);
    }
    /* output */
    printf("%d\n-\n", len);
    for (i = n - 1, j = len - 1; i > -1 && j > -1; i--)
        if (pos[i] == j) {
            out[j] = seq[i];
            j--;
        }
    for (i = 0; i < len; i++)
        printf("%d\n", out[i]);
}

void binsearch(int begin, int end, int index)
{
    int mid;

    while (begin <= end) {
        mid = (begin + end) / 2;
        if (v[mid] == seq[index]) {
            pos[index] = mid;
            return;
        }
        else if (v[mid] > seq[index])
            end = mid - 1;
        else
            begin = mid + 1;
    }
    
    mid = (begin + end) / 2;
    if (mid == 0 && index == 1) {
        v[0] = seq[index];
        pos[index] = 0;
    }
    else {
        v[mid + 1] = seq[index];
        pos[index] = mid + 1;
    }
}

ACM 231 Testing the CATCHER

Longest Increasing Subsequence反過來做！
變成Longest Decreasing Subsequence！

/* ACM 231 Testing the CATCHER
 * mythnc
 * 2012/01/15 21:19:58   
 * run time: 0.004
 */
#include <stdio.h>

int input(int *);
int lds(int *, int);

#define MAXM 10000

int main(void)
{
    int set, data;
    int catcher[MAXM];

    set = 0;
    while (scanf("%d", &data) && data != -1) {
        catcher[0] = data;
        if (set > 0)
            putchar('\n');
        printf("Test #%d:\n", ++set);
        printf("  maximum possible interceptions: %d\n",
               lds(catcher, input(catcher)));
    }

    return 0;
}

/* input: receive input data
 * and return the number of missile */
int input(int *catcher)
{
    int i;

    i = 1;
    while (scanf("%d", &catcher[i]) && catcher[i] != -1)
        i++;

    return i;
}

/* lds: return the longest decrement subsequence length */
int lds(int *catcher, int n)
{
    int len[MAXM];
    int i, j, maxlen;

    for (i = 0; i < n; i++)
        len[i] = 1;

    for (i = 0; i < n; i++)
        for (j = i + 1; j < n; j++)
            if (catcher[j] < catcher[i] && len[j] < len[i] + 1)
                len[j] = len[i] + 1;
                
    for (i = maxlen = 0; i < n; i++)
        if (len[i] > maxlen)
            maxlen = len[i];

    return maxlen;
}

ACM 103 Stacking Boxes

其實是一個Longest Increasing Subsequence……
相關的教學可以看這裡
之前想說應該是做3個sort，
先對維度做sort，接著對每個維度的第一個維度sort，
接著把所有的box依照sort就有解。
後來想想好像不對……

所以第三步驟其實不是作sort，是做LIS。
把整個題目想成是一個box lis就很簡單了。
單一個box由n個維度構成，所以box的大小由n個維度所決定。
而維度內先排列是必要的（因為要跟其他box比大小）
而題目要作最多的「大包小」的動作。
所以先把每個box依照大小順序做排列也是必要的。
如此小的在前面，大的在後面，才可以找出最多的「大包小」。

/* ACM 103 Stacking Boxes
 * mythnc
 * 2012/01/15 14:42:45   
 * run time: 0.008
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXBOX 30
#define MAXD   10

typedef struct box {
    int num;
    int dimen[MAXD];
} Box;

void init(int, int);
int cmpd(const void *, const void *);
int cmpb(const void *, const void *);
int lis(int, int);
void output(int);

Box b[MAXBOX];
int len[MAXBOX], pre[MAXBOX];

int main(void)
{
    int n, d;

    while (scanf("%d %d", &n, &d) == 2) {
        init(n, d);
        output(lis(n, d));
    }

    return 0;
}

/* init: receive input data, initialize b content,
 * and sort data */
void init(int n, int d)
{
    int i, j;

    for (i = 0; i < n; i++) {
        b[i].num = i + 1;
        len[i] = 1;
        pre[i] = -1;
        for (j = 0; j < d; j++)
            scanf("%d", &b[i].dimen[j]);
        qsort(b[i].dimen, d, sizeof(int), cmpd);
    }
    qsort(b, n, sizeof(Box), cmpb);
}

/* cmpd: sort dimension for qsort() */
int cmpd(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

/* cmpb: sort dimen[0] for qsort() */
int cmpb(const void *a, const void *b)
{
    return ((Box *)a)->dimen[0] - ((Box *)b)->dimen[0];
}

/* lis: find longest increasing subsequence.
 * the unit is "box"
 * return its pos */
int lis(int n, int d)
{
    int i, j, k, maxi;

    for (i = 0; i < n; i++)
        for (j = i + 1; j < n; j++) {
            for (k = 0; k < d && b[j].dimen[k] > b[i].dimen[k]; k++)
                ;
            if (k == d && len[i] + 1 > len[j]) {
                len[j] = len[i] + 1;
                pre[j] = i;
            }
        }

    for (i = 1, maxi = 0; i < n; i++)
        if (len[i] > len[maxi])
            maxi = i;

    return maxi;
}

/* output: output lis len and seq */
void output(int i)
{
    int num;
    int inc[MAXBOX];
    /* output max lis len */
    printf("%d\n", len[i]);

    num = 0;
    while (1) {
        inc[num++] = b[i].num;
        if (pre[i] == -1)
            break;
        i = pre[i];
    }
    /* out lis seq */
    printf("%d", inc[--num]);
    for (i = num - 1; i > -1; i--)
        printf(" %d", inc[i]);
    putchar('\n');
}

ACM 10608 Friends

Union-Find Disjoint Sets。
同ACM10583。
這次用weightedunion + collapsingfind去解。

原本直接把第一行吃掉不處理，
結果一直WA……
後來吃掉第一行並做處理後就AC了 =.=。
這測資有問題……可能是m後面不只m行……
心機啊！

/* ACM 10608 Friends
 * mythnc
 * 2012/01/14 23:12:34   
 * run time: 0.076
 */
#include <stdio.h>

#define MAXNODE 30001

void init(int);
void input(int);
int collapsingfind(int);
void weightedunion(int, int);
int count(int);

int node[MAXNODE];

int main(void)
{
    int n, m, set;

    scanf("%d", &set);
    while(set--) {
        scanf("%d %d", &n, &m);
        init(n);
        input(m);
        printf("%d\n", count(n));
    }

    return 0;
}

/* init: initialize each node to different sets */
void init(int n)
{
    int i;

    for (i = 1; i <= n; i++)
        node[i] = -1;
}

void input(int n)
{
    int i, v1, v2;

    for (i = 0; i < n; i++) {
        scanf("%d %d", &v1, &v2);
        weightedunion(collapsingfind(v1), collapsingfind(v2));
    }
}

/* collapsingfind: find root first,
 * then use collapsing rule to collapse all nodes
 * form v to root. return the set of node v */
int collapsingfind(int v)
{
    int root, trail, tmp;

    for (root = v; node[root] >= 0; root = node[root])
        ;
    for (trail = v; trail != root; trail = node[trail]) {
        tmp = trail;
        node[tmp] = root;
    }

    return root;
}

/* weightedunoin: union s1 and s2 */
void weightedunion(int s1, int s2)
{
    if (s1 == s2)
        return;

    if (s1 <= s2) {
        node[s1] += node[s2];
        node[s2] = s1;
    }
    else {
        node[s2] += node[s1];
        node[s1] = s2;
    }
}

/* count: return the max nodes set */
int count(int n)
{
    int min, i;

    for (i = 1, min = -1; i <= n; i++)
        if (node[i] < min)
            min = node[i];

    return -min;
}

ACM 10583 Ubiquitous Religions

Union-Find Disjoint Sets。
還是一樣做weighted union。

/* ACM 10583 Ubiquitous Religions
 * mythnc
 * 2012/01/14 22:48:07   
 * run time: 0.2
 */
#include <stdio.h>

#define MAXNODE 50001

void init(int);
void input(int);
int find(int);
void weightedunion(int, int);
void output(int *, int);
int count(int);

int node[MAXNODE];

int main(void)
{
    int n, m, set;

    set = 0;
    while (scanf("%d %d", &n, &m) && n != 0) {
        init(n);
        input(m);
        output(&set, n);
    }

    return 0;
}

/* init: initialize each node to different sets */
void init(int n)
{
    int i;

    for (i = 1; i <= n; i++)
        node[i] = -1;
}

void input(int n)
{
    int i, v1, v2;

    for (i = 0; i < n; i++) {
        scanf("%d %d", &v1, &v2);
        weightedunion(find(v1), find(v2));
    }
}

/* find: return the set of node v */
int find(int v)
{
    for (; node[v] >= 0; v = node[v])
        ;

    return v;
}

/* weightedunoin: union s1 and s2 */
void weightedunion(int s1, int s2)
{
    if (s1 == s2)
        return;

    if (s1 <= s2) {
        node[s1] += node[s2];
        node[s2] = s1;
    }
    else {
        node[s2] += node[s1];
        node[s1] = s2;
    }
}

/* output: output result */
void output(int *set, int n)
{
    printf("Case %d: %d\n", ++*set, count(n));
}

/* count: return the number of different sets */
int count(int n)
{
    int sum, i;

    for (i = 1, sum = 0; i <= n; i++)
        if (node[i] < 0)
            sum++;

    return sum;
}

ACM 793 Network Connections

一樣是Union-Find Disjoint Sets。
這次用weightedunion實作。

/* ACM 793 Network Connections
 * mythnc
 * 2012/01/14 12:41:37   
 * run time: 0.072
 */
#include <stdio.h>

#define MAXNODE 10001
#define LINEMAX 100

typedef enum {FALSE = 0, TRUE} bool;

void init(int *, int);
int find(int, int *);
void weightedunion(int, int, int *);

int main(void)
{
    int node[MAXNODE];
    bool set;
    int n, v1, v2, yes, no;
    char line[LINEMAX];

    scanf("%*d");
    getchar(); /* eat '\n' */
    getchar(); /* eat blank line */
    set = FALSE;
    while (fgets(line, LINEMAX, stdin))
        switch (line[0]) {
            /* compare */
            case 'q':
                sscanf(line, "%*c %d %d", &v1, &v2);
                if (find(v1, node) == find(v2, node))
                    yes++;
                else
                    no++;
                break;
            /* add */
            case 'c':
                sscanf(line, "%*c %d %d", &v1, &v2);
                weightedunion(find(v1, node), find(v2, node), node);
                break;
            /* output */
            case '\n':
                if (set)
                    putchar('\n');
                printf("%d,%d\n", yes, no);
                set = TRUE;
                break;
            default:
                sscanf(line, "%d", &n);
                init(node, n);
                yes = no = 0;
        }
    /* output last data set */
    if (set)
        putchar('\n');
    printf("%d,%d\n", yes, no);

    return 0;
}

/* init: init each node to disjoint set */
void init(int *node, int n)
{
    int i;

    for (i = 1; i <= n; i++)
        node[i] = -1;
}

/* find: find the set of node v */
int find(int v, int *node)
{
    for (; node[v] >= 0; v = node[v])
        ;

    return v;
}

/* weightedunoin: do i and j set union to one set */
void weightedunion(int i, int j, int *node)
{
    if (i == j)
        return;

    if (i <= j) {
        node[i] += node[j];
        node[j] = i;
    }
    else {
        node[j] += node[i];
        node[i] = j;
    }
}

ACM 459 Graph Connectivity

Union-Find Disjoint Sets標準題！

char轉int並做map，
接著find set再做union即可

/* ACM 459 Graph Connectivity
 * mythnc
 * 2012/01/13 23:34:04   
 * run time: 0.020
 */
#include <stdio.h>

#define MAXLETTER 26
#define LINEMAX   4  /* 2 + '\n' + '\0' */

void init(int *, int);
int find(int *, int);
void unionsub(int, int, int *);
int count(int *, int);

int main(void)
{
    int i, set, n;
    int node[MAXLETTER];
    char c;
    char token[LINEMAX];

    scanf("%d", &set);
    getchar(); /* eat '\n' */
    scanf("%*c"); /* eat blank line */
    for (i = 0; i < set; i++) {
        scanf("%c", &c);
        getchar();
        n = c - 'A' + 1;
        init(node, n);
        while (fgets(token, LINEMAX, stdin) && token[0] != '\n')
            unionsub(find(node, token[0] - 'A'), find(node, token[1] - 'A'), node);
        /* ouput */
        if (i > 0)
            putchar('\n');
        printf("%d\n", count(node, n));
    }

    return 0;
}

/* init: initialize each node to -1 */
void init(int *node, int n)
{
    int i;

    for (i = 0; i < n; i++)
        node[i] = -1;
}

/* find: find root of node x */
int find(int *node, int x)
{
    for (; node[x] != -1; x = node[x])
        ;
    return x;
}

/* unionsub: union i and j two sets to one set */
void unionsub(int i, int j, int *node)
{
    if (i != j)
        node[i] = j;
}

/* count: return the number of subgraph */
int count(int *node, int n)
{
    int sum, i;

    for (i = sum = 0; i < n; i++)
        if (node[i] < 0)
            sum++;

    return sum;
}

ACM 291 The House Of Santa Claus

一筆劃問題。
相對於以點(vertex)為準的dfs，做以線(edge)為準的dfs即可。

不過問題就來了，如何表示edge是否走訪呢？
我的作法是做一個visited[MAXEDGE]，
接著在graph的struct中增加一筆pos資料，
表示edge所在visited的位置。
從vertex 1開始走訪，
每次都判斷是否還有edge可以走訪，
若有就繼續走，走到edge == 9即可。
（共8個點，所以走到第九次就要output）

話說關於graph的問題我都用adjancency list去做，
從來沒用過adjancency martix，在這裡，
看到人家用adjancency martix的解法……真是為之驚嘆！
看來我殺雞用牛刀，開太空梭買菜了 -_-。

所以其實也可以做以點為準的dfs，
但是要紀錄的是edge，走訪到第九層就做output + return即可。
用一個二維陣列做graph，另一個二維陣列做edge紀錄！
偉哉adjancency martix！

所以重點其實是紀錄點或是紀錄線嘛……

/* ACM 291 The House Of Santa Claus
 * mythnc
 * 2012/01/13 18:53:08   
 * run time: 0.004
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXEDGE 8
#define MAXNODE 6 /* Node 0~5 */

typedef struct node {
    /* pos: edge position */
    int pos, node;
    struct node *next;
} Node;

typedef enum {FALSE = 0, TRUE} bool;

void init(int, int, int);
void backtrack(int, int);
void freeg(void);

Node *g[MAXNODE] = {NULL};
/* record edge is visited or not */
bool visited[MAXEDGE];
char output[MAXEDGE + 1];

int main(void)
{
    int i;

    init(1, 2, 0);
    init(2, 1, 0);
    init(1, 3, 1);
    init(3, 1, 1);
    init(1, 5, 2);
    init(5, 1, 2);
    init(2, 3, 3);
    init(3, 2, 3);
    init(2, 5, 4);
    init(5, 2, 4);
    init(3, 4, 5);
    init(4, 3, 5);
    init(3, 5, 6);
    init(5, 3, 6);
    init(4, 5, 7);
    init(5, 4, 7);

    output[0] = 1 + '0';
    backtrack(1, 1);
    freeg();

    return 0;
}

/* init: initialize graph */
void init(int v1, int v2, int pos)
{
    Node *pt, *tmp;

    tmp = (Node *)malloc(sizeof(Node));
    tmp->next = NULL;
    tmp->node = v2;
    tmp->pos = pos;

    if (g[v1] == NULL) {
        g[v1] = tmp;
        return;
    }
    pt = g[v1];
    while (pt->next != NULL)
        pt = pt->next;
    pt->next = tmp;
}

/* backtrack: use backtracking method to output answer */
void backtrack(int index, int node)
{
    Node *pt;
    int pos;

    if (index == MAXEDGE + 1) {
        output[index] = '\0';
        printf("%s\n", output);
        return;
    }

    for (pt = g[node]; pt; pt = pt->next) {
        pos = pt->pos;
        node = pt->node;
        if (!visited[pos]) {
            visited[pos] = TRUE;
            output[index] = node + '0';
            backtrack(index + 1, node);
            visited[pos] = FALSE;
        }
    }
}

/* freeg: free all graph node */
void freeg(void)
{
    Node *pt, *tmp;
    int i;

    for (i = 0; i < MAXNODE; i++) {
        pt = g[i];
        while (pt != NULL) {
            tmp = pt;
            pt = pt->next;
            free(tmp);
        }
    }
}

ACM 336 A Node Too Far

BFS或DFS。 話說用BFS沒有實際想像的好……
走訪次數還要另外紀錄
所以用DFS應該也無不可吧？
不知道有沒有更好的方法？

第一次莫名其妙的RE。
也不知道是哪裡有問題……
只好防呆一下。
(1)假設input給的兩點為同一點 -> edge to self node。
這時候不做update()，只做addg()。
(2)假設給的node跟ttl，其中node不為graph上的任一點，當然未走訪任一點。
所以不做走訪，直接回傳node數。
防呆之後，再上傳一次就莫名其妙AC了。
可能(1)跟(2)都要防呆一下就ok。

第一次用union，不知效果如何。
其實都是int，但是意義不太一樣。
一個是pointer of array的node，一個是array連出去的linked list node。
在array的field表示該數字，
linked list上的field表示該數字所在的位置。
原本想在linked list上也存該數字，
但是數字又要轉成位置，
所以就直接存位置，省去一次轉換。

/* ACM 336 A Node Too Far
 * mythnc
 * 2012/01/13 13:10:30   
 * run time: 0.052
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXNODE 30

/* save num in array node, but save pos in linked node */
typedef union name {
    int num, pos;
} u;

typedef struct node {
    u field;
    /* times: the ttl times */
    int times;
    struct node *next;
} Node;

typedef enum {FALSE = 0, TRUE} bool;

void input(int);
int search(int);
int addg(int);
void update(int, int);
int bfs(int, int);
void addq(int);
int deleteq(void);
void freeg(void);

Node graph[MAXNODE];
int numnode, front, end;
int queue[MAXNODE];
bool visited[MAXNODE];

int main(void)
{
    int edge, v, ttl, set, sum;

    set = 0;
    while (scanf("%d", &edge) && edge != 0) {
        input(edge);
        while (scanf("%d %d", &v, &ttl) && !(v == 0 && ttl == 0)) {
            sum = bfs(search(v), ttl);
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",
                   ++set, sum, v, ttl);
        }
        freeg();
    }

    return 0;
}

/* input: receive edge and initialize graph */
void input(int n)
{
    int i, v1, v2, pos1, pos2;

    for (i = numnode = 0; i < n; i++) {
        scanf("%d %d", &v1, &v2);
        pos1 = search(v1);
        if (pos1 == -1)
            pos1 = addg(v1);
        pos2 = search(v2);
        if (pos2 == -1)
            pos2 = addg(v2);
        if (pos1 != pos2) {
            update(pos1, pos2);
            update(pos2, pos1);
        }
    }
}

/* search: find v in graph.
 * if find return its position
 * else return -1 */
int search(int v)
{
    int i;

    for (i = 0; i < numnode; i++)
        if (graph[i].field.num == v)     
            return i;

    return -1;
}

/* addg: add v in graph and
 * return the postion of v */
int addg(int v)
{
    graph[numnode].field.num = v;
    graph[numnode].next = NULL;

    return numnode++;
}

/* update: update the edges of pos1 and pos2 */
void update(int pos1, int pos2)
{
    Node *pt, *tmp;

    tmp = (Node *)malloc(sizeof(Node));
    tmp->field.pos = pos2;
    tmp->next = NULL;

    pt = graph[pos1].next;
    if (pt == NULL) {
        graph[pos1].next = tmp;
        return;
    }
    /* find last link node */
    while (pt->next != NULL)
        pt = pt->next;
    pt->next = tmp;
}

/* bfs: do bfs. the times of bfs has to equal to ttl
 * return unvisited node number */
int bfs(int pos, int ttl)
{
    int times, sum;
    Node *pt;
    sum = numnode;
    /* no such node */
    if (pos == -1)
        return sum;
    /* init visited array, queue tag and graph[pos] times */
    memset(visited, FALSE, MAXNODE * sizeof(int));
    front = end = graph[pos].times = 0;

    visited[pos] = TRUE;
    sum--;
    if (graph[pos].times == ttl)
        return sum;

    addq(pos);
    while (front != end) {
        pos = deleteq();
        for (times = graph[pos].times + 1, pt = graph[pos].next; pt; pt = pt->next) {
            pos = pt->field.pos;
            if (!visited[pos]) {
                visited[pos] = TRUE;
                sum--;
                graph[pos].times = times;
                if (times < ttl)
                    addq(pos);
            }
        }
    }

    return sum;
}

/* addq: add the graph[pos] and its adjacency node
 * to queue */
void addq(int pos)
{
    queue[end++] = pos;
    end %= MAXNODE;
}

/* deleteq: delete the 1st element in queue.
 * and return the element */
int deleteq(void)
{
    int pos;

    pos = queue[front++];
    front %= MAXNODE;

    return pos;
}

/* freeg: free graph node */
void freeg(void)
{
    Node *pt, *tmp;
    int i;

    for (i = 0; i < numnode; i++) {
        pt = graph[i].next;
        while (pt != NULL) {
            tmp = pt;
            pt = pt->next;
            free(tmp);
        }
    }
}

ACM 727 Equation

infix轉postfix。

讓我想到當年的作業了……
雖然當時要寫判斷合法、中序轉後續跟算值。
不過括號問題還傻傻的暴力解，兩個禮拜才把東西生出來，真是寫到快起肖。
用stack不就輕鬆多了嗎 -.-

結果現在1hr就完成中序轉後序，囧。

operand直接output，
operator要判斷優先度。
當吃進來的operator優先度比stack[top]優先度高，
就直接push；
低或相等的話，pop到stack[top]比operator高或stack為空為止。
所以(最高，直接丟到stack。
/、*次高，若top是*、/就要先pop，再push。
+、-最低，遇到其他+、-、*、/都要pop，再push。
遇到)要無條件pop到(為止。

(算是特例，吃進來時最高，但是在top時最低。
所以+、-、*、/遇到top為(時，就可以直接push。

最後當吃進來的token為'\0'時，pop到stack為空為止即可。
最後就是output格式問題。

/* ACM 727 Equation
 * mythnc
 * 2012/01/13 09:44:34
 * run time: 0.136
 */
#include <stdio.h>
#include <string.h>

#define LINEMAX  10
#define MAXSTACK 50

void postfix(void);
void pop(void);
void push(char *);

char stack[LINEMAX][MAXSTACK];
int count;

int main(void)
{
    scanf("%*d");
    getchar();
    getchar();
    postfix();

    return 0;
}

/* postfix: infix to postfix */
void postfix(void)
{
    char line[LINEMAX];

    count = 0;
    while (fgets(line, LINEMAX, stdin)) {
        line[strlen(line) - 1] = '\0';
        /* operator */
        if (line[0] == '+' || line[0] == '-' && strlen(line) == 1) {
            while (count > 0 && stack[count - 1][0] != '(')
                pop();
            push(line);
        }
        else if (line[0] == '*' || line[0] == '/') {
            while (count > 0 && stack[count - 1][0] != '('
                   && stack[count - 1][0] != '+' && stack[count - 1][0] != '-')
                pop();
            push(line);
        }
        else if (line[0] == '(')
            push(line);
        else if (line[0] == ')') {
            while (stack[count - 1][0] != '(')
                pop();
            count--;
        }
        /* terminal condition */
        else if (line[0] == '\0') {
            while (count != 0)
                pop();
            printf("\n\n");
        }
        /* operand */
        else
            printf("%s", line);
    }
    while (count != 0)
        pop();
    putchar('\n');
}

/* pop: print out the top element */
void pop(void)
{
    printf("%s", stack[--count]);
}

/* push: push line to stack */
void push(char *line)
{
    strcpy(stack[count++], line);
}

ACM 514 Rails

又是一題腦殘題……
題目給的output最後的Yes下面空行，
但是要我們上傳的output最後要有空行。
=.=，真是有夠機車。

用stack就可以解，其實不用stack也可以解，懶得想了……
被stupid output搞得好煩……

/* ACM 514 Rails
 * mythnc
 * 2012/01/12 21:22:57   
 * run time: 0.076
 */
#include <stdio.h>

#define MAX 1000

typedef enum {FALSE = 0, TRUE} bool;

void init(int *, int);
bool input(int *, int);
bool simulate(int *, int *, int);
void push(int);
int pop(void);
int top(void);

int stack[MAX];
int count;

int main(void)
{
    int n;
    int list[MAX], cmp[MAX];

    while (scanf("%d", &n) && n != 0) {
        init(list, n);
        while (input(cmp, n))
            if (simulate(list, cmp, n))
                printf("Yes\n");
            else
                printf("No\n");
        putchar('\n');
    }

    return 0;
}

/* init: initialize list */
void init(int *list, int n)
{
    int i;

    for (i = 0; i < n; i++)
        list[i] = i + 1;
}

/* input: receive input data */
bool input(int *cmp, int n)
{
    int i;

    for (i = 0; i < n; i++) {
        scanf("%d", &cmp[i]);
        if (cmp[i] == 0)
            return FALSE;
    }

    return TRUE;
}

/* simulate: simulate coaches state */
bool simulate(int *list, int *cmp, int n)
{
    int i, j;
    
    for (i = j = count = 0; i < n; i++) {
        if (j < n && list[j] == cmp[i])
            j++;
        else if (count != 0 && top() == cmp[i])
            pop();
        else if (j < n && list[j] != cmp[i]) {
            while (j < n && cmp[i] != list[j])
                push(list[j++]);
            if (j == n || list[j] != cmp[i])
                return FALSE;
            j++;
        }
        else
            return FALSE;
    }

    return TRUE;
}

/* push: push x in top */
void push(int x)
{
    stack[count++] = x;
}

/* pop: pop the top value */
int pop(void)
{
    return stack[--count];
}

/* top: return top value */
int top(void)
{
    return stack[count - 1];
}

ACM 127 "Accordian" Patience

stack。
其實可以使用在單一空間上表示多個stack的方式，
不過這樣要移來移去，好累啊……
都給每個pile一個stack不就很方便嗎！

pile用linked list實作，
(本來想用array，但是每次empty就要copy，超麻煩）
每個pile各有一個stack。
從第一個pile到最後一個pile。
每次都先-3，再-1。
每次減完要判斷是否在pile中，
若在pile中要檢查是否match，
若match，就做pop跟push。
pop完要判斷該pile是否empty，
若empty就移出linked list。
之後移到push的pile上繼續做-3、-1的動作。
若-3與-1皆沒match，那就移到下一個pile繼續-3、-1。

一次就AC，超爽的～

/* ACM 127 "Accordian" Patience
 * mythnc
 * 2012/01/12 17:02:02   
 * run time: 0.296
 */
#include <stdio.h>
#include <string.h>

#define MAX     52
#define MAXCHAR 3

typedef struct pile {
    char card[MAX][MAXCHAR];
    int count;
    struct pile *next, *pre;
} Pile;

typedef enum {FALSE = 0, TRUE} bool;

void input(Pile *);
int simulate(Pile *);
bool match(Pile *, Pile *);
void push(Pile *, char *);
void pop(Pile *, char *);
bool empty(Pile *);
void relink(Pile *);
void output(Pile *, int);

int main(void)
{
    Pile p[MAX];
    int n;

    while (scanf("%s", p[0].card[0]) && p[0].card[0][0] != '#') {
        input(p);
        n = simulate(p);
        output(p, n);
    }

    return 0;
}

/* input: receive input data and initialize */
void input(Pile *p)
{
    int i;

    p[0].count = 1;
    p[0].pre = NULL;
    p[0].next = &p[1];
    for (i = 1; i < MAX; i++) {
        scanf("%s", p[i].card[0]);
        p[i].count = 1;
        p[i].pre = &p[i - 1];
        if (i != MAX - 1)
            p[i].next = &p[i + 1];
        else
            p[i].next = NULL;
    }
}

/* simulate: simulate Accordian */
int simulate(Pile *head)
{
    int n, i;
    Pile *pt, *cmp;
    char s[MAXCHAR];

    n = MAX;
    for (pt = head; pt;) {
        /* 3rd pile to the left */
        for (i = 1, cmp = pt->pre; cmp && i < 3; cmp = cmp->pre, i++)
            ;
        if (cmp && match(pt, cmp)) {
            pop(pt, s);
            push(cmp, s);
            if (empty(pt)) {
                relink(pt);
                n--;
            }
            pt = cmp;
            continue;
        }
        /* neighbour on the left */
        cmp = pt->pre;
        if (cmp && match(pt, cmp)) {
            pop(pt, s);
            push(cmp, s);
            if (empty(pt)) {
                relink(pt);
                n--;
            }
            pt = cmp;
            continue;
        }
        pt = pt->next;
    }

    return n;
}

/* match: match condition */
bool match(Pile *p, Pile *q)
{
    return q->card[q->count - 1][0] == p->card[p->count - 1][0]
        || q->card[q->count - 1][1] == p->card[p->count - 1][1];
}

/* push: put s in top of p */
void push(Pile *p, char *s)
{
    strcpy(p->card[p->count++], s);
}

/* pop: pop out the top card */
void pop(Pile *p, char *s)
{
    strcpy(s, p->card[--p->count]);
}

/* empty: return TRUE if stack is empty
 * else return FALSE */
bool empty(Pile *p)
{
    return p->count == 0;
}

/* relink: rearrange linked list */
void relink(Pile *p)
{
    if (p->pre)
        p->pre->next = p->next;
    if (p->next)
        p->next->pre = p->pre;
}

/* output: output result */
void output(Pile *p, int n)
{
    if (n == 1) {
        printf("1 pile remaining: 52\n");
        return;
    }

    printf("%d piles remaining:", n);
    for (; p; p = p->next)
        printf(" %d", p->count);
    putchar('\n');
}

ACM 11462 Age Sort

sort it!

/* ACM 11462 Age Sort
 * mythnc
 * 2012/01/12 11:17:32   
 * run time: 0.856
 */
#include <stdio.h>
#include <stdlib.h>

void input(int *, int);
int cmp(const void *, const void *);
void output(int *, int);

int main(void)
{
    int n;
    int *list;

    while (scanf("%d", &n) && n != 0) {
        list = (int *)malloc(sizeof(int) * n);
        input(list, n);
        qsort(list, n, sizeof(int), cmp);
        output(list, n);
        free(list);
    }
    return 0;
}

/* input: receive input data */
void input(int *list, int n)
{
    int i;

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

/* cmp: for qsort() */
int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

/* output: output result */
void output(int *list, int n)
{
    int i;

    printf("%d", list[0]);
    for (i = 1; i < n; i++)
        printf(" %d", list[i]);
    putchar('\n');
}

ACM 10810 Ultra-QuickSort

同ACM10327
做stable sort，計算swap次數。
最大次數為maxn * (maxn - 1) / 2。
所以用long long。

/* ACM 10810 Ultra-QuickSort
 * mythnc
 * 2012/01/12 10:43:46   
 * run time: 0.196
 */
#include <stdio.h>
#include <stdlib.h>

void input(int *, int);
long long merge(int *, int *, int, int);

int main(void)
{
    int n;
    int *ary, *tmp;

    while (scanf("%d", &n) && n != 0) {
        ary = (int *)malloc(sizeof(int) * n);
        tmp = (int *)malloc(sizeof(int) * n);
        input(ary, n);
        printf("%lld\n", merge(ary, tmp, 0, n));
        free(ary);
        free(tmp);
    }

    return 0;
}

/* input: receive input data */
void input(int *ary, int n)
{
    int i;

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

/* merge: merge sort */
long long merge(int *ary, int *tmp, int head, int tail)
{
    int half, i, j, k;
    long long c;

    /* already sorted */
    if (tail - head == 1)
        return 0;
    /* unsorted list -> merge into 2 sub lists */
    half = (head + tail) / 2;  /* (x / 2) == (x >> 1) */
    c = merge(ary, tmp, head, half);
    c += merge(ary, tmp, half, tail);
    /* sort 2 sublists and merge */
    k = i = head;
    j = half;
    while (i < half && j < tail)
        if (ary[j] < ary[i]) {
            tmp[k++] = ary[j++];
            c += half - i;
        }
        else
            tmp[k++] = ary[i++];
    while (i < half)
        tmp[k++] = ary[i++];
    while (j < tail)
        tmp[k++] = ary[j++];
    for (i = head; i < tail; i++)  /* copy the sorted list to ary */
        ary[i] = tmp[i];

    return c;
}

ACM 10258 Contest Scoreboard

又一題腦殘題……
每次寫到腦殘題頭都痛死惹……
首先problem數最多是13，不是什麼9……-.-。

另外只要得到correct之後，
不管之後又得到correct或是incorrect，
通通不用管它……

問題是題目有寫嗎？有嗎？沒吧！
那誰知道這種機車狀況要怎麼處理？
定義一下會死嗎？
無聊！

/* ACM 10258 Contest Scoreboard
 * mythnc
 * 2012/01/11 23:07:41   
 * run time: 0.004
 */
#include <stdio.h>
#include <string.h>

#define LINEMAX 25
#define MAXP 13
#define MAXC 100

typedef struct contestant {
    int num, solved, penalty;
    int tried[MAXP], ac[MAXP];
} Contestant;

typedef enum {FALSE = 0, TRUE} bool;

int input(Contestant *);
int find(Contestant *, int, int);
int cmp(const void *, const void *);
void output(Contestant *, int);

int main(void)
{
    Contestant con[MAXC];
    int set, i, n;

    scanf("%d", &set);
    getchar();
    getchar();
    for (i = 0; i < set; i++) {
        if (i > 0)
            putchar('\n');
        n = input(con);
        qsort(con, n, sizeof(Contestant), cmp);
        output(con, n);
    }

    return 0;
}

/* input: receive input datas */
int input(Contestant *con)
{
    int num, prob, time, n, pos;
    char sub;
    char line[LINEMAX];

    n = 0;
    while (fgets(line, LINEMAX, stdin)) {
        if (strlen(line) <= 1) /* blank line */
            break;
        sscanf(line, "%d %d %d %c", &num, &prob, &time, &sub);
        pos = find(con, num, n);
        if (pos == -1) {
            /* add and init */
            con[n].num = num;
            con[n].solved = con[n].penalty = 0;
            memset(con[n].tried, 0, MAXP);
            memset(con[n].ac, FALSE, MAXP);
            pos = n++;
        }
        if (sub == 'C' && !con[pos].ac[prob - 1]) {
            con[pos].solved++;
            con[pos].penalty += time + con[pos].tried[prob - 1];
            con[pos].ac[prob - 1] = TRUE;
        }
        else if (sub == 'I' && !con[pos].ac[prob - 1])
            con[pos].tried[prob - 1] += 20;
    }

    return n;
}

/* find: if num in con return it's position
 * else retrn -1 */
int find(Contestant *con, int num, int n)
{
    int i;

    for (i = 0; i < n; i++)
        if (con[i].num == num)
            return i;

    return -1;
}

/* cmp: for qsort() */
int cmp(const void *a, const void *b)
{
    if (((Contestant *)a)->solved != ((Contestant *)b)->solved)
        return ((Contestant *)b)->solved - ((Contestant *)a)->solved;
    else if (((Contestant *)a)->penalty != ((Contestant *)b)->penalty)
        return ((Contestant *)a)->penalty - ((Contestant *)b)->penalty;
    else
        return ((Contestant *)a)->num - ((Contestant *)b)->num;
}

/* output: output results */
void output(Contestant *con, int n)
{
    int i;

    for (i = 0; i < n; i++)
        printf("%d %d %d\n", con[i].num, con[i].solved, con[i].penalty);
}