infoarena

Aici puteţi discuta despre problema Dinozaur (http://infoarena.ro/problema/dinozaur).

Formulare ambiguu

Ce este ambiguu in legatura cu formularea?

Mie mi se pare foarte clar enuntul...

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

Daca nu va rog sa-mi explicati  :)

Poate avea si lungime 1.

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

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

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.

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  :peacefingers:

#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;
}             :fighting:

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

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

Si ce e in neregula cu al primul for?

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

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

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

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

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.

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

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