Q10375: Choose and divide

/*
    exp(x) return a double, so we have to convert its datatype to long double
    long double: printf("%Lf"), scanf("%LF")

    Run time: 0.056
*/
#include <stdio.h>
#include <math.h>

long double compute(int m, int n);

int main()
{
    int p, q, r, s;
    long double tmp1, tmp2, result;


    while (scanf("%d%d%d%d", &p, &q, &r, &s) == 4)
    {
        if (2*q > p)
            q = p - q;
        if (2*s > r)
            s = r - s;

        if (!q) tmp1 = 0;
        else    tmp1 = compute(p, q);

        if (!s) tmp2 = 0;
        else    tmp2 = compute(r, s);

        result = exp(tmp1-tmp2);

        printf("%.5Lf\n", result);
    }

    return 0;
}

long double compute(int m, int n)
{
    int i;
    long double tmp = 0;

    for ( i = 1; i <= m; i++)
        tmp += log(i);

    for ( i = 1; i <= n; i++)
        tmp -= log(i);

    for ( i = 1; i <= (m-n); i++)
        tmp -= log(i);

    return tmp;

}

Q291: The House Of Santa Claus

/*
    利用DFS去做
    Run time: 0.000
*/
#include <stdio.h>
const int N = 5;
int arr[N][N] = {
                    {0,1,1,0,1},
                    {1,0,1,0,1},
                    {1,1,0,1,1},
                    {0,0,1,0,1},
                    {1,1,1,1,0}
                };
int record[9];

void DFS(int count, int index);

int main()
{
    int count = 8;
    DFS(count, 0);

}

void DFS(int count, int index)
{
    static int m;  // to record the node index
    int i, j, k;

    if (count == 0)
    {
        record[m] = index+1;  // record the node

        for ( k = 0; k < 9; k++)
            printf("%d", record[k]);
        printf("\n");

        return;
    }

    else
    {
        for ( i = 0; i < N; i++)
        {
            if (arr[index][i])
            {
                arr[index][i] = 0;  // line delete
                arr[i][index] = 0;  // line delete

                // whether there is no line at line index or not
                for ( j = 0; j < N; j++)
                    if (arr[i][j])
                        break;

                // if there is no line at line index
                if (j == N && count-1)
                {
                    arr[index][i] = 1;
                    arr[i][index] = 1;
                    continue;
                }

                count--;  // line number delete
                record[m++] = index+1;  // record the node

                DFS(count, i);  // recursive call

                arr[index][i] = 1;  // line recovery
                arr[i][index] = 1;  // line recovery
                count++;  // line number recovery
                m--;
            }
        }
    }

}

Q136: Ugly Numbers

// Run time: 0.080
#include <stdio.h>
const int N = 1500;

int ugly[N] = {1, 2, 3, 4, 5};
int base[3] = {2, 3, 5};
int min(int *arr);

int main()
{
    int cnt = 5;
    int tmp[3];
    int i, j;
    int index;

    while (cnt <= N)
    {
        for ( i = 0; i < 3; i++)
        {
            for ( j = 0; ugly[j] <= ugly[cnt-1]/base[i]; j++);
            tmp[i] = ugly[j]*base[i];
        }

        index = min(tmp);
        ugly[cnt++] = tmp[index];
    }

    printf("The 1500'th ugly number is %d.\n", ugly[N-1]);

    return 0;
}

int min(int *arr)
{
    int min;
    min = arr[0];

    if (min > arr[1])
    {
        min = arr[1];
        if (min > arr[2])
            return 2;
        return 1;
    }

    if (min > arr[2])
        return 2;

    return 0;
}

Q374: Big Mod

/*
    recursive

    terminal condition: P = 0 or P = 1
    if P is odd, B^P = B^(p-1)*B
    if P is even, B^P = B^(P/2) * B^(P/2)

    Run time: 0.010
*/
#include <stdio.h>
long long int compute(int B, int P, int M);

int main()
{
    int B, P, M;
    long long int remainder;

    while (scanf("%d%d%d", &B, &P, &M) == 3)
    {
        remainder = compute(B, P, M);
        printf("%lld\n", remainder);
    }

    return 0;
}

long long int compute(int B, int P, int M)
{
    if (!P) return 1;
    if (P == 1) return B;
    else
    if (P%2)
        return (compute(B, P-1, M)*compute(B, 1, M))%M;
    else
        return (compute(B, P/2, M)*compute(B, P/2, M))%M;
}

Q10220: I Love Big Numbers !

/*
    也可以和 Q623: 500! 一樣用二維的ARRAY
    但這題只要SUM不要階層的值
    所以 arr 可以一直用

    如果用二維會太浪費空間

    Run time: 0.030
*/
#include <stdio.h>
#define LEN 2600
#define N 1000

int arr[LEN];
int len[N+1];
void calculate();

int main()
{
    int n;
    int i;
    int sum;
    calculate();

    while (scanf("%d", &n) != EOF)
    {
        printf("%d\n", len[n]);
    }

    return 0;
}

void calculate()
{
    int i, j;

    arr[0] = 1;
    len[0] = 1, len[1] = 1;

    for ( i = 1; i <= N; i++)
    {
        for ( j = 0; j < LEN; j++)
            arr[j] *= i;

        for ( j = 0; j < LEN; j++)
        {
            // to calculate carry
            if (arr[j] >= 10)
            {
                arr[j+1] += arr[j]/10;
                arr[j] %= 10;
            }
        }

        for ( j = 0; j < LEN; j++)
            len[i] += arr[j];
    }
}

Q623: 500!

/*
    上傳時再改成 LEN: 2600, N: 1000
    用上一個的結果去算就不會TLE了

    Run time: 0.410
*/
#include <stdio.h>
#define LEN 2600
#define N 1000

int arr[N+1][LEN];
void calculate();

int main()
{
    int n;
    int i;

    calculate();

    while (scanf("%d", &n) != EOF)
    {
        printf("%d!\n", n);

        for ( i = LEN-1; i >= 0; i--)
            if (arr[n][i])
                break;

        for ( ; i >= 0; i--)
            printf("%d", arr[n][i]);
        printf("\n");
    }

    return 0;
}

void calculate()
{
    int i, j;

    // initial value: 0! = 1, 1! = 1
    arr[0][0] = 1, arr[1][0] = 1;

    for ( i = 2; i <= N; i++)
    {
        for ( j = 0; j < LEN; j++)
        {
            arr[i][j] += arr[i-1][j] * i;

            // to calculate carry
            if (arr[i][j] >= 10)
            {
                arr[i][j+1] += arr[i][j]/10;
                arr[i][j] %= 10;
            }
        }
    }
}

Q10573: Geometry Paradox

// Run time: 0.000
#include <stdio.h>
#include <math.h>
#define PI 2*acos(0.0)

int check(char *s);

int main()
{
    int N;
    int num;
    int r1, r2;
    int t;
    char str[6];
    double area;

    scanf("%d\n", &N);

    while (N--)
    {
        gets(str);

        num = check(str);

        // argument number
        if (num == 2)
        {
            sscanf(str, "%d%d", &r1, &r2);
            area = 2*r1*r2*PI;
        }
        else
        {
            sscanf(str, "%d", &t);
            area = double(t*t)/8.0*PI;
        }

        printf("%.4lf\n", area);
    }

    return 0;
}

int check(char *s)
{
    int i;

    for ( i = 0; s[i] != '\0'; i++)
        if (s[i] == ' ')
            return 2;

    return 1;
}

Q10515: Power et al.

// Run time: 0.100
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int N = 102;
int arr[10] = {1, 1, 4, 4, 2, 1, 1, 4, 4, 2};

int calculate(int m, int n);

int main()
{
   char s[N+1], t[N+1];
   int len1, len2;
   int m, n;
   while (scanf("%s%s", s, t))
   {
       m = atoi(s);
       n = atoi(t);

       if (!m && !n)     break;

       if (!m)
       {
           printf("0\n");
           continue;
       }

       if (!n)
       {
           printf("1\n");
           continue;
       }

       len1 = strlen(s);
       len2 = strlen(t);

       m = s[len1-1] - '0';  // digit in ones
       n = (t[len2-2]-'0')*10 + t[len2-1]-'0';  // digits in ones and tens


       printf("%d\n", calculate(m, n));
   }

   return 0;
}

int calculate(int m, int n)
{
   int i;
   int prod = 1;

   n = n%arr[m] ? n%arr[m] : arr[m];

   for ( i = 0; i < n; i++)
       prod = prod*m;

   return prod%10;
}

Hex相乘

/*
    輸入：兩個16進位的數(最多10位數)
    輸出：十六進位的相乘結果
    Sample input:
                 123456ABC
                 ABC123456
    Sample output:
                 C36B1DC2784380B28

    想法：因為以前教的乘法都是在10進位，但是學過二進位就知道，其實乘法都一樣，只是在不同的基底下
          進位的門檻不一樣，例如10進位就是要10以上才進位，二進位是2以上進位，所以16進位要16以上進位。

    Note：如果直接用電腦的計算機算會overflow，因為現在的compiler最多只支援到64bits
          所以這題必須使用和大數乘法或者階層相同的概念去做。

    Algo：
         1.輸入16進位，把其當作字串
         2.每個字元去轉換成整數陣列，每個位數存一格
         3.乘法運算的實現(但每做完一個位數的乘法，就要檢查是否需要進位)
         4.因為運算的結果都是0~15的數字，所以必須轉成十六進位

*/
#include <stdio.h>
#include <string.h>
#define N 10
int arr[N];
int arr2[N];
int sum[2*N];
char s1[N+1];
char s2[N+1];
int assign(char ch);
char trans(int n);

int main()
{
    int n;
    int len1, len2;
    int i, j, k, m;
    while (true)
    {
        gets(s1);
        gets(s2);

        len1 = strlen(s1);
        len2 = strlen(s2);

        for ( i = 0; i < N; i++)
            arr[i] = arr2[i] = 0;

        for ( i = 0; i < 2*N; i++)
            sum[i] = 0;

        for ( i = 0; i < len1; i++)
            arr[i] = assign(s1[i]);

        for ( i = 0; i < len2; i++)
            arr2[i] = assign(s2[i]);

        for ( i = len1-1, m = 0; i >= 0; i--, m++)
            for ( j = len2-1, k = m; j >= 0; j--)
                sum[k++] += arr[i]*arr2[j];


        // 要從個位一直到最後一位
        for ( j = 0; j < 2*N; j++)
        {
            // 從個位開始找是否 >= 16，要進位
            if (sum[j] >= 16)
            {
                sum[j+1] += sum[j]/16;
                sum[j] = sum[j]%16;
            }
        }

        // 從大位數開始找到非零的！從2*N-1開始找
        for ( i = 2*N-1; i >= 0; i--)
            if (sum[i])
                break;

        for ( j = i; j >= 0; j--)
            printf("%c", trans(sum[j]));

        printf("\n");

    }

    return 0;
}

int assign(char ch)
{
    if (ch >= '0' && ch <= '9')
        return ch-'0';
    else
        return ch-'A'+10;
}

char trans(int n)
{
    if (n >= 0 && n <= 9)
        return n+'0';
    else
        return 'A' + n - 10;
}

Q10310: Dog and Gopher

// Run time: 0.010
#include <stdio.h>

double gx, gy, dx, dy;
bool test(double arr[2]);
double distance(double x, double y, double arr[2]);
int main()
{
    int n;
    int i;

    while (scanf("%d", &n) != EOF)
    {
        double hole[n][2];
        scanf("%lf %lf %lf %lf", &gx, &gy, &dx, &dy);

        for ( i = 0; i < n; i++)
            scanf("%lf %lf", &hole[i][0], &hole[i][1]);

        for ( i = 0; i < n; i++)
            if (test(hole[i]))
                break;

        printf("The gopher ");
       
        if (i == n)
            printf("cannot escape.\n");
        else
            printf("can escape through the hole at (%.3lf,%.3lf).\n", hole[i][0], hole[i][1]);
    }

    return 0;
}

bool test(double arr[2])
{
    double d, g;
    d = distance(dx, dy, arr);
    g = distance(gx, gy, arr);

    // without sqrt, so we should use 4 times to compare.
    if (4*g  <= d)
        return true;
    else
        return false;

}

double distance(double x, double y, double arr[2])
{
    return (arr[0]-x)*(arr[0]-x)+(arr[1]-y)*(arr[1]-y);
}

Q10298: Power String

// Run time: 0.140
#include <stdio.h>
#include <string.h>
const int N = 1000000;
char str[N+1];
int calculate(int length);

int main()
{
    int length;
    int n;

    while (gets(str) && str[0] != '.')
    {
        length = strlen(str);
        n = calculate(length);
        printf("%d\n", n);
    }
    return 0;
}

int calculate(int length)
{
    int i, j, k;
    int len;
    bool s;
    char tmp[length+1];

    for ( i = 0; i < length; i++)
    {
        if (!(length%(i+1)))
        {
            s = true;

            // assign substring to tmp
            for ( j = 0; j <= i; j++)
                tmp[j] = str[j];
            tmp[j] = '\0';

            // tmp's length
            len = j;

            // look for other substring
            for ( j = len; j < length; j+= len)
            {
                for ( k = 0; k < len; k++)
                {
                    if (tmp[k] != str[j+k])
                    {
                        s = false;
                        break;
                    }
                }

                if (!s) break;
            }

            if (s)  break;
        }

    }

    // if i == length, it means substring is equal to str
    return (i == length) ? 1 : length/(i+1);

}

Q10295: Hay Points

// Run time: 0.000
#include <stdio.h>
#include <string.h>

typedef struct {
    char word[17];
    int pay;
} Work;

int main()
{
    char str[25];  // dictionary string
    char tmp[100]; // job descriptions string
    int m, n;
    int i, j;  // loop counting
    int sum;
    while (scanf("%d%d", &m, &n) == 2)
    {
        Work work[m];

        getchar();

        for ( i = 0; i < m; i++)
        {
            gets(str);
            sscanf(str, "%s %d", work[i].word, &work[i].pay);
        }

        for ( i = 0; i < n; i++)
        {
            sum = 0;

            while (true)
            {
                scanf("%s", tmp);

                if (tmp[0] == '.')
                   break;

                for ( j = 0; j < m; j++)
                    if (!strcmp(tmp, work[j].word))
                        sum += work[j].pay;
            }

            printf("%d\n", sum);
        }
    }
}

Q10287: Gifts in a Hexagonal Box

// Run time: 0.200
#include <stdio.h>
#include <math.h>
#define EPS pow(10, -11)
#define m sqrt(7)
#define n sqrt(3)

int main()
{
   double length;

   while (scanf("%lf", &length) != EOF)
   {
       printf("%.10lf ", length*n/2+EPS);
       printf("%.10lf ", length*(2*n-3)+EPS);
       printf("%.10lf ", length*(n/4)+EPS);
       printf("%.10lf\n", length*(0.6*m-0.7*n)+EPS);
   }

   return 0;
}

Q10622: Perfect Pth Powers

/*
    prime factorization

    Run time: 0.000
*/
#include <stdio.h>
const int N = 46350;
const int NUM = 4793;

bool isprime[N+1];
int prime[NUM];

void findPrime();
int calculate(int n);
int select(int *arr, int index);
int abs(int n);

int main()
{
    findPrime();

    int n;
    int p;
    while (scanf("%d", &n) && n)
    {
        if (n == -2147483648)
        {
           printf("31\n");
           continue;
        }

        p = calculate(n);
        printf("%d\n", p);
    }

}

void findPrime()
{
    int i, j;

    for ( i = 2; i*i <= N; i++)
        if (!isprime[i])
            for ( j = 2*i; j <= N; j += i)
                isprime[j] = true;

    for ( i = 2, j = 0; i <= N; i++)
        if (!isprime[i])
            prime[j++] = i;
}

int calculate(int n)
{
    int arr[NUM] = {0};
    int i, j;
    int m;
    int tmp;
    int index;
    int min;

    tmp = m = abs(n);

    for ( i = 0; (i < NUM) && (prime[i]*prime[i] <= tmp) && (m != 1); i++)
    {
        while (!(m%prime[i]))
        {
            m /= prime[i];
            arr[i]++;
        }
    }

    index = i;

    // select a suitable num in *arr
    min = select(arr, index);

    // if fail in divide
    if (min == -1)
        return 1;

    // find min
    for ( i = 1; i < index; i++)
        if (arr[i] && arr[i] < min)
            min = arr[i];

    // if divided with remainder
    for ( i = 0; i < index; i++)
        if (arr[i]%min)
            return 1;

    // if n >= 0, then p can be either odd or even
    if (n > 0)
        return min;
    // if n < 0, then p must be odd
    else
    {
        while (!(min%2))
            min /= 2;
        return min;
    }

}

int select(int *arr, int index)
{
    int i;
    for ( i = 0; i < index; i++)
        if (arr[i])
            return arr[i];
    return -1;
}

int abs(int n)
{
    return n >= 0 ? n : -n;
}

Q10591: Happy Number

// Run time: 0.000
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char str[10];
int test(int len);
int main()
{
    int i, j;
    int n;
    int tmp;
    int len;
    int num;
    int cnt = 0;
    scanf("%d", &n);

    while (n--)
    {
        scanf("%s", str);
        tmp = atoi(str);
        len = strlen(str);
        num = test(len);

        if (num)
            printf("Case #%d: %d is a Happy number.\n", ++cnt, tmp);
        else
            printf("Case #%d: %d is an Unhappy number.\n", ++cnt, tmp);

    }

    return 0;

}

int test(int len)
{
    int i;
    int sum = 0;

    for ( i = 0; i < len; i++)
        sum += (str[i]-'0')*(str[i]-'0');


    if (sum == 1)
        return 1;

    if (sum >= 10)
    {
        snprintf(str, sizeof(str), "%d\0", sum);
        len = strlen(str);
        return test(len);
    }

    return 0;
}

Q10196: Check the Check

/*
   array 的 index 如果超出範圍記得要事先預防掉
   不然會出錯

   Run time: 0.000
*/
#include <stdio.h>
#include <string.h>
#include <ctype.h>
const int SIZE = 8;
char str[SIZE][SIZE+1];
void run();
bool testwhite(int x, int y);
bool testblack(int x, int y);
bool knight(int x, int y, char ch);
bool bishop(int x, int y, char ch);
bool rook(int x, int y, char ch);
bool range(int x, int y);
void print(int n);

int main()
{
   int i, j;
   int eof;
   char ch;

   while (true)
   {
       eof = 0;
       for ( i = 0; i < SIZE; i++)
       {
           scanf("%s", str[i]);

           if (!strcmp(str[i], "........"))
               eof++;
       }

       if (eof == SIZE)
           break;

       run();
   }

   return 0;
}

void run()
{
   int i, j;
   int state = 3;
   bool s = true;

   for ( i = 0; i < SIZE; i++)
   {
       for ( j = 0; j < SIZE; j++)
       {
           if (str[i][j] == 'K')
           {
               s = false;
               if  (testwhite(i, j))
               {
                   state = 1; // 白色輸
                   print(state);
                   return;
               }
           }
       }

       if (!s) break;
   }

   s = true;

   for ( i = 0; i < SIZE; i++)
   {
       for ( j = 0; j < SIZE; j++)
       {
           if (str[i][j] == 'k')
           {
               s = false;
               if (testblack(i, j))
               {
                   state = 2; // 黑色輸
                   print(state);
                   return;
               }

           }
       }
       if (!s) break;
   }

   print(state);
}

bool testwhite(int x, int y)
{
   int i, j;
   bool s = false;

   // pwan
   if ((range(x-1, y-1) && str[x-1][y-1] == 'p') || (range(x-1, y+1) && str[x-1][y+1] == 'p'))
       return true;

   if (knight(x, y, 'n'))
       return true;

   if (bishop(x, y, 'b'))
       return true;

   if (rook(x, y, 'r'))
       return true;

   // queen
   if (bishop(x, y, 'q'))
       return true;
   if (rook(x, y, 'q'))
       return true;

   return false;

}

bool testblack(int x, int y)
{
   int i, j;
   bool s = false;

   // pawn
   if ((range(x+1, y-1) && str[x+1][y-1] == 'P') || (range(x+1, y+1) && str[x+1][y+1] == 'P'))
       return true;

   if (knight(x, y, 'N'))
       return true;

   if (bishop(x, y, 'B'))
       return true;

   if (rook(x, y, 'R'))
       return true;

   // Queen
   if (bishop(x, y, 'Q'))
       return true;
   if (rook(x, y, 'Q'))
       return true;

   return false;
}

bool knight(int x, int y, char ch)
{
   if (range(x-2, y+1) && str[x-2][y+1] == ch)
       return true;
   if (range(x-1, y+2) && str[x-1][y+2] == ch)
       return true;
   if (range(x+1, y+2) && str[x+1][y+2] == ch)
       return true;
   if (range(x+2, y+1) && str[x+2][y+1] == ch)
       return true;
   if (range(x+2, y-1) && str[x+2][y-1] == ch)
       return true;
   if (range(x+1, y-2) && str[x+1][y-2] == ch)
       return true;
   if (range(x-1, y-2) && str[x-1][y-2] == ch)
       return true;
   if (range(x-2, y-1) && str[x-2][y-1] == ch)
       return true;

   return false;
}

bool bishop(int x, int y, char ch)
{
   bool s = false;
   int i, j;

   // 往右上角推
   for ( i = x-1, j = y+1; i >= 0 && j < SIZE; i--, j++)
   {
       if (isalpha(str[i][j]) && str[i][j] != ch)
           break;

       if (str[i][j] == '.')
           continue;

       s = true;
   }

   if (s)  return true;

   // 往右下角推
   for ( i = x+1, j = y+1; i < SIZE && j < SIZE; i++, j++)
   {
       if (isalpha(str[i][j]) && str[i][j] != ch)
           break;

       if (str[i][j] == '.')
           continue;

       s = true;
   }

   if (s)  return true;

   // 往左上角推
   for ( i = x-1, j = y-1; i >= 0 && j >= 0; i--, j--)
   {
       if (isalpha(str[i][j]) && str[i][j] != ch)
           break;

       if (str[i][j] == '.')
           continue;

       s = true;
   }

   if (s)  return true;

   // 往左下角推
   for ( i = x+1, j = y-1; i < SIZE && j >= 0; i++, j--)
   {
       if (isalpha(str[i][j]) && str[i][j] != ch)
           break;

       if (str[i][j] == '.')
           continue;

       s = true;
   }

   if (s)  return true;

   return false;
}

bool rook(int x, int y, char ch)
{
   bool s = false;
   int i, j;

   // 往下推
   for ( i = x+1, j = y; i < SIZE; i++)
   {
       if (isalpha(str[i][j]) && str[i][j] != ch)
           break;

       if (str[i][j] == '.')
           continue;

       s = true;
   }

   if (s)  return true;

   // 往上推
   for ( i = x-1, j = y; i >= 0; i--)
   {
       if (isalpha(str[i][j]) && str[i][j] != ch)
           break;

       if (str[i][j] == '.')
           continue;

       s = true;
   }

   if (s)  return true;

   // 往左推
   for ( i = x, j = y-1; j >= 0; j--)
   {
       if (isalpha(str[i][j]) && str[i][j] != ch)
           break;

       if (str[i][j] == '.')
           continue;

       s = true;
   }

   if (s)  return true;

   // 往右推
   for ( i = x, j = y+1; j < SIZE; j++)
   {
       if (isalpha(str[i][j]) && str[i][j] != ch)
           break;

       if (str[i][j] == '.')
           continue;

       s = true;
   }

   if (s)  return true;

   return false;
}

bool range(int x, int y)
{
   if (x >= 0 && x < SIZE && y >= 0 && y < SIZE)
       return true;

   return false;
}
void print(int n)
{
   static int cnt = 0;

   if (n == 1)
       printf("Game #%d: white king is in check.\n", ++cnt);
   else
   if (n == 2)
       printf("Game #%d: black king is in check.\n", ++cnt);
   else
       printf("Game #%d: no king is in check.\n", ++cnt);
}

Q10188: Automated Judge Script

/*
    Note:
    1

    2


    這樣是PE

    2
    10188
    2005
    3
    101
    88
    2005
    這樣是PE
    Run time: 0.000
*/
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define AC 0
#define PE 1
#define WA 2
#define SIZE 120
#define N 100
char ans[N][SIZE+1];
char str[N][SIZE+1];
int accept(int n);
int present(int n, int m);

void print(int n);

int main()
{
    int n, m;
    int i;
    int state;
    while (scanf("%d", &n))
    {
        if (!n) break;

        state = WA;

        // getchar 不要放在scanf裡
        getchar();

        for ( i = 0; i < n; i++)
            gets(ans[i]);

        scanf("%d", &m);

        // getchar 不要放在scanf裡
        getchar();

        for ( i = 0; i < m; i++)
            gets(str[i]);

        if (n == m)
        {
            if (accept(n))
            {
                state = AC;
                print(state);
                continue;
            }
        }

        if (present(n, m))
        {
            state = PE;
            print(state);
            continue;
        }

        print(state);

    }

    return 0;
}

int accept(int n)
{
    int i, j;
    for ( i = 0; i < n; i++)
        if (strcmp(ans[i], str[i]))
            return false;

    return true;
}

int present(int n, int m)
{
    int i, j, k;
    char s1[N*SIZE];
    char s2[N*SIZE];

    for ( i = 0, k = 0; i < n; i++)
        for ( j = 0; ans[i][j] != '\0'; j++)
            if (isdigit(ans[i][j]))
                s1[k++] = ans[i][j];

    s1[k] = '\0';

    for ( i = 0, k = 0; i < m; i++)
        for ( j = 0; str[i][j] != '\0'; j++)
            if (isdigit(str[i][j]))
                s2[k++] = str[i][j];

    s2[k] = '\0';

    if (!strcmp(s1, s2))
        return true;
    else
        return false;
}

void print(int n)
{
    static int run;

    if (n == AC)
        printf("Run #%d: Accepted\n", ++run);

    else
    if (n == PE)
        printf("Run #%d: Presentation Error\n", ++run);

    else
    if (n == WA)
        printf("Run #%d: Wrong Answer\n", ++run);

}

Q10365: Blocks

// Run time: 0.000
#include <stdio.h>
#define MIN 1000000  // enough huge number
int main()
{
    int num;
    int n;
    int min;
    int i, j, k;
    int area;
    scanf("%d", &num);

    while (num--)
    {
        scanf("%d", &n);

        min = MIN;

        for ( i = 1; i <= n; i++)
        {
            if (!(n%i))
            for ( j = i; j <= n/i; j++)
            {
                if (!(n%(i*j)))
                {
                    k = n/i/j;
                    if (k < j)  break;

                    if (i*j*k == n)
                    {
                        area = (i*j+j*k+i*k)*2;
                        min = area < min ? area : min;
                    }
                }
            }
        }

        printf("%d\n", min);
    }
   
    return 0;
}

Q10268: 498'

// Run time: 0.120
#include <stdio.h>
#define N 500000
int arr[N];
void calculate(int x, int num);

int main()
{
    int i;
    int num;
    int x;
    while (scanf("%d", &x) != EOF)
    {
        for ( i = 0; ; i++)
        {
            scanf("%d", &arr[i]);

            if (getchar() == '\n')
                break;
        }

        num = i; // <=

        if (x)
            calculate(x, num);
        else
            printf("%d\n", arr[num-1]);


    }

    return 0;
}

void calculate(int x, int num)
{
    int i, j;
    long long int sum = 0;
    long long int product = 1;

    for ( i = num-1, j = 1; i >= 0; i--, j++)
    {
        sum += arr[i]*product*j;
        product *= x;
    }

    printf("%lld\n", sum);
}

Q10258: Contest Scoreboard

/*
    contestant  problem  time  L
    其中contestant為參賽者編號（1～100）
    problem為題目編號（1～9）
    time為上傳的時間（從比賽開始算起的分鐘數）
    L為裁判結果，分為C、I、R、U、E。C代表正確，I代表不正確，後三者不影響分數

    Run time: 0.000
*/
#include <stdio.h>
#define N 100
typedef struct {
    bool join;
    bool prob[9];
    int wrong[9];
    int penalty;
    int finish;
    int accept[9];
} Score;
Score record[N];
bool s[N];

void init();
void assign(int n, int question, int time, char result);
void calculate();
void sort();
int select();

int main()
{
    char str[N];
    int n;
    int num, q, t;
    char ch;

    scanf("%d\n", &n);

    while (n--)
    {
        // 設定一些value
        init();

        while (gets(str))
        {
            if (str[0] == '\0') break;

            // 拆解字串
            sscanf(str, "%d %d %d %c", &num, &q, &t, &ch);

            // 如果這個人解這題還沒accept
            if (!record[num-1].prob[q-1])
                assign(num, q, t, ch);
        }

        // calculate the penalty: (number of wrong answer)*20 + accepting time
        calculate();


        /*
            sorting's priority:
            1. solve the number of problems
            2. the less penalty, the better rank
            3. if (1) and (2) are the same, and displayed in order of increasing team numbers
        */
        sort();

        if (n)
           printf("\n");
    }

    return 0;
}

void init()
{
    int i, j;

    for ( i = 0; i < N; i++)
    {
        for ( j = 0; j < 9; j++)
        {
            record[i].prob[j] = false;
            record[i].wrong[j] = 0;
        }
        record[i].penalty = 0;
        record[i].finish = 0;
        record[i].join = false;
        s[i] = false;
    }
}

void assign(int n, int question, int time, char result)
{
    // 表示有參加比賽
    record[n-1].join = true;

    // if the user got the Accept result
    if (result == 'C')
    {
        record[n-1].prob[question-1] = true;
        record[n-1].accept[question-1] = time;
        record[n-1].finish++;
    }

    // if the user got the Wrong result
    else
    if (result == 'I')
        record[n-1].wrong[question-1]++;
}

void calculate()
{
    int i, j;

    for ( i = 0; i < N; i++)
        if (record[i].join)
            for ( j = 0; j < 9; j++)
                if (record[i].prob[j])
                    record[i].penalty += 20*record[i].wrong[j] + record[i].accept[j];
}

void sort()
{
    int i, j;
    int index;
    int max;
    for (; ;)
    {
        index = select();
        if (index == -1)    return;

        max = record[index].finish;

        for ( i = 0; i < N; i++)
        {
            if (record[i].join && !s[i] && (i != index))
            {
                if (record[i].finish > max)
                {
                    s[index] = false;
                    max = record[i].finish;
                    s[i] = true;
                    index = i;
                }
                else
                if (record[i].finish == max)
                {
                    if (record[i].penalty < record[index].penalty)
                    {
                        max = record[i].finish;
                        index = i;
                    }
                }
            }
        }
        s[index] = true;
        printf("%d %d %d\n", index+1, record[index].finish, record[index].penalty);
    }

}

int select()
{
    int i;

    for ( i = 0; i < N; i++)
    {
        if (record[i].join && !s[i])
        {
            s[i] = true;
            return i;
        }
    }
    return -1;
}

Q10242: Fourth Point!!

/*
    利用平行四邊形的 座標和(sum) 性質
    Run time: 0.000
*/
#include <stdio.h>
double arr[4][2];
int test();
void calculate(int n);
int main()
{
    int i, j;
    int state;

    while (scanf("%lf", &arr[0][0]) != EOF)
    {
        scanf("%lf", &arr[0][1]);
        for ( i = 1; i < 4; i++)
            scanf("%lf%lf", &arr[i][0], &arr[i][1]);

        state = test();
        calculate(state);
    }
    return 0;
}

int test()
{
    int state;

    if (arr[0][0] == arr[2][0] && arr[0][1] == arr[2][1])
        state = 1;
    else
    if (arr[0][0] == arr[3][0] && arr[0][1] == arr[3][1])
        state = 2;
    else
    if (arr[1][0] == arr[2][0] && arr[1][1] == arr[2][1])
        state = 3;
    else
        state = 4;

    return state;
}

void calculate(int n)
{
    double x, y;

    if (n == 1)
    {
        x = arr[1][0]+arr[3][0]-arr[0][0];
        y = arr[1][1]+arr[3][1]-arr[0][1];
        printf("%.3lf %.3lf\n", x, y);
        return;
    }
    if (n == 2)
    {
        x = arr[1][0]+arr[2][0]-arr[0][0];
        y = arr[1][1]+arr[2][1]-arr[0][1];
        printf("%.3lf %.3lf\n", x, y);
        return;
    }

    if (n == 3)
    {
        x = arr[0][0]+arr[3][0]-arr[1][0];
        y = arr[0][1]+arr[3][1]-arr[1][1];
        printf("%.3lf %.3lf\n", x, y);
        return;
    }

    if (n == 4)
    {
        x = arr[0][0]+arr[2][0]-arr[1][0];
        y = arr[0][1]+arr[2][1]-arr[1][1];
        printf("%.3lf %.3lf\n", x, y);
        return;
    }
}

Q10223: How many nodes ?

/*
    Catalan Number:
    1. C(n) = C(n-1)*(4n-2) / (n+1)
    2. C(n) = (2n)! / ( n!(n+1)! )
    3. C(n) = C(0)C(n-1) + C(1)C(n-2) +....+ C(n-1)C(0)

    Run time: 0.000
*/
#include <stdio.h>

int main()
{
    double arr[19];
    unsigned int n;
    int i;

    double prod;


    //  利用第二式寫的
/*
    int twice_n;
    for ( i = 0; i < 19; i++)
    {
        prod = 1;
        twice_n = (i+1)*2;
        for ( j = 0; j < i; )
            prod *= (double)twice_n--/++j;
        prod /= ++j;
        arr[i] = prod;

    }
*/
    //  利用第一式寫的
    arr[0] = 1;
    for ( i = 2; i <= 19; i++)
        arr[i-1] = arr[i-2]*(4*i-2)/(i+1);


    while (scanf("%u", &n) != EOF)
    {
        for ( i = 0; i < 19; i++)
            if (arr[i] == n)
               {printf("%d\n", i+1);  continue;}
    }

    return 0;
}

Q10235: Simply Emirp

/*
    注意：字串assign完之後要在最後一位後面加上 '\0'  不然會讀錯
    Run time: 0.040
*/
#include <stdio.h>
#include <string.h>
#define N 1000000
bool isprime[N+1];

int main()
{
    int i, j;

    for ( i = 2; i*i <= N; i++)
        if (!isprime[i])
            for ( j = 2*i; j <= N; j+=i)
                isprime[j] = true;

    int n;
    int reverse;
    int len;
    char str[7];
    char rev[7];

    while (scanf("%d", &n) != EOF)
    {
        if (isprime[n])
        {
            printf("%d is not prime.\n", n);
            continue;
        }

        snprintf(str, sizeof(str), "%d\0", n);

        len = strlen(str);

        for ( i = len-1, j = 0; i >= 0; i--)
            rev[j++] = str[i];

        rev[j] = '\0';

        sscanf(rev, "%d", &reverse);

        if (!isprime[reverse] && (n != reverse))
            printf("%d is emirp.\n", n);
        else
            printf("%d is prime.\n", n);

    }

    return 0;
}

Q10219: Find the ways!

/*
    先把組合數算出來
    再把結果放到 string 裡
    去算他的長度
    就是幾位數

    Run time: 0.000
*/
#include <stdio.h>
#include <string.h>

int main()
{
    int n, m;
    int i;
    double prod;
    char str[100];
    while (scanf("%d%d", &n, &m) == 2)
    {
        prod = 1;
        for ( i = 0; i < m; )
            prod *= (double)n--/++i;

        snprintf(str, sizeof(str), "%.0lf\0", prod);
        printf("%d\n", strlen(str));
    }

    return 0;
}

Q10200: Prime Time

// Run time: 0.080
#include <stdio.h>
#include <math.h>
#define EPS pow(10, -9)  // 誤差用
#define N 10007
int prime[1230];
int arr[N];
bool isprime[N+1];
bool state[N+1];
int calculate(int n);
bool test(int n);

int main()
{
    int i, j;

    // 找2到超過10000的質數
    for ( i = 2; i <= N; i++)
        if (!isprime[i])
            for ( j = 2*i; j <= N; j+=i)
                isprime[j] = true;

    // assign prime to array
    for ( i = 2, j = 0; i <= N; i++)
        if (!isprime[i])
            prime[j++] = i;

    int a, b;
    int n;
    int cnt = 0;
    double percent;


    for ( i = 0; i <= 10000; i++)
    {
        n = calculate(i);
        arr[i] = test(n) ? ++cnt : cnt;
    }

    while (scanf("%d%d", &a, &b) == 2)
    {
        if (a >= 1 && arr[a] == arr[a-1])
            percent = ((arr[b]-arr[a])*100+EPS)/(b-a+1);
        else
            percent = ((arr[b]-arr[a]+1)*100+EPS)/(b-a+1);
        printf("%.2lf\n", percent);
    }

    return 0;

}

int calculate(int n)
{
    return n * n + n + 41;
}

bool test(int n)
{
    int i;
    for ( i = 0; prime[i]*prime[i] <= n; i++)
        if (!(n%prime[i]))
            return false;

    return true;
}

Q10193: All You Need Is Love

// Run time: 0.000
#include <stdio.h>
#include <string.h>
#define N 30
int calculate(int *arr, int len);
int gcd(int a, int b);
int main()
{
    char s1[N+1];
    char s2[N+1];
    int arr1[N];
    int arr2[N];

    int i;  // (for loop)'s count
    int n;  // 輸入組數
    int cnt = 0;  // for output counting
    int len1, len2;  // input string's length
    int a, b;  // trans to binary

    scanf("%d\n", &n);

    while (n--)
    {
        gets(s1);
        gets(s2);

        len1 = strlen(s1);
        len2 = strlen(s2);

        for ( i = 0; i < len1; i++)
            arr1[i] = s1[i] - '0';

        for ( i = 0; i < len2; i++)
            arr2[i] = s2[i] - '0';

        a = calculate(arr1, len1);
        b = calculate(arr2, len2);

        if (gcd(a, b) != 1)
            printf("Pair #%d: All you need is love!\n", ++cnt);
        else
            printf("Pair #%d: Love is not all you need!\n", ++cnt);

    }

    return 0;
}

int calculate(int *arr, int len)
{
    int i;
    int sum = 0;
    int weight = 1;

    for ( i = len-1; i >= 0; i--)
    {
        sum += arr[i]*weight;
        weight *= 2;
    }

    return sum;
}

int gcd(int a, int b)
{
    if (!a)
        return b;
    else
        return gcd(b%a, a);
}

Q10189: Minesweeper

// Run time: 0.000
#include <stdio.h>
#define N 100
char str[N][N+1];
int arr[N][N];
int main()
{
    int i, j;
    int row, col;
    int cnt = 0;
    bool s = false;

    while (scanf("%d%d", &row, &col))
    {
        if (!row && !col)   break;

        getchar();

        for ( i = 0; i < row; i++)
            gets(str[i]);

        for ( i = 0; i < row; i++)
            for ( j = 0; j < col; j++)
                arr[i][j] = 0;

        for ( i = 0; i < row; i++)
        {
            for ( j = 0; j < col; j++)
            {
                if (str[i][j] == '*')
                {
                    if (i >= 1)
                    {
                        if (j >= 1) arr[i-1][j-1]++;
                        arr[i-1][j]++;
                        if (j < col-1)  arr[i-1][j+1]++;
                    }

                    if (j >= 1) arr[i][j-1]++;
                    if (j < col-1) arr[i][j+1]++;

                    if (i < row-1)
                    {
                        if (j >= 1) arr[i+1][j-1]++;
                        arr[i+1][j]++;
                        if (j < col-1) arr[i+1][j+1]++;
                    }

                }
            }
        }

        if (s)
           printf("\n");
        s = true;

        printf("Field #%d:\n", ++cnt);
        for ( i = 0; i < row; i++)
        {
            for ( j = 0; j < col; j++)
            {
                if (str[i][j] == '*')
                    putchar('*');
                else
                    printf("%d", arr[i][j]);
            }
            printf("\n");
        }
    }
}

Q10167: Birthday Cake

/*
    判斷點是否在線上，或者在線的上方或下方
    然後去統計全部的點數
    如果一樣多就OK

    Run time: 0.230
*/
#include <stdio.h>
void choose(int *arr[2], int N);
bool test(int A, int B, int *arr[2], int N);

int main()
{
    int N;
    int i;

    while (scanf("%d", &N))
    {
        if (!N) break;

        int **arr = new int*[2*N];
        for ( i = 0; i < 2*N; i++)
            arr[i] = new int[2];

        for ( i = 0; i < 2*N; i++)
            scanf("%d%d", &arr[i][0], &arr[i][1]);

        choose(arr, N);

    }

    return 0;
}

void choose(int *arr[2], int N)
{
    int i, j;
    int a, b;
    for ( i = -500; i <= 500; i++)
        for ( j = -500; j <= 500; j++)
            if (test(i, j, arr, N))
                return;
}

bool test(int A, int B, int *arr[2], int N)
{
    int i, j;
    int result;
    int positive = 0;
    int negative = 0;

    for ( i = 0; i < 2*N; i++)
    {
        result = A*arr[i][0] + B*arr[i][1];
        if (result > 0)
            positive++;
        else
        if (result < 0)
            negative++;
        else
            return false;
    }

    if (positive == negative)
    {
        printf("%d %d\n", A, B);
        return true;
    }

    return false;
}

Q10161: Ant on a Chessboard

/*
    先把平方根為整數的找出來
    再去算剩下的
   
    Run time: 0.000
*/
#include <stdio.h>
#include <math.h>

int main()
{
    int N;
    int k;
    int row, col;
    while (scanf("%d", &N))
    {
        if (!N) break;

        k = (int)sqrt(N);

        if (k*k == N)
        {
            if (k%2)
                printf("1 %d\n", k);
            else
                printf("%d 1\n", k);
        }

        else
        {
            if (k%2)
            {
                if (N <= k*k+k+1)
                    printf("%d %d\n", N-k*k, k+1);
                else
                {
                    row = col = k+1;

                    while (N-- != k*k+k+1)
                        col--;

                    printf("%d %d\n", row, col);
                }
            }
            else
            {
                if (N <= k*k+k+1)
                    printf("%d %d\n", k+1, N-k*k);
                else
                {
                    row = col = k+1;

                    while (N-- != k*k+k+1)
                        row--;

                    printf("%d %d\n", row, col);
                }
            }
        }

    }
    return 0;
}

Q10112: Myacm Triangles

/*
   判斷是否在三角形內，我用面積的和的方法來看
   如果大於表示在外面，等於就是在裡面或線上
   fabs(total-t_area) < 1e-6 因為double 會有誤差

   Run time: 0.000
*/
#include <stdio.h>
#include <math.h>

typedef struct {
   int x, y;
   char ch;
} Pos;
Pos pos[15];

double t_area;
double max;

// calculate the triangle area
double triangle(Pos a, Pos b, Pos c);

// 因為輸出必須按照字母順序
void sort(char a, char b, char c);
void swap(int &a, int &b);

int main()
{
   int n;
   int i, j, k;
   int l;
   int index_a, index_b, index_c;

   double area_a, area_b, area_c;
   double total;

   while (scanf("%d", &n))
   {
       if (!n) break;

       getchar();

       for ( i = 0; i < n-1; i++)
           scanf("%c%d%d\n", &pos[i].ch, &pos[i].x, &pos[i].y);
       scanf("%c%d%d", &pos[i].ch, &pos[i].x, &pos[i].y);

       max = 0;

       for ( i = 0; i < n; i++)
       {
           for ( j = i+1; j < n; j++)
           {
               for ( k = j+1; k < n; k++)
               {
                   // calculate the triangle area
                   t_area = triangle(pos[i], pos[j], pos[k]);

                   if (t_area > max)
                   for ( l = 0; l < n; l++)
                   {
                       if (l == i || l == j || l == k) continue;

                       area_a = triangle(pos[i], pos[j], pos[l]);
                       area_b = triangle(pos[i], pos[l], pos[k]);
                       area_c = triangle(pos[l], pos[j], pos[k]);

                       total = area_a+area_b+area_c;

                       if (fabs(total-t_area) < 1e-6)
                           break;
                   }

                   if (l == n && max < t_area)
                   {
                       index_a = i;
                       index_b = j;
                       index_c = k;
                       max = t_area;
                   }
               }
           }
       }

       sort(pos[index_a].ch, pos[index_b].ch, pos[index_c].ch);

   }

   return 0;
}

double triangle(Pos a, Pos b, Pos c)
{
   double area;
   area = a.x*b.y+b.x*c.y+c.x*a.y-(b.x*a.y+c.x*b.y+a.x*c.y);
   area = area >= 0 ? area : -area;

   return 0.5*area;
}

void sort(char a, char b, char c)
{
   int i, j;
   int index;
   int arr[3];
   int n = 3;
   arr[0] = a;
   arr[1] = b;
   arr[2] = c;

   int max;
   for ( i = 0; i < n-1; i++)
   {
       max = arr[0];
       index = 0;
       for ( j = 0; j < n-i; j++)
       {
           if (arr[j] > max)
           {
               max = arr[j];
               index = j;
           }
       }
       swap(arr[index], arr[j-1]);
   }

   for ( i = 0; i < n; i++)
       printf("%c", arr[i]);
   printf("\n");
}

void swap(int &a, int &b)
{
   int tmp;
   tmp = a;
   a = b;
   b = tmp;
}

Q10105: Polynomial coefficients

// Run time: 0.010
#include <stdio.h>
int arr[12];
double calculate(int n, int m);

int main()
{
    int n, k;
    int i;
    double prod;
    int sum;
    while (scanf("%d%d", &n, &k) == 2)
    {
        prod = 1;
        sum = 0;
        for ( i = 0; i < k; i++)
            scanf("%d", &arr[i]);

        for ( i = 0; i < k; i++)
            sum += arr[i];

        if (sum > n)
        {
            printf("0\n");
            continue;
        }
        for ( i = 0; i < k; i++)
        {
            prod *= calculate(n, arr[i]);
            n -= arr[i];
        }
        printf("%.0lf\n", prod);

    }

    return 0;
}

double calculate(int n, int m)
{
    int i, j;
    double sum = 1;

    if (2*m > n)
        m = n-m;

    for ( i = 0; i < m;)
        sum *= double(n--)/double(++i);

    return sum;
}

Q10106: Product

/*
    大數的乘法
    必須利用int arr[n]去一個一個乘
    這跟階層到很高的階層數的題目類似

    Run time: 0.000
*/
#include <stdio.h>
#include <string.h>
#define N 251
char prod1[N];
char prod2[N];
int arr1[N];
int arr2[N];
int ans[2*N];
void to_INT(int len1, int len2);
void prod(int len1, int len2);

int main()
{
    int len1, len2;
    while (gets(prod1) != NULL)
    {
        gets(prod2);

        len1 = strlen(prod1);
        len2 = strlen(prod2);

        to_INT(len1, len2);

        prod(len1, len2);

    }

    return 0;
}

void to_INT(int len1, int len2)
{
    int i, j;

    for ( i = len1-1, j = 0; i >= 0; i--, j++)
        arr1[j] = prod1[i]-'0';

    for ( i = len2-1, j = 0; i >= 0; i--, j++)
        arr2[j] = prod2[i]-'0';
}

void prod(int len1, int len2)
{
    int i, j, k;

    for ( i = 0; i < 2*N; i++)
        ans[i] = 0;

    for ( i = 0; i < len1; i++)
    {
        for ( j = 0, k = i; j < len2; j++)
            ans[k++] += arr1[i]*arr2[j];

        for ( j = 0; j < k-1; j++)
        {
            if (ans[j] >= 10)
            {
                ans[j+1] += ans[j]/10;
                ans[j] %= 10;
            }
        }
    }

    for ( i = k-1; i >= 0; i--)
        if (ans[i]) break;

    if (i == -1)  printf("0\n");

    else
    {
        for ( ; i >= 0; i--)
            printf("%d", ans[i]);
        printf("\n");
    }

}

Q10041: Vito's family

/*
    Sorting first, and find the median.
    At last, calculating the distance.
    Run time: 0.060
*/
#include <stdio.h>
int sort(int *arr, int n);
int median(int n);
void swap(int &a, int &b);

int main()
{
    int num;
    int n; // number of neighbor
    int i;

    scanf("%d", &num);
    while (num--)
    {
        scanf("%d", &n);
        int arr[n];

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

        printf("%d\n", sort(arr, n));
    }

    return 0;
}

int sort(int *arr, int n)
{
    int i, j;
    int max;
    int index;
    int sum = 0;

    // using selection sort
    for ( i = 0; i < n-1; i++)
    {
        max = arr[0];
        index = 0;
        for ( j = 0; j < n-i; j++)
        {
            if (arr[j] > max)
            {
                max = arr[j];
                index = j;
            }
        }
        swap(arr[index], arr[j-1]);
    }

    // find median
    index = median(n);

    for ( i = 0; i < n; i++)
        sum += (arr[i] >= arr[index]) ? arr[i]-arr[index] : arr[index] - arr[i];

    return sum;
}

int median(int n)
{
    return n%2 ? (n+1)/2-1 : n/2-1;
}

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

Q10056: What is the Probability?

// Run time: 0.010
#include <stdio.h>
double calculate(int n, double p, int index);
int main()
{
   int num;  // 輸入組數
   int n; // 人數
   double prob; // Probability
   int index; // which player

   scanf("%d", &num);
   while (num--)
   {
       scanf("%d%lf%d", &n, &prob, &index);

       if (!prob)
           printf("0.0000\n");
       else
           printf("%.4lf\n", calculate(n, prob, index));
   }

   return 0;
}

double calculate(int n, double p, int index)
{
   int i;
   double arr[n];
   double non_win = 1-p;
   double weight = 1-p;
   double prod;

   arr[0] = p; // initial

   for ( i = 1; i < n; i++)
   {
       prod = non_win*p;  // 前面都沒發生的機率 * 事件發生的機率
       arr[i] = prod;
       non_win = non_win*weight;
   }

   double sum = 0;

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

   return arr[index-1]/sum;
}

Q10015: Joseph's Cousin

/*
    質數選法用sieve
    要讓跑的次數少一點
    不然會很沒有效率
    Run time: 0.030
*/
#include <stdio.h>
#define N 32610
int prime[3500];
bool isprime[N];
void assignPrime();
int test(int n);

int main()
{
    assignPrime();
    int n;
    int survivor;
    while (scanf("%d", &n))
    {
        if (!n) break;

        survivor = test(n);
        printf("%d\n", survivor);
    }
    return 0;
}

void assignPrime()
{
    int i, j;

    for ( i = 2; i*i <= N; i++)
        if (!isprime[i])
            for ( j = 2*i; j <= N; j+=i)
                isprime[j] = true;

    for ( i = 2, j = 0; i <= N; i++)
        if (!isprime[i])
            prime[j++] = i;
}

int test(int n)
{
    int left = n;
    int count;
    int index = 0;
    int i, j;
    bool arr[n];

    for ( i = 0; i < n; i++)
        arr[i] = true;

    for ( i = 0; i < n-1; i++)
    {
        count = (left < prime[i]) ? prime[i]%left : prime[i];

        for ( j = 0; j < count; index++)
        {
            if (index == n)
                index = 0;

            if (arr[index])
                j++;
        }

        arr[--index] = false;
        index++;
        left--;
    }

    for ( i = 0; i < n; i++)
        if (arr[i])
            return (i+1);
}

Q10014: Simple calculations

// Run time: 0.010
#include <stdio.h>
int main()
{
   int num; // 輸入組數
   int n;
   int i;  // for loop count
   int weight;
   double s, e; // a(0) and a(n+1)
   double sum, total;

   scanf("%d", &num);

   while (num--)
   {
       sum = total = weight = 0;

       scanf("%d", &n);
       scanf("%lf%lf", &s, &e);

       double arr[n];
       for ( i = 0; i < n; i++)
           scanf("%lf", &arr[i]);

       sum = s*n+e;

       for ( i = n-1; i >= 0; i--)
           total += (weight+=2)*arr[i];

       printf("%.2lf\n", (sum-total)/(n+1));

       if (num)
           printf("\n");
   }

   return 0;
}

Q10010: Where's Waldorf?

// Run time: 0.000
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define N 50
char str[N][N+1];
char arr[N+1];
void check(int length, char ch, int row, int len);
bool test(int row, int col, int length, int row, int len);

int main()
{
    int n;
    int row, len;
    int length; // check string's length
    int num;
    int i, j;

    scanf("%d", &n);
    while (n--)
    {
        scanf("%d%d\n", &row, &len);

        // input
        for ( i = 0; i < row; i++)
            gets(str[i]);

        // toupper
        for ( i = 0; i < row; i++)
            for ( j = 0; j < len; j++)
                str[i][j] = toupper(str[i][j]);

        scanf("%d\n", &num);

        // input for check string
        while (num--)
        {
            gets(arr);
            length = strlen(arr);

            // toupper case
            for ( i = 0; i < length; i++)
                arr[i] = toupper(arr[i]);

            check(length, arr[0], row, len);
        }
        if (n)
            printf("\n");
    }

    return 0;
}

void check(int length, char ch, int row, int len)
{
    int i, j;
    for ( i = 0; i < row; i++)
        for ( j = 0; j < len; j++)
            if (str[i][j] == ch)
                if (test(i, j, length, row, len))
                    return;
}

bool test(int r, int c, int length, int row, int len)
{
    int i, j, k;

    // 往左看
    if (c-length >= -1)
    {
        for ( i = c-1, j = 1; j < length; i--, j++)
            if (str[r][i] != arr[j])
                break;
        if (j == length)
        {
            printf("%d %d\n", r+1, c+1);
            return true;
        }
    }

    // 往右看
    if (len-c >= length)
    {
        for ( i = c+1, j = 1; j < length; i++, j++)
            if (str[r][i] != arr[j])
                break;
        if (j == length)
        {
            printf("%d %d\n", r+1, c+1);
            return true;
        }
    }

    // 往上看
    if (r-length >= -1)
    {
        for ( i = r-1, j = 1; j < length; i--, j++)
            if (str[i][c] != arr[j])
                break;
        if (j == length)
        {
            printf("%d %d\n", r+1, c+1);
            return true;
        }
    }

    // 往下看
    if (r+length <= row)
    {
        for ( i = r+1, j = 1; j < length; i++, j++)
            if (str[i][c] != arr[j])
                break;
        if (j == length)
        {
            printf("%d %d\n", r+1, c+1);
            return true;
        }
    }

    // 往左上
    if (c-length >= -1 && r-length >= -1)
    {
        for ( i = r-1, j = c-1, k = 1; k < length; i--, j--, k++)
            if (str[i][j] != arr[k])
                break;
        if (k == length)
        {
            printf("%d %d\n", r+1, c+1);
            return true;
        }
    }

    // 往右下
    if (len-c >= length && r+length <= row)
    {
        for ( i = r+1, j = c+1, k = 1; k < length; i++, j++, k++)
            if (str[i][j] != arr[k])
                break;
        if (k == length)
        {
            printf("%d %d\n", r+1, c+1);
            return true;
        }
    }

    // 往左下
    if (c-length >= -1 && r+length <= row)
    {
        for ( i = r+1, j = c-1, k = 1; k < length; i++, j--, k++)
            if (str[i][j] != arr[k])
                break;
        if (k == length)
        {
            printf("%d %d\n", r+1, c+1);
            return true;
        }
    }

    // 往右上
    if (len-c >= length && r-length >= -1)
    {
        for ( i = r-1, j = c+1, k = 1; k < length; i--, j++, k++)
            if (str[i][j] != arr[k])
                break;
        if (k == length)
        {
            printf("%d %d\n", r+1, c+1);
            return true;
        }
    }

    return false;
}

Q10008: What's Cryptanalysis

// Run time: 0.000
#include <stdio.h>
#include <ctype.h>
#define N 26
int arr[N];
bool state[N];
void calculate(char ch);
void sort();
int select();

int main()
{
    char ch;
    int n;
    int i;
    bool s = true;
    scanf("%d\n", &n);
    while (n--)
    {
        while (true)
        {
            if ((ch = getchar()) == '\n')
                break;
            calculate(ch);
        }
    }

    sort();

    return 0;
}

void calculate(char ch)
{
    ch = toupper(ch);
    if (isalpha(ch))
        arr[ch-'A']++;
}

void sort()
{
    int max, index;
    int i;
    for (; ;)
    {
        index = select();

        if (index == -1)
            return;

        max = arr[index];

        state[index] = true;

        for ( i = 0; i < N; i++)
        {
            if (!state[i] && arr[i] > max)
            {
                state[index] = false;
                state[i] = true;
                max = arr[i];
                index = i;
            }
        }

        printf("%c %d\n", index+'A', arr[index]);
    }
}

int select()
{
    int i;
    for ( i = 0; i < N; i++)
        if (!state[i] && arr[i])
            return i;
    return -1;
}

Q825: Walking on the Safe Side

// Run time: 0.000
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 101
int arr[N][N];
char str[1000];
void reset(int row, int col);
void assign(int row, int len);
void check(int row, int col);
int calculate(int row, int col);

int main()
{
  int n, row, col;
  int count, len;
  int i;

  scanf("%d", &n);
  while (n--)
  {
      scanf("%d%d\n", &row, &col);

      reset(row, col);

      for ( i = 1; i <= row; i++)
      {
          gets(str);
          len = strlen(str);
          assign(i, len);
      }

      check(row, col);

      count = calculate(row, col);
      printf("%d\n", count);

      if (n)  printf("\n");
  }

}

void reset(int row, int col)
{
  int i, j;
  for ( i = 1; i <= row; i++)
      for ( j = 1; j <= col; j++)
          arr[i][j] = 1;
}

void assign(int row, int len)
{
  int i, tmp;
  bool state = false;

  for ( i = 0; i < len; i++)
  {
      if (str[i] == ' ')  continue;
      tmp = atoi(str+i);

      if (state)
          arr[row][tmp] = 0;
      else
          state = true;
  }
}

void check(int row, int col)
{
  // 因為只能往右或下不能往左或上
  // 所以要做確認是否有誤
  int i, index;

  for ( i = 2; i < row; i++)
      if (!arr[i][1])
          break;
  index = i;

  if ( i != row)
      for ( i = index; i <= row; i++)
          arr[i][1] = 0;

  for ( i = 2; i < col; i++)
      if (!arr[1][i])
          break;
  index = i;

  if ( i != col)
      for ( i = index; i <= col; i++)
          arr[1][i] = 0;
}
int calculate(int row, int col)
{
  int i, j;

  for ( i = 2; i <= row; i++)
      for ( j = 2; j <= col; j++)
          arr[i][j] = arr[i][j] ? arr[i][j-1] + arr[i-1][j] : 0;

  return arr[row][col];
}

Q846: Steps

// Run time: 0.010
#include <stdio.h>
#include <math.h>
int calculate(int x, int y);
int main()
{
    int n;
    int step;
    int a, b;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d%d", &a, &b);
        step = calculate(a, b);
        printf("%d\n", step);
    }
    return 0;
}

int calculate(int x, int y)
{
    int sum = 0;
    int weight = 2;
    int n, cnt;

    n = y-x;

    if (!n)
        return 0;

    for ( ;sum < n; sum += weight, weight += 2);

    x = (int)sqrt(sum);

    if (n > x*x)
        cnt = 2*x;
    else
        cnt = 2*x-1;

    return cnt;
}

Q729: The Hamming Distance Problem

//  Run time: 0.820
#include <stdio.h>
#define N 16
int arr[N];
int len, distance;
void test(int len);
void calculate();
void print();

int main()
{
    int n;
    scanf("%d", &n);

    while (n--)
    {
        scanf("%d%d", &len, &distance);
        test(len);
        if (n)
            printf("\n");
    }

    return 0;
}

void test(int len)
{
    int i, j;
    int prod = 1;
    for ( i = 0; i < len; i++)
    {
        arr[i] = 0;
        prod *= 2;
    }

    for ( i = 0; i < prod; i++)
    {
        calculate();
        arr[0]++;
        for ( j = 0; j < len-1; j++)
        {

            if (arr[j] >= 2)
            {
                arr[j+1] += arr[j]/2;
                arr[j] %= 2;
            }
        }
    }
}

void calculate()
{
    int i;
    int count = 0;
    for ( i = 0; i < len; i++)
        count = arr[i] ? count+1 : count;

    if (count == distance)
        print();
}

void print()
{
    int i;
    for ( i = len-1; i >= 0; i--)
        printf("%d", arr[i]);
    printf("\n");
}

Q694: The Collatz Sequence

/*
   The same as Q100
   Run time: 0.050
*/
#include <stdio.h>
int calculate(long long int n, long long int limit);
int main()
{
   long long int num, limit;
   int count;
   int cnt = 0;
   while (scanf("%lld%lld", &num, &limit))
   {
       if (num < 0 && limit < 0)
           break;

       count = calculate(num, limit);

       printf("Case %d: A = %lld, limit = %lld, number of terms = %d\n", ++cnt, num, limit, count);

   }
}

int calculate(long long int n, long long int limit)
{
   int len = 1;
   while (n != 1)
   {
       n = n%2 ? 3*n+1 : n/2;

       if (n > limit)
           return len;
       len++;
   }
   return len;
}

Q343: What Base Is This ?

// Run time: 0.010
#include <stdio.h>
#include <string.h>
int find(int *num, int len);
int calculate(int *num, int len, int base);

int main()
{
    char str1[100], str2[100];
    int arr1[100], arr2[100];
    int len1, len2;
    int i; // base1
    int j; // base2
    int x, y;
    int m1, m2;
    while (scanf("%s%s", str1, str2) == 2)
    {
        len1 = strlen(str1);
        len2 = strlen(str2);

        for ( i = 0; i < len1; i++)
        {
            if (str1[i] >= '0' && str1[i] <= '9')
                arr1[i] = int(str1[i])-48;
            else
                arr1[i] = str1[i]- 'A' + 10;
        }
        for ( i = 0; i < len2; i++)
        {
            if (str2[i] >= '0' && str2[i] <= '9')
                arr2[i] = int(str2[i])-48;
            else
                arr2[i] = str2[i] - 'A' + 10;
        }

        m1 = find(arr1, len1);
        m2 = find(arr2, len2);

  //    printf("m1: %d, m2: %d\n", m1, m2);

        bool state = false;
        for ( i = m1; i <= 36; i++)
        {
            for ( j = m2; j <= 36; j++)
            {
                x = calculate(arr1, len1, i);
                y = calculate(arr2, len2, j);

                if (x < y)
                    break;
                else
                if (x == y)
                {
                    state = true;
                    break;
                }
            }

            if (state)
                break;
        }
        if (!state) // no one can equal
            printf("%s is not equal to %s in any base 2..36\n", str1, str2);
        else
            printf("%s (base %d) = %s (base %d)\n", str1, i, str2, j);

    }

    return 0;
}

int find(int *num, int len)
{
    if (len == 1 && (num[0] == 0 || num[0] == 1))
        return 2;
    int i;
    int max = num[0];
    for ( i = 1; i < len; i++)
    {
        if (num[i] > max)
            max = num[i];
    }
    return max+1;

}

int calculate(int *num, int len, int base)
{
    int i;
    int sum = 0;
    int weight = 1;

    for ( i = len-1; i >= 0; i--)
    {
        sum += num[i]*weight;
        weight *= base;
    }

    return sum;
}

Q679: Dropping Balls

/*
    這題要用 binary 來想
    假設 level = 4, times 可能 1~8 但會減1 就是 0~7

    times   binary system  position

                    位數
                    012
      0      1000 + 000     8+0
      1      1000 + 100     8+4
      2      1000 + 010     8+2
      3      1000 + 110     8+6
      4      1000 + 001     8+1
      5      1000 + 101     8+5
      6      1000 + 011     8+3
      7      1000 + 111     8+7
    Run time: 0.090
*/
#include <stdio.h>
int main()
{
    int n;
    int level;
    int times;
    int i;
    int pos;
    int weight;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d%d", &level, &times);

        // 0 to 2^(level-1)-1 讓次數介於這個範圍
        // 就可以用 binary 來表示了
        times--;

        // 要算 leaf 的第一個 node
        // 同時也代表最後一層有幾個node
        pos = 1;
        for ( i = 0; i < level-1; i++)
            pos *= 2;

        // 用 level-1個 bits
        // 因為node 編號最多也才 pos + pos - 1
        bool arr[level-1];

        // assign the bits to be zero
        for ( i = 0; i < level-1; i++)
            arr[i]= false;

        // calculate the times to binary
        for ( i = 0; i < level-1; i++)
        {
            arr[i] = times%2;
            times /= 2;
        }

        // calculate the position
        weight = 1;
        for ( i = level-2; i >= 0; i--)
        {
            pos += weight*arr[i];
            weight *= 2;
        }

        printf("%d\n", pos);

    }

}

Q686: Goldbach's Conjecture(II)

/*
    這題和 Q543類似
    只是要算有幾個解
    所以只要算到 N/2 即可(要相異解)
    但注意 n = 4 = 2+2
    這是和Q543不一樣的地方
    n的限制是從4到32767

    Run time: 0.000
*/
#include <stdio.h>
#define N 32768
int main()
{
    int n;
    int i, j;
    bool arr[N+1];

    for ( i = 3; i < N; i+=2)
        arr[i] = true;

    for ( i = 3; i*i < N; i+=2)
        if (arr[i])
           for ( j = 3*i; j < N; j+=i)
               if (arr[j])
                  arr[j] = false;


    while (scanf("%d", &n))
    {
        if (!n) break;

        int cnt = 0;
        if (n == 4)
        {
            printf("1\n");
            continue;
        }

        for ( i = 3; i <= n/2; i+=2)
        {
            if (arr[i])
            {
                j = n-i;
                if (arr[j])
                    cnt++;
            }
        }
        printf("%d\n", cnt);
    }
}

Q661: Blowing Fuses

// Run time: 0.000
#include <stdio.h>
#define N 20
int arr[N];
bool state[N];
int main()
{
    int n; // how many electric
    int m; // time's? open or close
    int c; // capacity
    int i; // for loop's count
    int sum; // total
    int tmp; // using for scanf
    int max; // maximum
    int count = 0; // which sequence?
    bool blown; // blown or not

    while (scanf("%d%d%d", &n, &m, &c))
    {
        if (!n && !m && !c) break;

        // n台電器的電流，而且初始都是關著
        for ( i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);
            state[i] = false;
        }

        max = 0;
        sum = 0;
        blown = false;

        for ( i = 0; i < m; i++)
        {
            scanf("%d", &tmp);

            // 原本是open
            if (state[tmp-1])
            {
                sum -= arr[tmp-1];
                state[tmp-1] = false;
            }

            // 原本是close
            else
            {
                sum += arr[tmp-1];
                if (sum > c)
                    blown = true;

                if (max < sum)
                    max = sum;
                state[tmp-1] = true;
            }

        }

        printf("Sequence %d\n", ++count);

        if (blown)
            printf("Fuse was blown.\n\n");
        else
        {
            printf("Fuse was not blown.\n");
            printf("Maximal power consumption was %d amperes.\n\n", max);
        }
    }

    return 0;
}

Q612: DNA Sorting

// Run time: 0.110
#include <stdio.h>
typedef struct {
    char str[51];
    int cnt;
    int sort;
} string;
string DNA[100];

int calculate(char *str, int len);
void print(string *s, int n);

int main()
{
    int num;
    int len, n;
    int i, j;
    scanf("%d", &num);
    while (num--)
    {
        scanf("%d%d\n", &len, &n);

        // DNA string input
        for ( i = 0; i < n; i++)
        {
            gets(DNA[i].str);
            DNA[i].sort = i;
        }
        // calculate the length of each DNA's string
        for ( i = 0; i < n; i++)
            DNA[i].cnt = calculate(DNA[i].str, len);

        if (n != 1)
           print(DNA, n);

        // if only one input
        else
           printf("%s\n", DNA[0].str);

        if (num)
            printf("\n");
    }

    return 0;
}

int calculate(char *str, int len)
{
    int i, j;
    int cnt = 0;
    for ( i = 0; i < len-1; i++)
        for ( j = i+1; j < len; j++)
            if (str[i] > str[j])
                cnt++;

    return cnt;
}

void print(string *s, int n)
{
    int i, j;
    int index;
    int count = 0;
    int min;
    bool state[n];

    for ( i = 0; i < n; i++)
        state[i] = true;

    for (;;)
    {
        for ( i = 0; i < n; i++)
            if (state[i])
                break;

        min = s[i].cnt;
        index = i;
        state[i] = false;

        for ( j = 0; j < n; j++)
        {
            if (min > s[j].cnt && state[j])
            {
                // 如果發現更小的，要把之前的 state 還原成true
                state[index] = true;
                min = s[j].cnt;
                state[j] = false;
                index = j;
            }
        }

        printf("%s\n", s[index].str);

        if (++count == n)
            return;
    }
}

Q587: There's treasure everywhere!

/*
  這題要注意誤差，因為double會有誤差
  Run time: 0.010
*/
#include <stdio.h>
#include <stdlib.h> // atoi(str) 要用
#include <string.h> // strlen(str), strcmp(str)要用
#include <ctype.h>  // isdigit(ch) 判斷是否為數字用的
#include <math.h>   // sqrt(2.0) 和 EPS 要用
#define EPS pow(10, -9)  // 誤差要用的, double容易有誤差
#define sqrt2 sqrt(2.0)
char str[201];
int main()
{
  int i;
  int len;
  double move;
  double x, y;
  int cnt = 0;

  while (gets(str))
  {
      if (!strcmp(str, "END"))    break;

      len = strlen(str);
      x = y = 0.0;

      for (i = 0; i < len; i++)
      {
          move = atoi(str+i); // 取出數字

          while (isdigit(str[i])) // 跳過數字到非數字
                i++;

          // N, E, S, W 四種方向其中之一
          if (str[i+1] == ',' || str[i+1] == '.')
          {
              switch (str[i])
              {
                  case 'N': y += move; break;
                  case 'E': x += move; break;
                  case 'S': y -= move; break;
                  case 'W': x -= move; break;
              }
              i++;
          }

          // NE, NW, SE, SW 四種方向其中之一
          else
          {
              // 座標要取cos(PI/4), sin(PI/4)

              move /= sqrt2;

              switch (str[i])
              {
                  case 'N':
                      x += (str[i+1] == 'E') ? move : -move;
                      y += move;
                      break;
                  case 'S':
                      x += (str[i+1] == 'E') ? move : -move;
                      y -= move;   break;
              }

              i+=2;
          }
      }
      printf("Map #%d\n", ++cnt);
      printf("The treasure is located at (%.3lf,%.3lf).\n", EPS+x, EPS+y);
      printf("The distance to the treasure is %.3lf.\n\n", EPS+sqrt(x*x+y*y));
  }

}

Q576: Hiaku Review

// Run time: 0.000
#include <stdio.h>
#include <string.h>
bool test(char ch);
bool check(int turn, int cnt);
char str[201];

int main()
{
    int len;
    int cnt;
    int i, j;

    while (gets(str))
    {
        if (!strcmp("e/o/i", str))  break;

        len = strlen(str);
        cnt = 0;
        bool state = false;
        for ( i = 0, j = 1; i < len; i++)
        {
            if (str[i] == '/')
            {
                if (check(j, cnt))
                {
                    cnt = 0;
                    j++;
                    state = false;
                    continue;
                }
                else
                {
                    printf("%d\n", j);
                    break;
                }
            }
            if (test(str[i]) && !state)
            {
                state = true;
                cnt++;
            }
            else
            if (!test(str[i]))
                state = false;
        }
        if (i == len)
        {
            if (check(j, cnt))  printf("Y\n");
            else    printf("3\n");
        }

    }
    return 0;
}
bool test(char ch)
{
    if (ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u'||ch=='y')
        return true;
    else
        return false;

}

bool check(int turn, int cnt)
{
    if (turn == 1)
    {
        if (cnt == 5)
            return true;
        else
            return false;
    }
    else
    if (turn == 2)
    {
        if (cnt == 7)
            return true;
        else
            return false;
    }
    else
    if (turn == 3)
    {
        if (cnt == 5)
            return true;
        else
            return false;
    }

}

Q573: The Snail

/*
    注意:蝸牛不會爬負的，只有晚上會滑下去一個高度
    Run time: 0.000
*/
#include <stdio.h>

int main()
{
    double H, init, down, factor;
    double slide;
    double sum;
    double last;
    int day;
    while (scanf("%lf%lf%lf%lf", &H, &init, &down, &factor))
    {
        if (!H)   break;

        day = 1;
        sum = init;
        slide = init*(factor/100);
        last = init;

        while (true)
        {
            // morning
            if (sum > H)
            {
                printf("success on day %d\n", day);
                break;
            }

            // night
            sum -= down;
            if (sum < 0)
            {
                printf("failure on day %d\n", day);
                break;
            }

            day++;
            sum += last-slide;
            if (slide != init)
                last = last-slide;
        }
    }
    return 0;
}

Q568: Just the Facts

// Run time: 0.010
#include <stdio.h>

int main()
{
    int n;
    int i;
    long long int prod;
    while (scanf("%d", &n) != EOF)
    {
        prod = 1;
        for ( i = 2; i <= n; i++)
        {
            prod *= i;
            while (!(prod%10))  prod /= 10;
                prod %= 100000;
        }
        printf("%5d -> %lld\n", n, prod%10);
    }

    return 0;

}

Q555: Bridge Hands

/*
 用gets(str)才會對
 用scanf("%c%c", &a, &b);會Time limit exceeded
 Run time: 0.060
*/
#include <stdio.h>
#define N 0
#define E 1
#define S 2
#define W 3

typedef struct {
  int dir;
 char suit;
 char rank;
} Card;
Card card[52];
int arr[4][13];

void assign(Card p);
int index(char ch);
void print(int turn);
char reverse(int index);

int main()
{
 char ch;
 int i, j;
 int aspect;

 while (1)
 {
     scanf("%c\n", &ch);
     if (ch == '#')  return 0;

     if (ch == 'N')
         aspect = N;
     else
     if (ch == 'E')
         aspect = E;
     else
     if (ch == 'S')
         aspect = S;
     else
         aspect = W;

     char str[53];

     gets(str);


     for ( i = 0, j = 0; i < 52; i+=2)
     {
         card[j].suit = str[i];
         card[j].rank = str[i+1];
         card[j].dir = (aspect+j+1)%4;
         j++;
     }
     gets(str);
     for ( i = 0; i < 52; i+=2)
     {
         card[j].suit = str[i];
         card[j].rank = str[i+1];
         card[j].dir = (aspect+j+1)%4;
         j++;
     }

     for ( i = 0; i < 52; i++)
         assign(card[i]);

     printf("S:");   print(S);   printf("\n");
     printf("W:");   print(W);   printf("\n");
     printf("N:");   print(N);   printf("\n");
     printf("E:");   print(E);   printf("\n");

 }
 return 0;
}

void assign(Card p)
{
 int x = index(p.rank);
 if (p.suit == 'C')
     arr[0][x] = p.dir;
 else
 if (p.suit == 'D')
     arr[1][x] = p.dir;
 else
 if (p.suit == 'S')
     arr[2][x] = p.dir;
 else
 if (p.suit == 'H')
     arr[3][x] = p.dir;
}

int index(char ch)
{
 if (ch >= '2' && ch <= '9')
     return ch-'0'-2;
 if (ch == 'T')
     return 8;
 if (ch == 'J')
     return 9;
 if (ch == 'Q')
     return 10;
 if (ch == 'K')
     return 11;
 if (ch == 'A')
     return 12;
}
void print(int turn)
{
 int i, j;
 for ( i = 0; i < 4; i++)
     for ( j = 0; j < 13; j++)
         if (arr[i][j] == turn)
         {
             if (i == 0)
                 printf(" C");
             else
             if (i == 1)
                 printf(" D");
             else
             if (i == 2)
                 printf(" S");
             else
             if (i == 3)
                 printf(" H");
             printf("%c", reverse(j));
         }
}

char reverse(int index)
{
 if (index >= 0 && index <= 7)   return index+'2';
 if (index == 8)  return 'T';
 if (index == 9)  return 'J';
 if (index == 10) return 'Q';
 if (index == 11) return 'K';
 if (index == 12) return 'A';
}

Q543: Goldbach's Conjecture

/*
   先算完全部，算質數的方法：用篩的(sieve)
   不用管even部分，因為這裡已經把質數除了2以外都是odd
   Run time: 0.090
*/
#include <stdio.h>
#define N 1000000
int main()
{
   int n;
   int i, j;
   bool arr[N+1];

   for ( i = 3; i < N; i+=2)
       arr[i] = true;

   for ( i = 3; i*i < N; i+=2)
       if (arr[i])
          for ( j = 3*i; j < N; j+=i)
              if (arr[j])
                 arr[j] = false;


   while (scanf("%d", &n))
   {
       if (!n) break;
       bool s = false;

       for ( i = 3; i <= n/2; i+=2)
       {
           if (arr[i])
           {
               j = n-i;
               if (arr[j])
               {
                   printf("%d = %d + %d\n", n, i, j);
                   s = true;
                   break;
               }
           }
       }
       if (!s)
          printf("Goldbach's conjecture is wrong\n");
   }
}

Q530: Binomial Showdown

// Run time: 0.000
#include <stdio.h>
void combination(int N, int M);
int main()
{
   int N, M;
   while (true)
   {
       scanf("%d%d", &N, &M);
       if (!N && !M)   break;

       if (M > N/2)
           M = N - M;

       combination(N, M);
   }
   return 0;
}

void combination(int N, int M)
{
   int i;
   double prod = 1;
   for ( i = 0; i < M; i++)
       prod *= double(N--)/double(i+1);

   printf("%.0lf\n", prod);
}

Q516: Prime Land

// Run time: 0.320
#include <stdio.h>
void trans(int n);
bool isprime(int n);
int arr[15];

// 因為最大數為32767，所以平方根只要到181就可以了
int p[42]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
             71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,
             149,151,157,163,167,173,179,181};
int main()
{
   int i, j;
   int num;
   int root;
   int prod;
   while (scanf("%d", &root))
   {
       if (!root)  break;
       arr[0] = root;
       for ( i = 1; ; i++)
       {
           scanf("%d", &arr[i]);
           if (getchar() == '\n')
               break;
       }
       num = ++i;
       prod = 1;

       for ( i = 0; i < num; i += 2)
           for ( j = 0; j < arr[i+1]; j++)
               prod *= arr[i];

       prod--; // 減1
       trans(prod);
   }
   return 0;
}

void trans(int n)
{
   if (isprime(n))
   {
       printf("%d 1\n", n);
       return;
   }
   int i, j;
   int cnt;
   bool state = false;

   for ( i = n/2; i >= 2; i--)
   {
       if (!(n%i) && isprime(i))
       {
          cnt = 0;
          while (true)
          {
               if (!(n%i))
               {
                   cnt++;
                   n /= i;
               }
               else
               {
                   if (state)
                       printf(" %d %d", i, cnt);
                   else
                   {
                       printf("%d %d", i, cnt);
                       state = true;
                   }
                   break;
               }
          }
       }
   }
   printf("\n");


}

bool isprime(int n)
{
   int i;
   for ( i = 0; p[i]*p[i] <= n; i++)
       if (!(n%p[i]))
           return false;

   return true;
}

Q498: Polly the Polynomial

// Run time: 0.530
#include <stdio.h>
#define N 1000
int arr[N];
void calculate(int x, int num);

int main()
{
   int i;
   int num;
   int x;
   while (true)
   {
       for ( i = 0; ; i++)
       {
           if (scanf("%d", &arr[i]) != EOF)
           {
               if (getchar() == '\n')
                   break;
           }
           else
               return 0;
       }
       num = i; // <=

       while (true)
       {
           if (scanf("%d", &x) != EOF)
           {
               calculate(x, num);
               if (getchar() == '\n')
               {
                   putchar('\n');
                   break;
               }
               else
                   putchar(' ');
           }
       }

   }

   return 0;
}

void calculate(int x, int num)
{
   int i, j;
   int sum = 0;
   int product;
   int weight = num;
   for ( i = 0; i <= num; i++)
   {
       product = 1;
       for ( j = 0; j < weight; j++)
           product *= x;
       sum += arr[i]*product;
       weight--;
   }
   printf("%d", sum);
}

Q492: Pig-Latin

// Run time: 0.090
#include <stdio.h>
#include <ctype.h>
bool test(char ch);

int main()
{
  int i, j;
  char ch;
  char root;
  bool s;
  while (true)
  {
      i = 0;
      while (true)
      {
          ch = getchar();

          if (ch == EOF)
              return 0;

          if (isalpha(ch)) // 如果是字母的話
          {
              if (!i)  // 是一個單字的第一個字母
              {
                  s = test(ch);
                  if (s)
                      printf("%c", ch);
                  else
                      root = ch;

                  i++;
              }
              else
                  printf("%c", ch);
          }

          else  // 如果不是字母的話
          {
              if (!i)
              {
                  printf("%c", ch);
                  break;
              }

              if (s)
                  printf("ay%c", ch);
              else
                  printf("%cay%c", root, ch);

              break;
          }
      }

  }

  return 0;
}

bool test(char ch)
{
  if (ch == 'A' || ch == 'a')
      return true;
  if (ch == 'E' || ch == 'e')
      return true;
  if (ch == 'I' || ch == 'i')
      return true;
  if (ch == 'O' || ch == 'o')
      return true;
  if (ch == 'U' || ch == 'u')
      return true;

  return false;
}

Q490: Rotating Sentences

/*
 輸入最後一行需加上 Ctrl + Z
 Run time: 0.000
*/
#include <stdio.h>
#include <string.h>
#define N 100
char arr[N+1][N+1];
int len[N+1];
int main()
{
  int i, j;
  int max = 0;
  int level;
  for ( i = 0; ; i++)
      if (gets(arr[i]) == NULL)
          break;
      else
      {
          len[i] = strlen(arr[i]);
          if (max < len[i])
              max = len[i];
      }

  level = i;

  for (i = 0; i < max; i++)
  {
      for ( j = level-1; j >= 0; j--)
      {
          if (arr[j][i] != '\0')
              printf("%c", arr[j][i]);
          else
              printf(" ");
      }
      printf("\n");
  }

  return 0;
}