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