020 Dinozaur

[•dushmi]

Aici puteţi discuta despre problema Dinozaur.

[•catalinutzb]

Formulare ambiguu

[•repp4radu]

Ce este ambiguu in legatura cu formularea?

Mie mi se pare foarte clar enuntul...

[•atatomir]

Subsecventa poate avea lungime 1? adica daca gasesc de 2 ori "x" se considera 2 subsecvente identice ?

Daca nu va rog sa-mi explicati 

[•PlayLikeNeverB4]

Poate avea si lungime 1.

[•catalinutzb]

Tocmai despre asta vorbeam, formulare ambiguu, nu se precizeaza lungimea minima a unei secvente, in acest caz in care o secventa poate fii de lungime 1 problema are o rezolvare penibila, pur si simplu verifici cu un vector unde memorezi de cate ori apare fiecare litera in functie de codul sau ASCII si astfel daca in vector gasesti vreun numar >=2 atunci scrii 1 altfel scrii 0... Si totul dintr-o singura parcurgere => O(n) => undeva la 0.07 secunde

[•klamathix]

Pai da, asta inseamna, ca e usoara. Nu ca e ambiguu enuntul. Voiai sa mentionam si ce restrictii nu se aplica ? )

[•popa_marcel]

In general in Arhiva Monthly sunt probleme mai usoare.Consider ca dificultatea problemelor se vede in timp de concurs unde conteaza si timpul in care se rezolva problema.

[•catalinutzb]

Am luat 0 puncte pe sursa asta dar nu inteleg ce nu e bine... Poate secventa nu poate fi si de 1 caracter... Va pun sursa, cine poate si vrea sa ma ajute 

#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream f("dinozaur.in");
ofstream g("dinozaur.out");

int main(){

    char T[100001];
    long C[30];
    long i,lung;
    bool ok=0;

    f>>T;
    lung=strlen(T);
    for (i=1;i<=30;i++)
        C=0;
    for (i=0;i<=strlen(T);i++){
        C[T-96]++;
        if (C[T-96]>=2){
            ok=1;
            break;
        }
    }

    if (ok)
        g<<1<<"\n";
    else
        g<<0<<"\n";

    return 0;
}             

[•cristiavra]

de la i=0; i< strlen(T) incearca asa in cel de-al doilea for si vezi ca in primul for nu asa se face initializarea unui vector

[•catalinutzb]

Da, multumesc mult, acum iau undeva la 80 de puncte, nu da pe 2 teste... trebuie sa ma mai uit la cazuri particulare

[•catalinutzb]

Si ce e in neregula cu al primul for?

[•cristiavra]

pai C este un vector => are indici => C [ i ] = 0; sau ai putea folosi memset din STL

[•catalinutzb]

Stiu ca orice vector are C[1], C[2].... = 0 dar asta e teoretic, in practica am intampinat UNEORI (nu totimpul) vectori care nu au val 0, mai ales la vectori de lungime mare, stiu ca aici nu e cazul dar acea initializare chiar nu are probleme

[•cristiavra]

am observat ulterior daca te vei uita peste codul tau postat apare: C=0 si trebuia C [ i ] =0 . dar acolo e bine... cazuri speciale nu cred ca sunt

[•catalinutzb]

Da intr-adevar, nu stiu cum a aparut C=0 ala acolo....

Am luat 100 de puncte... Postez aici sursa, daca mai vrea sa o vada cineva:

#include <fstream>
#include <cstring>
using namespace std;
ifstream f("dinozaur.in");
ofstream g("dinozaur.out");

int main(){

    char T[100001];
    long C[30];
    long i,lung;
    bool ok=0;

    f>>T;
    lung=strlen(T);
    if (lung>0){
        for (i=1;i<=30;i++)
            C=0;
        for (i=0;i<lung;i++){
            C[T-96]++;
            if (C[T-96]>=2){
                ok=1;
                break;
            }
        }

        if (ok)
            g<<1<<"\n";
        else
            g<<0<<"\n";
    }
    else
        g<<0<<"\n";

    return 0;
}

[•cristiavra]

nu cred ca e tocmai ok sa postez sursa...pana la urma asta este esenta INFOARENA - sa incercam sa rezolvam cat mai multe probleme nu sa luam sursa gata facute.Oricum daca este vreo probleme se va sesiza vrun admin.

[•catalinutzb]

Acolo la C=0 e o greseala, sursa mea nu era de la inceput asa... Dar site-ul infoarena nu ma lasa sa postez, am incercat sa editez si acolo cand editez imi apare bine C=0, dar cand postez e C=0

[•cristiavra]

incearca sa lasi spatiii intre si scrie asa C [ i ] = 0 ;

[•klamathix]

[ i ] e codul pentru italic pe forum, de asta nu-ti merge.