Balaurul Arhirel se decide să înveţe biologie, aşa că doreşte să cumpere manualul de clasa a X-a. Din păcate, acesta nu se mai găsește pe piaţă, dar Balaurul reuşeşte să găsească o copie la un prieten. După ce începe să citească, Balaurul Arhirel observă că există greşeli în copia prietenului, iar într-un impuls de energie, se hotărăşte să corecteze manualul. El are la dispoziţie un dicţionar de M cuvinte dintre care trebuie să extragă variante pentru cuvântul greşit. Asupra cuvântului greşit balaurul poate să facă următoarele schimbări în așa fel încât acesta să ajungă la o variantă din dicționar:
– poate șterge o literă;
– poate insera o literă;
– poate schimba o literă în altă literă.
Totuși, Balaurul Arhirel este leneş, aşa că nu doreşte să opereze mai mult de K schimbări în cuvântul greșit pentru a-l aduce la o formă corectă (existentă în dicționar).

Cerința

Ajutaţi-l pe Balaurul Arhirel să afle care dintre cuvintele din dicţionar ar putea fi variante ale cuvântului greşit.

Date de intrare

Fișierul de intrare cuvinte8.in conţine pe prima linie cele două numere M şi K, separate printr-un spaţiu, reprezentând numărul de cuvinte din dicţionar şi numărul maxim de modificări ce pot fi efectuate asupra cuvântului ce trebuie corectat. Pe a doua linie se găsesc separate printr-un spaţiu lungimea cuvântului greşit, L[cuvânt], şi cuvântul greşit. Pe următoarele M linii se găsesc cuvintele din dicţionar, câte un cuvânt pe o linie în forma următoare: pe linia i lungimea L[i-2] a cuvântului i-2, separată printr-un singur spaţiu de cuvântul i-2.

Date de ieșire

Fișierul de ieșire cuvinte8.out va conţine M linii. Pe linia i se află valoarea 1 pentru cazul în care cuvântul i din dicţionar este o variantă pentru cuvântul greşit dat, respectiv valoarea 0 în caz contrar.

Restricții și precizări

0 < M < 21
0 < K < 31
0 < lungimea oricărui cuvânt (inclusiv cel greșit) < 10001
Cuvintele sunt formate doar din literele alfabetului latin, iar literele mici diferă de cele mari (de exemplu, Z nu este acelaşi lucru cu z).

Exemplu

cuvinte8.in

6 2
6 radiux
5 ladin
6 Radius
6 ridica
5 radio
6 adipos
5 cadiu

cuvinte8.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema cuvinte8:

#include <cstdio>
#include <cstring>

#define NMAX 10000
#define KMAX 30

#define min(a,b) (((a) < (b)) ? a : b)
#define max(a,b) (((a) > (b)) ? a : b)
#define INF 667

using namespace std;

int A[2][NMAX+KMAX];
int M, K, L1, L2;
char s1[NMAX+KMAX+1], s2[NMAX+KMAX+1];

int main()
{
    int t, i, j, v = 0, n = 1, pl;

    freopen("cuvinte8.in","r",stdin);
    scanf("%d %d", &M, &K);
    scanf("%d %s", &L1, s1+1);

    freopen("cuvinte8.out","w",stdout);
    for (t = 0; t < M; t++)
    {
        scanf("%d %s", &L2, s2+1);
        for (i = 0; i <= K; i++)
            A[v][i] = i;
        A[v][K+1] = INF;

        for (i = 1; i <= L2; i++)
        {
            pl = min(i+K+2, L1+1);

            if (i-K-2 >= 0)
                A[n][i-K-2] = INF;
            else
                A[n][0] = i;

            for (j = max(1, i-K-1); j < pl; j++)
                if (s1[j] == s2[i])
                    A[n][j] = A[v][j-1];
                else
                {
                    A[n][j] = min(A[v][j],A[v][j-1]);
                    A[n][j] = min(A[n][j],A[n][j-1]) + 1;
                }
            A[n][pl] = INF;

            v ^= 1;  n ^= 1;
        }

        printf("%d\n",(A[v][L1]<=K));
    }
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2426 cuvinte8

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2426 cuvinte8 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2426 cuvinte8