BitCell

Your IT power source
http://www.bitcell.info/

[5] Concurs - Punct inalt

http://www.bitcell.info/concurs-punct-inalt-t161.html

Page 1 of 1

[5] Concurs - Punct inalt

PostPosted: 03 Mar 2010, 17:56
by Mihai
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 :).

Re: [5] Concurs - Punct inalt

PostPosted: 08 Mar 2010, 11:53
by Dexter
Participarea mea, in atasament.

Re: [5] Concurs - Punct inalt

PostPosted: 14 Mar 2010, 00:10
by Mihai
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
  1. #include <stdio.h>
  2.  
  3. FILE*f;
  4. size_t file_size;
  5.  
  6. char text[50000];
  7.  
  8. //rezolvarea propriu-zisa a problemei
  9. int munte(FILE*f,const char*text)
  10. {
  11.     /*
  12.         FILE*f = fisierul in care se afiseaza raspunsul
  13.         text = textul sursa, nevalidat, nu se tine cont aici de lungimea sa
  14.     */
  15.     int lit1[27]={0},lit2[27]={0};
  16.     unsigned long combinari=0;// numarul maxim de combinari este 25,000*24,999 = 624,975,000
  17.    
  18.     const char*p;
  19.     unsigned int i,c;
  20.    
  21.     /*
  22.         Rezolvarea consta in doi pasi. In primul pas se parcurge sirul si se noteaza
  23.     numarul de aparitii al fiecarei litere. In al doilea pas se parcurge inca odata
  24.     sirul, prin acelasi procedeu, dar la fiecare litera in parte se afla:
  25.         1)cate litere exista inaintea sa, in sir, care au codul ASCII mai mic.
  26.         2)cate litere vor mai exista, care au codul ASCII mai mic (avand rezultatul primei parcurgeri).
  27.    
  28.         Implementarea foloseste 2 vectori a cate 26 de elemente de tip int, initializati la zero.
  29.     lit1[i] = cate litere mai mici decat i EXISTA
  30.     lit2[i] = cate litere mai mici decat i AM GASIT pana la in momentul de fata
  31.     lit1[i]-lit2[i] = cate litere mai mici decat i exista DUPA POZITIA CURENTA
  32.    
  33.     REZULTAT:
  34.         (lit1[i]-lit2[i])*lit1[i] = cate combinatii se pot forma (conform enuntului), care au
  35.     litera curenta in centru. (b=pozitia curenta, S[a]<S[b],S[b]>S[c])
  36.     */
  37.    
  38.     //PRIMA PARCURGERE
  39.    
  40.     p=text; //parcurgem cu un pointer
  41.     while(*p) //cat timp, nu am ajuns la sfarsitul sirului
  42.     {
  43.         c=(*p++)^96; //aflam pozitia caracterului in alfabet si trecem pointerul pe pozitia urmatoare
  44.         /*
  45.             La nivel de bit, in ASCII, literele mari se reprezinta astfel:
  46.                 010x xxxx      
  47.             iar literele mici se reprezinta astfel:
  48.                 011x xxxx
  49.             Cei mai nesemnificativi 5 biti ("xxxxx"), separat, desemneaza numarul literei din alfabetul
  50.         englez. Desi pot lua valori de la 0 la 31, numai pozitiile 1..26 reprezinta litere.
  51.  
  52.             Numarul 96, se descompune in binar ca 01100000. Efectuand operatia XOR intre numarul 96 si
  53.         codul ASCII al unui caracter dat, vom obtine un numar intre 1 si 26 inclusiv, daca acel caracter
  54.         este litera a alfabetului englez. In caz contrar, vom obtine alte valori.
  55.         */
  56.        
  57.         if(c&&c<27) //daca c este litera a alfaberului
  58.             for(i=c+1;i<=26;i++)lit1[i]++; //completeaza vectorul 1 conform explicatiilor de mai sus
  59.         else
  60.         {
  61.             printf("Invalid character 0x%d%d at position %d in file. Only a-z letters are allowed!",((*p)/16),((*p)%16),p-text);
  62.             return 1;
  63.         }
  64.     }
  65.    
  66.     //A DOUA PARCURGERE
  67.    
  68.     p=text; //parcurgem cu un pointer
  69.     while(*p) //cat timp nu suntem la sfarsitul textului
  70.     {
  71.         c=(*p++)^96; //afla numarul literei din alfabet (textul este validat dupa prima parcurgere)
  72.         for(i=c+1;i<=26;i++)lit2[i]++;//completeaza vectorul 2 conform explicatiilor de mai sus
  73.         combinari+=(lit1[c]-lit2[c])*lit2[c];//prin inmultire, calculeaza cate combinatii se pot obtine
  74.                 //cu litera curenta, in centru
  75.     }
  76.    
  77.     //am terminat; variabila 'combinari' contine numarul de perechi care satisfac conditia din enunt
  78.     fprintf(f,"%lu",combinari);
  79.     return 0;
  80. }
  81.  
  82. #include <time.h>
  83. clock_t start,stop;
  84.  
  85. int main(){
  86.     if((f=fopen("bitcell5.in","r")))
  87.     {
  88.         fseek(f, 0, SEEK_END);
  89.         file_size = ftell(f);
  90.         fseek(f, 0, SEEK_SET);
  91.         if(file_size<=50000)
  92.         {
  93.             fscanf(f,"%s",text);
  94.             fclose(f);
  95.             if((f=fopen("bitcell5.out","w")))
  96.             {
  97.                 start=clock();
  98.                 if(munte(f,text))return 1; //error?
  99.                 stop=clock();
  100.                 fclose(f);
  101.                 printf("\n\nExecution time: %.4f",((float)stop-start)/CLK_TCK);
  102.                 getchar();
  103.                 return 0;
  104.             }
  105.             else printf("Cannot create output file \"bitcell5.out\".");
  106.         }
  107.         else printf("Input file \"bitcell5.in\" too big (over 50000 characters).");
  108.     }
  109.     else printf("Input file \"bitcell5.in\" not found.");
  110.     getchar();
  111.     return 1;
  112. }
  113.  
All times are UTC + 2 hours [ DST ]
Page 1 of 1
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/