Cod sursa(job #1557975)

Utilizator stoianmihailStoian Mihail stoianmihail Data 28 decembrie 2015 15:28:26
Problema Multiplu Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>

#define Nadejde 2000000
#define BIT 2
#define NIL -1

int A, B;
int qhead, qtail;
int Q[Nadejde + 1];
char seen[Nadejde];
char digit[Nadejde];
int parent[Nadejde];

/** Afiseaza numarul dorit. **/
void traceBack(int hash) {
  if (hash != NIL) {
    traceBack(parent[hash]);
    fprintf(stdout, "%d", digit[hash]);
  }
}

/** cmmdc(u, v). **/
int gcd(int u, int v) {
  return v ? gcd(v, u % v) : u;
}

/** cmmmc(u, v). **/
int lcm(int u, int v) {
  return (1LL * u * v) / gcd(u, v);
}

/** Pune in coada restul "v". **/
void enqueue(int v, int last, int from) {
  Q[qtail] = v;
  digit[v] = last;
  parent[v] = from;
  seen[v] = NIL;
  qtail++;
}

/** Ia din coada restul "v". **/
void dequeue(int *v) {
  (*v) = Q[qhead];
  qhead++;
}

/** Genereaza resturile numerelor formate din 0 si 1. **/
void bfs(int MOD) {
  int i, h, next;

  enqueue(1, 1, NIL);
  do {
    dequeue(&h);
    for (i = 0; i < BIT; i++) {
      next = ((h << 3) + (h << 1) + i) % MOD;
      if (!seen[next]) {
        enqueue(next, i, h);
      }
    }
  } while ((qhead != qtail) && (!seen[0]));
  traceBack(0);
}

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

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

  /* Calcularea solutiei si afisarea ei. */
  freopen("multiplu.out", "w", stdout);
  bfs(lcm(A, B));
  fclose(stdout);

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