865 Text2

[•DITzoneC]

Aici puteţi discuta despre problema Text2.

[•chera_lary]

Cum au fost deduse recurentele la aceasta problema? 

[•xtreme]

              |
sir:  a b c d e g h  i  j  k
poz:1 2 3 4 5 6 7 8 9 10
Daca ai un sir de caractere 'sir' si tu stii ca sufixul din sir care incepe pe pozitia a 4-a(de exemplu) se poate imparti in k-1 cuvinte in x modalitati si tu akuma ai vrea sa mai adaugi un cuvant(din restu caracterelor ramase dupa ce am ales sufixul) pentru a obtine un sufix care se poate imparti in k cuvinte.Este destul de clar ca vom avea x modalitati de a imparti in k cuvinte si acest nou sufix.Se verifica daca se pot lua si alte cuvinte si se actualizeaza suma.
Rog sa ma corecteze cineva daca gresesc.     

[•AndreiD]

Evaluatorul de la aceasta problema nu este bun. Pentru primele doua cerinte corecte iau 100 puncte.

[•andrei-alpha]

Evaluatorul de la aceasta problema nu este bun. Pentru primele doua cerinte corecte iau 100 puncte.

Era o gresala in eval. Acum n-ar mai trebui sa iei 100 fara cerinta 3. 

[•chera_lary]

Multumesc!

[•misino]

Imi poate spune si mie cineva ce am gresit la aflarea numarului de posibilitati?

Cod:

for(i=0;i<l;++i)
    {
        if(l-i<=20&&urmv[i]!=-1)
        a[0][i]=1;
        else
        a[0][i]=-1;
    }
    cl=0;
    for(i=2;i<=n;++i)
    {
        cl^=1;
        for(j=l-1;j>=0;--j)
        {
            a[cl][j]=-1;
            s1=ok=0;
            for(k=1;k<=20&&j+k-1<l;++k)
            {
                if(urmv[j]==-1||j+k-1<urmv[j])
                continue;
                if(a[cl^1][k+j]!=-1)
                {
                    ok=1;
                    s1=(s1+a[cl^1][j+k])%MOD;
                }
            }
            if(ok)
            a[cl][j]=s1;
        }
    }
    g<<a[0][cl]<<'\n';