|
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: Igrica
|
U gradiću u kom žive Kići i Ćiki postoji jedna
nagradna igrica. U igrici ima m učesnika. Svaki učesnik
izabere neko od prvih n slova engleske abecede. Onda se od tih
slova napravi jedna reč - slovo koje je izabrao prvi učesnik je
prvo slovo te reči, itd. Na kraju se prebroji koliko puta se
svako od slova pojavljuje u toj reči. Svi oni koji su izabrali
slovo koje se pojavljuje neparan broj puta dobijaju brodić.
Učesnici naravno ne znaju koja će slova ostali birati, ali
pošto su Kići i Ćiki jako simpatični oni su uspeli da od
svakog učesnika saznaju po nekoliko slova koja on sigurno
neće izabrati.
I sada oni imaju zadatak za vas: za svako od prvih n slova oni
će vam reći da li žele da se ono pojavi paran broj puta,
neparan broj puta ili im je svejedno. Vi treba da im kažete
koliko od reči koje se mogu dobiti u ovoj igrici zadovoljavaju te
njihove uslove (pretpostavljamo da niko nije slagao Kićija i
Ćikija). Pošto broj reči može biti velik, dovoljno je da im
kažete ostatak pri deljenju tog broja sa 10.007.
Ulaz:
(Ulazni podaci se nalaze u datoteci igrica.in) U prvom redu ulazne datoteke nalaze se dva broja,
n i m (broj slova iz alfabeta koja mogu biti korišćena i broj učesnika u igri). Sledi m redova sa
po n brojeva u svakom od njih - u i-tom od tih redova j-ti broj je 0 ako i-ti učesnik sigurno
neće izabrati j-to slovo, odnosno 1 ako možda hoće. U
poslednjem redu datoteke nalazi se još n brojeva - j-ti od
njih je 0 ako Kići i ćiki žele da se j-to slovo pojavi
paran broj puta, 1 ako žele da se pojavi neparan broj puta,
odnosno -1 ako im je svejedno.
Izlaz:
(Izlazne podatke upisati u datoteku igrica.out) U izlaznoj datoteci treba da se nalazi jedan
broj - broj reči koje zadovoljavaju Kićijeve i ćikijeve
uslove po modulu 10.007.
Ograničenja:
Neka je ki broj jedinica u redu datoteke koji odgovara
i-tom učesniku.
- u 20% test primera: n ≤ 10, m ≤ 6, 1 ≤ ki ≤ n
- u 20% test primera: n ≤ 15, m ≤ 12, 1 ≤ ki ≤ 3
- u ostalim primerima: n ≤ 15, m ≤ 50, 1 ≤ ki ≤ n
Primer 1:
igrica.in
|
|
igrica.out
|
5 4
1 0 0 0 1
1 1 1 0 0
1 0 1 0 0
0 0 1 0 0
1 -1 0 -1 -1
|
|
3
|
Objašnjenje.
Prvi učesnik će izabrati neko od slova {A,E}, drugi {A,B,C}, treći {A,C}
i četvrti {C}. Traži nam se broj reči u kojima se A pojavljuje neparan a C paran broj
puta. Moguće su sledeće reči:
AAAC, AACC, ABAC, ABCC, ACAC, ACCC, EAAC, EACC, EBAC, EBCC, ECAC, ECCC.
Među njima reči koje zadovoljavaju uslov su ABCC, EACC, ECAC - ima ih 3.
|
|
fajl: igrica.cpp
|
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
const int mod = 10007;
const int maxN = 15;
const int maxM = 50;
const int maxDvaNaN = 40000;
int n, m, dvaNaN;
int k[maxM];
int moguceSlovo[maxM][maxN];
int potrebno[maxN];
int koliko[2][maxDvaNaN];
int main() {
freopen("igrica.in", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
k[i] = 0;
for (int j = 0; j < n; j++) {
int pom;
scanf("%d", &pom);
if (pom == 1) {
moguceSlovo[i][k[i]] = j;
k[i]++;
}
}
}
for (int i = 0; i < n; i++)
scanf("%d", &(potrebno[i]));
dvaNaN = 1 << n;
memset(koliko, 0, sizeof(koliko));
koliko[0][0] = 1;
int trenutni = 0, prethodni = 1;
for (int i = 0; i < m; i++) {
trenutni = 1 - trenutni;
prethodni = 1 - prethodni;
for (int j = 0; j< dvaNaN; j++)
koliko[trenutni][j] = 0;
for (int j = 0; j < k[i]; j++)
for (int staraMaska = 0; staraMaska < dvaNaN; staraMaska++) {
int novaMaska = 1 << moguceSlovo[i][j];
if ((novaMaska & staraMaska) == 0)
novaMaska = staraMaska | novaMaska;
else novaMaska = staraMaska & (~novaMaska);
koliko[trenutni][novaMaska] += koliko[prethodni][staraMaska];
if (koliko[trenutni][novaMaska] >= mod)
koliko[trenutni][novaMaska] -= mod;
}
}
int res = 0;
for (int tek = 0; tek < dvaNaN; tek++) {
bool zadovoljava = true;
for (int i = 0; i < n; i++) {
if ((potrebno[i] == 0) && ((tek & (1 << i)) != 0))
zadovoljava = false;
if ((potrebno[i] == 1) && ((tek & (1 << i)) == 0))
zadovoljava = false;
}
if (zadovoljava) {
res += koliko[trenutni][tek];
if (res >= mod) res -= mod;
}
}
freopen("igrica.out", "w", stdout);
printf("%d\n", res);
return 0;
}
|
|
|