Blog·Tanky WooABOUTRSS

HDOJ 2919 Adding Sevens

26 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=2919

在timest的帮助下,终于AC了。

似乎第一次写超过100行的ACM题~~~

原来自己在大数相加时,在判断是否进位上错误了,

他给出了一组数据,107107+093=

也就是99+2=

这个答案应该是101

可我的却是01,也就是063010

后来看下代码才发现 :

我只想到了a+b后最高位大于等于10.

却没考虑到也可能是在处理前面的情况时,一直进位到最高位,而使最高位进位。

就如99+2,相加后是11和9,最高位9<10,但是11进位后导致9变成了10~~~

汗,还是自己对大数加法没有统一的好好写写,每次都是直接写的,经常把风格换来换去~~~

代码比较乱,写得很迷糊,变量名也没起好,乱糟糟的。

这里hash1数组是从7数码想10进制数转换的,而hash2是从10进制数向7数码转换的。

 #include 
#include 
using namespace std;
// Author: Tanky Woo
char input[110];
char A[50], B[50];
char A2D[15], B2D[15];
int C2D[15];
int a, b;
// 0-063
// 1-010
// 2-093
// 3-079
// 4-106
// 5-103
// 6-119
// 7-011
// 8-127
// 9-107
int hash1[128];
char *hash2[11] = {"063","010","093", "079", "106", "103","119","011", "127", "107"};
int main()
{
    hash1[63] = 0;
    hash1[10] = 1;
    hash1[93] = 2;
    hash1[79] = 3;
    hash1[106] = 4;
    hash1[103] = 5;
    hash1[119] = 6;
    hash1[11] = 7;
    hash1[127] = 8;
    hash1[107] = 9;
//---------------------
    while(scanf("%s", input) && strcmp(input, "BYE") != 0)
    {
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        getchar();
        int jishu = 0;
        int k ;
        for(k = 0; input[k] != '+'; ++k)
            A[jishu++] = input[k];
        jishu = 0;
        k++;
        for(; input[k] != '='; ++k)
            B[jishu++] = input[k];
    //  printf("A=%s B=%s\n", A, B);
        memset(A2D, 0, sizeof(A2D));
        memset(B2D, 0, sizeof(B2D));
    //  printf("A=%s B=%s\n", A, B);

        // 把A转换成10进制数
        int cnt1 = 0, j = 0;
        int temp = 0;
        int i;
        for(i = 0; i <= strlen(A); ++i)   // 注意要多加一位,也就是<=,否则最后一次j==3无法判断
        {
            if(j == 3)
            {
                //printf("temp=%d\n", temp);
                A2D[cnt1++] = hash1[temp]+'0';
                temp = 0;
                j = 0;
            }
            temp *= 10;
            temp += A[i]-'0';
            j++;
        }

        // 把B转换成10进制数
        int cnt2 = 0;
        j = 0;
        temp = 0;
        for(i = 0; i <= strlen(B); ++i)
        {
            if(j == 3)
            {
            //  printf("temp=%d\n", temp);
                B2D[cnt2++] = hash1[temp]+'0';
                temp = 0;
                j = 0;
            }
            temp *= 10;
            temp += B[i]-'0';
            j++;
        }
        //printf("%s %s\n", A2D, B2D);
        //reverse(B2D, B2D+cnt2);
        //reverse(A2D, A2D+cnt1);
        int a_temp[15], b_temp[15];
        memset(a_temp, 0, sizeof(a_temp));
        memset(b_temp, 0, sizeof(b_temp));
        int tot1 = 0;
        for(int i = strlen(A2D)-1; i >= 0; --i)
            a_temp[tot1++] = A2D[i]-'0';

        int tot2 = 0;
        for(int i = strlen(B2D)-1; i >= 0; --i)
            b_temp[tot2++] = B2D[i]-'0';
        //printf("%s %s\n", A2D, B2D);
        int tot = tot1>tot2? tot1:tot2;
        for(int i = 0; i < tot; ++i)
            a_temp[i] += b_temp[i];

        int len = tot;

        for(i = 0; i < tot; ++i)
        {
            if(i == tot-1 && a_temp[i]>=10)
                len++;
            if(a_temp[i] >= 10)
            {
                a_temp[i+1] += a_temp[i]/10;
                a_temp[i] %= 10;
            }
        }
        //-------------------------------

    //  printf("len=%d\n", len);
    //  for(int i = 0; i < len; ++i)
    //      printf("%d", a_temp[i]);
    //  printf("\n");
        //-------------------------------
        printf("%s+%s=", A, B);
        for(int i = len-1; i >=0 ; --i)
            printf("%s", hash2[a_temp[i]]);
        printf("\n");

    }
    return 0;
}