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