Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992Code (c):
#include <stdio.h>
#include <stdbool.h>
#define MAX_GRADOVA 40
#define MAX_OSOBA (MAX_GRADOVA-1)
#define MAX_KORAKA (MAX_GRADOVA >= 3 ? 2*MAX_GRADOVA-4 : MAX_GRADOVA-1)
struct graf
{
int br_gradova;
bool povezani[MAX_GRADOVA][MAX_GRADOVA];
};
struct osobe
{
int br_osoba;
int mesto[MAX_OSOBA];
};
int unesi_broj(const char *text)
{
int broj;
if (text!=NULL) {
printf("%s", text);
}
fflush(stdout);
scanf("%d", &broj);
return broj;
}
void unesi_graf(struct graf *graf)
{
graf->br_gradova = 0;
for (int i = 0; i < MAX_GRADOVA; ++i) {
for (int j = 0; j < MAX_GRADOVA; ++j) {
graf->povezani[i][j] = false;
}
}
graf->br_gradova = unesi_broj("Unesi broj gradova : ");
int broj_puteva = unesi_broj("Unesi broj puteva : ");
printf("Unesi puteve:\n");
for (int p = 0; p < broj_puteva; ++p) {
int i = unesi_broj(NULL) - 1;
int j = unesi_broj(NULL) - 1;
graf->povezani[i][j] = graf->povezani[j][i] = true;
}
}
void unesi_osobe(struct osobe *osobe)
{
osobe->br_osoba = unesi_broj("Unesi broj osoba : ");
for (int i = 0; i < osobe->br_osoba; ++i) {
printf("Unesi grad u kome se nalazi osoba %d : ", i+1);
osobe->mesto[i] = unesi_broj(NULL) - 1;
}
}
int main()
{
struct graf graf;
struct osobe osobe;
unesi_graf(&graf);
unesi_osobe(&osobe);
int max_koraka = graf.br_gradova >= 3 ? 2*graf.br_gradova-4 : graf.br_gradova-1;
bool dostizno[MAX_OSOBA][MAX_GRADOVA][MAX_KORAKA+1] = { false };
int grad_susreta = -1;
int korak;
for (int osoba = 0; osoba < MAX_OSOBA; ++osoba) {
dostizno[osoba][osobe.mesto[osoba]][0] = true;
}
for (korak = 1; korak<=max_koraka; ++korak) {
for (int osoba = 0; osoba < osobe.br_osoba; ++osoba) {
for (int iz_grada = 0; iz_grada < graf.br_gradova; ++iz_grada) {
if (dostizno[osoba][iz_grada][korak-1]) {
for (int u_grad = 0; u_grad < graf.br_gradova; ++u_grad) {
if (graf.povezani[iz_grada][u_grad]) {
dostizno[osoba][u_grad][korak] = true;
}
}
}
}
}
for (int grad = 0; grad < graf.br_gradova; ++grad) {
bool nadjen = false;
for (int osoba = 0; osoba < osobe.br_osoba; ++osoba) {
if (dostizno[osoba][grad][korak]==false) {
nadjen = true;
break;
}
}
if (nadjen == false) {
grad_susreta = grad;
break;
}
}
if (grad_susreta != -1) {
break;
}
}
if (grad_susreta == -1) {
printf("Ne mogu se sresti u istom gradu.\n");
return 0;
}
printf("Mogu se svi sresti u gradu %d. Evo putanja za svakoga:\n", grad_susreta+1);
for (int osoba = 0; osoba < osobe.br_osoba; ++osoba) {
printf("Osoba %d :", osoba+1);
int putanja[MAX_GRADOVA];
putanja[0] = osobe.mesto[osoba];
putanja[korak] = grad_susreta;
int mesto = grad_susreta;
for (int i = korak-1; i >= 1; --i) {
for (int grad = 0; grad < graf.br_gradova; ++grad) {
if (dostizno[osoba][grad][i] && graf.povezani[grad][mesto]) {
putanja[i] = grad;
mesto = grad;
break;
}
}
}
for (int i = 0; i <= korak; ++i) {
printf(" %d", putanja[i]);
}
printf(".\n");
}
return 0;
}
#include <stdio.h>
#include <stdbool.h>
#define MAX_GRADOVA 40
#define MAX_OSOBA (MAX_GRADOVA-1)
#define MAX_KORAKA (MAX_GRADOVA >= 3 ? 2*MAX_GRADOVA-4 : MAX_GRADOVA-1)
struct graf
{
int br_gradova;
bool povezani[MAX_GRADOVA][MAX_GRADOVA];
};
struct osobe
{
int br_osoba;
int mesto[MAX_OSOBA];
};
int unesi_broj(const char *text)
{
int broj;
if (text!=NULL) {
printf("%s", text);
}
fflush(stdout);
scanf("%d", &broj);
return broj;
}
void unesi_graf(struct graf *graf)
{
graf->br_gradova = 0;
for (int i = 0; i < MAX_GRADOVA; ++i) {
for (int j = 0; j < MAX_GRADOVA; ++j) {
graf->povezani[i][j] = false;
}
}
graf->br_gradova = unesi_broj("Unesi broj gradova : ");
int broj_puteva = unesi_broj("Unesi broj puteva : ");
printf("Unesi puteve:\n");
for (int p = 0; p < broj_puteva; ++p) {
int i = unesi_broj(NULL) - 1;
int j = unesi_broj(NULL) - 1;
graf->povezani[i][j] = graf->povezani[j][i] = true;
}
}
void unesi_osobe(struct osobe *osobe)
{
osobe->br_osoba = unesi_broj("Unesi broj osoba : ");
for (int i = 0; i < osobe->br_osoba; ++i) {
printf("Unesi grad u kome se nalazi osoba %d : ", i+1);
osobe->mesto[i] = unesi_broj(NULL) - 1;
}
}
int main()
{
struct graf graf;
struct osobe osobe;
unesi_graf(&graf);
unesi_osobe(&osobe);
int max_koraka = graf.br_gradova >= 3 ? 2*graf.br_gradova-4 : graf.br_gradova-1;
bool dostizno[MAX_OSOBA][MAX_GRADOVA][MAX_KORAKA+1] = { false };
int grad_susreta = -1;
int korak;
for (int osoba = 0; osoba < MAX_OSOBA; ++osoba) {
dostizno[osoba][osobe.mesto[osoba]][0] = true;
}
for (korak = 1; korak<=max_koraka; ++korak) {
for (int osoba = 0; osoba < osobe.br_osoba; ++osoba) {
for (int iz_grada = 0; iz_grada < graf.br_gradova; ++iz_grada) {
if (dostizno[osoba][iz_grada][korak-1]) {
for (int u_grad = 0; u_grad < graf.br_gradova; ++u_grad) {
if (graf.povezani[iz_grada][u_grad]) {
dostizno[osoba][u_grad][korak] = true;
}
}
}
}
}
for (int grad = 0; grad < graf.br_gradova; ++grad) {
bool nadjen = false;
for (int osoba = 0; osoba < osobe.br_osoba; ++osoba) {
if (dostizno[osoba][grad][korak]==false) {
nadjen = true;
break;
}
}
if (nadjen == false) {
grad_susreta = grad;
break;
}
}
if (grad_susreta != -1) {
break;
}
}
if (grad_susreta == -1) {
printf("Ne mogu se sresti u istom gradu.\n");
return 0;
}
printf("Mogu se svi sresti u gradu %d. Evo putanja za svakoga:\n", grad_susreta+1);
for (int osoba = 0; osoba < osobe.br_osoba; ++osoba) {
printf("Osoba %d :", osoba+1);
int putanja[MAX_GRADOVA];
putanja[0] = osobe.mesto[osoba];
putanja[korak] = grad_susreta;
int mesto = grad_susreta;
for (int i = korak-1; i >= 1; --i) {
for (int grad = 0; grad < graf.br_gradova; ++grad) {
if (dostizno[osoba][grad][i] && graf.povezani[grad][mesto]) {
putanja[i] = grad;
mesto = grad;
break;
}
}
}
for (int i = 0; i <= korak; ++i) {
printf(" %d", putanja[i]);
}
printf(".\n");
}
return 0;
}
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
