Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 1 KB
#include <stdio.h>
#include <stdint.h>
uint8_t elek[1000][1000];
size_t n, e;
int8_t cache_bal[1000][1000], cache_jobb[1000][1000];
int beolvas(void)
{
int a, b;
size_t i, j;
if (scanf("%d %d", &n, &e) != 2) {
printf("hibas bemenet\n");
return 0;
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
elek[i][j] = 0;
for (i = 0; i < e; i++) {
if (scanf("%d %d", &a, &b) != 2) {
printf("hibas bemenet\n");
return 0;
}
elek[a - 1][b - 1] = 1;
elek[b - 1][a - 1] = 1;
}
return 1;
}
int el(int u, int v)
{
return elek[u][v];
}
int mod(int x)
{
if (x < 0)
x += n;
return x % n;
}
void nullaz(void)
{
size_t i, j;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
cache_bal[i][j] = -1;
cache_jobb[i][j] = -1;
}
}
int bal(int u, int v);
int jobb(int u, int v);
int bal(int u, int v)
{
u = mod(u);
v = mod(v);
if (cache_bal[u][v] >= 0)
return cache_bal[u][v];
if (u == v)
cache_bal[u][v] = 1;
else
cache_bal[u][v] = (bal(u, v - 1) && el(v - 1, v)) ||
(jobb(v - 1, u) && el(u, v));
return cache_bal[u][v];
}
int jobb(int u, int v)
{
u = mod(u);
v = mod(v);
if (cache_jobb[u][v] >= 0)
return cache_jobb[u][v];
if (u == v)
cache_jobb[u][v] = 1;
else
cache_jobb[u][v] = (jobb(u, v + 1) && el(v + 1, v)) ||
(bal(v + 1, u) && el(u, v));
return cache_jobb[u][v];
}
void megold(void)
{
size_t i, j;
nullaz();
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
if (bal(i + 1, j) && jobb(i, j)) {
printf("IGEN\n");
return;
}
}
#if 0
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%2d ", cache_bal[i][j]);
printf("\n");
}
printf("\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%2d ", cache_jobb[i][j]);
printf("\n");
}
#endif
printf("NEM\n");
}
int main(void)
{
if (!beolvas())
return 1;
megold();
return 0;
}
