Glenn's ACM code: 2009-03-01

2009年3月7日星期六

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

2009年3月5日星期四

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

2009年3月3日星期二

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

2009年3月2日星期一

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

}

2009年3月1日星期日

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

2009年3月7日 星期六

Q10622: Perfect Pth Powers

2009年3月5日 星期四

Q10591: Happy Number

2009年3月3日 星期二

Q10196: Check the Check

2009年3月2日 星期一

Q10188: Automated Judge Script

2009年3月1日 星期日

Q10365: Blocks

Q10268: 498'

2009年3月7日星期六

2009年3月5日星期四

2009年3月3日星期二

2009年3月2日星期一

2009年3月1日星期日