|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Mrav Mika
|
Mrav Mika je vredan mrav i mnogo voli da kopa rupe i pravi tunele. Toliko voli to
da radi, da je iskopao čak n (5 ≤ n ≤ 1.000) rupa, koje su međusobno povezane sa m (1 ≤
m ≤ 10.000) tunela. Međutim, mrav Mika nije znao zlatno pravilo kopača rupa i tunela.
Ono nalaže da je mogućnost podele rupa u dve grupe, tako da između grupa postoji bar
⌊ m / 2 ⌋
tunela, neophodan uslov za stabilnost podzemnog sistema a samim tim i dobijanje dozvole
za korišćenje tunela. Inspekcija je došla kod Mike da proveri da li se pridržavao ovog
pravila, a kako Mika ipak želi da svoje tunele pusti u rad, zanima ga da li je ono možda
slučajno zadovo eno. Kako rupa i tunela ima previše, ovo je pretežak zadatak za Mikin
mali mozak te vas je zamolio da mu pomognete. Dakle, potrebno je da nađete traženu podelu
rupa u dve grupe (svaka rupa mora pripadati tačno jednoj grupi) ili da mu saopštite da
neće moći da koristi tunele.
Ulaz.
(Ulazni podaci se učitavaju iz datoteke mika.in.) U prvom redu nalaze se brojevi
n i m. Rupe su označene redom brojevima od 1 do n. U narednih m redova nalaze se po dva
broja a i b, i oni označavauj da između rupa označenih brojevima a i b postoji direktan
tunel. Između dve rupe može da postoji najviše jedan direktan tunel.
Izlaz.
(Izlazne podatke upisati u datoteku mika.out) Ukoliko nije moguće napraviti
takvu podelu rupa, ispisati -1. U suprotnom, u prvom redu ispisati koliko ima rupa u
prvoj i koliko u drugoj grupi, i potom u naredna dva reda redne brojeve rupa koje pripadaju
prvoj, odnosno drugoj grupi.
Primer 1.
mika.in
|
|
mika.out
|
8 10
1 2
1 5
1 6
5 6
2 6
3 8
3 7
3 4
4 8
7 8
|
|
4 4
5 6 7 8
1 2 3 4
|
Primer 2.
mika.in
|
|
mika.out
|
5 5
1 2
2 3
3 4
4 5
5 1
|
|
3 2
3 4 5
1 2
|
|
|
fajl: mika.cpp
|
#include <iostream>
#include <cstdio>
using namespace std;
const long MaxN = 1001;
long n, m;
long susedCnt[MaxN];
long sused[MaxN][MaxN]; // broj cvorova je mali pa mozemo i ovako da pamtimo listu suseda
bool grupa[MaxN]; // da li pripada prvoj grupi?
long grupaCnt[MaxN]; // koliko cvor gadja unutar svoje grupe
bool dobar[MaxN]; // da li je cvor u listi dobrih ili losih cvorova
// lista suseda zadovoljenih i nezadovoljenih cvorova
long next[MaxN];
long prev[MaxN];
// pocetak liste
int goodStart, badStart;
char fileIn[] = "mika.in";
char fileOut[] = "mika.out";
void ubaci(int &list, int k)
{
if (list == -1)
{
// prazna lista
list = k;
prev[k] = -1;
next[k] = -1;
}
else
{
// na pocetak
prev[list] = k;
next[k] = list;
prev[k] = -1;
list = k;
}
}
void izbaci(int &list, int k)
{
if (list == k)
{
list = next[list];
if (list != -1)
prev[list] = -1;
}
else
{
next[prev[k]] = next[k];
if (next[k] != -1)
prev[next[k]] = prev[k];
}
}
// dodaje nov cvor u odgovarajucu listu
void novCvor(int k)
{
if (grupaCnt[k] > susedCnt[k] / 2)
{
// los cvor
dobar[k] = false;
ubaci(badStart, k);
}
else
{
// dobar cvor
dobar[k] = true;
ubaci(goodStart, k);
}
}
void transfer()
{
int v = badStart;
// posle prebacivanja, cvor postaje dobar
dobar[v] = true;
izbaci(badStart, v);
ubaci(goodStart, v);
for (int i = 0; i < susedCnt[v]; i++)
{
int w = sused[v][i];
if (grupa[w] == grupa[v])
{
// bili ista grupa, vise nisu
grupaCnt[w]--;
grupaCnt[v]--;
// mozda je postao dobar
if (!dobar[w] && (grupaCnt[w] <= susedCnt[w] / 2))
{
// izbacujemo ga iz liste losih, i guramo u listu dobrih
dobar[w] = true;
izbaci(badStart, w);
ubaci(goodStart, w);
}
}
else
{
// postali su ista grupa
grupaCnt[w]++;
grupaCnt[v]++;
// mozda je cvor w postao los
if (dobar[w] && (grupaCnt[w] > susedCnt[w] / 2))
{
// izbacujemo ga iz liste dobrih, i guramo u listu losih
dobar[w] = false;
izbaci(goodStart, w);
ubaci(badStart, w);
}
}
}
// promeni grupu
grupa[v] = !grupa[v];
}
int main()
{
FILE *f = fopen(fileIn, "r");
fscanf(f, "%ld %ld", &n ,&m);
for (int i = 0; i < n; i++)
{
grupaCnt[i] = 0;
susedCnt[i] = 0;
// inicijalna grupa
if (i < n/2) grupa[i] = true;
else grupa[i] = false;
}
for (long i = 0; i < m; i++)
{
long a, b;
fscanf(f, "%ld %ld", &a, &b);
a--; b--;
sused[a][susedCnt[a]++] = b;
sused[b][susedCnt[b]++] = a;
if (grupa[a] == grupa[b])
{
grupaCnt[a]++;
grupaCnt[b]++;
}
}
fclose(f);
goodStart = -1;
badStart = -1;
for (int i = 0; i < n; i++)
novCvor(i);
// prebacujemo iz jedne grupe u drugu, dokle god mozemo
while (badStart != -1)
{
transfer();
}
int grupa1 = 0, grupa2 = 0;
for (int i = 0; i < n; i++)
{
if (grupa[i])
grupa1++;
else
grupa2++;
}
f = fopen(fileOut, "w");
fprintf(f, "%d %d\n", grupa1, grupa2);
for (int i = 0; i < n; i++)
if (grupa[i]) fprintf(f, "%d ", (i+1));
fprintf(f, "\n");
for (int i = 0; i < n; i++)
if (!grupa[i]) fprintf(f, "%d ", (i+1));
fprintf(f, "\n");
fclose(f);
return 0;
}
|
|
|