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.

igrica.cpp    2,094 b      izvorni kod rešenja
igrica.tests.rar    5,354 b      test primeri

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 ≤ kin
  • u 20% test primera: n ≤ 15, m ≤ 12, 1 ≤ ki ≤ 3
  • u ostalim primerima: n ≤ 15, m ≤ 50, 1 ≤ kin

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