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.

besenje.cpp    1,440 b      izvorni kod rešenja
besenje.tests.7z    2,884,609 b      test primeri

zadatak: Bešenje

Mirko i Slavko igraju igru bešenja. Igra započinje tako što Mirko zamišlja reč iz datog rečnika i zapisuje po jednu crticu za svako slovo zamišljene reči. Tada Slavko počinje sa pogađanjem: Slavko nabraja slova za koja misli da se mogu naći u zamišljenoj reči. Ukoliko Slavko pogodi, svaku crticu koja je pre zamenjivala to slovo Mirko zamenjuje sa njim. Ukoliko se Slavkovo slovo ne nalazi u reči, Mirko dobija jedan poen.

Primer toka igre.
Događaj Stanje na papiru
Mirko je zamislio reč BAKICA. - - - - - -
Slavko pita za pojavljivanje slova A - A - - - A
Slavko pita za pojavljivanje slova E - A - - - A
Slavko pita za pojavljivanje slova B B A - - - A

Međutim, Mirko i Slavko su morali da prekinu igru u nekom trenutku. Kako Mirko nije želeo da otkrije svoju reč, Slavko je rešio da sam izračuna koliko reči iz rečnika mogu biti tražene reči. Pomozite Slavku i napišite program koji će rešiti Slavkove muke.

Ulaz:

(Ulazni podaci se nalaze u datoteci besenje.in.) U prvom redu ulazne datoteke nalaze se dva prirodna broja n i m (1 ≤ n ≤ 100.000, 0 ≤ m ≤ 25) koji predstavljaju broj reči u rečniku i broj slova za koje je Slavko pitao, redom. U drugom redu ulaza nalazi se niz od m velikih slova engleskog alfabeta, razdvojenih po jednim znakom razmaka, koji predstavljaju slova za čije pojavljivanje je Slavko pitao. Sledeći red sadrži reč sastavljenu od velikih slova engleskog alfabeta i znaka "-", koja predstavlja stanje na papiru na kraju igre. Narednih n linija sadrže po jednu reč iz rečnika. Reči su sastavljena od velikih slova engleskog alfabeta dužina ne većih od 30.

Izlaz:

(Izlazne podatke upisati u datoteku besenje.out) U prvom i jedinom redu ispisati broj reči koji zadovo avaju dato stanje i niz pogađanja.

Primer:

besenje.in      besenje.out
3 3
A C D
--CA
KUCA
ZGRADA
MACA
        
1

Objašnjenje.

Jedina reč koja zadovoljava stanje je reč "KUCA".

fajl: besenje.cpp
/*
  Author: Andreja Ilic, PMF Nis
  e-mail: andrejko.ilic@gmail.com
  Complexity: O(n * 30)
*/
#include<stdio.h>
#include<string.h>
#define MAX_LEN 35

int n, m, sol;
char state [MAX_LEN], word [MAX_LEN], pom;
bool guess [26];

  int main()
  {
    FILE *in = fopen ("besenje.in", "r");
    FILE *out = fopen ("besenje.out", "w");

    sol = 0;
    for (int i = 0; i < 26; i++)
      guess [i] = false;

    // Unos stanja i upitanih slova
    fscanf (in, "%d %d\n", &n, &m);
    for (int i = 0; i < m; i++)
    {
      fscanf (in, "%c", &pom);
      guess [pom - 'A'] = true;
      fscanf (in, "%c", &pom);
    }

    fscanf (in, "%s", &state);
    int stateLen = strlen(state);

    // Istipivanje svake reci pojedinacno
    for (int i = 0; i < n; i++)
    {
      fscanf (in, "%s", &word);
      int wordLen = strlen(word);
      
      // Jednakost duzina
      if (stateLen != wordLen)
        continue;

      // Pokapanje sa stanjem i upitanim slovima
      bool ok = true;
      for (int i = 0; i < stateLen; i++)
      {
        // Poklapanje sa slovima iz stanja
        if ((state [i] != '-') && (state [i] != word [i]))
        {
          ok = false;
          break;
        }

        // Ukoliko je nepoznato slovo u stanju, nije smelo biti upitano
        if ((state [i] == '-') && (guess [word [i] - 'A']))
        {
          ok = false;
          break;
        }
      }

      if (ok)
        sol++;
    }

    fprintf (out, "%d\n", sol);

    fclose(out);
    fclose(in);

    return 0;
  }