Cod sursa(job #37873)

Utilizator tvladTataranu Vlad tvlad Data 25 martie 2007 12:56:58
Problema Next Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 9-a si gimnaziu Marime 1.66 kb
#include <cstdio>
#include <cstring>

const int NC = 1000001;

int n[NC], d[NC], r[NC], c[NC];
char s[NC];

void print ( int a[] ) {
	for (int i = a[0]; i>0; --i) {
		printf("%d",a[i]);
	}
	printf("\n");
}

void shl ( int a[], int kt ) {
	memmove(&a[kt+1],&a[1],sizeof(int)*a[0]);
	memset(&a[1],0,sizeof(int)*kt);
	a[0] += kt;
}

bool maimare( int a[], int b[] ) {
	if (a[0] == b[0]) {
		for (int i = 1; i<a[0]; ++i) {
			if (a[i] != b[i]) {
				return a[i] > b[i];
			}
		}
		return true;
	} else {
		return a[0] > b[0];
	}
}

void scadere ( int a[], int b[] ) {
	int t = 0;
	for (int i = b[0]+1; i<=a[0]; ) b[i++] = 0;
	for (int i = 1; i<=a[0]; ++i) {
		a[i] = a[i] - (b[i] + t);
		if (a[i] < 0) t = 1;
		else t = 0;
		if (t == 1) a[i] += 10;
	}
	while (a[a[0]] == 0) --a[0];
}

void adunare ( int a[], int b[] ) {
	int t = 0;	
	if (b[0] > a[0]) {
		for (int i = a[0]+1; i<b[0]; ++i) a[i] = 0;
		a[0] = b[0];
	} else {
		for (int i = b[0]+1; i<a[0]; ++i) b[i] = 0;
	}
	for (int i = 1; i<=a[0]; ++i) {
		a[i] += b[i] + t;
		t = a[i] / 10;
		a[i] %= 10;
	}
	if (t != 0) a[++a[0]] = t;
}

void impartire ( int a[], int b[], int r[], int c[] ) {
	r[0] = 0; c[0] = a[0];
	for (int i = a[0]; i > 0; --i) {
		shl(r,1);
		r[1] = a[i];
		c[i] = 0;
		while (maimare(r,b)) {
			++c[i];
			scadere(r,b);
		}
	}	
	while (c[c[0]] == 0) --c[0];
}

int main() {
	freopen("next.in","r",stdin);
	freopen("next.out","w",stdout);
	
	scanf("%s",s);
	n[0] = strlen(s);
	for (int i = 1; i<=n[0]; ++i) {
		n[n[0]-i+1] = s[i-1] - '0';
	}
	scanf("%s",s);
	d[0] = strlen(s);
	for (int i = 1; i<=d[0]; ++i) {
		d[d[0]-i+1] = s[i-1] - '0';
	}
	
	impartire(n,d,r,c);
	scadere(n,r);
	adunare(n,d);
	
	print(n);
	return 0;
}