1093 Palalila2

[•wefgef]

Aici puteti discuta despre problema Palalila2.

[•APOCALYPTO]

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.

[•Vman]

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, ...)

[•APOCALYPTO]

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.

[•spatarel]

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.

[•nutzu2010]

imi puteti spune si mie  ce trebuie sa pun aici pentru a nu mai primi warning-ul asta?

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

[•pauldb]

Cred ca e din cauza ca fisierul sursa se termina pe randul cu "}" si nu pe un rand nou.

[•nutzu2010]

da,asta  era,mersi

[•nutzu2010]

imi puteti spune ce trebuie sa folosesc  pentru a putea avea siruri cu  lungimea de 500000 de caractere?

[•dornescuvlad]

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.

[•nutzu2010]

folosesc c,nu c++

[•nutzu2010]

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

[•SpiderMan]

E foarte eficienta si usor de implementat .

[•nutzu2010]

la ce metoda te referi?

[•SpiderMan]

A lui Spatarel .

[•nutzu2010]

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) ?

[•PlayLikeNeverB4]

Da, desi nu cred ca trebuie oprit pasul cand v[i]=v[i+1]

[•SpiderMan]

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 .

[•nutzu2010]

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?

[•PlayLikeNeverB4]

Pana cand ajungi la sfarsitul sirului, evident.

[•SpiderMan]

Adica faci un while cu conditia i + 1 < N, i = 0, si in acest for bagi acele 2 while-uri.

[•nutzu2010]

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?

[•SpiderMan]

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 ) .

[•nutzu2010]

da,se pare ca merge,inca nu am inteles algoritimul dar credeti ca o sa mearga si pentru un sir de 640 kB?

[•nutzu2010]

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