Cod sursa(job #1001897)

Utilizator Gusti666Lucaciu Catalin Gusti666 Data 26 septembrie 2013 15:21:38
Problema Next Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#define LG_MAX 1000000 + 1
using namespace std;
ifstream f("next.in");
ofstream g("next.out");
int suma1[LG_MAX],modul[LG_MAX],rezultat[LG_MAX],n[LG_MAX],x[LG_MAX],rest[LG_MAX],cat[LG_MAX];

  typedef int BigNumber[LG_MAX];

  void citire(BigNumber x){
  int i;
  char s[LG_MAX];
  f>>s;
  x[0]=strlen(s);
  for(i = x[0]-1; i >= 0; i--) x[x[0]-i] = s[i]-'0';
     for(i = x[0]+1; i < LG_MAX; i++) x[i] = 0;
  }
  void afisare(BigNumber x)
{
     for(int i = x[0]; i >= 1; i--)
        g<<(x[i]);

}
void suma(BigNumber a,BigNumber b,BigNumber s)
{
    int i,cifra,t = 0,max;

    //completam numarul cel mai mic cu zeroouri nesemnificative
    if(a[0] < b[0]) { max = b[0]; for(i = a[0]+1; i <= b[0]; i++) a[i] = 0; }
    else            { max = a[0]; for(i = b[0]+1; i <= a[0]; i++) b[i] = 0; }

    for(i = 1; i <= max; i++)
    {
      cifra = a[i] + b[i] + t; //calculam noua cifra
      s[i] = cifra % 10;
      t = cifra/10;            //calculam cifra de transport
    }
    if(t) s[i] = t; else i--;
    s[0] = i;
}
void diferenta(BigNumber a,BigNumber b,BigNumber d)
{
     int i,t = 0;
     if(a[0] < b[0])
     {
         diferenta(a,b,d);
     }
     else
     {
       for(i = 1; i <= a[0]; i++)
       {
           d[i] = a[i]-b[i]+t;                //diferenta
           if(d[i] < 0) d[i]+= 10,t = -1;  //calculam cifra de transport
           else t = 0;
        }
        i--;
        while(i && !d[i]) i--;
        d[0] = i;
     }
}
int compara(BigNumber a,BigNumber b)
{
    int i;
    if(a[0] < b[0]) return -1;
    if(a[0] > b[0]) return  1;
    for(i = a[0]; i >= 1 && a[i] == b[i]; i--)
      ;
    if(i < 0) return 0;
    if(a[i] < b[i]) return -1;
    return 1;
}
void p10(BigNumber x,int nr)
{
     int i;
     for(i = x[0]; i >= 1; i--) x[i+nr] = x[i];
     for(i = 1; i <= nr; i++) x[i] = 0;
     x[0] += nr;
}
 void impartire(BigNumber a,BigNumber b,BigNumber c,BigNumber r)
{
     int i;
     r[0] = 0; c[0] = a[0];
     for(i = a[0]; i >= 1; i--)
     {
        p10(r,1); r[1] = a[i];
        c[i] = 0;

        while(compara(b,r) != 1)
        {
           c[i]++;
           diferenta(r,b,r);
        }

     }
     while(!c[c[0]] && c[0] > 1) c[0]--;
     while(!r[r[0]] && r[0] > 1) r[0]--;
}


int main()
{citire(n);
citire(x);
//g<<(n+x)-(n+x)%x;
suma(n,x,suma1);
impartire(suma1,x,cat,rest);
diferenta(suma1,rest,rezultat);
afisare(rezultat);





    return 0;
}