1065 A+B and C (64bit)(20) - PAT甲级

1065 A+B and C (64bit)(20)

Given three integers A, B and C in [−2^63,2^63], you are supposed to tell whether A+B>C.

Input Specification:

The first line of the input gives the positive number of test cases, T (≤10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.

Output Specification:

For each test case, output in one line Case #X: true if A+B>C, or Case #X: false otherwise, where X is the case number (starting from 1).

Sample Input:

3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0

Sample Output:

Case #1: false
Case #2: true
Case #3: false

Solution:

case2 wrong error, 手误.

实现大整数的加减, 符号另外算。

要解释一下的是符号,
对于A+B, 如果AB是同号的, 大整数相加后, 符号记成A或B的符号; 如果AB异号, 比较AB大小, 计算结果是 较大数-较小数(sub), 符号是较大数的符号.
比较A+B结果和C, 若rst和C异号, 符号为负的一定小; 若rst和C同号, 负号的话谁大整数小, 谁实际更大, 正号大整数大的结果更大.

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

struct Bign {
  int d[1005];
  int len;
  Bign() {
    memset(d, 0, sizeof(d));
    len = 0;
  }
};

Bign change(string s) {
  Bign a;
  a.len = s.length();
  for (int i = 0; i < a.len; i++) {
    a.d[i] = s[a.len-1-i] - '0';
  }
  return a;
}

Bign add(Bign a, Bign b) {
  Bign ans;
  int carry = 0;
  // for (int i = 0; i < a.len || i < a.len; i++) {
  for (int i = 0; i < a.len || i < b.len; i++) {      // case2, debug:01
    int temp = a.d[i] + b.d[i] + carry;
    ans.d[ans.len++] = temp % 10;
    carry = temp / 10;
  }
  if (carry) {
    ans.d[ans.len++] = carry;
  }
  return ans;
}

Bign sub(Bign a, Bign b) {
  Bign ans;

  for (int i = 0; i < a.len || i < b.len; i++) {
    if (a.d[i] < b.d[i]) {
      a.d[i+1]--;
      a.d[i] += 10;
    }
    ans.d[ans.len++] = a.d[i] - b.d[i];
  }
  while (ans.len - 1 >= 1 && ans.d[ans.len-1] == 0) {
    ans.len--;
  }
  return ans;
}

int compare(Bign a, Bign b) {
  if (a.len < b.len) return -1;
  else if (a.len > b.len) return 1;
  else {
    for (int i = 0; i < a.len; i++) {
      if (a.d[i] < b.d[i]) {
        return -1;
      } else if (a.d[i] > b.d[i]) {
        return 1;
      }
    }
    return 0;
  }
}

int main() {
  int T; cin >> T;
  for (int i = 0 ; i < T; i++) {
    // ..
    string a, b, c; cin >> a >> b >> c;
    int flag_a = 1, flag_b = 1, flag_c = 1, flag_add = 1;
    if (a[0] == '-') {
      flag_a = -1;
      a = a.substr(1, b.length()-1);
    }  // else flag_a = 1;
    if (b[0] == '-') {
      flag_b = -1;
      b = b.substr(1, b.length()-1);
    }
    if (c[0] == '-') {
      flag_c = -1;
      c = c.substr(1, c.length()-1);
    }
    Bign ba = change(a), bb = change(b), bc = change(c), rst_add;
    if (flag_a * flag_b == 1) {
      flag_add = flag_a;
      rst_add = add(ba, bb);
    } else {   // diff flag, compare
      int cmp_ab = compare(ba, bb);
      if (cmp_ab > 0) {
        flag_add = flag_a;
        rst_add = sub(ba, bb);
      } else if (cmp_ab < 0) {
        flag_add = flag_b;
        rst_add = sub(bb, ba);
      } else {  // -5 + 5 = 0
        flag_add = 1;
        rst_add = sub(ba, bb);
      }
    }
    string ans = "";
    if (flag_add < 0 && flag_c > 0) {
      ans = "false";
    } else if (flag_add > 0 && flag_c < 0) {
      ans = "true";
    } else if (flag_add < 0 && flag_c < 0) {
      ans = compare(rst_add, bc) < 0 ? "true" : "false";
    } else if (flag_add > 0 && flag_c > 0) {
      ans = compare(rst_add, bc) > 0 ? "true" : "false";
    }
    cout << "Case #" << i+1 << ": " << ans << endl;
  }
  return 0;
}