Pagini recente » Cod sursa (job #1869429) | Cod sursa (job #3185145) | Cod sursa (job #1857928) | Cod sursa (job #743242) | Cod sursa (job #1557975)
#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;
}