infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Grigorean din Decembrie 13, 2010, 00:38:22



Titlul: 1093 Palalila2
Scris de: Andrei Grigorean din Decembrie 13, 2010, 00:38:22
Aici puteti discuta despre problema Palalila2 (http://infoarena.ro/problema/palalila2).


Titlul: Răspuns: 1093 Palalila2
Scris de: Dragos din Decembrie 13, 2010, 15:02:56
Am o intrebare.
Nu cumva primul element trebuia sa fie mereu mai mic decat al doilea?
Eu am facut in ambele variante si cred ca din acest motiv iau 50.


Titlul: Răspuns: 1093 Palalila2
Scris de: Duta Vlad din Decembrie 13, 2010, 15:06:15
primul element al subsirului trebuie sa fie mai mic lexicografic decat al 2-lea (scrie in enunt: s1<s2, s2>s3, s3<s4, s4>s5, ...)


Titlul: Răspuns: 1093 Palalila2
Scris de: Dragos din Decembrie 13, 2010, 15:07:23
primul element al subsirului trebuie sa fie mai mic lexicografic decat al 2-lea (scrie in enunt: s1<s2, s2>s3, s3<s4, s4>s5, ...)
Da. Asta era. :aha:


Titlul: Răspuns: 1093 Palalila2
Scris de: Dan-Constantin Spatarel din Decembrie 15, 2010, 22:50:30
Am participat la concurs on-site si, apoi, am ascultat solutiile oficiale. Propun o solutie alternativa, cu care am obtinut punctaj maxim:

1. Se parcurge sirul pana cand V[ i ] >= V[ i + 1 ] sau se termina.
2. Se parcurge sirul pana cand V[ i ] <= V[ i + 1 ] sau se termina.
3. Se revine la 1.

Solutia se incrementeaza la pasii 1 si 2.
Cand se termina sirul, se afiseaza solutia.

Astept pareri despre corectitudine, timpul de executie si dificultatea de implementare. :)


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Februarie 14, 2011, 13:13:02
imi puteti spune si mie  ce trebuie sa pun aici pentru a nu mai primi warning-ul asta?
Citat
Compilare:
user.c:43:2: warning: no newline at end of file
si asta e codul sursa:
Cod:
#include <stdio.h>
#include <string.h>
#include <ctype.h>


int main()
{
FILE *poz,*afisare;
char S[100];
int i=1,j=2,nr=1,max=0;
poz=fopen("palalila2.in","r");
if (poz==NULL)
printf("eroare");
else
{
fgets(S,sizeof(S),poz);
while (S[i]!='\0')
{
if ((S[i-1]<S[i]) && (S[i]>S[j]))
{
nr+=2;
i+=2;
j+=2;
}
else
{
++j;
}
if (j==strlen(S))
{
if (nr>max)
max=nr;
++i;
j=i+1;
}

}
}
afisare=fopen("palalila2.out","w");
fprintf(afisare,"%d",max);
fputs("\n\n",afisare);
return 0;
}




Titlul: Răspuns: 1093 Palalila2
Scris de: Paul-Dan Baltescu din Februarie 14, 2011, 13:21:59
Cred ca e din cauza ca fisierul sursa se termina pe randul cu "}" si nu pe un rand nou.


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Februarie 14, 2011, 13:30:02
da,asta  era,mersi


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Februarie 14, 2011, 15:21:18
imi puteti spune ce trebuie sa folosesc  pentru a putea avea siruri cu  lungimea de 500000 de caractere?


Titlul: Răspuns: 1093 Palalila2
Scris de: Vlad Eugen Dornescu din Februarie 14, 2011, 15:48:29
Daca folosesti biblioteca <fstream> (declari ifstream fin("palalila2.in"); ofstream fout("palalila2.out"); citeste cu fin.getline(Sir, lungimea maxima a sirului). getline(char*, val) e functia din <string.h> care permite citirea asta.
Poti citi si cu gets(S) un sir si folosesti biblioteca <cstdio> cu functia gets(Sir).
Mai poti incerca sa citesti caracter cu caracter intr-o variabila, si sa le bagi in vectorul de siruri pe rand.


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Februarie 14, 2011, 15:56:09
folosesc c,nu c++


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Februarie 15, 2011, 13:56:07
imi puteti da un sfat prin care sa reduc timpul programului meu?
peste 2 kb dureaza foarte mult si acolo timp de executie pe test  e de doar 0.5 sec

sau daca pot sa vad un cod sursa care a luat maxim la ac problema


@Spatarel Dan Constantin o sa incerc si ideea ta


Titlul: Răspuns: 1093 Palalila2
Scris de: Simoiu Robert din Februarie 15, 2011, 17:07:52
E foarte eficienta si usor de implementat ;).


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Februarie 15, 2011, 17:39:15
la ce metoda te referi?


Titlul: Răspuns: 1093 Palalila2
Scris de: Simoiu Robert din Februarie 15, 2011, 17:54:04
A lui Spatarel .


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Februarie 22, 2011, 10:01:25


1. Se parcurge sirul pana cand V[ i ] >= V[ i + 1 ] sau se termina.
2. Se parcurge sirul pana cand V[ i ] <= V[ i + 1 ] sau se termina.
3. Se revine la 1.

Solutia se incrementeaza la pasii 1 si 2.
Cand se termina sirul, se afiseaza solutia.



n-am inteles solutia lui Spatarel
parcurgem sirul intr-un while mare care contine alte 2 while-uri (adica cele de la punctul 1 si 2,cu conditiile impuse) ?


Titlul: Răspuns: 1093 Palalila2
Scris de: George Marcus din Februarie 22, 2011, 13:41:39
Da, desi nu cred ca trebuie oprit pasul cand v[i]=v[i+1]


Titlul: Răspuns: 1093 Palalila2
Scris de: Simoiu Robert din Februarie 22, 2011, 15:04:54
1. Se parcurge sirul atata timp cat V[ i ] >= V[i + 1] && i + 1 < N
2. Se parcurge sirul atata timp cat V[ i ] <= V[i + 1] && i + 1 < N
3. Se reia pasul 1

Solutia se incrementeaza la sfarsitul pasului 1 si la inceputul pasului 2, dar la inceputul pasului 2 se incrementeaza doar daca i + 1 < N .


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Februarie 27, 2011, 14:44:43
1. Se parcurge sirul atata timp cat V[ i ] >= V[i + 1] && i + 1 < N
2. Se parcurge sirul atata timp cat V[ i ] <= V[i + 1] && i + 1 < N
3. Se reia pasul 1

Solutia se incrementeaza la sfarsitul pasului 1 si la inceputul pasului 2, dar la inceputul pasului 2 se incrementeaza doar daca i + 1 < N .

se reia pasul 1 pana cand?


Titlul: Răspuns: 1093 Palalila2
Scris de: George Marcus din Februarie 27, 2011, 15:15:05
Pana cand ajungi la sfarsitul sirului, evident.


Titlul: Răspuns: 1093 Palalila2
Scris de: Simoiu Robert din Februarie 27, 2011, 15:48:08
Adica faci un while cu conditia i + 1 < N, i = 0, si in acest for bagi acele 2 while-uri.


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Februarie 27, 2011, 20:08:12
n-am inteles ,am pus un cod dar imi da 36 si ar trebui sa-mi dea 7

Cod:
#include <stdio.h>

int main()
{
        char t[13]="nostressATfmi";
        int i=0,j=0,N=13,sol=0;
        while (i+1<N)
        {

            while ((t[j] >= t[j+1]) && (j + 1 < N))
            {
                ++j;
                ++sol;

            }
            j=0;
            while ((t[j] <= t[j + 1]) && (j + 1 < N))
            {
                ++j;
                ++sol;
            }
            j=0;
            ++i;
        }
        printf("%d",sol);
        getch();
        return 0;
}



si pe langa asta mai trebuie ca acest cod sa se termine in maxim 0,5 sec cu sirul de 640 kb...cum fac asta?


Titlul: Răspuns: 1093 Palalila2
Scris de: Simoiu Robert din Februarie 27, 2011, 20:22:52
Nu trebuie sa incrementezi solutia IN WHILE, ci trebuie sa incrementezi dupa fiecare while, mai precis dupa primul si imediat inaintea celui de-al doilea, cu precizarea ca i + 1 < N. Si nu trebuie folosit niciun j, folosesti acel i, adica in loc de j pui peste tot i, si nu modifici pe i ( cum ai acolo j = 0 ) .


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Februarie 28, 2011, 16:44:26
da,se pare ca merge,inca nu am inteles algoritimul dar credeti ca o sa mearga si pentru un sir de 640 kB?


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Martie 08, 2011, 19:52:58
pana la urma am facut o varianta a mea care merge pentru exemplul dat la problema:nostressATfmi ,dar cand o postez pe infoarena imi afiseaza incorect la toate testele...imi puteti spune ce gresala am facut in cod sau macar un sir mai mare pe care pot sa testez raspunsul.

Cod:
#include <stdio.h>
#include <string.h>


int main()
{
    int j=2,i=1,nr=1;
    char s[500000];
    FILE *poz,*pozout;
    poz=fopen("palalila2.in","r");
    fgets(s,sizeof(s),poz);
    while (s[i]!='\0')
    {
        if (s[i-1]>s[j])
        {
            if (s[i]>s[j])
            {
                i=j+1;
                j=i+1;
                nr+=2;
            }
            else
            {
                ++j;
                if (j==strlen(s))
                {
                    ++i;
                    j=i+1;
                }
            }
        }
        else
        {
            ++i;
            j=i+1;
        }
    }
    fclose(poz);
    pozout=fopen("palalila2.out","w");
    fprintf (pozout,"%d",nr);
    fclose(pozout);
    return 0;
}




Titlul: Răspuns: 1093 Palalila2
Scris de: Simoiu Robert din Martie 08, 2011, 20:29:48
Nu ai facut acolo nimic din ce ti-am zis, nu vad cele 2 while-uri in while-ul principal.


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Martie 09, 2011, 18:33:08
ba am facut si cum mi-ai zis tu si a mers problema (nu am mai postat-o pe forum)...si mi-am continuat si ideea mea imbunatatita ,cred eu...dar nu vad unde e gresala in cod ,ca iau 0 puncte


Titlul: Răspuns: 1093 Palalila2
Scris de: Simoiu Robert din Martie 09, 2011, 19:09:45
Dar am vazut codul tau si nu vad cele 3 while-uri in total. Daca vrei da-mi un P.M. si iti dau sursa.


Titlul: Răspuns: 1093 Palalila2
Scris de: nutzu2009 din Martie 09, 2011, 19:46:53
Dar am vazut codul tau si nu vad cele 3 while-uri in total. Daca vrei da-mi un P.M. si iti dau sursa.

codul sursa cu cele trei while-uri?nu il vreau pentru ca l-am facut sa mearga pana la urma doar ca nu am postat problema pe forum
si am incercat si solutia mea cea veche(pentru exemplul:"nostressATfmi" da 7,deci e bine) dar iau 0 puncte.