UVa : 338 - Long Multiplication

問題概要

http://uva.onlinejudge.org/external/3/338.html
入出力を見ればわかりますが, 掛け算のひっ算の過程を出力せよという問題です.
ひっ算の途中で, 0だけの行が出てくる場合は, 出力に含めないようにします.
0の行を除いた上で, ひっ算の途中計算が, 2行未満になる場合は, 答えだけを出力する必要があります.
例えば,

 10

 10

 --

10




-

100

はダメです.
ひっ算の途中計算は, 1行しかないので, 次のように答えの行だけを出力するようにします.

 10

 10

 --

100

アルゴリズム

問題概要によると, 入力される値は, 最大10ケタあります.
つまり, 最大の掛け算では, 9999999999 * 9999999999 を計算しなければならないことになります.
この計算, 残念ながら, 2^64 に収まりません.
面倒ですが, 文字列で管理しましょう.

プログラム

久々に, C言語で書いてみました.

#include <stdio.h>
#include <string.h>

//整数 a (文字列管理) * b を行い, s に代入する(文字列)
void mult(char *s,char *a,int b){
  int i;
  int len = strlen(a);
  int cal[100];

  for(i=0;i<len;i++){
    cal[i] = (a[i] - '0') * b;
  }
  //繰り上げ処理
  for(i=len-1;i>0;i--){
    if(cal[i] >= 10){
      cal[i-1] += cal[i] / 10;
      cal[i] %= 10;
    }
  }

  //aより桁数が増える場合
  if(cal[0] >= 10){
    s[0] = (cal[0] / 10) + '0';
    s[1] = (cal[0] % 10) + '0';
    for(i=1;i<len;i++){
      s[i+1] = cal[i] + '0';
    }
    s[len+1] = '\0';
  }
  //aと桁数が一緒の場合
  else{
    for(i=0;i<len;i++){
      s[i] = cal[i] + '0';
    }
    s[len] = '\0';
  }
}

int main(void){
  int i,j;
  int alen,blen,len,anslen,max,maxAB;
  int cal[100];
  int cnt;
  char a[100],b[100];
  char s[100][100];
  char ans[100];

  while(scanf("%s%s",a,b) == 2){
    alen = strlen(a);
    blen = strlen(b);
    cnt = 0;

    memset(cal,0,sizeof(cal));
    for(i=0;i<blen;i++){
      mult(s[i],a,b[blen-i-1]-'0');
      if(s[i][0] == '0'){ //0の行はとばす
        continue;
      }

      cnt++; //0でない行をカウント
      len = strlen(s[i]);
      for(j=0;j<len;j++){
        cal[j+i] += s[i][len-j-1] - '0';
      }
    }

    //繰り上げ処理
    for(i=0;i<30;i++){
      if(cal[i] >= 10){
        cal[i+1] += cal[i] / 10;
        cal[i] %= 10;
      }
    }
    while(i > 0 && cal[i] == 0) i--;

    for(j=0;i>=0;i--,j++){
      ans[j] = cal[i] + '0';
    }
    ans[j] = '\0';
    anslen = j;

    maxAB = (alen > blen ? alen : blen);
    max = (maxAB > anslen ? maxAB : anslen);

    //ひっ算の途中計算が, 2行以上ある場合は, 過程を出力
    if(cnt >= 2){
      for(i=0;i<max-alen;i++) putchar(' ');
      puts(a);
      for(i=0;i<max-blen;i++) putchar(' ');
      puts(b);
      for(i=0;i<max-maxAB;i++) putchar(' ');
      for(i=0;i<maxAB;i++) putchar('-');
      putchar('\n');

      for(i=0;i<blen;i++){
        if(s[i][0] == '0') continue;
        len = strlen(s[i]);
        for(j=0;j<max-len-i;j++) putchar(' ');
        puts(s[i]);
      }
      for(i=0;i<max;i++) putchar('-');
      putchar('\n');
      puts(ans);
    }
    //2行未満の場合, 答えだけを出力
    else{
      for(i=0;i<max-alen;i++) putchar(' ');
      puts(a);
      for(i=0;i<max-blen;i++) putchar(' ');
      puts(b);
      for(i=0;i<max-maxAB;i++) putchar(' ');
      for(i=0;i<maxAB;i++) putchar('-');
      putchar('\n');
      for(i=0;i<max-anslen;i++) putchar(' ');
      puts(ans);
    }

    putchar('\n');
  }

  return 0;
}