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);
}