Cod sursa(job #1524105)

Utilizator nedelcu11Nedelcu Mihai Vlad nedelcu11 Data 13 noiembrie 2015 16:00:24
Problema Next Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#define D 40000
using namespace std;
ifstream f("next.in");
ofstream g("next.out");
typedef int Huge[4000];
Huge a,b,d,r;
int n,i;
char c=0;
void Shl(Huge H, int Count)
/* H <- H*10ACount */
{
  /* Shifteaza vectorul cu Count pozitii */
  memmove(&H[Count+1],&H[1],sizeof(int)*H[0]);
  /* Umple primele Count pozitii cu 0 */
  memset(&H[1],0,sizeof(int)*Count);
  /* Incrementeaza numarul de cifre */
  H[0]+=Count;
}
int Sgn(Huge H1, Huge H2) {
  // Elimina zero-urile semnificative, daca exista.
  while (H1[0] && !H1[H1[0]]) H1[0]--;
  while (H2[0] && !H2[H2[0]]) H2[0]--;

  if (H1[0] < H2[0]) {
    return -1;
  } else if (H1[0] > H2[0]) {
    return +1;
  }

  for (int i = H1[0]; i > 0; --i) {
    if (H1[i] < H2[i]) {
      return -1;
    } else if (H1[i] > H2[i]) {
      return +1;
    }
  }
  return 0;
}
void Subtract(Huge a,Huge b)
{ int i, T=0;
  for (i=b[0]+1;i<=a[0];) b[i++]=0;
  for (i=1;i<=a[0];i++)
    a[i]+= (T=(a[i]-=b[i]+T)<0) ? 10 : 0;
  while (!a[a[0]]) a[0]--;
}
void Add(Huge a, Huge b)
/* a <- a+b */
{ int i,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;
}
void DivideHuge(Huge A, Huge B, Huge C, Huge R)
/* A/B = C rest R */
{ int i;

  R[0]=0;C[0]=A[0];
  for (i=A[0];i;i--)
    { Shl(R,1);R[1]=A[i];
      C[i]=0;
      while (Sgn(B,R)!=1)
        { C[i]++;
          Subtract(R,B);
        }
    }
  while (!C[C[0]] && C[0]>1) C[0]--;
}
int main()
{   f.get(c);
    while(c!='\n')
    {   a[++a[0]]=c-'0';
        f.get(c);
    }
    reverse(a+1,a+a[0]+1);
    f.get(c);
    while(c!='\n')
    {   b[++b[0]]=c-'0';
        f.get(c);
    }
    reverse(b+1,b+b[0]+1);
    DivideHuge(a,b,d,r);
    if(r) {Subtract(b,r);Add(a,b);}
    for(int i=a[0];i>=1;i--) g<<a[i];
    return 0;
}