ACM 101 The Blocks Problem

除了硬幹好像也沒別招了？
不過儲存資料的結構實在長的很噁心……
之前用2維陣列存，這次試著用結構存看看
本題可以練習到stack的運作方式。
之前ACM10038 free就被WA，
這次free就沒事 -_-。

/* ACM 101
 * mythnc
 * 2011/10/14 16:08:24   
 * run time: 0.008
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXARY 25

typedef struct robot {
    int *block;
    int count;
} Action;

void init(Action *[], int n);
int position(Action *[], int *, int);
void clear(Action *[], int *);
void move(Action *[], int *, int *);
void print(Action *[], int);

int main(void)
{
    /* a[3]: 0 for a, 1 for position a, 2 for block a */
    /* same as b */
    int n, a[3], b[3];
    char str1[MAXARY], str2[MAXARY];
    Action *arm[MAXARY];

    scanf("%d", &n);
    init(arm, n);
    while (scanf("%s %d %s %d", str1, a, str2, b) == 4) {
        if (a[0] == b[0])
            continue;
        if ((a[1]= position(arm, a, n)) ==
            (b[1]= position(arm, b, n)))
            continue;
        if (strcmp(str1, "move") == 0)
            clear(arm, a);
        if (strcmp(str2, "onto") == 0)
            clear(arm, b);
        move(arm, b, a);
    }
    print(arm, n);
    return 0;
}

/* init: initialize arm */
void init(Action *arm[], int n)
{
    int i;

    for (i = 0; i < n; i++) { /* initialize arm */
        arm[i] = (Action *)malloc(sizeof(Action));
        arm[i]->block = (int *)malloc(sizeof(int) * n);
        arm[i]->count = 0;
        arm[i]->block[arm[i]->count++] = i;
    }
}

/* position: return position and block of pt[0] */
int position(Action *arm[], int *pt, int n)
{
    int i, j;

    for (i = 0; i < n; i++)
        for (j = 0; j < arm[i]->count; j++)
            if (arm[i]->block[j] == pt[0]) {  /* position i, block j */
                pt[2] = j;
                return i;
            }
}

/* clear: clear blocks above x */
void clear(Action *arm[], int *x)
{
    int tmp;

    while (arm[x[1]]->count != x[2] + 1) {  /* return tmp to it's position */
        tmp = arm[x[1]]->block[--arm[x[1]]->count];
        arm[tmp]->block[arm[tmp]->count++] = tmp;
    }
}

/* move: move a to b */
void move(Action *arm[], int *b, int *a)
{
    int i;

    for (i = a[2]; i < arm[a[1]]->count; i++)
        arm[b[1]]->block[arm[b[1]]->count++] = arm[a[1]]->block[i];
    arm[a[1]]->count = a[2];
}

/* print: print out final state */
void print(Action *arm[], int n)
{
    int i, j;

    for (i = 0; i < n; i++) {
        printf("%d:", i);
        for (j = 0; j < arm[i]->count; j++)
            printf(" %d", arm[i]->block[j]);
        free(arm[i]->block);
        free(arm[i]);
        printf("\n");
    }
}

ACM 10071 Back to High School Physics

直接做。

/* ACM 10071
 * mythnc
 * 2011/10/13 18:58:58   
 * run time: 0.02
 */
#include <stdio.h>

int main(int argc, char *argv[])
{
    int t, v;

    while (scanf("%d %d", &v, &t) != EOF )
        printf("%d\n", 2 * v * t);
    return 0;
}

ACM 10062 Tell me the frequencies!

概念同ACM10008。
也是沒想到比較好的算則。
ary0到95對應ascii code 32到127。
由小至大輸出，ascii code高的優先。

/* ACM 10062
 * mythnc
 * 2011/10/13 18:48:47
 * run time: 0.004
 */
#include <stdio.h>

int output(int *);

int main(void)
{
    int c, newline;
    int ary[96] = { 0 };

    newline = 0;
    while ((c = getchar()) != EOF) {
        if (c > 31 && c < 128)
            ary[c - 32]++;
        if (c == '\n') {
            if (++newline > 1)
                printf("\n");
            while (output(ary))
                ;
        }
    }
    return 0;
}

/* output: print out the result from high ascii value to low */
int output(int *s)
{
    int i, j, min;

    for (min = 1001, i = 95; i > -1; i--)
        if (min > s[i] && s[i] > 0) {
            min = s[i];
            j = i;
        }
    if (min == 1001)   /* if no element have to printed */
        return 0;
    printf("%d %d\n", j + 32, min);
    s[j] = 0;
    return 1;
}

ACM 10056 What is the Probability ?

機率好難……
一開始的想法很單純，答案就是題目給的浮點數。
後來想想發現，第i個人擲骰，i未必為1，
而也未必在第一輪就骰出。
所以我想的太簡單了 -.-。
所以正確的思考方式應該為：
n個人中第k個人骰贏得機率是多少？
此人可能在第一輪骰贏、第二輪骰贏、第三輪骰贏……一直到他骰贏的那輪為止。
假設骰贏的機率為p，沒骰贏的機率為q = p - 1
第k個人要骰贏，前面k-1個人一定不會骰贏：
q ^ (k-1)
此人自己需骰贏：
q ^ (k-1) * p
如果他沒骰贏，遊戲被迫進入第二輪，
即第一輪大家都沒骰贏：
q ^ n
第二輪中他骰贏的情況（第一輪沒人贏，第二輪他贏）：
(q ^ n) * q ^ (k-1) * p
第三輪中他骰贏的情況（前二輪沒人贏，第三輪他贏）：
(q ^ 2n) * q ^ (k-1) * p
類推，到第x+1輪他骰贏的情況（前x輪沒人贏，第x+1輪他贏）：
(q ^ xn) * q ^ (k-1) * p
所以若要計算他所有骰贏的可能情況，
就是第一輪骰贏的機率 + 第二輪骰贏的機率 + ... + 第x輪骰贏的機率：
q ^ (k-1) * p + (q ^ n) * q ^ (k-1) * p + (q ^ 2n) * q ^ (k-1) * p + ... + (q ^ xn) * q ^ (k-1) * p
以下化簡原式：

1. q ^ (k-1) * p [1 + (q ^ n) + (q ^ 2n) + ... + (q ^ xn)] (取出q ^ (k-1)*p)
   
2. 1 + (q ^ n) + (q ^ 2n) + ... + (q ^ xn) 是無窮等比級數（根本就不知道他哪一輪會贏）
   

公比為q ^ n。
所以2.式可以化簡為1 / (1 - q ^ n)（查詢等比級數公式/無窮等比級數公式）
原式化簡為：
[q ^ (k-1) * p] / (1 - q ^ n)。
另外要注意，當p為0時，此公式分母為0，所以輸出需另外處理。
（就是輸出0.0000而已啦）

/* ACM 10056
 * mythnc
 * 2011/10/13 11:47:52   
 * run time: 0.008
 */
#include <stdio.h>
#include <math.h>

int main(void)
{
    int set, n, k;  /* n players, the kth player */
    double p;

    scanf("%d", &set);
    while (set-- > 0) {
        scanf("%d %lf %d", &n, &p, &k);
        if (p == 0.0) {
            printf("0.0000\n");
            continue;
        }
        if (k == 1)
            printf("%.4f\n", p / (1 - pow(1-p, n)));
        else
            printf("%.4f\n", p * pow(1-p, k-1) / (1 - pow(1-p, n)));
    }
    return 0;
}

ACM 10055 Hashmat the Brave Warrior

直接做。
2 ^ 32比unsigned int多1，所以用long long int存資料囉。
要不然會WA。

/* ACM 10055
 * mythnc
 * 2011/10/13 09:47:17   
 * run time = 0.06
 */
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    long long int x, y;

    while (scanf("%lld %lld",&x,&y) != EOF)
        if (x > y)
            printf("%lld\n", x - y);
        else
            printf("%lld\n", y - x);
    return 0;
}