Skip to content

Instantly share code, notes, and snippets.

@wasabili
Created October 29, 2010 08:28
Show Gist options
  • Save wasabili/653145 to your computer and use it in GitHub Desktop.
Save wasabili/653145 to your computer and use it in GitHub Desktop.
A+B Problem
#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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment