USACO Calf Flac

Longest Palindromic Substring。
不過很gy的是還限制只能比對字母。
是說也可以用暴力枚舉解……。
Z Algorithm真是很威……

/*
ID: mythnc2
LANG: C
TASK: calfflac
2012/01/10 16:44:34   
*/
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 20010
#define MIN(X, Y) (X <= Y ? X : Y)

int find(int);
int init(int);
int match(int, int, int);
void print(FILE *, int);

char t[MAX];
char s[MAX * 2];
int z[MAX * 2];

int main (void)
{
    FILE *fin, *fout;
    int c, i, n;

    fin = fopen("calfflac.in", "r");
    fout = fopen("calfflac.out", "w");

    i = 0;
    while ((c = fgetc(fin)) != EOF)
        t[i++] = c;
    t[i] = '\0';

    n = find(i);
    print(fout, n);

    fclose(fin);
    fclose(fout);

    return 0;
}

/* find: find maximum palindrome substring */
int find(int n)
{
    int i, mirror, border, center, right;

    n = init(n);

    /* modified z Algorithm */
    center = right = 0;
    for (i = z[0] = 1; i < n; i++)
        if (i > right) {
            z[i] = match(i, i, n);
            center = i;
            right = i + z[i] - 1;
        }
        else {
            mirror = center - (i - center);
            border = right - i + 1;
            if (z[mirror] == border) {
                z[i] = border + match(i - border, i + border, n);
                center = i;
                right = i + z[i] - 1;
            }
            else
                z[i] = MIN(z[mirror], border);
        }

    return n;
}

/* init: initialize s */
int init(int n)
{
    int i, j;

    memset(s, '.', sizeof(s));
    for (i = j = 0; i < n; i++)
        if (isalpha(t[i])) {
            s[2 * j + 1] = tolower(t[i]);
            j++;
        }

    return 2 * j + 1;
}

/* match: from s[a] to left and from s[b] to right
 * do char compare symmetrically */
int match(int a, int b, int n)
{
    int i;

    i = 0;
    while (a - i >= 0 && b + i < n && s[a - i] == s[b + i])
        i++;

    return i;
}

/* print: print out result */
void print(FILE *fout, int n)
{
    int i, j, pos, from, to, k;

    /* find max len */
    for (i = 1, pos = 0; i < n; ++i)
        if (z[i] > z[pos])
            pos = i;

    /* remove '.' */
    i = pos - (z[pos] - 1);
    if (!(i & 1))
        i++;
    for (n = 0; i <= pos + z[pos] - 1; i += 2, n++)
        s[n] = s[i];

    /* print out len */
    fprintf(fout, "%d\n", n);
    /* print out substring */
    for (i = j = from = to = 0; i < strlen(t); i++)
        if (isalpha(t[i]) && tolower(t[i]) == s[j]) {
            from = k = i;
            while (tolower(t[k]) == s[j] && j < n && k < strlen(t)) {
                j++, k++;
                to = k;
                while (!isalpha(t[k]) && k < strlen(t))
                    k++;
            }
            if (j == n)
                break;
            else
                j = from = to = 0;
        }
    for (i = from; i < to; i++)
        fprintf(fout, "%c", t[i]);
    putc('\n', fout);
}

USACO Barn Repair

被婊到……
USACO的Greedy Algorithm說明文寫得根本不是Greedy Algorithm……
什麼求n = 5時先求n = 4的最佳解，害我想到DP去。
（因為n = 4的最佳解必定是n = 3的最佳解……根本就是從n = 1往上推的意思）

如果演算法正確還ok，
問題是DP的code到測資第5組就gg惹 =.=。
你說這不會讓人想殺人嗎？

其實也不用管什麼Greedy不Greedy的，
直接想作法還比較實際……
Greedy Algorithm這名詞真是抽象無比。

先對C做sort。
接著算出每個C之間的間距，一樣sort。
再計算只用1塊板子的長度Len，
當m = 1表示用1塊板子，Len就是答案。
m = 2時，Len要減去最大間距，
m = 3時，Len要減去最大間距與次大間距。
若m >= C，直接output C。
其實就這樣而已……

另外fopen本來就要fclose吧？
USACO的code從不做fclose，
無言。

盡信書不如無書。
一堆google別人想的解法還比USACO的好太多了 = =。

/*
ID: mythnc2
LANG: C
TASK: barn1
barn repair
2011/11/16 16:21:20   
*/
#include <stdio.h>
#include <stdlib.h>

#define MAXARY 200

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

int main (void)
{
    FILE *fin, *fout;
    int n, nc, i, sum;
    int ary[MAXARY], diff[MAXARY];

    fin = fopen("barn1.in", "r");
    fout = fopen("barn1.out", "w");

    fscanf(fin, "%d %*d %d", &n, &nc);
    for (i = 0; i < nc; i++)
        fscanf(fin, "%d", ary + i);

    if (n < nc) {
        qsort(ary, nc, sizeof(int), cmp);
        for (i = 0; i < nc - 1; i++)
            diff[i] = ary[i + 1] - ary[i] - 1;
        qsort(diff, nc - 1, sizeof(int), cmp);
        sum = ary[nc - 1] - ary[0] + 1;
        for (i = nc - 2; n > 1 ; i--, n--)
            sum -= diff[i];
        fprintf(fout, "%d\n", sum);
    }
    else
        fprintf(fout, "%d\n", nc);

    fclose(fin);
    fclose(fout);
    return 0;
}

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

USACO Mixing Milk

原來這種算則就叫greedy algorithm……

每次找最便宜的milk，
接著確認amount供應是否正常，
反覆此二步驟，直到滿足amount量，
輸出金額。

先做sort好像會比較好一點……

/*
ID: mythnc2
LANG: C
TASK: milk
Mixing Milk
2011/11/14 21:57:02
*/
#include <stdio.h>

#define MAXF 5000

typedef struct provider {
    int price;
    int amount;
} Provider;

int findmin(Provider *, int);
int checkamount(Provider, int);

int main (void)
{
    FILE *fin, *fout;
    int amount, farmer, i, sum, min, quan;
    Provider milk[MAXF];

    fin = fopen("milk.in", "r");
    fout = fopen("milk.out", "w");

    fscanf(fin, "%d %d", &amount, &farmer);
    for (i = 0; i < farmer; i++)
        fscanf(fin, "%d %d", &milk[i].price, &milk[i].amount);

    for (sum = 0; amount; milk[min].price = 1001) {
        min = findmin(milk, farmer);
        quan = checkamount(milk[min], amount);
        sum += quan * milk[min].price;
        amount -= quan;
    }

    fprintf(fout, "%d\n", sum);

    return 0;
}

/* findmin: return the minimum milk.price element */
int findmin(Provider *milk, int n)
{
    int i, min;

    for (i = 1, min = 0; i < n; i++)
        if (milk[i].price < milk[min].price)
            min = i;

    return min;
}

/* checkamount: return the milk.amount provide
 * actually */
int checkamount(Provider milk, int amount)
{
    if (milk.amount > amount)
        return amount;

    return milk.amount;
}

USACO Dual Palindromes

跟Palindromic Squares類似。
要注意S雖然有範圍，
但主要是求出N的個數，
個數有可能超過S的範圍。

/*
ID: mythnc2
LANG: C
TASK: dualpal
Dual Palindromes
2011/11/14 20:30:40   
*/
#include <stdio.h>
#include <string.h>

#define MAXCHAR 15
#define TRUE    1
#define FALSE   0

void conversion(int, int, char *);
int pal(char *);

int main (void)
{
    FILE *fin, *fout;
    int n, s, i, j, count;
    char t[MAXCHAR];

    fin = fopen("dualpal.in", "r");
    fout = fopen("dualpal.out", "w");

    fscanf(fin, "%d %d", &n, &s);

    for (i = s + 1; n; i++)
        for (count = 0, j = 2; j < 11; j++) {
            conversion(j, i, t);
            if (pal(t))
                count++;
            if (count > 1) {
                fprintf(fout, "%d\n", i);
                n--;
                break;
            }
        }

    return 0;
}

/* conversion: conver n in base of b,
 * save in t */
void conversion(int b, int n, char *t)
{
    int i, mod;
    char map[] = "0123456789";

    for (i = 0; n; i++) {
        t[i] = map[n % b];
        n /= b;
    }
    t[i] = '\0';
}

/* pal: if t is palindrome return TRUE,
 * else return FALSE */
int pal(char *t)
{
    int i, j;

    for (i = 0, j = strlen(t) - 1; i < j; i++, j--)
        if (t[i] != t[j])
            return FALSE;

    return TRUE;
}

USACO Palindromic Squares

印出平方次為回文的數字與該平方，
有趣的題目。
跟上一題一樣，可以一次一個慢慢判斷平方次，
也可以一次判斷完300個平方。
竟然是回文，最中間的數就不用判斷，
也不用作reverse，倒是數字輸出要reverse。
數字跟平方數都要依照base去做輸出。

/*
ID: mythnc2
LANG: C
TASK: palsquare
Palindromic Squares
2011/11/08 11:09:53   
*/
#include <stdio.h>
#include <string.h>

#define MAXN    300
#define MAXCHAR 20
#define TRUE    1
#define FALSE   0

void conversion(int, int, char *);
void reverse(char *);
int pal(char *);

int main (void)
{
    FILE *fin, *fout;
    int base, i;
    char trans[MAXCHAR];
    char number[MAXCHAR];

    fin = fopen("palsquare.in", "r");
    fout = fopen("palsquare.out", "w");

    fscanf(fin, "%d", &base);

    for (i = 0; i < MAXN; i++) {
        conversion(base, (i + 1) * (i + 1), trans);
        /* output */
        if (pal(trans)) {
            conversion(base, i + 1, number);
            reverse(number);
            fprintf(fout, "%s %s\n", number, trans);
        }
    }
    return 0;
}

/* conversion: conver n in base of b save in t */
void conversion(int b, int n, char *t)
{
    int i, mod;
    char map[] = "0123456789ABCDEFGHIJ";

    /* n conversion */
    for (i = 0; n; i++) {
        t[i] = map[n % b];
        n /= b;
    }
    t[i] = '\0';
}

/* reverse: reverse string 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;
    }
}

/* pal: return TRUE if array t is palindrome,
 * else return FALSE */
int pal(char *t)
{
    int i, j;

    for (i = 0, j = strlen(t) - 1; i < j; i++, j--)
        if (t[i] != t[j])
            return FALSE;

    return TRUE;
}

USACO Name That Number

第一次遇到開檔問題……
把字典的字母轉成數字並做排序，
出現Q或Z不做轉換。
再把輸入檔的數字，
從字典檔裡做match，
找到就可以output。

本來想用qsort，但是數字相同時，
qsory會重排，所以只好自己寫個sort。

不過這種方法好笨啊！
寫完看到它的分析才知道，
反過來做比較快！
直接從輸入檔的數字，
跟字典的字母做比較，
比較時才把字母轉成數字，
發現沒match，就再找下一個字母，
直到找到為止。

不過這兩種方法有好有壞……
像我就是一次先弄完，之後輸入的數字就可以直接找。
它的作法是每次都從字典的開頭往後找。

不過這題，因為輸入檔只有一筆數字，
所以用它的方法滿不錯的。
資料多筆的話就未必囉！

這大概是USACO跟UVA最大差異，
測資的處理方式不同。

/*
ID: mythnc2
LANG: C
TASK: namenum
Name That Number
2011/11/07 21:10:16   
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN    5000
#define MAXCHAR 12
#define TRUE    1
#define FALSE   0

typedef struct name {
    long long number;
    char name[MAXCHAR];
} Name;

int screen(char *);
void copy(Name *, char *);
void sort(Name *, int);
int cton(char);
int find(long long, Name *, int);
void printout(FILE *, int, Name *, int);

int main (void)
{
    FILE *fin, *fout, *fdict;
    char str[MAXCHAR + 1];
    Name cow[MAXN];
    int count, index;
    long long serial;

    fin = fopen("namenum.in", "r");
    fout = fopen("namenum.out", "w");
    fdict = fopen("dict.txt", "r");

    count = 0;
    while (fscanf(fdict, "%s", str) != EOF) {
        if (screen(str))
            continue;
        copy(&cow[count++], str);
        sort(cow, count);
    }

    fscanf(fin, "%lld", &serial);

    if ((index = find(serial, cow, count)) > -1)
        printout(fout, index, cow, count);
    else
        fprintf(fout, "NONE\n");

    return 0;
}

/* screen: if letter has Q or Z,
 * jump over it */
int screen(char *s)
{
    for (; *s != '\0'; s++)
        if (*s == 'Q' || *s == 'Z')
            return TRUE;

    return FALSE;
}

/* copy: copy the letter and number of s
 * to cow */
void copy(Name *cow, char *s)
{
    int i;

    /* copy letters */
    strcpy(cow->name, s);
    /* make letter to number */
    for (cow->number = i = 0; s[i] != '\0'; i++) {
        if (i > 0)
            cow->number *= 10;
        cow->number += cton(s[i]);
    }
}

/* sort: insertion sort array cow */
void sort(Name *cow, int n)
{
    int i;
    Name tmp;

    if (n < 2)
        return;

    tmp = cow[n - 1];
    for (i = n - 2; i > -1; i--)
        if (cow[i].number > tmp.number) {
            cow[i + 1] = cow[i];
            if (i == 0)
                cow[i] = tmp;
        }
        else {
            cow[i + 1] = tmp;
            break;
        }
}

/* cton: cast char to number */
int cton(char c)
{
    char letter[24] = {'A', 'B', 'C',
                       'D', 'E', 'F',
                       'G', 'H', 'I',
                       'J', 'K', 'L',
                       'M', 'N', 'O',
                       'P', 'R', 'S',
                       'T', 'U', 'V',
                       'W', 'X', 'Y'};
    int i;

    for (i = 0; i < 24; i++)
        if (c == letter[i])
            return 2 + i / 3;
}


/* find: find number in array cow
 * if find return index,
 * else return -1 */
int find(long long number, Name *cow, int n)
{
    int head, mid, tail;

    head = 0;
    tail = n - 1;
    while (head <= tail) {
        mid = (head + tail) / 2;
        if (cow[mid].number < number)
            head = mid + 1;
        else if (cow[mid].number > number)
            tail = mid - 1;
        else
            return mid;
    }

    return -1;
}

/* printout: print out result */
void printout(FILE *f, int i, Name *cow, int n)
{
    /* find the first same value number */
    while (cow[i - 1].number == cow[i].number && i - 1 >= 0)
        i--;
    /* print out */
    fprintf(f, "%s\n", cow[i].name);
    while (cow[i + 1].number == cow[i].number && i + 1 < n) {
        i++;
        fprintf(f, "%s\n", cow[i].name);
    }
}

USACO Transformations

直接做。
果然是個complete search，
也只能直接做。

/*
ID: mythnc2
LANG: C
TASK: transform
2011/11/04 22:41:28   
Transformations
*/
#include <stdio.h>

#define MAXN 10
#define TRUE  1
#define FALSE 0

int menu(char (*)[], char (*)[], int);
int de90(char (*)[], char (*)[], int);
int de180(char (*)[], char (*)[], int);
int de270(char (*)[], char (*)[], int);
void reflect(char (*)[], char (*)[], int);
int equal(char (*)[], char (*)[], int);

int main (void)
{
    FILE *fin, *fout;
    int n, i;
    char sq[MAXN][MAXN + 1], trans[MAXN][MAXN + 1];

    fin = fopen("transform.in", "r");
    fout = fopen("transform.out", "w");

    fscanf(fin, "%d", &n);
    for (i = 0; i < n; i++)
        fscanf(fin, "%s", sq[i]);
    for (i = 0; i < n; i++)
        fscanf(fin, "%s", trans[i]);
    fprintf(fout, "%d\n", menu(sq, trans, n));
    return 0;
}

/* menu: return one of the possible transformation */
int menu(char (*sq)[MAXN + 1], char (*trans)[MAXN + 1], int n)
{
    char mirror[MAXN][MAXN + 1];

    if (de90(sq, trans, n))
        return 1;

    if (de180(sq, trans, n))
        return 2;

    if (de270(sq, trans, n))
        return 3;

    reflect(sq, mirror, n);
    if (equal(mirror, trans, n))
        return 4;

    if (de90(mirror, trans, n) || de180(mirror, trans, n)
        || de270(mirror, trans, n))
        return 5;

    if (equal(sq, trans, n))
        return 6;

    return 7;
}

/* de90: if sq rotate 90 degree is trans return True */
int de90(char (*sq)[MAXN + 1], char (*trans)[MAXN + 1], int n)
{
    int i, j;

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (sq[i][j] != trans[j][n - 1 - i])
                return FALSE;

    return TRUE;
}

/* de180: if sq rotate 180 degree is trans return True */
int de180(char (*sq)[MAXN + 1], char (*trans)[MAXN + 1], int n)
{
    int i, j;

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (sq[i][j] != trans[n - 1 - i][n - 1 - j])
                return FALSE;

    return TRUE;
}

/* de270: if sq rotate 270 degree is trans return True */
int de270(char (*sq)[MAXN + 1], char (*trans)[MAXN + 1], int n)
{
    int i, j;

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (sq[i][j] != trans[n - 1 - j][i])
                return FALSE;

    return TRUE;
}

/* reflect: copy the reflection of sq to mirror */
void reflect(char (*sq)[MAXN + 1], char (*mirror)[MAXN + 1], int n)
{
    int i, j;

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            mirror[i][n - 1 - j] = sq[i][j];
}

/* equal: if sq is same as trans return True */
int equal(char (*sq)[MAXN + 1], char (*trans)[MAXN + 1], int n)
{
    int i, j;

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (sq[i][j] != trans[i][j])
                return FALSE;

    return TRUE;
}

USACO Milking Cows

奇怪看別人處理data都是一次吃完再handle，
我習慣能一個一個handle就先handle。
不過這樣coding似乎也沒比較快，而且有點複雜……
sort以後用內建qsort好了 @_@。

一次吃一行資料，
跟已經吃進來的資料做比較：
吃進來的資料，
可能start在某個farmer中，
或end在某個farmer中，
或是被某個farmer包含，
或包含某個farmer。
光吃資料就夠複雜了吧 -.-

之後做sort，就可以輸出最大milk times，
與idle times。

看來一次先吃完所有資料就不會這麼麻煩……
教學文也說這是complete search。

/*
ID: mythnc2
LANG: C
TASK: milk2
Milking Cows
2011/10/28 14:44:22   
*/
#include <stdio.h>

#define MAXN 5000
#define BEGIN   0
#define END     1
#define SWAP(x, y, t)  (t = x, x = y, y = t)

void addframer(int (*)[], int *, int *);
void maxf(int (*)[], int, int *, int *);
void sort(int (*)[], int *);

int main (void)
{
    FILE *fin, *fout;
    int farmer[MAXN][2];
    int tmp[2];
    int n, number, maxmilk, maxidle;

    fin = fopen("milk2.in", "r");
    fout = fopen("milk2.out", "w");

    fscanf(fin, "%d", &n);
    for (number = 0; n; n--) {
        fscanf(fin, "%d %d", tmp, tmp + 1);
        addframer(farmer, tmp, &number);
    }

    sort(farmer, &number);
    maxf(farmer, number, &maxmilk, &maxidle);

    fprintf(fout, "%d %d\n", maxmilk, maxidle);

    return 0;
}

/* adframer: if tmp in farmer, update it,
 * if not in farmer, add tmp */
void addframer(int (*farmer)[2], int *tmp, int *n)
{
    int i;

    for (i = 0; i < *n; i++) {
        /* 0 0 condition */
        if (farmer[i][BEGIN] == 0 && farmer[i][END] == 0)
            continue;

        /* tmp contain farmer[i] */
        if (tmp[BEGIN] < farmer[i][BEGIN]
            && tmp[END] > farmer[i][END]) {
            farmer[i][BEGIN] = farmer[i][END] = 0;
            continue;
        }
        /* farmer[i] contains tmp */
        else if (farmer[i][BEGIN] <= tmp[BEGIN]
                 && farmer[i][END] >= tmp[END])
            return;

        /* update: farmer[i] contains tmp[BEGIN] */
        if (farmer[i][BEGIN] < tmp[BEGIN]
            && tmp[BEGIN] <= farmer[i][END]) {
            tmp[BEGIN] = farmer[i][BEGIN];
            farmer[i][BEGIN] = farmer[i][END] = 0;
            /* start from head again */
            i = -1;
        }
        /* update: farmer[i] contains tmp[END] */
        else if (farmer[i][BEGIN] <= tmp[END]
            && tmp[END] < farmer[i][END]) {
            tmp[END] = farmer[i][END];
            farmer[i][BEGIN] = farmer[i][END] = 0;
            /* start from head again */
            i = -1;
        }
    }

    (*n)++;
    farmer[i][BEGIN] = tmp[BEGIN];
    farmer[i][END] = tmp[END];
}

/* maxf: find the maxmilk and maxidle times */
void maxf(int (*farmer)[2], int n, int *milk, int *idle)
{
    int i;

    if (n == 1) {
        *milk = farmer[0][END] - farmer[0][BEGIN];
        *idle = 0;
        return;
    }

    for (*idle = *milk = i = 0; i < n; i++) {
        if (*milk < farmer[i][END] - farmer[i][BEGIN])
            *milk = farmer[i][END] - farmer[i][BEGIN];
        if (i < n - 1 && *idle < farmer[i][BEGIN] - farmer[i + 1][END])
            *idle = farmer[i][BEGIN] - farmer[i + 1][END];
    }
}

/* sort: selection sort from high to low does not contain 0 */
void sort(int (*f)[2], int *n)
{
    int i, j, max, tmp;

    for (i = 0; i < *n - 1; i++) {
        for (max = j = i; j < *n; j++)
            if (f[max][BEGIN] < f[j][BEGIN])
                max = j;
        if (max != i) {
            SWAP(f[max][BEGIN], f[i][BEGIN], tmp);
            SWAP(f[max][END], f[i][END], tmp);
        }
    }

    /* delete 0 0 */
    while (f[*n - 1][BEGIN] == 0 && f[*n - 1][END] == 0)
        (*n)--;
}

USACO Broken Necklace

寫得很爛，根本不知道可以怎麼做，囧。
只好硬幹。寫到快起肖，悲劇。

先找每組珠子的數目數，之後存起來，
接著找最大的珠子數，
再檢查該珠子的兩側（因為環狀），
是否有算錯，
例如bwrwb可能是1 3 1或2 1 2。
沒錯的話就可以輸出。

/*
ID: mythnc2
LANG: C
TASK: Beads
Broken Necklace
2011/10/27 11:41:05   
*/
#include <stdio.h>
#include <string.h>

#define MAXARY 360

typedef struct record{
    int count;
    char *head, *tail;
} Record;

int firstlen(char *);
void movefirst(char *, int);
char *len(char *, Record *, int *);
int backward(char *);
int maxvalue(Record *, int);
int pairs(Record *, Record);
int reverse(char *, char *);

int main(void)
{
    FILE *fin, *fout;
    char bead[MAXARY];
    char *move;
    Record rec[MAXARY];
    int n, i, step;

    fin = fopen("beads.in", "r");
    fout = fopen("beads.out", "w");
    
    fscanf(fin, "%d", &n);
    fscanf(fin, "%s", bead);

    if ((i = firstlen(bead)) == n) {  /* one color */
        fprintf(fout, "%d\n", i);
        return 0;
    }
    else
        movefirst(bead, i);

    for (move = bead, i = 0; *move; i++) {
        move = len(move, &rec[i], &step);
        if (step)
            i++;
    }

    if (i < 3)
        fprintf(fout, "%d\n", rec[0].count + rec[1].count);
    else
        fprintf(fout, "%d\n", maxvalue(rec, i));

    return 0;
}

/* firstlen: count the first length
 * also use this function to count w length */
int firstlen(char *bead)
{
    int i;

    i = 0;
    /* if first char is w, skip over it */
    while (bead[i] == 'w')
        i++;
    if (bead[i] == '\0')   /* all beads is w color */
        return i;

    if (bead[i] == 'b')
        while (bead[i] == 'b' || bead[i] == 'w')
            i++;
    else
        while (bead[i] == 'r' || bead[i] == 'w')
            i++;
    return i;
}

/* movefirst: rearrange string bead,
 * move the first len to last */
void movefirst(char *bead, int n)
{
    int i;
    char tmp[n];

    strncpy(tmp, bead, n);
    for (i = 0; bead[i + n] != '\0'; i++)
        bead[i] = bead[i + n];
    bead[i] = '\0';
    strncat(bead, tmp, n);
}

/* len: count the len of each color bead
 * and return the position after count */
char *len(char *move, Record *rec, int *step)
{
    int wcount;
    char *w;

    wcount = rec->count = *step = 0;
    rec->head = move;
    if (*move == 'b')
        while (*move == 'b' || *move == 'w') {
            if (*move == 'w' && wcount == 0) {
                wcount = firstlen(move);
                w = move;
            }
            rec->count++;
            move++;
        }
    else  /* color r */
        while (*move == 'r' || *move == 'w') {
            if (*move == 'w' && wcount == 0) {
                wcount = firstlen(move);
                w = move;
            }
            rec->count++;
            move++;
        }

    if (wcount > rec->count) {
        *step = 1;
        rec->count -= backward(move); /* corrected count */
        move = w + wcount;            /* corrected position */
        rec->tail = w;
        (++rec)->count = wcount;      /* the next count value */
        rec->head = w;
    }
    rec->tail = move;
    return move;
}

/* backward: backward pointer to find previous color,
 * which is not w color return the backward steps */
int backward(char *back)
{
    int count;

    count = 0;
    while (*--back == 'w')
        count++;

    return count;
}

/* maxvalue: find the max element
 * if max is not only one, judge them sequentially
 * return the biggest count of this element 
 * and its adjacence */
int maxvalue(Record *rec, int n)
{
    int i, max, count, tmp;
    int index[MAXARY];

    for (max = i = 0; i < n; i++)
        if (rec[max].count < rec[i].count)
            max = i;
    /* find the number of max */
    for (count = i = 0; i < n; i++)
        if (rec[max].count == rec[i].count)
            index[count++] = i;

    for (max = i = 0; i < count; i++) {
        if (index[i] == 1)
            tmp = pairs(&rec[n - 1], rec[2]) + rec[0].count;
        else if (index[i] == 0)
            tmp = pairs(&rec[n - 2], rec[1]) + rec[0].count;
        else if (index[i] == n - 1)
            tmp = pairs(&rec[n - 3], rec[0]) + rec[n - 1].count;
        else
            tmp = pairs(&rec[index[i] - 2], rec[index[i] + 1])
                   + rec[index[i]].count;
        if (tmp > max)
            max = tmp;
    }
    return max;
}

/* pairs: recalculate pre and next len
 * return the largest */
int pairs(Record *pre, Record next)
{
    int pv, nv;

    nv = firstlen(next.head);
    pv = reverse(pre->head, pre[1].tail);

    return nv > pv ? nv : pv;
}

/* reverse: reverse the beads before max,
 * recalulate it's len and return it */
int reverse(char *head, char *tail)
{
    char seq[MAXARY];
    char *move;
    int i;

    for (i = 0, move = tail - 1; move > head - 1; move--)
        seq[i++] = *move;
    seq[i] = '\0';

    return firstlen(seq);
}

USACO Friday the Thirteenth

就只是個數饅頭……
除了第一年的1月另外計算，
往後的1月13號都是去年的12月13號 + 31(DEC)。

/*
ID: mythnc2
LANG: C
TASK: friday
2011/10/26 19:37:31   
*/
#include <stdio.h>
 
#define MONTHS      12
#define FIRSTYEAR 1900
#define WEEK         7
 
int leap(int);
 
int main (void)
{
    FILE *fin, *fout;
    int n, i, j, day;
    int thirteen[WEEK] = { 0 };
    int month[MONTHS] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    enum Months {JAN, FEB};
 
    fin = fopen("friday.in", "r");
    fout = fopen("friday.out", "w");
 
    fscanf(fin, "%d", &n);
 
    /* simplify months */
    for (i = 0; i < MONTHS; i++)
        month[i] %= WEEK;
 
    for (day = 1 + 12, i = 0; i < n; i++) {
        if (i > 0)       /* DEC/13 + 31 = JAN/13 */
            day += month[j];
        day %= WEEK;
        thirteen[day]++;
        for (j = JAN; j < MONTHS - 1; j++) {
            day += month[j];
            if (j == FEB && leap(i))
                day++;
            day %= WEEK;
            thirteen[day]++;
        }
    }
    /* printout: from sat to fri */
    fprintf(fout, "%d", thirteen[WEEK - 1]);
    for (i = 0; i < WEEK - 1; i++)
        fprintf(fout, " %d", thirteen[i]);
    fprintf(fout, "\n");
    return 0;
}
 
/* leap: calculate the year is a leap year or not
 * return 1 if is, 0 if is not */
int leap(int i)
{
    int year;
 
    year = FIRSTYEAR + i;
    return year % 4 == 0 && year % 100 != 0
           || year % 400 == 0;
}

USACO Greedy Gift Givers

給錢的人要減去錢，分不完的不用分，(-$ + $ % n)
拿到錢的要平分($ / n)。
其實NP是N個人，
也表示有N筆資料要處理，
害我以為輸入資料是不定數了，
(英文太爛，哭哭）
用for代替EOF處理即可。

/*
ID: mythnc2
LANG: C
TASK: gift1
2011/10/25 18:37:46   
*/
#include <stdio.h>
#include <string.h>

#define LEN   20
#define N     10
/* giver: the money giver have to pay */
#define GIVER(person, money, n)  person.money += money % n - money
/* taker: the money taker get */
#define TAKER(person, money, n)  person.money += money / n

typedef struct group {
    char name[LEN + 1];
    int money;
} People;

int findname(People *, char *);
void eatname(FILE *, int);
void printout(FILE *, People *, int);

int main(void)
{
    FILE *fin, *fout;
    int n, i, j, money, ntake;
    char tmp[LEN + 1];
    People person[N];

    fin = fopen("gift1.in", "r");
    fout = fopen("gift1.out", "w");

    fscanf(fin, "%d", &n);
    for (i = 0; i < n; i++) {
        fscanf(fin, "%s", person[i].name);
        person[i].money = 0;    /* init */
    }

    while (1) {
        if (fscanf(fin, "%s", tmp) == EOF) 
            break;
        fscanf(fin, "%d %d", &money, &ntake);
        if (money == 0) {                      /* haven't to give money */
            if (ntake > 0)
                eatname(fin, ntake);
            continue;
        }

        i = findname(person, tmp);             /* the giver name */
        GIVER(person[i], money, ntake);
        for (i = 0; i < ntake; i++) {
            fscanf(fin, "%s", tmp);
            j = findname(person, tmp);         /* the taker name */
            TAKER(person[j], money, ntake);
        }
    }
    /* output */
    printout(fout, person, n);
    return 0;
}

/* findname: find the tmp name in person,
 * return the index of that name */
int findname(People *person, char *tmp)
{
    int i;

    for (i = 0; ; i++)
        if (strcmp(person[i].name, tmp) == 0)
            return i;
}

/* eatname: eat name token */
void eatname(FILE *fin, int n)
{
    while (n--)
        fscanf(fin, "%*s");
}

/* printout: print out the results */
void printout(FILE *fout, People *person, int n)
{
    int i;

    for (i = 0; i < n; i++)
        fprintf(fout, "%s %d\n", person[i].name, person[i].money);
}

USACO Your Ride Is Here

熟悉USACO格式用題目。
每乘一次就做一次mod會比較好。

/*
ID: mythnc2
LANG: C
TASK: ride
*/
#include <stdio.h>
 
#define MAXARY 10
 
int product(char *);
 
int main(void)
{
    FILE *fin, *fout;
    char comet[MAXARY], group[MAXARY];
 
    fin = fopen("ride.in", "r");
    fout = fopen("ride.out", "w");
 
    fscanf(fin, "%s\n", comet);
    fscanf(fin, "%s\n", group);
 
    if (product(comet) == product(group))
        fprintf(fout, "GO\n");
    else
        fprintf(fout, "STAY\n");
    return 0;
}
 
/* product: return the product mod 47 of letters */
int product(char *ary)
{
    int p;
 
    p = 1;
    while (*ary) {
        p *= (*ary - 'A' + 1);
        p %= 47;
        ary++;
    }
    return p;
}