ACM 10281 Average Speed

單純的距離 = 時間差 * 速率。
每次求出新的時間後就代替舊有時間，
如此時間差可以馬上求得。
input用fgets先吃，再用sscanf抓資料。
有三行重複……感覺很醜，但是位置也不能改啊 orz。

/* ACM 10281 Average Speed
 * mythnc
 * 2011/12/31 08:12:03   
 * run time: 0.008
 */
#include <stdio.h>

#define LINEMAX 20

int main(void)
{
    char line[LINEMAX];
    int h, m, s, t1, t2;
    int newv, v;
    double dis;

    h = m = s = t1 = v = 0;
    dis = 0.0;
    while (fgets(line, LINEMAX, stdin))
        if (sscanf(line, "%d:%d:%d %d", &h, &m, &s, &newv) == 4) {
            t2 = h * 3600 + m * 60 + s;
            dis += (double)((t2 - t1) * v) / 3600.0;
            t1 = t2;
            v = newv;
        }
        else if (sscanf(line, "%d:%d:%d", &h, &m, &s) == 3) {
            t2 = h * 3600 + m * 60 + s;
            dis += (double)((t2 - t1) * v) / 3600.0;
            t1 = t2;
            /* output */
            printf("%02d:%02d:%02d %.2f km\n", h, m, s, dis);
        }

    return 0;
}

ACM 900 Brick Wall Patterns

觀察n值與排列方式。
事實上可以發現有直板跟橫板兩種情況。
直板一個佔用一個面積，橫板一個佔用兩個面積。
所以n = 1時，無橫板，
n = 2時，最多1個橫板，
n = 3時，最多1個橫板，
n = 4時，最多2個橫板，
n = 5時，最多2個橫板，
n = 6時，最多3個橫板。
可以發現最多橫板數為n / 2。
每多一個橫板，組合方式就會多一種。
n = 1時，無橫板的組合，
n = 2時，無橫板的組合 + 1個橫板的組合，
n = 3時，無橫板的組合 + 1個橫板的組合，
n = 4時，無橫板的組合 + 1個橫板的組合 + 2個橫板的組合，
n = 5時，無橫板的組合 + 1個橫板的組合 + 2個橫板的組合，
n = 6時，無橫板的組合 + 1個橫板的組合 + 2個橫板的組合 + 3個橫板的組合。
無橫板的組合，就都是直板：Cn取n。
1個橫板的組合，為n - 2個直板 + 1個橫板：C的n - 1取1。
2個橫板的組合，為n - 4個直板 + 2個橫板：C的n - 2取2。
看出來了嗎？
每多一塊橫板，直板的數目就會少2。
有了直板與橫板的數目，就可以求得組合的情況。
其實就是要算這種問題：
有m塊直板跟n塊橫板，求其組合方式：(m + n)! / (n! * m!)。
把組合數加一加，就是答案了。
可以利用ACM369的方式計算組合。

/* ACM 900 Brick Wall Patterns
 * mythnc
 * 2011/12/30 10:12:43   
 * run time: 0.008
 */
#include <stdio.h>

#define MAXN 50
#define MIN(X, Y) ((X <= Y) ? X : Y)

long long count(int);
long long com(int, int);
int gcd(int, int);

int main(void)
{
    int n, i;

    while (scanf("%d", &n) && n != 0)
        printf("%lld\n", count(n));

    return 0;
}

/* count: return the combination numbers */
long long count(int n)
{
    int i, ver, hor;
    long long times;

    times = 1;
    ver = n - 2;
    hor = 1;
    while (ver >= 0) {
        times += com(ver, hor);
        ver -= 2;
        hor++;
    }

    return times;
}

/* com: return the combination times:
 * (m + n)! / (n! * m!) */
long long com(int m, int n)
{
    int sum, i, j, times, factor, tmp;
    long long ans[MAXN] = { 0 };

    if (m == 0 || n == 0)
        return 1;
    if (m == 1 || n == 1)
        return m + n;

    times = 0;
    sum = m + n;
    /* init */
    for (i = sum - MIN(m, n) + 1; i <= sum; i++)
        ans[times++] = i;
    /* simplify */
    for (i = 2; i <= MIN(m, n); i++) {
        tmp = i;
        for (j = 0; j < times; j++) {
            if (ans[j] % tmp == 0) {
                ans[j] /= tmp;
                break;
            }
            if ((factor = gcd(tmp, ans[j])) != 1) {
                ans[j] /= factor;
                tmp /= factor;
            }
        }
    }
    /* cal ans */
    for (i = 1; i < times; i++)
        ans[0] *= ans[i];

    return ans[0];
}

/* gcd: return gcd */
int gcd(int a, int b)
{
    while ((a %= b) && (b %= a))
        ;

    return a + b;
}

ACM 10699 Count the factors

找質因數個數。

每次找到一個因數p後，就讓n = n / p，
再繼續對n做找因數的動作。
如此計算因數總數即為答案。

先建一個質數表再做會比較快。

/* ACM 10699 Count the factors
 * mythnc
 * 2011/12/29 09:41:28   
 * run time: 0.024
 */
#include <stdio.h>

int countp(int);

int main(void)
{
    int n;

    while (scanf("%d", &n) && n != 0)
        printf("%d : %d\n", n, countp(n));

    return 0;
}

/* countp: return the number of prime factor */
int countp(int n)
{
    int i, count;

    for (i = 2, count = 0; n != 1; i++) {
        if (n % i == 0) {
            count++;
            while (n % i == 0)
                n /= i;
        }
    }

    return count;
}

ACM 10931 Parity

邊轉成bin邊找1的個數即可。

/* ACM 10931 Parity
 * mythnc
 * 2011/12/28 08:14:34   
 * run time: 0.004
 */
#include <stdio.h>
#include <string.h>

#define MAXCHAR 32

int dectobin(int, char *);
void reverse(char *);

int main(void)
{
    int n, count;
    char bin[MAXCHAR];

    while (scanf("%d", &n) && n != 0) {
        count = dectobin(n, bin);
        reverse(bin);
        printf("The parity of %s is %d (mod 2).\n", bin, count);
    }
        
    return 0;
}

/* dectobin: make decimal number to
 * correspond its binary number,
 * and return the number of 1(bin) */
int dectobin(int n, char *b)
{
    int i, count;

    i = count = 0;
    while (n) {
        if (n % 2)
            count++;
        b[i++] = n % 2 + '0';
        n /= 2;
    }
    b[i] = '\0';

    return count;
}

/* reverse: reverse bin number */
void reverse(char *b)
{
    int i, j;
    char tmp;

    for (i = 0, j = strlen(b) - 1; i < j; i++, j--) {
        tmp = b[i];
        b[i] = b[j];
        b[j] = tmp;
    }
}

ACM 10004 Bicoloring

第一次寫graph，好刺激……

一開始想說沒這麼難吧？不就填色嗎！
填完答案就出來了！
不過像input為
1 2
3 4
2 3
就會gg了。
所以一定要是traversal + 填色兩個動作。
光是填或是光是traversal是不行的。

填色 + DFS檢查填色狀況。
利用adjacency list建graph。
之後從graph[0]開始填色（填在每個graph[i]），
填完每個跟graph[0]相連的node之後，做DFS走訪graph，
一樣先做填色的動作，再做DFS。
若填色時發現該node顏色與要填的顏色不一，
表示沒有bicolor的形式。
若能順利填完色走訪完整個graph，表示有bicolor的形式。

總覺得寫得很髒 orz，不知道有沒有其他比較好的方式，
填色O(e)感覺花了不少時間。

這個問題其實是一個Bipartite Graph。
解了Bipartite Graph這題就能解了，這題能解了Bipartite Graph也可以解了。

/* ACM 10004 Bicoloring
 * mythnc
 * 2011/12/26 19:44:34   
 * run time: 0.012
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXNODE 199
#define TRUE    1
#define FALSE   0

enum color {none, white, black};

typedef struct node {
    int n;
    enum color c;
    struct node *next;
} Node;

void init(Node **);
void input(Node **, int, int);
int check(Node **, int);
void freeg(Node **, int);

int visited[MAXNODE];

int main(void)
{
    int n, e, u, v, i;
    Node *graph[MAXNODE];

    while (scanf("%d", &n) && n != 0) {
        scanf("%d", &e);
        init(graph);
        for (i = 0; i < e; i++) {
            scanf("%d %d", &v, &u);
            input(graph, u, v);
            input(graph, v, u);
        }
        if (check(graph, 0))
            printf("BICOLORABLE.\n");
        else
            printf("NOT BICOLORABLE.\n");
        freeg(graph, n);
    }

    return 0;
}

/* init: initialize graph node to NULL and visited to zero */
void init(Node **graph)
{
    int i;

    for (i = 0; i < MAXNODE; i++) {
        graph[i] = NULL;
        visited[i] = FALSE;
    }
}

/* input: receive input data */
void input(Node **graph, int u, int v)
{
    Node *tmp, *pt;

    tmp = (Node *)malloc(sizeof(Node));
    tmp->n = u;
    tmp->c = none;
    tmp->next = NULL;
    if (!graph[v]) {
        graph[v] = (Node *)malloc(sizeof(Node));
        graph[v]->n = v;
        graph[v]->c = none;
        graph[v]->next = tmp;
    }
    else {
        pt = graph[v];
        while (pt->next)
            pt = pt->next;
        pt->next = tmp;
    }
}

/* check(dfs): check each node and
 * its adjacency are different colors.
 * if have same color stop dfs and return FALSE
 * else do dfs to the end and return TRUE */
int check(Node **graph, int n)
{
    enum color c;
    Node *pt;

    pt = graph[n];
    visited[n] = TRUE;
    if (pt->c == none) {
        pt->c = white;
        c = black;
    }
    else if (pt->c == white)
        c = black;
    else
        c = white;
    for (pt = pt->next; pt; pt = pt->next)
        if (graph[pt->n]->c == none)
            graph[pt->n]->c = c;
        else if (graph[pt->n]->c == c)
            ;
        else
            return FALSE;
    for (pt = graph[n]->next; pt; pt = pt->next)
        if (!visited[pt->n])
            if (!check(graph, pt->n))
                return FALSE;

    return TRUE;
}

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

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

ACM 10499 The Land of Justice

寫這麼多，其實只要知道，價錢是依照表面積來算即可。

球的表面積為4 * pi * r ^ 2，
球切成n塊的表面積為(1 / n)的球表面積 + 2塊(1 / 2)的圓面積，
所以n塊的總表面積為4 * pi * r ^ 2 + n * pi * r ^ 2。

利潤為(賣價 - 買價) / 買價。
[4 * pi * r ^ 2 + n * pi * r ^ 2 - 4 * pi * r ^ 2] / 4 * pi * r ^ 2，
=> n * pi * r ^ 2 / 4 * pi * r ^ 2，
=> n / 4。

乘上100，
=> 25n %，即為答案。

注意若n = 1為利潤為0%。

/* ACM 10499 The Land of Justice
 * mythnc
 * 2011/12/26 10:04:46   
 * run time: 0.024
 */
#include <stdio.h>

int main(void)
{
    long long n;

    while (scanf("%lld", &n) && n > 0)
        if (n == 1)
            printf("0%%\n");
        else
            printf("%lld%%\n", n * 25);

    return 0;
}

ACM 156 Ananagrams

一邊吃token，一邊判斷該token與已存的資料是否有anagram的現象，
若有，就不存，並把現有的token做tag；
若無，存起來。
吃完token後，把沒tag的資料做sort，
再output即可。

用linked list解，
練習ll的一些函式實作。

/* ACM 156 Ananagrams
 * mythnc
 * 2011/12/25 20:30:50   
 * run time: 0.008
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXL  21
#define FALSE 0
#define TRUE  1

typedef struct token {
    int tag, len;
    char word[MAXL];
    struct token *next;
} Token;

Token *input(void);
int ananagrams(Token *, char *);
int sameletter(char *, char *);
void *deletetag(Token **);
void *sort(Token **);
void output(Token *);
void freel(Token *);

int main(void)
{
    Token *head;

    head = input();
    deletetag(&head);
    sort(&head);
    output(head);
    freel(head);

    return 0;
}

/* input: eat input token */
Token *input(void)
{
    char word[MAXL];
    Token *tmp, *head, *current;

    head = current = NULL;
    while (scanf("%s", word) && word[0] != '#') {
        if (head && !ananagrams(head, word))
            continue;
        tmp = (Token *)malloc(sizeof(Token));
        if (!head)
            head = tmp;
        strcpy(tmp->word, word);
        tmp->len = strlen(word);
        tmp->tag = FALSE;
        tmp->next = NULL;
        if (current)
            current->next = tmp;
        current = tmp;
    }

    return head;
}

/* ananagrams: compare word in ll vs w,
 * if they are anagrams return FALSE
 * else return TRUE */
int ananagrams(Token *pt, char *w)
{
    while (pt) {
        if (pt->len == strlen(w) && sameletter(pt->word, w)) {
            pt->tag = TRUE;
            return FALSE;
        }
        pt = pt->next;
    }

    return TRUE;
}

/* sameletter: if s and t have same letter
 * return TRUE else return FALSE */
int sameletter(char *s, char *t)
{
    int letters[26] = { 0 };
    int i;

    for (i = 0; i < strlen(s); i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
            letters[s[i] - 'A']++;
        /* lowercase */
        else
            letters[s[i] - 'a']++;

    for (i = 0; i < strlen(t); i++)
        if (t[i] >= 'A' && t[i] <= 'Z') {
            if (letters[t[i] - 'A'] == 0)
                return FALSE;
            letters[t[i] - 'A']--;
        }
        /* lowercase */
        else {
            if (letters[t[i] - 'a'] == 0)
                return FALSE;
            letters[t[i] - 'a']--;
        }

    return TRUE;
}

/* deletetag: if tag == TRUE, delete it */
void *deletetag(Token **head)
{
    Token *pre, *pt, *tmp;

    pre = NULL;
    pt = *head;
    while (pt) {
        if (pt->tag) {
            if (!pre) {
                tmp = *head;
                *head = (*head)->next;
            }
            else {
                tmp = pt;
                pre->next = pt->next;
            }
            free(tmp);
            pt = pt->next;
            continue;
        }
        pre = pt;
        pt = pt->next;
    }
}

/* sort: insertion sort linked list */
void *sort(Token **head)
{
    Token *i, *j, *pre, *tmpi, *tmpj;

    for (i = (*head)->next; i; i = i->next) {
        tmpi = i;
        for (j = *head, pre = NULL; j != tmpi; pre = j, j = j->next)
            if (strcmp(tmpi->word, j->word) < 0) {
                if (pre)
                    pre->next = tmpi;
                else
                    *head = tmpi;
                tmpj = j;
                while (tmpj->next != tmpi)
                    tmpj = tmpj->next;
                tmpj->next = tmpi->next;
                tmpi->next = j;
                break;
            }
    }
}

/* output: output result */
void output(Token *pt)
{
    for (; pt; pt = pt->next)
        printf("%s\n", pt->word);
}

/* free: free linked list */
void freel(Token *pt)
{
    Token *tmp;

    while (pt) {
        tmp = pt;
        free(tmp);
        pt = pt->next;
    }
}

ACM 10432 Polygon Inside A Circle

n > 2，必定有三點，
任意兩點加上圓心會構成一個三角形，
共有n個三角形。
求出三角形的面積再乘以n即為答案。

已知三角形為等腰三角形，從底邊中間切一半，
可以得到兩塊一模一樣的直角三角形。
斜邊為R，對邊跟鄰邊都不知道。
斜邊與鄰邊的夾角a為360 / (n * 2)。
利用三角函數，可知對邊與鄰邊為sin(a) * R和cos(a) * R。
如此可求出此三角形面積：(1 / 2) * sin(a) * R * cos(a) * R。
一個等腰三角形由兩個直角三角形構成，n邊形由n個等腰三角形構成，
所以n邊形面積為n * 2 * (1 / 2) * sin(a) * R * cos(a) * R，
化簡後可得：n * sin(a) * R * cos(a) * R。

利用math.h的函式sin與cos即可求解。
但要先把度換成弧度（徑度）。
pi = 180度，
所以徑度 = pi / 180。
(pi / 180) * [360 / (n * 2)]，
化簡後為pi / n。

r可能為浮點數，要用double吃。

/* ACM 10432 Polygon Inside A Circle
 * mythnc
 * 2011/12/23 14:04:53   
 * run time: 0.008
 */
#include <stdio.h>
#include <math.h>

#define PI 3.141592653589793

int main(void)
{
    int n;
    double r;

    while (scanf("%lf %d", &r, &n) == 2)
        printf("%.3f\n", n * r * sin(PI / n) * r * cos(PI / n));

    return 0;
}

ACM 392 Polynomial Showdown

需要考慮的：
首項，係數（0、1、其他），次方（0、1、其他）、正負號。
只有0的情況要額外考慮。

/* ACM 392 Polynomial Showdown
 * mythnc
 * 2011/12/21 09:15:20   
 * run time: 0.108
 */
#include <stdio.h>
#include <string.h>

#define MAXD  9
#define TRUE  1
#define FALSE 0

void output(int *);

int main(void)
{
    int i;
    int poly[MAXD] = { 0 };

    while (scanf("%d", &poly[8]) == 1) {
        for (i = 7; i > -1; i--)
            scanf("%d", &poly[i]);
        output(poly);
        /* init */
        memset(poly, 0, sizeof(int) * MAXD);
    }

    return 0;
}

void output(int *p)
{
    int i, first;

    for (i = 8, first = TRUE; i > -1; i--) {
        if (p[i] == 0)
            continue;
        /* first element */
        if (first) {
            first = FALSE;
            if (p[i] < 0)
                putchar('-');
        }
        else if (p[i] > 0)
            printf(" + ");
        else
            printf(" - ");
        /* coefficient */
        if (p[i] > 1 && i != 0)
            printf("%d", p[i]);
        else if (p[i] < -1 && i != 0)
            printf("%d", -p[i]);
        /* degree */
        if (i > 1)
            printf("x^%d", i);
        else if (i == 1)
            putchar('x');
        else
            printf("%d", p[i] >= 0 ? p[i] : -p[i]);
    }
    if (first)
        putchar('0');
    putchar('\n');
}

ACM 10473 Simple Base Conversion

hex to dec，用%x吃，%d輸出；
dec to hex，用%d吃，%X輸出。

/* ACM 10473 Simple Base Conversion
 * mythnc
 * 2011/12/20 10:18:59   
 * run time: 0.016
 */
#include <stdio.h>

#define MAXCHAR 11

int main(void)
{
    char s[MAXCHAR];
    int n;

    while (scanf("%s", s) == 1) {
        /* hex to dec */
        if (s[1] == 'x') {
            sscanf(s, "%x", &n);
            printf("%d\n", n);
            continue;
        }
        /* dec to hex */
        sscanf(s, "%d", &n);
        if (n < 0)
            break;
        printf("0x%X\n", n);
    }

    return 0;
}

ACM 444 Encoder and Decoder

苦工題。
跟ACM713有點像。
encode時，先做mapping，之後做reverse；
decode時，先做reverse，再做mapping。

另外題目騙人，input最長並非80個char，
所以如果WA的話，就把array設為1000吧。
ACM真愛騙人。

/* ACM 444 Encoder and Decoder
 * mythnc
 * 2011/12/19 17:20:43   
 * run time: 0.004
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN    123
#define MAXCHAR 4
#define LINEMAX 1000
#define OTHERSC 7

void map(char (*)[]);
void itoa(char *, int);
void reverse(char *);
void decode(char *, char *);
void encode(char *, char (*)[], char *);

int main(void)
{
    char key[MAXN][MAXCHAR];
    char input[LINEMAX];
    char output[LINEMAX * 3];

    map(key);

    while (fgets(input, LINEMAX, stdin)) {
        /* eat newline */
        input[strlen(input) - 1] = '\0';
        /* number: decode it */
        if (input[0] >= '0' && input[0] <= '9')
            decode(input, output);
        /* encode it */
        else
            encode(input, key, output);
        /* output */
        printf("%s\n", output);
    }

    return 0;
}

/* map: map char to int */
void map(char (*key)[MAXCHAR])
{
    char tmp[MAXCHAR];
    int trans[] = {32, 33, 44, 46, 58, 59, 63};
    int i;

    /* uppercase letter */
    for (i = 65; i <= 90; i++) {
        itoa(tmp, i);
        strcpy(key[i], tmp);
    }
    /* lowercase letter */
    for (i = 97; i <= 122; i++) {
        itoa(tmp, i);
        strcpy(key[i], tmp);
    }
    /* others chars */
    for (i = 0; i < OTHERSC; i++) {
        itoa(tmp, trans[i]);
        strcpy(key[trans[i]], tmp);
    }
}

/* itoa: int to ascii */
void itoa(char *tmp, int n)
{
    int i;

    i = 0;
    while (n != 0) {
        tmp[i++] = n % 10 + '0';
        n /= 10;
    }
    tmp[i] = '\0';
    reverse(tmp);
}

/* reverse: reverse s */
void reverse(char *s)
{
    int i, j;
    char tmp;

    for (i = 0, j = strlen(s) - 1; i < j; i++, j--) {
        tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}

/* decode: decode number to ascii code */
void decode(char *s, char *output)
{
    int i, count;
    char tmp[MAXCHAR];

    reverse(s);
    for (i = count = 0; i < strlen(s); ) {
        if (s[i] == '1') {
            strncpy(tmp, s + i, 3);
            tmp[3] = '\0';
            i += 3;
        }
        else {
            strncpy(tmp, s + i, 2);
            tmp[2] = '\0';
            i += 2;
        }
        output[count++] = atoi(tmp);
    }
    output[count] = '\0';
}

/* encode: encode char to number */
void encode(char *s, char (*key)[MAXCHAR], char *output)
{
    char *pt;
    int i;

    output[0] = '\0';
    pt = output;
    for (i = 0; i < strlen(s); i++) {
        pt = strcat(pt, key[(int)s[i]]);
    }
    reverse(output);
}

ACM 112 Tree Summing

input轉tree想超久的，
做出來還是很happy。
（一次就AC超爽的）
解法很正統……
先建tree，之後才做traversal。
(1)建tree
因為()會是pair，所以先找到「(」即可丟入addtree()中，
當找到「)」後就return。
利用recursive就能建立完成。
(2)traversal
做preorder traversal，
利用stack紀錄每個node的value。
到leaf node時做sum，把sum存起來。

最後判斷input值是否與sum相同即可。

看到別人的解法是可以在建tree的同時做sum，
這樣之後就不用作traversal，會比較快。

/* ACM 112 Tree Summing
 * mythnc
 * 2011/12/18 19:06:31   
 * run time: 0.064
 */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAXCHAR 11
#define MAXN    1000
#define TRUE    1
#define FALSE   0

typedef struct node {
    char value[MAXCHAR];
    struct node *left, *right;
} Node;

Node *addtree(void);
void traversal(Node *, int *, int *);
int contain(int, int *, int);
void freet(Node *);

int stack[MAXN];
int stc;

int main(void)
{
    Node *root;
    int n, c, count;
    int sumall[MAXN];

    while (scanf("%d", &n) == 1) {
        /* find the 1st '(' */
        while ((c = getchar()) != '(')
            ;
        root = addtree();
        count = 0;
        traversal(root, sumall, &count);
        if (contain(n, sumall, count))
            printf("yes\n");
        else
            printf("no\n");
        freet(root);
    }

    return 0;
}

/* addtree: add node to root */
Node *addtree(void)
{
    Node *tmp;
    int c, left, vcount;

    tmp = (Node *)malloc(sizeof(Node));
    tmp->left = tmp->right = NULL;
    left = FALSE;
    vcount = 0;
    while ((c = getchar()) != ')')
        /* left node */
        if (c == '(' && !left) {
            tmp->left = addtree();
            left = TRUE;
        }
        /* right node */
        else if (c == '(' && left)
            tmp->right = addtree();
        /* integer */
        else if (isdigit(c) || c == '-') {
            tmp->value[vcount] = c;
            tmp->value[++vcount] = '\0';
        }
    if (vcount == 0) {
        free(tmp);
        return NULL;
    }
    return tmp;
}

/* traversal: traversal the tree */
void traversal(Node *pt, int *sumall, int *count)
{
    int i, sum;
    /* empty tree */
    if (pt == NULL)
        return;
    /* leaf node: left and right are NULL */
    if (pt->left == pt->right) {
        for (sum = i = 0; i < stc; i++)
            sum += stack[i];
        sumall[(*count)++] = sum + atoi(pt->value);
        return;
    }
    /* push */
    stack[stc++] = atoi(pt->value);
    traversal(pt->left, sumall, count);
    traversal(pt->right, sumall, count);
    /* pop */
    stc--;
}

/* contain: if n contain in sumall,
 * return TRUE, else return FALSE */
int contain(int n, int *sumall, int count)
{
    int i;
    /* negative */
    if (count == 0 && n < 0)
        return TRUE;

    for (i = 0; i < count; i++)
        if (sumall[i] == n)
            return TRUE;
    return FALSE;
}

/* freet: free all node */
void freet(Node *pt)
{
    if (pt == NULL)
        return;
    freet(pt->left);
    freet(pt->right);
    free(pt);
}

ACM 386 Perfect Cubes

由題目給的答案可以發現：
n^3 = a^3 + b^3 + c^3，
a <= b <= c。
所以迴圈就這樣寫即可！
a從2開始，b從a開始，c從b開始。
當a^3 + b^3 + c^3 < n^3時，c + 1。
a^3 + b^3 + c^3 == n^3時，找到一組，
a^3 + b^3 + c^3 > n^3時，b + 1。
a^3 + b^3 > n^3時，a + 1。
a == n時，終止。

/* ACM 386 Perfect Cubes
 * mythnc
 * 2011/12/18 12:17:31   
 * run time: 0.132
 */
#include <stdio.h>

#define CUBIC(X) (X * X * X)

void cal(int);

int main(void)
{
    int i;

    for (i = 6; i <= 200; i++)
        cal(i);

    return 0;
}

/* cal: calculate answer */
void cal(int n)
{
    int i, j, k, value;

    for (i = 2; i < n; i++)
        for (j = i; CUBIC(i) + CUBIC(j) < CUBIC(n); j++)
            for (k = j; ; k++) {
                value = CUBIC(i) + CUBIC(j) + CUBIC(k);
                if (value < CUBIC(n))
                    continue;
                else if (value == CUBIC(n))
                    printf("Cube = %d, Triple = (%d,%d,%d)\n", n, i, j, k);
                else
                    break;
            }
}

ACM 10323 Factorial! You Must be Kidding!!!

如同題目所寫，
Factorial! You Must be Kidding!!!
沒啥規則的一題 = =，
input有可能是負數，所以要考慮負數的情況。
什麼？你說負數有階層？娜舞摳琳！
是的題目也這樣寫啊！
反正-1!是Overflow，
-2!是Underflow，
-3!是Overflow，
-4!是Underflow，
以此類推，
至於為什麼……不要問比較好，
問了會腦殘。
(-1! = 0! / 0，把他當成無限大去想，
-2! = -1! / -1，負無限大）

/* ACM 10323 Factorial! You Must be Kidding!!! 
 * mythnc
 * 2011/12/17 09:24:42   
 * run time: 0.028
 */
#include <stdio.h>

#define MAX 6227020800LL

int main(void)
{
    int i, n;
    long long ans[20] = { 1 };

    for (i = 1; ans[i - 1] < MAX; i++)
        ans[i] = ans[i - 1] * i;

    while (scanf("%d", &n) == 1)
        if (n < 0) {
            n *= -1;
            if (n % 2 == 1)
                printf("Overflow!\n");
            else
                printf("Underflow!\n");
        }
        else if (n < 8)
            printf("Underflow!\n");
        else if (n >= i)
            printf("Overflow!\n");
        else
            printf("%lld\n", ans[n]);

    return 0;
}

ACM 10010 Where's Waldorf?

填字遊戲。
大小寫視為相同。
找到字首後，從其四面八方找第二個字母，
找到第二個字母後，繼續從該路線找第三個字母，
一直到最後一個字母，若都有找到，就是找到了，
要不然就從下一個路線開始，
路線都沒找到，就從下一個點開始。
要考慮邊界問題。

很懶的用了一堆全域變數。

/* ACM 10010 Where's Waldorf? 
 * mythnc
 * 2011/12/16 12:31:16   
 * run time: 0.008
 */
#include <stdio.h>

#define MAXF  50
#define MAXK  20
#define DIRC  8
#define RANGE(X, Y) X >= 0 && X < maxrow && Y >= 0 && Y < maxcol
#define TRUE  1
#define FALSE 0

void findword(void);
int move(int, int, int);
int sameletter(char, char);

char square[MAXF][MAXF + 1];
char word[MAXK][MAXF + 1];
int maxrow, maxcol, kword;

int main(void)
{
    int n, i, j, set;

    scanf("%d", &n);
    for (i = set = 0; i < n; i++) {
        /* input data */
        scanf("%d %d", &maxrow, &maxcol);
        getchar(); /* eat newline */
        for (j = 0; j < maxrow; j++)
            scanf("%s", square[j]);
        scanf("%d", &kword);
        getchar(); /* eat newline */
        for (j = 0; j < kword; j++)
            scanf("%s", word[j]);
        /* blank line in each set */
        if (set == 1)
            putchar('\n');
        findword();
        set = 1;
    }

    return 0;
}

/* findword: find the word position */
void findword(void)
{
    int i, j, k, find;

    for (i = 0; i < kword; i++) {
        for (find = j = 0; j < maxrow && !find; j++)
            for (k = 0; k < maxcol && !find; k++)
                if (sameletter(word[i][0], square[j][k]))
                    find = move(i, j, k);
        if (find)
            printf("%d %d\n", j, k);
    }
}

/* move: move around from (r, c),
 * if find return TRUE, else return FALSE */
int move(int n, int r, int c)
{
    int mover[] = {-1, -1, -1, 0, 1, 1, 1, 0};
    int movec[] = {-1, 0, 1, 1, 1, 0, -1, -1};
    int i, j, nextr, nextc;

    for (i = 0; i < DIRC; i++) {
        nextr = r + mover[i];
        nextc = c + movec[i];
        j = 1;
        /* find word from direction i */
        while (word[n][j] != '\0' && RANGE(nextr, nextc)
               && sameletter(word[n][j], square[nextr][nextc])) {
            j++;
            nextr += mover[i];
            nextc += movec[i];
        }
        /* find */
        if (word[n][j] == '\0')
            return TRUE;
    }

    return FALSE;
}

/* sameletter: if the letter is same
 * (regardless of case)
 * return TRUE
 * else return FALSE */
int sameletter(char s, char t)
{
    if (s == t)
        return TRUE;
    /* upper to lower */
    if (s >= 'A' && s <= 'Z')
        s = s - 'A' + 'a';
    if (t >= 'A' && t <= 'Z')
        t = t - 'A' + 'a';

    if (s == t)
        return TRUE;
    return FALSE;
}

ACM 357 Let Me Count The Ways

同ACM674。
要用long long，要不然會爆掉。

/* ACM 357 Let Me Count The Ways
 * mythnc
 * 2011/12/15 11:15:23   
 * run time: 0.044
 */
#include <stdio.h>

#define MAXN 30001
#define COIN 5

void cal(long long *);

int main(void)
{
    int n;
    long long ans[MAXN] = { 0 };

    cal(ans);

    while (scanf("%d", &n) == 1)
        if (ans[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", ans[n], n);

    return 0;
}

/* cal: pre calulate the answer */
void cal(long long *ans)
{
    int money[COIN] = {1, 5, 10, 25, 50};
    int i, j;

    ans[0] = 1;
    for (i = 0; i < COIN; i++)
        for (j = money[i]; j < MAXN; j++)
            ans[j] += ans[j - money[i]];
}

ACM 573 The Snail

蝸牛爬牆模擬題。
白天爬完要判斷一次，
晚上落後也要判斷一次。
當蝸牛不再爬後一直減到負數即可。

/* ACM 573 The Snail
 * mythnc
 * 2011/12/14 13:48:31   
 * run time: 0.020
 */
#include <stdio.h>

void snail(int, int, double, double);

int main(void)
{
    double fatigue, up;
    int wall, down;

    while (scanf("%d %lf %d %lf", &wall, &up, &down, &fatigue)
           && wall != 0) {
           snail(wall, down, up, fatigue);
    }

    return 0;
}

void snail(int wall, int down, double up, double fa)
{
    int day;
    double climb;
    /* init */
    day = 1;
    climb = 0.0;
    fa = up * fa / 100;
    while (1) {
        /* day climb */
        climb += up;
        if (climb > wall) {
            printf("success on day %d\n", day);
            return;
        }
        /* night fall */
        climb -= down;
        if (climb < 0.0) {
            printf("failure on day %d\n", day);
            return;
        }
        up -= fa;
        /* if up come to non-positive */
        if (up <= 0.0) {
            while (climb >= 0.0) {
                climb -= down;
                day++;
            }
            printf("failure on day %d\n", day);
            return;
        }
        /* another day */
        day++;
    }
}

ACM 147 Dollars

同ACM674，
先把面額都變成整數會比較好算，
1 / 0.05 = 20，
面額跟input都乘以20就能變整數。

/* ACM 147 Dollars
 * mythnc
 * 2011/12/13 14:56:54   
 * run time: 0.012
 */
#include <stdio.h>

#define MAXN 6001
#define COIN 11

void cal(long long *);

int main(void)
{
    long long ans[MAXN] = { 0 };
    double n;

    cal(ans);

    while (scanf("%lf", &n) && n != 0.0)
        printf("%6.2f%17lld\n", n, ans[(int)(n * 20)]);

    return 0;
}

/* cal: pre calulate answer */
void cal(long long *ans)
{
    int money[] = {1, 2, 4, 10, 20, 40,
                   100, 200, 400, 1000, 2000};
    int i, j;

    ans[0] = 1;
    for (i = 0; i < COIN; i++)
        for (j = money[i]; j < MAXN; j++)
            ans[j] += ans[j - money[i]];
}

ACM 674 Coin Change

經典DP題。
想了很久，還是想不出個所以然。
雖然看到公式也看到算法，還是不知道為什麼會這樣。
只能說……神奇啊
主要參考兩個網站：
algorithmist跟sagit教學，
公式是長這樣：
c(i,j) = c(i - 1,j) + c(i,j - ai)，
翻成國語是，
有i個元素要加總為j，共有c(i, j)的組合方式，
那麼，c(i, j)會等於i - 1個元素加總為j的組合，再加上i個元素加總為j - ai的組合。
很抽象吧……
舉個例子，
如果有硬幣面額1, 5, 10。
要算出0~26元的所有可能組合方式，
那就從面額1開始填0元到26元的可能，
0 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
接著填5，
0 1
1 1
2 1
3 1
4 1
5 2
6 2
7 2
8 2
9 2
10 3
11 3
12 3
13 3
14 3
15 4
16 4
17 4
18 4
19 4
20 5
21 5
22 5
23 5
24 5
25 6
26 6
看出來了嗎？
當只有1元時，所有可能的組合都是1種，
加入5元時，5元到9元的組合變成2(1 + 1)種，
10~14元的組合變成3(1 + 2)種，
對照公式c(i,n) = c(i - 1,n) + c(i,n - ai)，
1元跟5元對n元的組合情況為，
1元對n的組合情況 + 1元跟5元對n - 5元的組合情況！
至於為什麼會這樣呢，看了幾個subset sum的證明，
發現看不是很懂（很數學），所以就先背起來吧，
反正這是正確的……

反正就是每當加入了一個新的面額X元，
要計算n元的組合情況，
就要從之前i - 1個面額對n元的組合情況，加上現在i個面額對n - x元的組合情況。

而起始要從0元開始，0元只有一種情況，
就是什麼都不拿。
1元會從1元開始 + 1，
5元會從5元開始 + 1，
依此類推。

所以若要計算n元，
先把陣列初始為0，陣列[0]設為1，
從面額最小的開始到面額最大的，
依序從該面額開始到n元填入所有的組合情況，
答案就出來了。

重點是從該面額開始到面額n，
然後0元也要考慮，（這樣n -x元若為0才有解）
這裡卡真久，
解釋的不是很好。
sagit的解說滿詳細的，可以看他的。

/* ACM 674 Coin Change
 * mythnc
 * 2011/12/13 13:48:59   
 * run time: 0.036
 */
#include <stdio.h>

#define MAXC 7490
#define COIN 5

void cal(int *);

int main(void)
{
    int ans[MAXC] = { 0 };
    int n;

    cal(ans);

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

    return 0;
}

/* cal: pre calculate answer */
void cal(int *ans)
{
    int i, j;
    int money[] = {1, 5, 10, 25, 50};

    ans[0] = 1;
    for (i = 0; i < COIN; i++)
        for (j = money[i]; j < MAXC; j++)
            ans[j] += ans[j - money[i]];
}

ACM 443 Humble Numbers

ACM136進階版。
不能直接output了，囧。

第一次嘗試用DP解題目，似乎也沒這麼難，
不過要想得到算法。
主要的想法參考於這裡！
真是好厲害！

humble number = (2 ^ w) * (3 ^ x) * (5 ^ y) * (7 ^ z)
用DP的想法是，一開始只有1，1會變成2 3 5 7，
而2 3 5 7各自再乘上2 3 5 7後共有16種組合，
但是沒這麼多，因為有重複的情況。
前項的結果再乘上2 3 5 7，必定也是humble number，
（偉哉DP，好強大）
再繼續深入思考，
若一開始只有1，乘上2 3 5 7之後，取其中最小的一個數值。
這個情況下是2，這樣的話，下次質數2就是從第二個humble number開始乘(即2 * 2），
3 5 7還是要乘第一個質數(即3 * 1 5 * 1 7 * 1)，
接著四個數值繼續做比大小的動作（4 3 5 7相比），
這個情況下是3，所以下次質數3要從第二個humble number開始乘(即3 * 2）
也就是說，每次取完最小的值，
下次該質數就要從下一個humble number做相乘的動作，
因為上一個humble number已經乘完啦！
但還沒結束，還要考慮humble number相同的情況，
例如3 * 5或5 * 3，是一樣的，
所以如果一樣，就必須把3跟5的紀錄次數各 + 1，
意即，每次找到最小值之後，只要是2 3 5 7的乘積與此值相等，
就各要 + 1。

最後要注意ordinal number，以前英文沒學好，-_-，傻傻搞不清楚。
只要十位數是1，都是加th，（不管個位數是不是1 2 3）
其他的情況下，1 2 3分別加st nd rd，
其餘都是th。

/* ACM 443 Humble Numbers
 * mythnc
 * 2011/12/11 21:49:31   
 * run time: 0.012
 */
#include <stdio.h>
#include <string.h>

#define MAXN 5842

void precal(int *);
void output(int, int *);

int main(void)
{
    int ans[MAXN];
    int n;

    precal(ans);

    while (scanf("%d", &n) && n != 0)
        output(n, ans);

    return 0;
}

/* precal: previous calculation the answer */
void precal(int *ans)
{
    int t2, t3, t5, t7;
    int p2, p3, p5, p7, count;

    p2 = p3 = p5 = p7 = 0;
    ans[0] = count = 1;
    while (count < MAXN) {
        t2 = ans[p2] * 2;
        t3 = ans[p3] * 3;
        t5 = ans[p5] * 5;
        t7 = ans[p7] * 7;
        /* find the minimal */
        if (t2 <= t3 && t2 <= t5 && t2 <= t7)
            ans[count] = t2;
        else if (t3 < t2 && t3 <= t5 && t3 <= t7)
            ans[count] = t3;
        else if (t5 < t2 && t5 < t3 && t5 <= t7)
            ans[count] = t5;
        else if (t7 < t2 && t7 < t3 && t7 < t5)
            ans[count] = t7;
        /* if same, prime number have to move to next */
        if (t2 == ans[count])
            p2++;
        if (t3 == ans[count])
            p3++;
        if (t5 == ans[count])
            p5++;
        if (t7 == ans[count])
            p7++;

        count++;
    }
}

/* output: print out the answer in the format */
void output(int n, int *ans)
{
    char number[3];

    if (n % 100 < 10 || n % 100 > 20)
        switch (n % 10) {
            case 1:
                strcpy(number, "st");
                break;
            case 2:
                strcpy(number, "nd");
                break;
            case 3:
                strcpy(number, "rd");
                break;
            default:
                strcpy(number, "th");
        }
    else
        strcpy(number, "th");

    printf("The %d%s humble number is %d.\n", n, number, ans[n - 1]);
}

ACM 640 Self Numbers

反過來做，找到所有的generator，
剩下的就不是generator。

用一個array做mark的動作。

/* ACM 640 Self Numbers
 * mythnc
 * 2011/12/10 20:41:52   
 * run time: 0.08
 */
#include <stdio.h>

#define MAXN  1000001
#define TRUE  1
#define FALSE 0

int sumd(int);

int mark[MAXN];

int main(void)
{
    int i, sum;

    for (i = 1; i < MAXN; i++)
        if (!mark[i]) {
            sum = sumd(i);
            while (sum < MAXN && !mark[sum]) {
                mark[sum] = TRUE;
                sum = sumd(sum);
            }
        }
    /* output */
    for (i = 1; i < MAXN; i++)
        if (!mark[i])
            printf("%d\n", i);

    return 0;
}

/* sumd: do d(n) and return the value */
int sumd(int n)
{
    int sum;

    for (sum = n; n; n /= 10)
        sum += n % 10;

    return sum;
}

ACM 10252 Common Permutation

說是排列組合，其實是要找兩個string中一樣的letter。

加總各個string的letter出現次數，
接著從a to z，若次數不為0，以最小的為主，
輸出字母次數。
直接看code比較清楚 @@

另外，可能會有空白列，所以用fgets()。
(scanf()就WA啦)

/* ACM 10252 Common Permutation
 * mythnc
 * 2011/12/09 08:57:30   
 * run time: 0.012
 */
#include <stdio.h>
#include <string.h>

#define MAXCHAR  1002
#define ALPHABET 26

void countl(char *, int *);
void output(int *, int *);

int main(void)
{
    char line[MAXCHAR];
    int p1[ALPHABET], p2[ALPHABET];

    while (fgets(line, MAXCHAR, stdin)) {
        memset(p1, 0, sizeof(p1));
        countl(line, p1);
        fgets(line, MAXCHAR, stdin);
        memset(p2, 0, sizeof(p2));
        countl(line, p2);
        output(p1, p2);
    }

    return 0;
}

/* countl: count letter numbers */
void countl(char *line, int *p)
{
    int i;

    for (i = 0; i < strlen(line) - 1; i++)
        if (line[i] >= 'a' && line[i] <= 'z')
            p[line[i] - 'a']++;
}

/* output: output result in alphabetical order */
void output(int *p1, int *p2)
{
    int i;

    for (i = 0; i < ALPHABET; i++)
        for (; p1[i] > 0 && p2[i] > 0; p1[i]--, p2[i]--)
                printf("%c", 'a' + i);
    putchar('\n');
}

ACM 10220 I Love Big Numbers !

大數運算乘法，之後做位數加總。

/* ACM 10220 I Love Big Numbers !
 * mythnc
 * 2011/12/08 09:38:23   
 * run time: 0.020
 */
#include <stdio.h>

#define MAXD 2570
#define MAXN 1000

int bigmul(int *, int, int);
int sumdigit(int *, int);

int main(void)
{
    int n, i, digit;
    int answer[MAXN];
    int big[MAXD] = { 1 };
    /* pre calculate */
    for (i = digit = 1; i <= 1000; i++) {
        digit = bigmul(big, i, digit);
        answer[i - 1] = sumdigit(big, digit);
    }

    while (scanf("%d", &n) == 1)
        printf("%d\n", answer[n - 1]);

    return 0;
}

/* bigmul: do big * n, return its digit */
int bigmul(int *big, int n, int digit)
{
    int i;

    for (i = 0; i < digit; i++)
        big[i] *= n;
    /* find new digit */
    if (n < 10)
        digit++;
    else if (n < 100)
        digit += 2;
    else if (n < 1000)
        digit += 3;
    else
        digit += 4;
    /* carry */
    for (i = 0; i < digit; i++)
        if (big[i] > 9) {
            big[i + 1] += big[i] / 10;
            big[i] %= 10;
        }

    while (big[digit] == 0)
        digit--;
    return digit + 1;
}

/* sumdigit: return the sum of digits */
int sumdigit(int *big, int n)
{
    int i, sum;

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

    return sum;
}

ACM 440 Eeny Meeny Moo

同ACM151。

/* ACM 440 Eeny Meeny Moo
 * mythnc
 * 2011/12/07 08:07:57   
 * run time: 0.068
 */
#include <stdio.h>

#define MAXN 149

typedef struct list {
    int i;
    struct list *next;
    struct list *pre;
} List;

void init(List *);
int findm(List *, int);
void link(List *, int);

int main(void)
{
    List array[MAXN];
    int n, i;
    int ans[MAXN];

    init(array);

    for (i = 3; i < MAXN + 1; i++)
        ans[i - 1] = findm(array, i);

    while (scanf("%d", &n) && n != 0)
        printf("%d\n", ans[n - 1]);

    return 0;
}

/* init: initialize array */
void init(List *array)
{
    int i;

    for (i = 0; i < MAXN; i++)
        array[i].i = i + 1;
}

/* findm: find and return the number m */
int findm(List *ary, int n)
{
    int count, i, m;
    List *p;

    for (m = 2; ; m++) {  /* find m */
        link(ary, n);     /* link all again */
        p = ary;
        count = 1;
        while (count < n) {
            p->pre->next = p->next;  /* link arrange */
            p->next->pre = p->pre;
            for (i = 0; i < m; i++)  /* move */
                p = p->next;
            count++;
            if (p->i == 2)
                break;
        }
        if (count == n)
            return m;
    }
}

/* link: link array elements one by one
 * in a circle */
void link(List *p, int n)
{
    int i;

    p[0].next = &p[1];
    p[0].pre = &p[n - 1];
    for (i = 1; i < n; i++) {
        p[i].next = &p[(i + 1) % n];
        p[i].pre = &p[i - 1];
    }
}

ACM 834 Continued Fractions

做輾轉相除法！

/* ACM 834 Continued Fractions
 * mythnc
 * 2011/12/06 12:05:34   
 * run time: 0.012
 */
#include <stdio.h>

#define MAXK 1000

int cal(int, int, int *, int);
void print(int *, int);

int main(void)
{
    int a, b, count;
    int answer[MAXK];

    while (scanf("%d %d", &a, &b) == 2) {
        count = 0;
        if (a < b)
            answer[count++] = 0;
        count = cal(a, b, answer, count);
        print(answer, count);
    }

    return 0;
}

/* cal: find n and save it in ans
 * return the numbers */
int cal(int a, int b, int *ans, int count)
{
    while (a != 0 && b != 0)
        if (a > b) {
            ans[count++] = a / b;
            a %= b;
        }
        else {
            ans[count++] = b / a;
            b %= a;
        }

    return count;
}

/* print: print out result */
void print(int *ans, int n)
{
    int i;

    if (n == 1) {
        printf("[%d]\n", ans[0]);
        return;
    }
    printf("[%d;%d", ans[0], ans[1]);
    for (i = 2; i < n; i++) {
        printf(",%d", ans[i]);
    }
    printf("]\n");
}

ACM 118 Mutant Flatworld Explorers

模擬題。
我用0~3代表NESW。
遇到R就+1，L就-1。
活路就直接移動
死路的話判斷有無mark過。
有mark，不移動；
沒mark，output。

邊界問題WA一次 orz。

/* ACM 118 Mutant Flatworld Explorers
 * mythnc
 * 2011/12/05 14:23:59   
 * run time: 0.008
 */
#include <stdio.h>

#define MAXCO   51  /* 0 to 50 */
#define MAXCHAR 101
#define TRUE    1
#define FALSE   0
#define RANGE(X, Y) X >= 0 && X <= Y

typedef struct robot {
    int row, col, dir;
} Robot;

int ctoi(char);
int takeorder(Robot *, char *, int (*)[]);
int changedir(int);
void output(Robot);

int row, col;

int main(void)
{
    int fall;
    int mark[MAXCO][MAXCO] = { FALSE };
    char dir;
    char order[MAXCHAR];
    Robot ro;

    scanf("%d %d", &col, &row);
    while (scanf("%d %d %c", &ro.col, &ro.row, &dir) == 3) {
        getchar(); /* eat newline */
        scanf("%s", order);
        getchar(); /* eat newline */
        ro.dir = ctoi(dir);
        fall = takeorder(&ro, order, mark);
        output(ro);
        if (fall)
            printf(" LOST");
        putchar('\n');
    }

    return 0;
}

/* coti: convert c to correspond int
 * and return it */
int ctoi(char c)
{
    switch (c) { /* NESW <=> 0123 */
        case 'N':
            return 0;
        case 'E':
            return 1;
        case 'S':
            return 2;
        case 'W':
            return 3;
    }
}

/* takeorder: take the order,
 * do the correspond action,
 * and return fall or not */
int takeorder(Robot *ro, char *order, int (*mark)[MAXCO])
{
    int i, fall, nextr, nextc;
    int movec[] = {0, 1, 0, -1};
    int mover[] = {1, 0, -1, 0};

    for (fall = FALSE, i = 0; order[i] != '\0'; i++) {
        switch (order[i]) {
            case 'R':
                ro->dir = changedir(ro->dir + 1);
                break;
            case 'L':
                ro->dir = changedir(ro->dir - 1);
                break;
            case 'F':
                nextr = ro->row + mover[ro->dir];
                nextc = ro->col + movec[ro->dir];
                if (RANGE(nextc, col) && RANGE(nextr, row)) {
                    ro->col = nextc;
                    ro->row = nextr;
                }
                else if (!mark[ro->row][ro->col]){
                    mark[ro->row][ro->col] = TRUE;
                    fall = TRUE;
                }
        }
        if (fall)
            return fall;
    }

    return fall;
}

/* changedir: change the direction of ro */
int changedir(int dir)
{
    if (dir > 3)
        return dir % 4;
    else if (dir < 0)
        return dir + 4;
    return dir;
}

/* output: the information of robot */
void output(Robot ro)
{
    char s[] = "NESW";

    printf("%d %d %c", ro.col, ro.row, s[ro.dir]);
}

ACM 10970 Big Chocolate

奇怪的題目，應該是出錯吧？
2 2最少刀是2刀。
不過照他的測資給他答案是3刀。
這樣也沒什麼好算的，直接output答案。

/* ACM 10970 Big Chocolate
 * mythnc
 * 2011/12/05 13:32:12   
 * run time: 0.040
 */
#include <stdio.h>

int main(void)
{
    int m, n;

    while (scanf("%d %d", &m, &n) == 2)
        printf("%d\n", m * n - 1);

    return 0;
}

ACM 10424 Love Calculator

先對字串做mapping，之後可以得到number，
若number >= 10，需要再做mapping。
直到number < 10為止。

因為要算比例，不能超過100%。
所以會是a / b或b / a其中一種。
端看b > a或a > b。

/* ACM 10424 Love Calculator
 * mythnc
 * 2011/12/03 09:29:34   
 * run time: 0.004
 */
#include <stdio.h>

#define MAXCHAR 27 /* 25 + '\n' + '\0' */

double value(char *);
int onedigit(int);

int main(void)
{
    char name[2][MAXCHAR];
    double v[2];
    int i;

    while (fgets(name[0], MAXCHAR, stdin)) {
        fgets(name[1], MAXCHAR, stdin);
        for (i = 0; i < 2; i++)
            v[i] = value(name[i]);
        if (v[0] >= v[1])
            printf("%.2f %%\n", 100 * v[1] / v[0]);
        else
            printf("%.2f %%\n", 100 * v[0] / v[1]);
    }

    return 0;
}

/* value: return the value of name */
double value(char *s)
{
    int i, sum;

    for (i = sum = 0; s[i] != '\n'; i++)
        if (s[i] >= 'a' && s[i] <= 'z')
            sum += s[i] - 'a' + 1;
        else if (s[i] >= 'A' && s[i] <= 'Z')
            sum += s[i] - 'A' + 1;

    while (sum > 9)
        sum = onedigit(sum);

    return (double)sum;
}

/* onedigit: make sure n is one digit */
int onedigit(int n)
{
    int sum;

    for (sum = 0; n != 0;) {
        sum += n % 10;
        n /= 10;
    }

    return sum;
}

ACM 713 Adding Reversed Numbers

題目寫得烙烙長其實只是做大數運算加法。
先扣掉尾端的0，之後就能直接做加法。
做完加法之後，最前端的0也不要輸出即可。

練習寫虛擬碼看看……
eat token1 token2
cutouttrailingzero(token1)
cutouttrailingzero(token2)
sum = sumbig(token1 token2)
cutoutleadingzero(sum)
print(sum)

/* ACM 713 Adding Reversed Numbers
 * mythnc
 * 2011/12/02 12:34:53   
 * run time: 0.008
 */
#include <stdio.h>
#include <string.h>

#define MAXD 201

void ignorezero(char *, int);
int bigsum(char (*)[], int *);
void print(int *, int);

int main(void)
{
    char v[2][MAXD];
    int sum[MAXD];
    int i, digit;

    scanf("%*d");
    while (scanf("%s %s", v[0], v[1]) == 2) {
        for (i = 0; i < 2; i++)
            ignorezero(v[i], strlen(v[i]) - 1);
        memset(sum, 0, sizeof(sum));
        digit = bigsum(v, sum);
        print(sum, digit);
    }

    return 0;
}

/* ignorezero: cutting of trailing zero */
void ignorezero(char *s, int i)
{
    while (s[i] == '0')
        i--;

    s[i + 1] = '\0';
}

/* bigsum: do v[0] + v[1] = sum,
 * return sum's digit */
int bigsum(char (*v)[MAXD], int *sum)
{
    int i, j;

    for (i = 0; i < strlen(v[0]) && i < strlen(v[1]); i++)
        sum[i] += v[0][i] - '0' + v[1][i] - '0';
    for (; i < strlen(v[0]); i++)
        sum[i] += v[0][i] - '0';
    for (; i < strlen(v[1]); i++)
        sum[i] += v[1][i] - '0';
    /* carry */
    for (j = 0; j < i; j++)
        if (sum[j] > 9) {
            sum[j + 1] += sum[j] / 10;
            sum[j] %= 10;
        }

    if (sum[j] != 0)
        return j + 1;
    return j;
}

/* print: print out result */
void print(int *sum, int n)
{
    int i;
    /* do not print out leading zeros */
    for (i = 0; sum[i] == 0; i++)
        ;
    for (; i < n; i++)
        printf("%d", sum[i]);
    putchar('\n');
}

ACM 305 Joseph

「before the first good guy」，
有兩個意思：
(a)排在好人列裡第一個好人，
(b)所有好人中的第一個好人。
本題採用(b)，翻成國語就是
所有的好人都不能被殺死啦！

用ACM 151的方法去解，
但是不管演算法再怎麼修，
從k = 1算到k = 13都要花10秒的時間。
最後只好先算好答案再上傳了，囧。

後來參考別人的算法，
發現一招很厲害可以直接算的算則。

因為好人一定是前k個，壞人一定是最後的k個。
（共2k個）。
所以每次數完人頭後，m一定要是第k + 1個之後的數值，
否則就會殺到好人。
以k = 3為例，m直接用5代入。
0 1 2 3 4 5
g g g b b b
從0開始 + 5 - 1，為4，
4不為好人，之後刪掉一個壞人繼續做運算。
0 1 2 3 4
g g g b b
4 + (5 - 1) = 8
8 % 5(現有人口） = 3
3也不為好人，再刪掉一個壞人繼續做運算。
0 1 2 3
g g g b
3 + (5 - 1) = 7
7 % 4(現有人口) = 3
3也不為好人，再刪掉一個壞人。
現有人口為3，即k值。
表示當人口為k值時，即可停止運算，會傳m值。
當loop結束，而人口不為k值，表示殺錯人了，
m + 1從頭繼續運算。
真是好威的方法！

TLE code就不貼了。
用linked list移來移去好蠢，囧。

/* ACM 305 Joseph
 * mythnc
 * 2011/12/01 14:33:02   
 * version 2
 * run time: 0.076
 */
#include <stdio.h>

#define MAX 13

int findm(int);

int main(void)
{
    int k, i;
    int answer[MAX];

    for (i = 0; i < MAX; i++)
        answer[i] = findm(i + 1);

    while (scanf("%d", &k) && k != 0)
        printf("%d\n", answer[k - 1]);

    return 0;
}

/* findm: return minimum m */
int findm(int k)
{
    int m, re, position;

    for (m = k + 1; ; m++) {
        for (position = 0, re = 2 * k; re > k; re--) {
            position = (position + m - 1) % re;
            if (position < k)
                break;
        }
        if (re == k)
            return m;
    }
}

從1開始的版本寫完發現還是從0開始好 = =。

int findm(int k)
{
    int m, re, position;

    for (m = k + 1; ; m++) {
        for (re = 2 * k, position = 0; re > k; re--) {
            if (position == 0)
                position = m % re;
            else
                position = (position + m - 1) % re;
            if (position <= k && position != 0)
                break;
        }
        if (re == k)
            return m;
    }
}