BitCell

by **Mihai** » 03 Mar 2010, 17:56

Fie S un sir de caractere (maxim 50.000) litere mici ale alfabetului englez. In acest sir, spunem ca o pereche (S[a],S[b],S[c]) reprezinta un munte daca:

0<=a<b<c<lungimea textului
S[a]<S[b] si S[c]<S[b]

Fiind dat un sir de caractere, aflati cati munti contine!

Exemplu

bitcell5.in:
etaje

bitcell5.out
5

Explicatie:
Cei 5 munti sunt: eta, etj, ete, eje, aje.

Observatii:

Fisierele de intrare/iesire vor fi bitcell5.in/bitcell5.out.
O litera va fi considerata mai mare decat o alta daca se afla in alfabet dupa aceasta.
Data limita de inscriere in concurs este 13 martie 2010.

P.S.: Problema aceasta (sub un alt enunt) a fost propusa la Info-Oltenia 2010, proba pe echipe, clasele 9-10

.

by **Dexter** » 08 Mar 2010, 11:53

Participarea mea, in atasament.

by **Mihai** » 14 Mar 2010, 00:10

O sa fiu plecat o vreme, si cum azi era data limita si nu cred ca se mai inscrie nimeni pana la 12, il declar pe Dexter castigatorul concursului.
Sursa sa:

Line number On/Off | Expand/Contract | Select all

#include <stdio.h>
 
FILE*f;
size_t file_size;
 
char text[50000];
 
//rezolvarea propriu-zisa a problemei
int munte(FILE*f,const char*text)
{
    /*
        FILE*f = fisierul in care se afiseaza raspunsul
        text = textul sursa, nevalidat, nu se tine cont aici de lungimea sa
    */
    int lit1[27]={0},lit2[27]={0};
    unsigned long combinari=0;// numarul maxim de combinari este 25,000*24,999 = 624,975,000
    
    const char*p;
    unsigned int i,c;
    
    /*
        Rezolvarea consta in doi pasi. In primul pas se parcurge sirul si se noteaza
    numarul de aparitii al fiecarei litere. In al doilea pas se parcurge inca odata
    sirul, prin acelasi procedeu, dar la fiecare litera in parte se afla:
        1)cate litere exista inaintea sa, in sir, care au codul ASCII mai mic.
        2)cate litere vor mai exista, care au codul ASCII mai mic (avand rezultatul primei parcurgeri).
    
        Implementarea foloseste 2 vectori a cate 26 de elemente de tip int, initializati la zero.
    lit1[i] = cate litere mai mici decat i EXISTA
    lit2[i] = cate litere mai mici decat i AM GASIT pana la in momentul de fata
    lit1[i]-lit2[i] = cate litere mai mici decat i exista DUPA POZITIA CURENTA
    
    REZULTAT:
        (lit1[i]-lit2[i])*lit1[i] = cate combinatii se pot forma (conform enuntului), care au
    litera curenta in centru. (b=pozitia curenta, S[a]<S[b],S[b]>S[c])
    */
    
    //PRIMA PARCURGERE
    
    p=text; //parcurgem cu un pointer
    while(*p) //cat timp, nu am ajuns la sfarsitul sirului
    {
        c=(*p++)^96; //aflam pozitia caracterului in alfabet si trecem pointerul pe pozitia urmatoare
        /* 
            La nivel de bit, in ASCII, literele mari se reprezinta astfel:
                010x xxxx       
            iar literele mici se reprezinta astfel:
                011x xxxx
            Cei mai nesemnificativi 5 biti ("xxxxx"), separat, desemneaza numarul literei din alfabetul
        englez. Desi pot lua valori de la 0 la 31, numai pozitiile 1..26 reprezinta litere.
 
            Numarul 96, se descompune in binar ca 01100000. Efectuand operatia XOR intre numarul 96 si
        codul ASCII al unui caracter dat, vom obtine un numar intre 1 si 26 inclusiv, daca acel caracter
        este litera a alfabetului englez. In caz contrar, vom obtine alte valori.
        */
        
        if(c&&c<27) //daca c este litera a alfaberului
            for(i=c+1;i<=26;i++)lit1[i]++; //completeaza vectorul 1 conform explicatiilor de mai sus
        else
        {
            printf("Invalid character 0x%d%d at position %d in file. Only a-z letters are allowed!",((*p)/16),((*p)%16),p-text);
            return 1;
        }
    }
    
    //A DOUA PARCURGERE
    
    p=text; //parcurgem cu un pointer
    while(*p) //cat timp nu suntem la sfarsitul textului
    {
        c=(*p++)^96; //afla numarul literei din alfabet (textul este validat dupa prima parcurgere)
        for(i=c+1;i<=26;i++)lit2[i]++;//completeaza vectorul 2 conform explicatiilor de mai sus
        combinari+=(lit1[c]-lit2[c])*lit2[c];//prin inmultire, calculeaza cate combinatii se pot obtine
                //cu litera curenta, in centru
    }
    
    //am terminat; variabila 'combinari' contine numarul de perechi care satisfac conditia din enunt
    fprintf(f,"%lu",combinari);
    return 0;
}
 
#include <time.h>
clock_t start,stop;
 
int main(){
    if((f=fopen("bitcell5.in","r")))
    {
        fseek(f, 0, SEEK_END); 
        file_size = ftell(f); 
        fseek(f, 0, SEEK_SET); 
        if(file_size<=50000)
        {
            fscanf(f,"%s",text);
            fclose(f);
            if((f=fopen("bitcell5.out","w")))
            {
                start=clock();
                if(munte(f,text))return 1; //error?
                stop=clock();
                fclose(f);
                printf("\n\nExecution time: %.4f",((float)stop-start)/CLK_TCK);
                getchar();
                return 0;
            }
            else printf("Cannot create output file \"bitcell5.out\".");
        }
        else printf("Input file \"bitcell5.in\" too big (over 50000 characters).");
    }
    else printf("Input file \"bitcell5.in\" not found.");
    getchar();
    return 1;
}
 

BitCell

[5] Concurs - Punct inalt

[5] Concurs - Punct inalt

Re: [5] Concurs - Punct inalt

Re: [5] Concurs - Punct inalt

Who is online