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