TAKMIČENJA IZ PROGRAMIRANJA


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.

mika.cpp    3,362 b      izvorni kod rešenja
mika.tests.rar    139,855 b      test primeri
mika.checker.cpp    1,686 b      izvorni kod programa za testiranje

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;
}