2012年12月22日

UVa 276 - Egyptian Multiplication


#include <stdio.h>

long long cal(char* s) {
  long long sum = 0;
  int i;
  for (i = 0; s[i]; i++)
    if (s[i] == '|') sum++;
    else if (s[i] == 'n') sum += 10;
    else if (s[i] == '9') sum += 100;
    else if (s[i] == '8') sum += 1000;
    else if (s[i] == 'r') sum += 10000;
  return sum;
}

int print(int n) {
  int now = 10, len = 0, first = 1;
  while (n) {
    int times = (n % now) / (now / 10);
    n = n / now * now;
    if (times && !first) putchar(' '), len++;
    if (times) first = 0;
    while (times--) {
      if (now == 10) putchar('|');
      else if (now == 100) putchar('n');
      else if (now == 1000) putchar('9');
      else if (now == 10000) putchar('8');
      else  putchar('r');
      len++;
    }
    now *= 10;
  }
  return len;
}

int main() {
  char a[100], b[100];
  while (gets(a) && a[0] != ' ') {
    gets(b);
    long long sum1 = cal(a), sum2 = cal(b), now, temp = sum2;
    int i, check[17] = {};
    for (i = 16, now = 65536; i >= 0 && temp > 0; i--, now >>= 1)
      if (temp >= now) check[i] = 1, temp -= now;
    for (i = 0, now = 1; now <= sum2; i++, now <<= 1) {
      int len = print(now);
      if (check[i]) {
        len += 2;
        printf(" *");
      }
      printf("%.*s", 34 - len, "                                  ");
      print((sum1 * now) % 100000);
      puts("");
    }
    printf("The solution is: ");
    print((sum1 * sum2) % 100000);
    puts("");
  }
  return 0;
}

沒有留言:

張貼留言