Cod sursa(job #1571835)

Utilizator stoianmihailStoian Mihail stoianmihail Data 18 ianuarie 2016 16:11:25
Problema A+B Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 6.84 kb
#include <stdio.h>
#include <string.h>

#define Nadejde 20

typedef struct {
  int size, sign;
  int d[Nadejde + 1];
} huge;

void write(huge*);
int cmp(huge*, huge*, int);
huge add(huge*, huge*);
huge diff(huge*, huge*, int);
huge product(huge*, huge*);
huge division(huge*, huge*);

/** MIN(X, Y). **/
int MIN(int X, int Y) {
  return X < Y ? X : Y;
}

/** Transforma valoarea "x" in numar. **/
huge fromNumber(int x) {
  huge R;
  R.size = 0;

  /* Verifica daca e negativ. */
  if (x < 0) {
    R.sign = -1;
    x = -x;
  } else {
    R.sign = 1;
  }

  /* Calculeaza cifrele numarului. */
  do {
    R.d[++R.size] = x % 10;
    x /= 10;
  } while (x);
  return R;
}

/** Transforma sirul "str" in numar. **/
huge fromString(char *str) {
  huge R;
  R.size = 0;

  int until;
  if (str[0] == '-') {
    until = 1;
    R.sign = -1;
  } else {
    until = 0;
    R.sign = 1;
  }

  int i, len = strlen(str);

  for (i = len - 1; i >= until; i--) {
    R.d[++R.size] = str[i] - '0';
  }
  return R;
}

/** A > B: 1
 *  A = B: 0
 *  A < B: -1
**/
int cmp(huge *A, huge *B, int set) {
  int i, sign;

  /** Set este 1 doar daca ne uitam si la semn. **/

  if (set) {
    if (A -> sign == -1) {
      if (B -> sign == 1) {
        return -1;
      } else {
        sign = -1;
      }
    } else if (B -> sign == -1) {
      return 1;
    } else {
      sign = 1;
    }
  } else {
    sign = 1;
  }
  if (A -> size > B -> size) {
    return sign * 1;
  } else if (A -> size < B -> size) {
    return sign * -1;
  } else {
    for (i = A -> size; (i != 0) && (A -> d[i] == B -> d[i]); i--);
    if (i) {
      if (A -> d[i] > B -> d[i]) {
        return sign * 1;
      } else {
        return sign * -1;
      }
    } else {
      return 0;
    }
  }
}

/** Curata zerourile de la inceput. **/
void clear(huge *A) {
  while ((A -> size > 1) && (A -> d[A -> size] == 0)) {
    A -> size--;
  }
}

/** A + B, A si B numere intregi. **/
huge add(huge *A, huge *B) {
  huge R;
  R.size = 0;

  int i, sign, t = 0, sum, lim = MIN(A -> size, B -> size);

  if (A -> sign == -1) {
    if (B -> sign == -1) {
      sign = -1;
    } else {
      return diff(B, A, 0);
    }
  } else if (B -> sign == -1) {
    return diff(A, B, 0);
  } else {
    sign = 1;
  }

  for (i = 1; i <= lim; i++) {
    sum = A -> d[i] + B -> d[i] + t;
    t = (sum > 9);
    R.d[++R.size] = sum - (t << 3) - (t << 1);
  }
  for (; i <= A -> size; i++) {
    sum = A -> d[i] + t;
    t = (sum > 9);
    R.d[++R.size] = sum - (t << 3) - (t << 1);
  }
  for (; i <= B -> size; i++) {
    sum = B -> d[i] + t;
    t = (sum > 9);
    R.d[++R.size] = sum - (t << 3) - (t << 1);
  }
  if (t) {
    R.d[++R.size] = 1;
  }
  R.sign = sign;
  return R;
}

/** A - B, A si B numere intregi daca set = 1. Daca nu, A si B sunt numere naturale. **/
huge diff(huge *A, huge *B, int set) {
  huge R, tmp;
  int swap = 0;
  R.size = 0;

  /** Set este 1 doar daca vrem diferenta cu semn. **/

  if (!set) {
    if (cmp(A, B, 0) >= 0) {
      R.sign = 1;
    } else {
      swap = 1;
      tmp = *A;
      *A = *B;
      *B = tmp;
      R.sign = -1;
    }
  } else {
    tmp = *B;
    tmp.sign = -tmp.sign;
    if (A -> sign == -1) {
      if (B -> sign == 1) {
        return add(A, &tmp);
      } else {
        return add(&tmp, A);
      }
    } else if (B -> sign == -1) {
      return add(A, &tmp);
    } else {
        return diff(A, B, 0);
    }
  }

  int i, up, t = 0;

  for (i = 1; i <= B -> size; i++) {
    up = A -> d[i] - B -> d[i] - t;
    t = (up < 0);
    R.d[++R.size] = up + (t << 3) + (t << 1);
  }
  for (; i <= A -> size; i++) {
    up = A -> d[i] - t;
    t = (up < 0);
    R.d[++R.size] = up + (t << 3) + (t << 1);
  }
  if (swap) {
    tmp = *A;
    *A = *B;
    *B = tmp;
  }
  clear(&R);
  return R;
}

/** A * (10 ^ x), x >= 0 **/
huge shl(huge *A, int x) {
  huge R;
  R.size = 0;

  int i;

  for (i = A -> size; i; i--) {
    R.d[i + x] = A -> d[i];
  }
  for (i = 1; i <= x; i++) {
    R.d[i] = 0;
  }
  R.size = A -> size + x;
  R.sign = A -> sign;
  return R;
}

/** A / (10 ^ x), x >= 0 **/
huge shr(huge *A, int x) {
  huge R;
  R.size = 0;
  if (x < A -> size) {
    int i;

    for (i = x + 1; i <= A -> size; i++) {
      R.d[i - x] = A -> d[i];
    }
    R.size = A -> size - x;
    R.sign = A -> sign;
  } else {
    R.d[++R.size] = 0;
    R.sign = 1;
  }
  return R;
}

/** A * digit, 0 <= digit <= 9 si A este numar intreg. **/
huge mul(huge *A, int digit) {
  huge R;
  R.size = 0;

  if (digit) {
    int i, p, q = 0;

    for (i = 1; i <= A -> size; i++) {
      p = A -> d[i] * digit + q;
      q = p / 10;
      R.d[++R.size] = p - (q << 3) - (q << 1);
    }
    if (q) {
      R.d[++R.size] = q;
    }
    R.sign = A -> sign;
  } else {
    R.d[R.size = 1] = 0;
    R.sign = 1;
  }
  return R;
}

/** A * B, A si B sunt numere intregi **/
huge product(huge *A, huge *B) {
  huge R, tmp;
  R.size = 0;

  int i;

  for (i = 1; i <= B -> size; i++) {
    tmp = mul(A, B -> d[i]);
    tmp = shl(&tmp, i - 1);
    R = add(&R, &tmp);
  }
  R.sign = A -> sign * B -> sign;
  return R;
}

/** Cauta binar cea mai mare cifra care inmultita cu "min" este mai mica sau egala cu "max". **/
int search(huge *max, huge *min) {
  huge tmp;
  int mid, lo = -1, hi = 10;

  while (hi - lo > 1) {
    mid = (lo + hi) >> 1;
    tmp = mul(min, mid);
    if (cmp(&tmp, max, 0) <= 0) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  return lo;
}

/** Inverseaza numarul "A". **/
huge reverse(huge *A) {
  huge R;
  R.sign = A -> sign;
  R.size = A -> size;

  int i;

  for (i = A -> size; i; i--) {
    R.d[A -> size - i + 1] = A -> d[i];
  }
  return R;
}

/** A / B, A si B sunt numere intregi. **/
huge division(huge *A, huge *B) {
  huge R, tmp, time;
  R.size = 0;

  if (cmp(A, B, 0) >= 0) {
    int i, len = A -> size - B -> size;

    /* Vedem cu ce prefix pornim. */
    tmp = shr(A, len);
    if (cmp(&tmp, B, 0) >= 0) {
      tmp = shr(A, ++len);
    }

    for (i = len; i; i--) {
      tmp = shl(&tmp, 1);
      tmp.d[1] = A -> d[i];
      clear(&tmp);

      R.d[++R.size] = search(&tmp, B);
      time = mul(B, R.d[R.size]);
      tmp = diff(&tmp, &time, 0);
    }
    R.sign = A -> sign * B -> sign;
  } else {
    R.d[++R.size] = 0;
    R.sign = 1;
  }
  return reverse(&R);
}

/** Afiseaza numarul "A". **/
void write(huge *A) {
  int i;

  if (A -> sign == -1) {
    if ((A -> size == 1) && (A -> d[1] == 0)) {
      /* Daca "A" este 0. */
    } else {
      fputc('-', stdout);
    }
  }
  for (i = A -> size; i; i--) {
    fprintf(stdout, "%d", A -> d[i]);
  }
  fputc('\n', stdout);
}

int main(void) {
  int a, b;
  FILE *f = fopen("adunare.in", "r");

  /* Citirea datelor. */
  fscanf(f, "%d %d", &a, &b);
  fclose(f);

  /* Calcularea solutiei. */
  huge A = fromNumber(a);
  huge B = fromNumber(b);
  huge R = add(&A, &B);

  /* Afisarea solutiei. */
  freopen("adunare.out", "w", stdout);
  write(&R);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;

}