2014年3月13日木曜日

AOJ 0015 c

AOJの0015、入力された2つの数の和を出す問題なのですが、条件として80桁まで計算できないといけないみたいです。

問題文→http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015



long long unsigned int型（64ビット符号無し整数）でも0～18,446,744,073,709,551,615で20桁までしか扱えません。
そこで文字列として入力された数字を配列にひとつずつ入れていき、あとは筆算の要領で同じ桁同士足していけばいいと思ったのですが、何故かおかしな値が出てきてしまい何故だろうと悩みました。


いろいろ調べてみた結果、ここで初めて文字列には全て番号が割り振られていて、それは数字であっても同様であるということを知りました。
例えば'0'は48が割り当てられていているので、整数値の文字列をその通りの数字として扱うには

（整数値の文字列）- '0'
（整数値の文字列）- 48

のどちらかをする必要があるというわけです。

また、その他の方法として、整数値の文字列を整数型( int型 )に型変換するatoi()というものもあります。
参考→http://simd.jugem.jp/?eid=85

以下に自分の書いたコードを載せますが、実はこれ「time limit exceeded」でまだ通過していません。
足し算は成功しているのですが、時間がかかるようで…。
近いうちに他の言語で再挑戦しようと思っています。
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <stdio.h>
#include <string.h>
 
int main(void)
{
    unsigned char num1[100],num2[100];
    int ia,ib,i,j,k,l,num,ex,large,small;
    int size1,size2;
    int sum[100];
 
    scanf("%d",&num);//データセット数
 
    for (l = 0; l < num; ++l)
    {
        scanf("%s",num1);
        scanf("%s",num2);
 
        size1 = strlen(num1);
        size2 = strlen(num2);
 
        if (size2 >= size1)// 「>」にすると同じ値の時困る
        {
            large = (size2 - 1);
            small = (size1 - 1);
        }
        else if (size1 >= size2)
        {
            large = (size1 - 1);
            small = (size2 - 1);
        }
 
        //80桁以上でoverflow
        if (large > 80)
        {
            printf("overflow\n");
            continue;
        }
 
 
        //num1の数字の並びを逆に******************************************
        for(ia = 0; ia < 100; ia++)
        {
            if(num1[ia+1] == '\0')break;   //NULL文字は交換しないように
             
            ex = num1[ia];
            num1[ia] = num1[ia+1];
            num1[ia+1] = ex;
        }
 
        for (j = ia; j > 0 ; --j) //iaは文字列の大きさになってる
        {
            for (k = 0; k < j-1; ++k) //先頭の文字を後ろへ送ってる
                                      //ただしひとつずつ短く 一歩手前まで
            {
                ex = num1[k];
                num1[k] = num1[k+1];
                num1[k+1] = ex;
            }
        }
 
        j=0;
        k=0;
 
        //num2の数字の並びを逆に******************************************
        for(ib = 0; ib < 100; ib++)
        {
            if(num2[ib+1] == '\0')break;   //NULL文字は交換しないように
             
            ex = num2[ib];
            num2[ib] = num2[ib+1];
            num2[ib+1] = ex;
        }
 
        for (j = ib; j > 0 ; --j) //ibは文字列の大きさになってる
        {
            for (k = 0; k < j-1; ++k) //先頭の文字を後ろへ送ってる
                                      //ただしひとつずつ短く 一歩手前まで
            {
                ex = num2[k];
                num2[k] = num2[k+1];
                num2[k+1] = ex;
            }
        }
 
        j=0;
        k=0;
 
 
        //共に１桁の値が入力された時
        //(largeに0が入るから表示されない不具合回避)
        if (ia == 0 && ib == 0)
        {
            printf("%d\n", (num1[0]-48) + (num2[0]-48));
            continue;
        }
 
        //異なる桁が入力された時
        //以降の足し算の処理のためずれの分だけ0を格納
        if (ia != ib)
        {
            for (j = small + 1; j <= large ; ++j)
            {
                if (ia < ib)
                {
                    num1[j] = '0';
                }
                else if (ib < ia)
                {
                    num2[j] = '0';
                }
            }
        }
 
        //初期化
        for (i = 0; i <= large+1; ++i)
        {
            sum[i] = 0;
        }
 
        i = 0;
 
        for (i = 0; i <= large; ++i)
        {
            sum[i] += ((num1[i]-'0') + (num2[i]-'0'));
 
            if (sum[i] >= 10)//筆算的なアレで10超えてたら
            {
                sum[i] -= 10;   //１の位の数字を入れる
                sum[i+1] += 1;; //繰り上げ
 
                //(例)80 + 50の時など桁が変わる場合の処理
                if (i == large)
                {
                    large += 1;
                    break;
                }
            }
        }
 
        //足し算結果が80桁越えてもoverflow
        if (large > 80)
        {
            printf("overflow\n");
            continue;
        }
 
        for (i = large; i >= 0; --i)
        {
            printf("%d", sum[i]);
        }
        printf("\n");
 
        i = 0;
 
    }
 
    return 0;
}
投稿者 時刻:
ラベル: ,

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)