Cod sursa(job #1439114)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 21 mai 2015 15:21:06
Problema Next Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

#define NMax 1000002

#pragma warning(push)
#pragma warning(disable: 4996)

int x[NMax];
int result[NMax];
int unu[NMax];
long long d;
string s;
long long rest;

/* A <- A/X si intoarce A%X */
unsigned long Divide(int A[NMax], long long X)
{
	int i;
	long long R = 0;

	for (i = A[0]; i; i--)
	{
		R = 10 * R + A[i];
		A[i] = R / X;
		R %= X;
	}
	// trimming zeros from result
	while (!A[A[0]] && A[0]>1) A[0]--;

	// return rest
	return R;
}

void Mult(int H[NMax], long long X)
/* H <- H*X */
{
	int i;
	long long T = 0;

	for (i = 1; i <= H[0]; i++)
	{
		H[i] = H[i] * X + T;
		T = H[i] / 10;
		H[i] = H[i] % 10;
	}
	while (T) /* Cat timp exista transport */
	{
		H[++H[0]] = T % 10;
		T /= 10;
	}
}

/* A <- A+B */
void Add(int A[NMax], int B[NMax])
{
	int i;
	long long T = 0;

	if (B[0]>A[0])
	{
		for (i = A[0] + 1; i <= B[0];) A[i++] = 0;
		A[0] = B[0];
	}
	else for (i = B[0] + 1; i <= A[0];) B[i++] = 0;
	for (i = 1; i <= A[0]; i++)
	{
		A[i] += B[i] + T;
		T = A[i] / 10;
		A[i] %= 10;
	}
	if (T) A[++A[0]] = T;
}

int main()
{
	freopen("next.in", "r", stdin);
	freopen("next.out", "w", stdout);

	cin >> s;
	cin >> d;

	int j = 1;

	// put the digits in reverse order in x
	for (int i = s.length() - 1; i >= 0; --i)
	{
		x[j] = s[i] - '0';
		j++;
	}

	x[0] = s.length();

	rest = Divide(x, d);

	if (rest == 0)
		// numarul initial se divide cu d, il afisam
		cout << s << endl;
	else
	{
		// inmulteste catul+1 cu deimpartitul si afiseaza rezultatul
		unu[0] = 1;
		unu[1] = 1;
		Add(x, unu);
		Mult(x, d);
		for (int i = 1; i <= x[0]; ++i)
			cout << x[i];
		cout << endl;
	}
	
	return 0;
}

#pragma warning(pop)