Zadanie

V noci len tak ležíš a zrazu počuješ, ako ti do uška šušká ploštička. Jej druhá kamoška ti jemne obkuskáva lakeť. Keďže si programátor a fakt nemáš kamarátov, tak si povieš, že ploštice budú tvoje kamošky. Nezostáva ti nič iné ako ich chytiť do pohára. Ráno sa zobudíš a rozpamätáš sa, že ti tá ploštička niečo hovorila. Majú vlastný jazyk! …alebo to bude len náhoda. Zoberieš si plošticu číslo 2 a začneš počúvať jej slová a zapisovať ich. Z noci si však už len matne spomínaš na to, čo ti hovorila ploštica číslo 1, ale zapíšeš aj tieto slová. Ak úplne nevieš, aké písmenko vyslovila, zapíšeš si všetky, ktoré to mohli byť. Teraz ich už len porovnáš a prídeš na to, či sa jazyky zhodujú. Jednoduché, však?

Úloha

Vašou úlohou je zistiť, či obe ploštice používajú rovnaký jazyk – teda pokúsiť sa zistiť, či slovo, ktoré nám povedala ploštica číslo 2 sa môže zhodovať so slovom, ktoré si pamätáme z noci.

Formát vstupu

Na prvom riadku vstupu dostanete jedno číslo predstavujúce dĺžku slov (\(l\)). Na druhom riadku dostanete jedno číslo – počet dvojíc slov (\(w\)). Za nimi bude nasledovať \(w\) dvojíc riadkov. Na prvom z dvojice riadkov bude jedno slovo, zložené len z veľkých písmen anglickej abecedy. Na druhom riadku z dvojice bude slovo, ktoré si pamätáme z noci. Tieto slová vyzerajú takto: ak som si istý, aké písmenko ploštica povedala, je na tom mieste len písmenko napríklad A. Ak si nie som istý a mohli to byť rôzne písmenká (alebo iba jedno písmenko), sú uzavreté v zátvorkách napríklad (BD).

Formát výstupu

Na výstup vypíšte \(w\) riadkov – na riadku \(i\) vypíšte OK ak sa \(i\)-te slovo, môže zhodovať s \(i\)-tym nekompletným slovom – otázkou. Inak vypíšte NOT OK.

Hodnotenie

Sú 4 sady vstupov, v ktorých platia tieto obmedzenia:

Sada \(1\) \(2\) \(3\) \(4\)
\(1 \le l \le\) \(5\) \(15\) \(15\) \(50\)
\(1 \le w \le\) \(25\) \(50\) \(5\,000\) \(10\,000\)
\(1 \le l\cdot w \le\) \(100\) \(1\,000\) \(50\,000\) \(100\,000\)

Príklady

Input:

1
4
C
(AB)
B
(DB)
B
B
B
D

Output:

NOT OK
OK
OK
NOT OK
  1. Slovo C a slovo (AB), ktoré si pamätáme z noci sa nemôžu zhodovať.
  2. Slovo B a slovo (DB), ktoré si pamätáme z noci sa zhodovať môžu.
  3. Slovo B a slovo B, ktoré si pamätáme z noci sa zhodujú.
  4. Slovo B a slovo D, ktoré si pamätáme z noci sa nemôžu zhodovať.

Zo zadania

Ako zadanie hovorí, budeme spracovávať dvojice slov - jedno, ktoré vieme ako vyzerá (nazvime ho \(w\)) a druhé, ktoré si matne pamätáme z noci (nazvime ho \(q\)). Úlohou je zistiť, či sa slová môžu zhodovať.

Riešenie

Pre každé písmeno vo \(w\) sa budeme musieť pozrieť na písmeno alebo množinu písmen z \(q\) a zistiť, či medzi nimi existuje zhoda. Budeme si pamätať, na akej pozícii v slove \(w\) sa nachádzame a budeme prechádzať cez znaky slova \(q\). Ak sa i-ty znak z \(q\) nerovná (, vieme, že na tejto pozícii bude len jedno písmeno. Teda porovnáme písmeno z \(q\) s písmenom z \(w\). Ak sa nerovnajú, vypíšeme NOT OK a posunieme sa na ďalšiu dvojicu slov. Inak pokračujeme ďalším písmenom. Ak sa i-ty znak \(q\) rovná (, budeme prechádzať len cez \(q\), až kým nepriídeme po ) pričom si budeme ukladať do množiny písmená medzi zátvorkami. Po tom, ako sme našli v \(q\) znak ), pozrieme sa, či sa písmeno na pozícii, ktorú porovnáme, nachádza v tejto množine znakov. Ak sa v ňom nenachádza, vypíšeme NOT OK a posunieme sa na ďalšiu dvojicu slov. Takto prejdeme cez všetkých \(l\) znakov \(w\) a ak sme ich prešli všetky a nenašli nezhodu, môžeme vypísať OK.

Optimalnejsie riesenie

Optimálne riešenie je v podstate takmer totožné. V hore opísanom riešení prechádzame niektoré znaky viackrát. Práve vtedy, keď získavame znaky medzi zátvorkami a následne hľadáme, či sa v nich nachádza písmeno z \(w\) na porovnávanej pozícii. Riešenie vieme modifikovať tak, aby sme miesto pridávania do množiny rovno písmeno porovnávali s daným písmenom slova \(w\).

Časová a pamäťová zložitosť

Časová zložitosť bude lineárna, keďže vstupom prechádzame len raz. Pamäťová zložitosť je konštantná – rovná \(l\), keďže si musíme pamätať celé slovo \(w\) a jedno akutálne písmeno zo slova, ktoré si pamätáme z noci.

l = int(input())
d = int(input())

def createAlphabetArr(token: str) -> list:
    out = [False] * 26
    for i in token:
        out[ord(i) - ord('A')] = True
    return out


def correctWord(arr: list) -> int:
    for c in range(len(word)):
        ci = ord(word[c]) - ord('A')
        if not arr[c][ci]:
            return "NOT OK"
    return "OK"


for i in range(d):
    word = input()

    arr = []
    inp = input()
    j = 0
    while j < len(inp):
        c = inp[j]
        token = ""
        if c != '(':
            token = c
        else:
            while c != ")":
                j += 1
                c = inp[j]
                if c == ')': break
                token += c
            c = inp[j]
        arr.append(createAlphabetArr(token))
        j += 1
    print(correctWord(arr))
#include <iostream>
#include <vector>
#include <string>

void numberOfCorrectWords(const std::vector<std::vector<bool>> &arr, const std::string &word) {
    int out = 0;
    for (int i = 0; i < word.length(); ++i) {
        if (!arr[i][word[i] - 'A']) {
            std::cout<<"NOT OK"<<std::endl;
            return;
        }
    }
    std::cout<<"OK"<<std::endl;
    return;
}


int main(int argc, char const *argv[]) {
    int l = 0, w = 0, q = 0;
    std::cin >> l >> w;

    std::string word;
    for (int i = 0; i < w; ++i) {
        std::cin >> word;
        std::string query;
        std::vector<std::vector<bool>> arr(l, std::vector<bool>(26));
        std::cin >> query;
        int tokenInd = 0;
        for (int j = 0; j < query.length(); ++j) {
            char c = query[j];
            std::string token;
            if (c != '(') token += c;
            else {
                while (c != ')') {
                    c = query[++j];
                    if (c != ')') token += c;
                }
            }
            for (char ch: token) {
                arr[tokenInd][ch - 'A'] = true;
            }
            tokenInd++;
        }
        numberOfCorrectWords(arr, word);
    }
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.