Algoogle

Algorithm for Programming Contest

JOI 春合宿 2010 a+b problem

Category: JOI Tag: implementation

a+b problem

問題概要


2つの整数を足した答えを求めよ.

ただしその整数は10進表記で上の桁から順にどの数字が何個連続しているかという形で与えられる.

解法


整数を下位の桁から見ていく.
まず2つの整数のいずれかが区切られた部分ごとに足し算をする(繰り上がりは無視して2桁になってもよい).
各桁での繰り上がりは高々1なので前で区切った区間をさらに長さ1とそれ以外に分ける(前の区間の繰り上がりの影響は1桁分しかない).
長さ1の部分は前の区間からの繰り上がりを足す. それ以外は長さ1の部分の繰り上がり分を足した数にする.
またそれぞれ10で割ったあまりに直す.
最後に連続した区間で同じ数が来ていたらマージしてやれば求めたい答えがでる.
オーバーフローに注意する.

コード


(aplusb.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define int long long

int m[8], val[8][80010], num[8][80010], len[8][80010];

void solve()
{
        for (int i = 0; i < 2; i++)
                for (int j = 0; j < m[i]; j++)
                        len[i][j+1] = len[i][j]+num[i][j];
        int head[2] = {};
        while(head[0]<m[0] and head[1]<m[1]) {
                len[2][m[2]+1] = min(len[0][head[0]+1], len[1][head[1]+1]);
                num[2][m[2]] = len[2][m[2]+1]-len[2][m[2]];
                for (int i = 0; i < 2; i++) {
                        val[2][m[2]] += val[i][head[i]];
                        if(len[i][head[i]+1]==len[2][m[2]+1]) head[i]++;
                }
                m[2]++;
        }
        for (int i = 0; i < 2; i++) {
                while(head[i] < m[i]) {
                        len[2][m[2]+1] = len[i][head[i]+1];
                        num[2][m[2]] = len[2][m[2]+1]-len[2][m[2]];
                        val[2][m[2]] = val[i][head[i]];
                        head[i]++;
                        m[2]++;
                }
        }
        // ok before here

        int carry = 0;
        for (int i = 0; i < m[2]; i++) {
                int k = val[2][i]+carry;
                val[3][m[3]] = k%10;
                num[3][m[3]] = 1;
                len[3][m[3]+1] = len[3][m[3]]+1;
                m[3]++;
                if(num[2][i] > 1) {
                        k = val[2][i]+k/10;
                        val[3][m[3]] = k%10;
                        num[3][m[3]] = num[2][i]-1;
                        len[3][m[3]+1] = len[3][m[3]]+num[3][m[3]];
                        m[3]++;
                }
                carry = k/10;
        }
        if(carry) {
                val[3][m[3]] = carry;
                num[3][m[3]] = 1;
                len[3][m[3]+1] = len[3][m[3]]+1;
                m[3]++;
        }
        int pv = val[3][0];
        for (int i = 0; i < m[3]; i++) {
                if(val[3][i] != pv) {
                        val[4][m[4]] = pv;
                        len[4][m[4]+1] = len[3][i];
                        num[4][m[4]] = len[4][m[4]+1]-len[4][m[4]];
                        m[4]++;
                        pv = val[3][i];
                }
        }
        val[4][m[4]] = pv;
        len[4][m[4]+1] = len[3][m[3]];
        num[4][m[4]] = len[4][m[4]+1]-len[4][m[4]];
        m[4]++;
        cout << m[4] << endl;
        for (int i = 0; i < m[4]; i++)
                cout << val[4][m[4]-i-1] << ' ' << num[4][m[4]-i-1] << endl;

}

void input()
{
        for (int i = 0; i < 2; i++) {
                cin >> m[i];
                for (int j = 0; j < m[i]; j++)
                        cin >> val[i][m[i]-j-1] >> num[i][m[i]-j-1];
        }
}

signed main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        solve();
        return 0;
}

Comments