# 期中考參考解答

## 100!

#include <stdio.h>

int main() {
  int k, n;
  scanf("%d", &k);
  for (int testCase = 0; testCase < k; testCase++) {
    scanf("%d", &n);
    int sum = 0;
    while (n /= 5) {
      sum += n;
    }
    if (testCase != 0) printf("\n");
    printf("%d", sum);
  }
  return 0;
}

## Best destination for stargazing

#include <stdio.h>

int main() {
  char c;
  int row, col, testCase = 0;
  int stars[101][101];
  int colOffset[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  int rowOffset[8] = {0, -1, -1, -1, 0, 1, 1, 1};
  while (scanf("%d %d\n", &row, &col) != EOF) {
    testCase++;
    if (row == 0 || col == 0) break;
    // Initialize
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        stars[i][j] = 0;
      }
    }
    // Read stars
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        scanf("%c", &c);
        if (c == '*') {
          stars[i][j] = -1;
          for (int idx = 0; idx < 8; idx++) {
            int locRow = i + rowOffset[idx];
            int locCol = j + colOffset[idx];
            if (locRow >= 0 && locRow < row && locCol >= 0 && locCol < col) {
              if (stars[locRow][locCol] != -1) {
                stars[locRow][locCol] += 1;
              }
            }
          }
        }
      }
      getchar();
    }
    // Print stars
    if (testCase != 1) {
      printf("\n");
    }
    printf("Field #%d:\n", testCase);
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        if (stars[i][j] == -1) {
          printf("*");
        } else {
          printf("%d", stars[i][j]);
        }
      }
      printf("\n");
    }
  }
  return 0;
}

## Bangla Numbers

#include <stdio.h>
#define KUTI 10000000
#define LAKH 100000
#define HAJAR 1000
#define SHATA 100

void SplitUnit(long long int n) {
  if (n >= KUTI) {
    SplitUnit(n / KUTI);
    printf(" kuti");
    n %= KUTI;
  }
  if (n >= LAKH) {
    SplitUnit(n / LAKH);
    printf(" lakh");
    n %= LAKH;
  }
  if (n >= HAJAR) {
    SplitUnit(n / HAJAR);
    printf(" hajar");
    n %= HAJAR;
  }
  if (n >= SHATA) {
    SplitUnit(n / SHATA);
    printf(" shata");
    n %= SHATA;
  }
  if (n > 0) {
    printf(" %d", n);
  }
}

int main() {
  int testCase;
  long long int n;
  for (testCase = 1;; testCase++) {
    scanf("%lld", &n);
    if (n == -1) break;
    printf("%d.", testCase);
    if (n == 0) {
      printf(" 0");
    } else {
      SplitUnit(n);
    }
    printf("\n");
  }
}

## Do Not Access

#include <stdio.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

// 最後一行也要記得換行

char a[55][1010];
char b[1010];

int main(void) {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d%d", &m, &n);

    for (int i = 0; i < m; ++i) {
      scanf("%s", a[i]);
    }

    int ans = 0;
    for (int j = 0; j < n; j++) {
      int cnta = 0, cntt = 0, cntc = 0, cntg = 0;
      for (int i = 0; i < m; i++) {
        if (a[i][j] == 'A')
          cnta++;
        else if (a[i][j] == 'T')
          cntt++;
        else if (a[i][j] == 'C')
          cntc++;
        else
          cntg++;
      }
      int cnt_max = MAX(cnta, cntc);
      cnt_max = MAX(cnt_max, cntg);
      cnt_max = MAX(cnt_max, cntt);
      if (cnt_max == cnta)
        b[j] = 'A';
      else if (cnt_max == cntc)
        b[j] = 'C';
      else if (cnt_max == cntg)
        b[j] = 'G';
      else
        b[j] = 'T';
      ans += (m - cnt_max);
    }
    for (int i = 0; i < n; ++i) printf("%c", b[i]);
    printf("\n%d\n", ans);
  }
  return 0;
}

## Chihuahua Loves to Eat

#include <stdio.h>
#define SIZE 10101

int record[SIZE];

int step(int n) {
  if (n > 10000) {
    if (n % 2 == 1) {
      return 1 + step(3 * n + 1);
    } else {
      return 1 + step(n / 2);
    }
  }
  int index = 100 + n;
  if (record[index] != -1) {
    return record[index];
  }
  if (n < 0) {
    record[index] = 1 + step(n * n);
  } else if (n == 1) {
    record[index] = 1;
  } else if (n % 2 == 1) {
    record[index] = 1 + step(3 * n + 1);
  } else {
    record[index] = 1 + step(n / 2);
  }
  return record[index];
}

int main() {
  int lower, upper, maxIndex, maxValue;
  for (int i = 0; i < SIZE; i++) {
    record[i] = -1;
  }
  record[100] = 0;
  while (scanf("%d %d", &lower, &upper) != EOF) {
    maxIndex = lower;
    maxValue = -1;
    for (int i = lower; i <= upper; i++) {
      int val = step(i);
      if (val > maxValue) {
        maxIndex = i;
        maxValue = val;
      }
    }
    printf("Room_%d %d\n", maxIndex, maxValue);
  }
  return 0;
}

## Teach Otto a Lesson

#include <stdio.h>

// even 0 2 4 6 8
// prime 2 3 5 7

long long p = 1234567890;

// Calculate (x^k)%Mod
long long power(long long x, long long k, long long Mod) {
  x %= Mod;
  if (k == 0) {
    return 1;
  }
  if (k % 2 == 0) {
    return power((x * x) % Mod, k / 2, Mod) % Mod;
  }
  return (x * power((x * x) % Mod, (k - 1) / 2, Mod)) % Mod;
}

long long goodNums(long long length) {
  long long primeDigitNum = length / 2;
  long long evenDigitNum = length - primeDigitNum;

  long long powOf2 = length - 2 * primeDigitNum;
  long long powOf5 = length - evenDigitNum;

  return (power(2, powOf2, p) * power(5, powOf5, p)) % p;
}

int main() {
  long long length;
  while (scanf("%lld", &length) != EOF) {
    if (length == 0) {
      printf("0\n");
    } else {
      printf("%lld\n", goodNums(length));
    }
  }
}