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.

teleport.cpp    1,546 b      izvorni kod rešenja
teleport.tests.rar    22,931,113 b      test primeri

zadatak: Teleport
Usled prevelikog zagađenja vazduha, ljudi su morali da napuste Zemlju i sada žive u svemirskim stanicama. Navedene civilne stanice su numerisane brojevima 1, 2, ..., m. Radi odbrane od vanzemaljaca napravljeno je još n vojnih stanica. Između svake vojne i svake civilne stanice moguće je teleportovanje u tačno jednom smeru (ako je moguće teleportovanje iz stanice A u stanicu B nije moguće iz stanice B u A). Iz vojne stanice ili nije moguće teleportovanje ni u jednu civilnu stanicu ili je moguće teleportovanje u niz uzastopnih civilnih stanica (npr. iz vojne stanice moguće je teleportovanje u civilne stanice k, k + 1, ..., p gde je 1 ≤ k ≤ p ≤ m). Ne može se teleportovati od jedne civilne stanice do druge civilne, kao i od jedne vojne do druge vojne.

Međutim, vanzemaljci su rešili da osvoje planetu Zemlju. General Đurić je otkrio da vanzemaljci planiraju da napadnu neku stanicu X, ali ne zna tačno koju. On je procenio da ako vojsci treba više od 3 teleportovanja do napadnute stanice X ona će sigurno pasti u ruke vanzemaljaca. Zato je rešio da nađe sve vojne stanice sa kojih može da stigne da odbrani sve ostale stanice i tamo rasporedi vojsku. Kako je ostalo malo vremena - zamolio je vas mlade programere da mu pomognete.

Ulaz:

(Ulazni podaci se nalaze u datoteci teleport.in) U prvoj liniji ulazne datoteke se nalaze dva broja n i m (1 ≤ n, m ≤ 5x105) koji redom predstavljaju broj vojnih i broj civilnih stanica. Zatim sledi n linija koje opisuju veze između stanica: u i-toj (i = 1, 3, ...,n) liniji se nalaze dva cela broja a[i] i b[i] (0 ≤ a[i]b[i]m) koji predstavljaju krajnje civilne stanice u koje se može teleportovati iz i-te vojne stanice (iz vojne stanice moguće je teleportovanje u civilne stanice a[i], a[i] + 1, ..., b[i]). Ukoliko je je a[i] = b[i] = 0 tada se iz date vojne stanice direktno ne može stići ni u jednu civilnu

Izlaz:

(Izlazne podatke upisati u datoteku teleport.out) U prvom redu izlazne datoteke se nalazi broj vojnih stanica koje traži general Đurić, a u drugom lista tih vojnih stanica razdvojenih jednim razmakom.

Primer 1:

teleport.in      teleport.out
3 4
1 3
2 3
4 4
        
2
1 3

Objašnjenje.

Vojna stanica 2 ne zadovoljava Đurićevu procenu, jer najkraći putevi do civilne stanice 1 i vojne stanice 1 zahtevaju više od 3 teleportovanja.

Primer 2:

teleport.in      teleport.out
4 4
1 4
1 3
0 0
2 4
        
1 1
fajl: teleport.cpp
#include <stdio.h>
#include <stdlib.h>
#define MAXN 500001

int n, m;
int a [MAXN], b [MAXN], p [MAXN];
int count;
int sol [MAXN];

void input ()
{
  FILE *in;
  in = fopen ("teleport.in", "r");
  fscanf (in, "%d %d", &n, &m);
  for (int i = 0; i < n; i++)
    fscanf (in, "%d %d", &a [i], &b [i]);
  fclose (in);
}

int compare (const void *x, const void *y)
{
  int i = *(int*) x;
  int j = *(int*) y;
  if ((a [i] < a [j]) || ((a [i] == a [j]) && (b [i] > b [j])))
    return -1;
  if ((a [i] > a [j]) || ((a [i] == a [j]) && (b [i] < b [j])))
    return 1;
  return 0;
}

bool covered ()
{
  int right = 0;
  for (int i = 0; i < n; i++)
  {
    if (a [p [i]] > right + 1)
      return false;
    if (right < b [p [i]])
      right = b [p [i]];
  }
  return true;
}

void find_nonested ()
{
  int i = 0;
  while ((i < n) && (a [p [i]] == 0) && (b [p [i]] == 0))
    i++;
  int max = 0;
  while (i < n)
  {
    if (b [p [i]] > max)
    {
      if ((i < n) && !((a [p [i]] == a [p [i + 1]]) && (b [p [i]] == b [p [i + 1]])))
      {
        sol [count] = p [i];
        count++;
      }
      max = b [p [i]];
    }
    i++;
  }
}

void solve ()
{
  for (int i = 0; i < n; i++)
    p [i] = i;
  qsort (p, n, sizeof (int), compare);
  count = 0;
  if (covered () == true)
    find_nonested ();
}

void output ()
{
  FILE *out;
  out = fopen ("teleport.out", "w");
  fprintf (out, "%d\n", count);
  for (int i = 0; i < count; i++)
    fprintf (out, "%d ", sol [i] + 1);
  fclose (out);
}

int main ()
{
  input ();
  solve ();
  output ();
}