ACM 739 Soundex Indexing

做map跟處理output。

先讓soundex與字母做map。
不處理map後為0跟map後與前一個字母有相同map值的情況。
output要特別處理一下，值得一提的是：
printf("%*s\n", max, s);
max對應*，s對應s。
如此可以自由控制縮排。

/* ACM 739 Soundex Indexing
 * mythnc
 * 2012/01/04 11:35:35   
 * run time: 0.024
 */
#include <stdio.h>
#include <string.h>

#define LINEMAX 20

void map(char *, char *);

int main(void)
{
    char name[LINEMAX];
    char encode[5];

    printf("%9c%s%*c%s\n", ' ', "NAME", 25 - strlen("NAME"), ' ', "SOUNDEX CODE");
    while (scanf("%s", name) == 1) {
        map(name, encode);
        printf("%9c%s%*c%s\n", ' ', name, 25 - strlen(name), ' ', encode);
    }
    printf("%19c%s\n", ' ', "END OF OUTPUT");

    return 0;
}

/* map: map name to its correspond code */
void map(char *name, char *encode)
{
    int i, j;
    int table[26] = {0, 1, 2, 3, 0,
                     1, 2, 0, 0, 2,
                     2, 4, 5, 5, 0,
                     1, 2, 6, 2, 3,
                     0, 1, 0, 2, 0,
                     2};

    encode[0] = name[0];
    for (i = 1, j = 1; j < strlen(name) && i < 4; j++) {
        if (table[name[j] - 'A'] == 0
            || table[name[j] - 'A'] == table[name[j - 1] - 'A'])
            continue;
        encode[i++] = table[name[j] - 'A'] + '0';
    }
    while (i < 4)
        encode[i++] = '0';
    encode[i] = '\0';
}

ACM 661 Blowing Fuses

直接做……就只是個算安培……
開關打開要紀錄最高安培數即可。

/* ACM 661 Blowing Fuses
 * mythnc
 * 2012/01/03 23:17:33   
 * run time: 0.004
 */
#include <stdio.h>

#define MAXN 20
#define ON   1
#define OFF  0

typedef struct device {
    int state;
    int c;
} Device;

int maxpower(int, int);

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

    set = 0;
    while (scanf("%d %d %d", &n, &m, &c) && n != 0) {
        max = maxpower(n, m);
        if (max > c)
            printf("Sequence %d\nFuse was blown.\n\n", ++set);
        else {
            printf("Sequence %d\nFuse was not blown.\n", ++set);
            printf("Maximal power consumption was %d amperes.\n\n", max);
        }
    }

    return 0;
}

/* maxpower: return the max consumption power
 * during the sequence*/
int maxpower(int n, int m)
{
    int max, i, number, sum;
    Device dev[MAXN];
    /* init */
    for (i = 0; i < n; i++) {
        scanf("%d", &dev[i].c);
        dev[i].state = OFF;
    }
    /* switch start */
    for (i = max = sum = 0; i < m; i++) {
        scanf("%d", &number);
        if (dev[number - 1].state == ON) {
            dev[number - 1].state = OFF;
            sum -= dev[number - 1].c;
        }
        else {
            dev[number - 1].state = ON;
            sum += dev[number - 1].c;
            if (max < sum)
                max = sum;
        }
    }

    return max;
}

ACM 10420 List of Conquests

有點像千人斬 XD

兩種情況：
愛人可能重複或不重複。
如果不會重複，直接做binary search tree就可以了；
如果會重複除了binary search tree之外，還要對名字做紀錄。

token的處理，我用sscanf()先吃掉一個，再用strcpy()把第一個以後的往前copy。
因為不知道資料有多少筆，就用動態的方式存資料。
沒特別針對名字做最佳化，如果sort後再用binary search理當快一點。

最後其實資料是不會重複的，所以直接做binary search tree就好了。

/* ACM 10420 List of Conquests
 * mythnc
 * 2012/01/03 10:19:51   
 * run time: 0.016
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define LINEMAX 80
#define MAXCHAR 20

typedef struct woman {
    char *name;
    struct woman *next;
} Woman;

typedef struct node {
    char country[MAXCHAR];
    int count;
    Woman *list;
    struct node *left, *right;
} Tnode;

void token(char *, char *);
Tnode *addtree(Tnode *, char *, char *);
Woman *addwoman(Woman *, char *, int *);
void printtree(Tnode *);
void freetree(Tnode *);

int main(void)
{
    char name[LINEMAX];
    char country[MAXCHAR];
    Tnode *root;

    root = NULL;
    scanf("%*d");
    getchar();
    while (fgets(name, LINEMAX, stdin)) {
        token(country, name);
        root = addtree(root, country, name);
    }
    printtree(root);
    freetree(root);

    return 0;
}

/* token: split name to country and woman name */
void token(char *country, char *name)
{
    char *pt;

    sscanf(name, "%s", country);
    pt = name + strlen(country);
    while (*pt == ' ')
        pt++;
    strcpy(name, pt);
    pt = name + strlen(name);
    while (*(pt - 1) == '\n' || *(pt - 1) == ' ')
        pt--;
    *pt = '\0';
}

/* addtree: add country and name into bin search tree */
Tnode *addtree(Tnode *pt, char *country, char *name)
{
    int i;

    if (pt == NULL) {
        pt = (Tnode *)malloc(sizeof(Tnode));
        strcpy(pt->country, country);
        pt->left = pt->right = NULL;
        pt->count = 0;
        pt->list = NULL;
        pt->list = addwoman(pt->list, name, &pt->count);
    }
    else if ((i = strcmp(country, pt->country)) == 0)
        pt->list = addwoman(pt->list, name, &pt->count);
    else if (i < 0)
        pt->left = addtree(pt->left, country, name);
    else
        pt->right = addtree(pt->right, country, name);

    return pt;
}

/* addwoman: add woman name into list */
Woman *addwoman(Woman *head, char *name, int *count)
{
    Woman *pt;

    for (pt = head; pt; pt = pt->next)
        if (strcmp(pt->name, name) == 0)
            return head;

    pt = (Woman *)malloc(sizeof(Woman));
    pt->next = NULL;
    pt->name = (char *)malloc(strlen(name) + 1);
    strcpy(pt->name, name);
    ++*count;
    
    return head;
}

/* printtree: print out bin search tree */
void printtree(Tnode *pt)
{
    if (pt == NULL)
        return;

    printtree(pt->left);
    printf("%s %d\n", pt->country, pt->count);
    printtree(pt->right);
}

/* freetree: free() all nodes */
void freetree(Tnode *pt)
{
    Woman *tmp;

    if (pt == NULL)
        return;

    freetree(pt->left);
    freetree(pt->right);
    while (pt->list) {
        tmp = pt->list;
        pt->list = pt->list->next;
        free(tmp->name);
        free(tmp);
    }
    free(pt);
}

ACM 10195 The Knights Of The Round Table

利用海龍公式與內接圓半徑公式，
就可求得半徑r。

內接圓半徑 = 2 * S / (a + b + c)
p = (a + b + c) / 2代入，S用海龍代入。
化簡可得
√[(p - a) * (p - b) * (p - c) / p]。

唯一要注意的是，input可能為0，
這時候不構成三角形，因此也沒有所謂的內接圓半徑。
(WTF)

/* ACM 10195 The Knights Of The Round Table
 * mythnc
 * 2012/01/02 09:56:51   
 * run time: 0.008
 */
#include <stdio.h>
#include <math.h>

double radius(double, double, double);

int main(void)
{
    double a, b, c;

    while (scanf("%lf %lf %lf", &a, &b, &c) == 3)
        printf("The radius of the round table is: %.3f\n", radius(a, b, c));

    return 0;
}

double radius(double a, double b, double c)
{
    double p;
    
    if (a == 0.0 || b == 0.0 || c == 0.0)
        return 0.0;

    p = (a + b + c) / 2.0;

    return sqrt((p - a) * (p - b) * (p - c) / p);
}

ACM 408 Uniform Generator

complete search。
從0到mod - 1，探訪過的就做紀錄，
到第二次探訪時就停止。
比對探訪次數是否等於m即可。

法2：求step與mod是否互質也可。

/* ACM 408 Uniform Generator
 * mythnc
 * 2012/01/01 10:07:53   
 * run time: 0.068
 */
#include <stdio.h>
#include <string.h>

#define MAXMOD 10000000
#define TRUE   1
#define FALSE  0

int complete(int, int);

int visited[MAXMOD];

int main(void)
{
    int step, mod;

    while (scanf("%d %d", &step, &mod) == 2)
        if (complete(step, mod))
            printf("%10d%10d    Good Choice\n\n", step, mod);
        else
            printf("%10d%10d    Bad Choice\n\n", step, mod);

    return 0;
}

/* complete: return TRUE if s and m will
 * generate all numbers between 0 to m - 1
 * else return FALSE */
int complete(int s, int m)
{
    int count, x;

    s %= m;
    x = count = 0;
    while (!visited[x]) {
        visited[x] = TRUE;
        count++;
        x = (x + s) % m;
    }
    memset(visited, 0, sizeof(int) * m);

    if (count == m)
        return TRUE;
    return FALSE;
}