PAT Basic 1074. 宇宙无敌加法器

1. 题目描述：

地球人习惯使用十进制数，并且默认一个数字的每一位都是十进制的。而在 PAT 星人开挂的世界里，每个数字的每一位都是不同进制的，这种神奇的数字称为“PAT数”。每个 PAT 星人都必须熟记各位数字的进制表，例如“……0527”就表示最低位是 7 进制数、第 2 位是 2 进制数、第 3 位是 5 进制数、第 4 位是 10 进制数，等等。每一位的进制 d 或者是 0（表示十进制）、或者是 [2，9] 区间内的整数。理论上这个进制表应该包含无穷多位数字，但从实际应用出发，PAT 星人通常只需要记住前 20 位就够用了，以后各位默认为 10 进制。

在这样的数字系统中，即使是简单的加法运算也变得不简单。例如对应进制表“0527”，该如何计算“6203 + 415”呢？我们得首先计算最低位：3 + 5 = 8；因为最低位是 7 进制的，所以我们得到 1 和 1 个进位。第 2 位是：0 + 1 + 1（进位）= 2；因为此位是 2 进制的，所以我们得到 0 和 1 个进位。第 3 位是：2 + 4 + 1（进位）= 7；因为此位是 5 进制的，所以我们得到 2 和 1 个进位。第 4 位是：6 + 1（进位）= 7；因为此位是 10 进制的，所以我们就得到 7。最后我们得到：6203 + 415 = 7201。

2. 输入格式：

输入首先在第一行给出一个 N 位的进制表（0 < N ≤ 20），以回车结束。随后两行，每行给出一个不超过 N 位的非负的 PAT 数。

3. 输出格式：

在一行中输出两个 PAT 数之和。

4. 输入样例：

30527
06203
415

5. 输出样例：

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

找了一下午bug。。。这道题考察进制转换，有个点是如果当前位的进制是\(N\)，那么当前位上的最大数字为\(N-1\)，两数相加最大为\(2(N-1)\)，所以进位最大为1（因为达不到\(2N\)）。我们做十进制加法的时候进位也最多为1，只是之前没有留意到。。。所以这里两个不超过\(N\)位的数相加，结果最多为\(N+1\)位，上限为21位。剩下就是做好加法的进位即可。

第一次提交时testpoint3，4，5报wrong answer，检查了边界情况，额外增加了两个数均为零的判断，testpoint5通过，另外两个点一直过不了。。。无奈参考大佬题解：PAT 1074. 宇宙无敌加法器(20)-PAT乙级真题_柳婼的博客-CSDN博客，写的很简洁，但还是没找出自己代码的问题。找了一下午，最后自己修改测试样例为：

00000000000000000000
99999999999999999999
99999999999999999999

终于找到问题！因为一开始我是想着方便取两个数的各个位，就都定义为int类型，但是这里加数可以达到20位，int类型是有可能存不下的。。。所以只能将其存为字符串，改过来后终于AC。

My Code:

#include <stdio.h>
#include <string.h> // strlen header

//first submit testpoint3, 4, 5 wrong answer
int main(void)
{
    char base[21] = ""; // store base of every bit
    //int num1=0, num2=0;
    int bit1=0, bit2=0, tempBase=0, carry=0;
    char res[22] = "";
    int i=0; // iterator
    int baseLen = 0;
//     int j=0; // iterator
//     char tempCh = '\0';
    char num1[21] = "", num2[21]= "";
    int num1Len=0, num2Len=0;
    int flag =0; // outputFlag
    
    scanf("%s", base);
    //scanf("%d%d", &num1, &num2); // can't use int type, for number maybe too big to store in int.
    scanf("%s%s", num1, num2);
    
    baseLen = strlen(base);
    i=0;
    carry = 0;
    num1Len = strlen(num1);
    num2Len = strlen(num2);
    
    //while(num1 || num2)
    while(i<num1Len || i<num2Len)
    {
        if(i<=19)
        {
            tempBase = base[baseLen-1-i] - '0';
            if(!tempBase) tempBase=10; // decimal base
        }
        else // 20 bit and later
        {
            tempBase = 10;
        }
        
        if(i<num1Len)
        {
            bit1 = num1[num1Len-1-i]-'0';
        }
        else
        {
            bit1 = 0;
        }
        
        if(i<num2Len)
        {
            bit2 = num2[num2Len-1-i]-'0';
        }
        else
        {
            bit2 = 0;
        }
//         bit1 = num1%10;
//         bit2 = num2%10;
        res[i] = ((bit1+bit2+carry) % tempBase) + '0';
        carry = (bit1+bit2+carry) / tempBase;
        
        ++i;
//         num1/=10;
//         num2/=10;
    }
    
//     //while(carry) // handle the carry
//     while(i<=baseLen-1 && carry)
//     {
//         if(i<=19)
//         {
//             tempBase = base[baseLen-1-i] - '0';
//             if(!tempBase) tempBase=10; // decimal base
//         }
//         else // 20 bit and later
//         {
//             tempBase = 10;
//         }
//         //printf("baseNow: %d\n", tempBase);
        
//         res[i] = (carry % tempBase) + '0';
//         carry = carry / tempBase;
        
//         ++i;
//     }
    
    if(carry)
    {
        res[i] = '1';
        ++i;
    }
    
    res[i] = '\0';
    
//     for(i=0, j=strlen(res)-1; i<j; ++i, --j) // reverse res array
//     {
//         tempCh = res[i];
//         res[i] = res[j];
//         res[j] = tempCh;
//     }
    
//     if(!strlen(res)) // num1 num2 both == 0, fixed testpoint5
//     {
//         printf("0\n");
//     }
//     else
//     {
//         printf("%s\n", res);
//     }
    
    for(i=strlen(res)-1; i>=0; --i)
    {
        if(res[i] != '0' || flag)
        {
            flag = 1;
            printf("%c", res[i]);
        }
    }
    if(flag) printf("\n");
    else printf("0\n");
    
    return 0;
}


// // refer to https://blog.csdn.net/liuchuo/article/details/79067142
// #include <iostream>
// #include <string>
// using namespace std;

// int main(void)
// {
//     string s, s1, s2, ans;
//     int carry = 0, flag=0;
    
//     cin >> s >> s1 >> s2;
//     ans = s;
//     string ss1(s.length() - s1.length(), '0');
//     s1 = ss1 + s1;
//     string ss2(s.length() - s2.length(), '0');
//     s2 = ss2 + s2;
//     for(int i= s.length()-1; i>=0; --i)
//     {
//         int mod = s[i] == '0'? 10 : (s[i]-'0');
//         ans[i] = (s1[i] - '0' + s2[i] - '0' + carry) % mod + '0';
//         carry = (s1[i] - '0' + s2[i] - '0' + carry) / mod;
//     }
    
//     //cout << ans << endl;
    
//     if(carry !=0) 
//     {
//         ans = '1' + ans;
//         //cout << carry << endl;
//     }
//     for(int i=0; i< ans.size(); ++i)
//     {
//         if(ans[i] != '0' || flag ==1)
//         {
//             flag = 1;
//             cout << ans[i];
//         }
//     }
//     if(flag == 0) cout << 0;
    
//     return 0;
// }