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.

igra.cpp    1,164 b      izvorni kod rešenja
igra.tests.7z    99,315 b      test primeri

zadatak: Igra

Mirko i Slavko igraju sledeću igru: Mirko počinje igru zamišljanjem neke reči. Međutim, on ne kaže Slavku koju je reč zamislio, već mu kaže samo prvo slovo te reči. Sada Slavko zamišlja reč koja počinje slovom koje je Mirko rekao i kaže Mirku prva dva slova svoje reči. Mirko sada opet zamišlja reč koja počinje slovima koje je Slavko rekao (nova reč može, ali i ne mora biti reč koju je na početku zamislio) i kaže Slavku prva tri slova. Ova procedura se nastavlja sve dok slova koja kaže Mirko ili Slavko ne formiraju kompletnu reč. Igrač koji prvi formira kompletnu reč je izgubio igru. To znači iako je Mirko, na primer, zamislio reč 'lepota' i kaže Slavku prva četiri slova 'lepo' - on gubi, jer je reč 'lepo' takođe reč srpskog jezika.

Kako bi igra bila ravnopravna, oba igrača mogu iskoristiti samo reči iz unapred definisanog rečnika. Ako oba igrača igraju optimalno, tada je moguće odrediti ko će na kraju igre biti pobednik. Optimalno igranje podrazumeva da svaki od igrača nastoji da dobije igru u što je moguće manje poteza (znajuči da će i njegov protivnik takođe igrati optimalno); ukoliko igrač ne može da dobije igru, onda želi da izgubi što je moguće kasnije.

Krajnji ishod igre je reč iz rečnika koju kaže igrač koji gubi. Ako u nekom momentu nije bitno za dalji razvoj igre koje slovo će igrač odabrati - on bira uvek slovo koje dolazi ranije u engleskoj abecedi (leksikografski najmanje). Odrediti koji igrač pobeđuje u ovoj igri i reč kojom se igra završava.

Ulaz:

(Ulazni podaci se učitavaju iz datoteke igra.in.) U prvom redu se nalazi prirodni broj n (1 ≤n ≤ 5000). U sledećih n redova se nalazi po jedna reč sastavljena od malih slova engleske abecede, dužine manje ili jednake od 50, koja predstavlja reč iz zajedničkog rečnika za oba igrača.

Izlaz:

(Izlazni podaci se ispisuju u datoteku igra.out.) U prvom redu ispisati koji igrač pobeđuje (1 za Mirka i 2 za Slavka), a u drugom redu ispisati reč kojom se igra završava, ako oba igrača igraju optimalno.

Primer 1:

igra.in      igra.out
8
avioni
banana
berza
selo
seobe
kosa
kola
kuca
        
1
kola

Objašnjenje.

Ako Mirko kaže slovo 'b', tada će Slavko pobediti biranjem reči 'berza' tako što kaže slovo 'e'. Slično, ako Mirko kaže slovo 's', sigurno gubi. Najzad, Mirko pobeđuje ako zamisli bilo koju reč na 'a' ili 'k'. Ako bi odabrao reč 'avioni' pobedio bi u šest poteza, dok u ostalim slučajevima pobeđuje u 4 poteza. Zato Mirko bira slovo 'k'. Zatim Slavko bira slovo 'o', pa onda Mirko slovo 'l' (zato sto 'l' dolazi pre 's' po leksikografskom uređenju) i Slavko slavko na kraju bira slovo 'a'. Dakle, pobeđuje Mirko (prvi igrač), a tražena reč na kraju igre je 'kola'.

Primer 2:

igra.in      igra.out
3
zzz
zzza
ttt
        
2
ttt
fajl: igra.cpp
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

#define MAXN 5001
#define INFTY 999999999

vector<string> words;
string final;
int n;

string play (int left, int right, int length) 
{
  if (words [left].length() == length) 
    return words [left];
  string best;
  int best_value = -INFTY;
  int p = left;
  int v;
  while (p < right) 
  {
    int q = p + 1;
    while((q < right) && (words [q][length] == words [p][length])) 
      q++;
    string s = play (p, q, length + 1);
    if ((s.length() - length) & 1) 
      v = -10000 + (s.length() - length);
    else 
      v = 10000 - (s.length() - length);
    if (v > best_value) 
    { 
      best_value = v; 
      best = s; 
    }
    p = q;
  }
  return best;
}

int main ()
{
  ifstream in("igra.in");
  in >> n;
  string s;
  for (int i = 0; i < n; i++)
  {
    in >> s;
    words.push_back (s);
  }
  in.close ();

  sort (words.begin(), words.end());
  final = play (0, words.size(), 0);

  ofstream out("igra.out");
  if ((final.length () & 1) == 0)
    out << 1 << endl;
  else
    out << 2 << endl;
  out << final << endl;
  out.close ();
  return 0;
}