Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI春合宿 2010-day2 aplusb

問題文 : 足し算

解法 :
vectorを使って実際に足し算を行う.
繰り上がり/桁数が変わる位置のみに微妙な変化があり, 間の数の計算は省くことができる.

コード :

#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long lint;
typedef pair<int, lint> P;

int main()
{
	int m1, m2;
	int idx1 = 0, idx2 = 0;
	vector<P> n1, n2;
	vector<P> ret;
	
	n1.push_back(P(0, LLONG_MAX));
	n2.push_back(P(0, LLONG_MAX));
	
	scanf("%d", &m1);
	
	for (int i = 0; i < m1; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		n1.push_back(P(a, b));
	}
	
	scanf("%d", &m2);
	
	for (int i = 0; i < m2; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		n2.push_back(P(a, b));
	}
	
	reverse(n1.begin(), n1.end()); reverse(n2.begin(), n2.end());
	
	int carry = 0;
	
	while (1){
		if (n1[idx1].second == 0) idx1++;
		if (n2[idx2].second == 0) idx2++;
		if (n1[idx1].second > 100000000 && n2[idx2].second > 100000000) break;
		
		int ns = min(n1[idx1].second, n2[idx2].second);
		
		n1[idx1].second -= ns; n2[idx2].second -= ns;
		
		if (n1[idx1].first + n2[idx2].first + carry < 10){
			ret.push_back(P(n1[idx1].first + n2[idx2].first + carry, 1));
			if (ns - 1) ret.push_back(P(n1[idx1].first + n2[idx2].first, ns - 1));
			carry = 0;
		}
		else {
			ret.push_back(P((n1[idx1].first + n2[idx2].first + carry) % 10, 1));
			if (ns - 1) ret.push_back(P((n1[idx1].first + n2[idx2].first + 1) % 10, ns - 1));	
			carry = 1;
		}
	}
	if (carry == 1) ret.push_back(P(1, 1));
	reverse(ret.begin(), ret.end());
	
	int size = 0;
	
	for (int i = 0; i < ret.size();){
		size++;
		int j = i + 1;
		while (j != ret.size() && ret[i].first == ret[j].first){
			ret[i].second += ret[j].second; ret[j].second = 0;
			j++;
		}
		i = j;
	}
	
	printf("%d\n", size);
	
	for (int i = 0; i < ret.size(); i++){
		if (ret[i].second) printf("%d %lld\n", ret[i].first, ret[i].second);
	}
	
	return (0);
}