A+B Problem

aplusb.cpp

#include<cstdio>
#include<stack>
#include<queue>
#include<vector>

using namespace std;

typedef struct {
	int v;
	long long int n;
} node;
	
main(){
	stack<node> a;
	stack<node> b;
	
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		node x;
		scanf("%d%d",&(x.v),&(x.n));
		a.push(x);
	}
	
	int m;
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		node x;
		scanf("%d%d",&(x.v),&(x.n));
		b.push(x);
	}
	
	queue<node> q;
	int alen,blen,av,bv;
	alen = blen = 0;
	while(1){
		if(alen==0&&blen==0&&a.empty()&&b.empty()) break;
		if(alen==0&&a.empty()){
			node x;
			x.n = blen;
			x.v = bv;
			q.push(x);
			while(!b.empty()){
				q.push(b.top());b.pop();
			}
			break;
		}
		if(blen==0&&b.empty()){
			node x;
			x.n = alen;
			x.v = av;
			q.push(x);
			while(!a.empty()){
				q.push(a.top());a.pop();
			}
			break;
		}
		node x;
		if(alen==0){
			x = a.top();a.pop();
			alen = x.n;
			av = x.v;
		}
		if(blen==0){
			x = b.top();b.pop();
			blen = x.n;
			bv = x.v;
		}
		
		x.n = min(alen,blen);
		x.v = av+bv;
		q.push(x);
		alen -= x.n;
		blen -= x.n;
	}
	
/*	while(!q.empty()){
		node x = q.front();q.pop();
		printf("%d %d\n", x.v, x.n);
	}
	return 0;*/
	
	queue<node> q2;
	
	bool kuriage=false;
	while(!q.empty()){
		node x = q.front();q.pop();
		if(kuriage){
			if(x.v == 9){
				node y;
				y.n = x.n;
				y.v = 0;
				q2.push(y);
			}else if(x.v < 9){
				node y;
				y.n = 1;
				y.v = x.v+1;
				q2.push(y);
				node z;
				z.n = x.n-1;
				z.v = x.v;
				q2.push(z);
				kuriage = false;
			}else{
				node y;
				y.n = x.n;
				y.v = x.v%10+1;
				q2.push(y);
			}
		}else {
			if(x.v <= 9){
				q2.push(x);
			}else {
				node y;
				y.n = 1;
				y.v = x.v%10;
				q2.push(y);
				node z;
				z.n = x.n-1;
				z.v = x.v%10+1;
				q2.push(z);
				kuriage = true;
			}
		}
	}
	if(kuriage){
		node x;
		x.n = 1;
		x.v = 1;
		q2.push(x);
	}
	
/*	while(!q2.empty()){
		node x = q2.front();q2.pop();
		printf("%d %d\n", x.v, x.n);
	}
	return 0;*/
	
	queue<node> q3;
	
	node tmp = q2.front();q2.pop();
	int last = tmp.v;
	long long int len = tmp.n;
	int counter = 0;
	while(!q2.empty()){
		node x = q2.front();q2.pop();
		if(x.v == last){
			len+=x.n;
		}else{
			node y;
			y.n = len;
			y.v = last;
			if(y.n!=0){
				q3.push(y);
				counter++;
			}
			last = x.v;
			len = x.n;
		}
	}
	node x;
	x.n = len;
	x.v = last;
	if(x.n!=0){
		q3.push(x);
		counter++;
	}
	
	stack<node> q4;
	
	tmp = q3.front();q3.pop();
	last = tmp.v;
	len = tmp.n;
	counter = 0;
	while(!q3.empty()){
		node x = q3.front();q3.pop();
		if(x.v == last){
			len+=x.n;
		}else{
			node y;
			y.n = len;
			y.v = last;
			if(y.n!=0){
				q4.push(y);
				counter++;
			}
			last = x.v;
			len = x.n;
		}
	}
	x;
	x.n = len;
	x.v = last;
	if(x.n!=0){
		q4.push(x);
		counter++;
	}
	
	
	printf("%d\n", counter);
	while(!q4.empty()){
		node x = q4.top();q4.pop();
		printf("%d %lld\n", x.v,x.n);
	}
}