Eu am facut problema cu sort din STL si pentru aflarea pozitiei am folosit lower_bound. De ce imi da TLE pe 5 teste? http://infoarena.ro/job_detail/728522

L.E: Am luat 100pct.

Cine imi poate da un link direct catre ONI by net?

Mersi.

NU ai folosit long long pentru rezultat, vectorul a si N le lasi int, si schimbi doar REZULTATUL, adica x-ul ala din print (asa era parca), il faci long long, si afisezi cu "%lld".

Ms. Acum am luat 100 pct.

foloseste long long

Am folosit long long.

Eu ce gresesc in rezolvarea mea? Am facut un ssm. http://infoarena.ro/job_detail/718368

Um...nu prea avem cum sa stim ce ai tu prin cod, vad ca ai si TLE. Incearca sa faci problema pe hartie cu niste exemple, si o sa observi ceva (se poate afla pozitia de inceput in O(N) pur, daca exista vreo posibilitate de a parcurge traseul).

Am facut asta de 100 de ori pe hartie. Am vreo 80 de surse trimise numai la prob asta si tot 60pct iau. La una din ele aveam 4 incorecte si toate intrau in timp.

Eu ce gresesc in rezolvarea mea? Am facut un ssm. http://infoarena.ro/job_detail/718368

Am declarat vectorul prea mare si am primit MLE. Am pierdut 100 pct pt asta la OJI 2012.

Se poate gasi un program mai detaliat, care este perioada de desfasurare? Nu am gasit pe site.

In ce zile se vor tine probele?

Gasesti regulamentul pe www.olimpiada.info

ce fac gresit, sau ce declar in plus de tot imi da MLE?, cum ar trebui facut astfel incat sa nu imi mai dea MLE pe ult. 4 teste pt ca algoritmul meu e bun.

Alex, tu citesti intr-un vector de siruri fiecare rand, dupa care il parcurgi secvential; nu e nevoie de asta, citeste fiecare rand si apoi proceseaza-l... deci ideea e sa nu citesti tot fisierul la inceput 

Bun, deci tu zici ca pot sa fac programul in timp O(1) - constant ?

ce fac gresit, sau ce declar in plus de tot imi da MLE?, cum ar trebui facut astfel incat sa nu imi mai dea MLE pe ult. 4 teste pt ca algoritmul meu e bun.

[1 2 0]

Nu cumva pentru N=3 raspunsul e 6?

congfiguratii:

0 0 3
0 1 2
1 0 2
1 2 0 <- aici oare?
1 1 1
0 2 1

[nu]

Scuze dacă m-am făcut înțeles greșit, nu mă comparam pe mine cu tine sau cu altcineva, tot ce vroiam să zic e că oricum nu făceam de 200, chiar dacă mai strângeam ceva să mă calific și eu.

În ce ai citat tu, eu am zis că dacă nu scoteam luam (probabil) 100, am scris în paginile anterioare care a fost motivul pentru care am scos acea parte. Probabil a fost vina mea, probabil nu, cine știe.

Am stiut de la inceput ca nu la mine te-ai referit ci in general, dar eu vreau sa spun urmatoarea chestie: sunt clasa a-10-a si eu si prietenul meu cel mai bun am facut amandoi cate o problema(eu pe a 2-a, el pe prima). Mie mi-a dat raspunsul corect pentru orice test posibil pt. ca am facut-o si pe numere mari si cu recurenta exact ca in sursa oficiala, iar el a facut programul tot ca in sursa oficiala respectiv problemei lui, dar lui nu-i dadea raspunsul corect ( ii dadea un numar negativ foarte mare sau ceva de genu). Concluzie: el avea un bug in problema ( main() sau alta functie ) iar eu nu aveam nici un bug, ci doar am declarat vectorul prea mare. ( a[500000] in loc de a[10000] sau chiar a[5000] ).

Aici am vrut eu sa ajung. ( referitor la mesajul anterior ).

[daca]

Nu mai fiți revoltați ca v-ați/nu v-ați calificat la ONI, eu nu m-am calificat și nu regret asta, știu că m-aș fi putut califica dacă nu aș fi șters o chestie din program (cel puțin presupun), dar știu că nu aș fi luat 200 de puncte, ceea ce înseamnă că mai am de lucru. Până la urmă la olimpiadă nu trebuie să fii bun, ci să fii mai bun ca alții, cum scria într-o carte căreia i-am uitat numele.

Stai o secunda, aici e o mica diferenta intre tine si mine. Tu zici ca daca stergeai o chestie din program luai 100pct. Dar inainte sa termin ce am de zis vreau sa-mi raspunzi la o intrebare : "Iti rula programul si cu bug-ul ala?", sau doar iti dadea alte numere, sau mesaj de eroare in fereastra compilatorului?

AS putea baga eu pb. de la OJI anul asta ?

Daca poti e perfect! Mersi!

Si eu am pierdut 100 p anul trecut pt ca am scris int in loc de short intr-un loc . Doar asa o sa inveti. Data urmatoare:

Da, dar tu te-ia calificat la ONI , eu nu. La judetul meu s-au califcat 2 cu 25 pct fiecare. Daca stiam asta si mai stiam ca la prima prob. trebuia doar sa numar niste blestemate de stelute si la cealalta sa fac un simplu back pe care probabil luam vreo 20 pct. acum aveam 40 si eram calofocat de pe primul loc la ONI.

Cine poate si cand pune problemele de la OJI in arhiva, si poate si cele de la gimnaziu.....?

App, nu vi se pare ciudat ce s-a intamplat anu asta la OJI? Toata lumea sa aiba punctaje mici la clasele 10-12, iar la clasa a-10-a sa nu dea Lee (Alee, Insule, Rj, etc.), problemele din anii anteriori.

L.E.  Cui i s-a mai intamplat sa piarda 100 puncte sau o calificare din cauza ca declarat un vector prea mare ( culori - a[500000] (eu) si in sursa oficiala a[10000]- pt 100 pct.)?

Cine are problema facuta de 100 pct cu implementarea STL-urilor: lower_bound si Upper_bound? Am facut-o dar imi da 0 pct si as vrea si eu sa vad ce gresesc. Eu incerc sa accesez problema de la indicatii, dar imi da mesaj de eroare.

MinGW am folosit. Eu am avut singurul monitor din ala mare din toata sala, palpaia imaginea, tastatura tot trecea in romana. Pe langa astea, au facut olimpiada in 3 scoli ca nu aveau destule calculatoare.

Dar atunci cum ai aflat timpul de executie? Pe minGW 2.05 dupa ce se termina rularea programului iti scrie 2 randuri , iar pe unu din ele "return 0"(sau o val pe care o scrii tu dupa return). In schimb pe codeblocks, pe pagina compilatorului iti afiseaza si timpul de executie cu  mii-mi in coada.

La culori eu am facut un back care mergea in 0.198 sec pt n=28, mai mult nu mai mergea si am luat doar 10 pct.

Tu ai folosit codeblocks?

Eu am avut un rapan de calculator si la tastatura numerica semnul " / " era defapt semnul " * ", si invers.

["N<=45"]

In legatura cu punctajele, nu stiu ce sa zic. Nu sunt in masura sa comentez limitele de memorie ale problemelor. Poate ca exact asta s-a dorit a fi cea mai mare dificultate a primei probleme (daca nu ma insel, culori era prima) : gasirea unei solutii "cat mai optime" din pdv al memoriei.

De obicei, un program optim e unul cu timp de rulare cat mai mic. De aceea au pus timp : 0.2 sec. La "Culori"(care era defapt a 2-a) au pus si o conditie suplimenatara la Restrictii "N<=45" ca sa vezi ca nu e ca raspuns "un numar format pe 15 cifre" (maxim pe categoria intregi). Daca e numar mai mare de 15 cifre inseamna ca e pe numere mari exact cum cerea si problema.

Plus de asta daca nu ma crezi poti face un back-tracking de proba (exact cum am facut eu acolo) sa vezi ca dupa N>20 problema iese din timp, iar pt N=19 solutia era formata din 6 cifre, deci pt N=5000 solutia avea ceva "cifre".


In legatura cu memoria nu au fost nici ei prea corecti. La prima prob. au dat 4MB cu 3MB pt stiva. Daca ce zici tu e adevarat inseamna ca acum eram calificat la ONI.

Pai diferenta este ca tu ai declarat asa

Cod:

int a[500000]

Chestia asta inseamna aproximativ 2 MB de memorie, iar tu aveai disponibil doar 1MB. La OJI / ONI trb sa ai foarte mare grija la memoria declarata, deoarece nu este ca pe infoarena (aici ti se pune doar memoria folosita). Si, din pacate, in cazuri ca acesta nu se poate face nimic (Am avut si eu aceeasi problema la ONI anu' trecut si am pierdut vreo 70 de puncte ).

OK. Dar cum calculez cata memorie folosesc?

Si in plus de asta ai vazut ce punctaje sau luat, nu trebuia sa avem memorie ceva mai mare, ca la 11-12 ?

[MAREA DIFERENTA?]

Au afisat solutiile.

Intre asta:

Cod:

#include <fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int a[500000], n, putere;

void prod()
{
    a[0]=1;
    a[1]=3;

    int t=0, x=0, i;

    while(putere)
    {
        for(i=1; i<=a[0]; ++i)
        {
            x=a[i]*3+t;
            a[i]=x%10;
            t=x/10;
        }
        while(t)
        {
            a[++a[0]]=t%10;
            t/=10;
        }
        putere--;
    }
}

void par1()
{
    int x=0, t=0, i;

    for(i=1; i<=a[0]; ++i)
    {
        x=a[i]*8+t;
        a[i]=x%10;
        t=x/10;
    }
    while(t)
    {
        a[++a[0]]=t%10;
        t/=10;
    }
}

void impar1()
{
    int x=0, t=0, i;

    for(i=1; i<=a[0]; ++i)
    {
        x=a[i]*2+t;
        a[i]=x%10;
        t=x/10;
    }
    while(t)
    {
        a[++a[0]]=t%10;
        t/=10;
    }
}

void impar2()
{
    int x=0, t=0, i;

    for(i=1; i<=a[0]; ++i)
    {
        x=a[i]*7+t;
        a[i]=x%10;
        t=x/10;
    }
    while(t)
    {
        a[++a[0]]=t%10;
        t/=10;
    }
}

int main()
{
    f>>n;

    if(n==1)
    {
        g<<5<<"\n";
        return 0;
    }

    if(n==2)
    {
        g<<8<<"\n";
        return 0;
    }

    if(n==3)
    {
        g<<14<<"\n";
        return 0;
    }

    putere=n/2-2;

    prod();

    if(n%2==0)
    {
        par1();
        for(int i=a[0]; i>=1; --i) g<<a[i];
    }

    else
    {
        impar1();
        impar2();
        for(int i=a[0]; i>=1; --i) g<<a[i];
    }
}

si asta :

Cod:

#include<fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int n,i,A[10000];
unsigned long long nr=1;
void mul(int A[], int B)
{
int i, t = 0;
for (i = 1; i <= A[0] || t; i++, t /= 10)
A[i] = (t += A[i] * B) % 10;
A[0] = i - 1;
}
int main()
{f>>n;
 if(n==1)g<<5;
 else if(n==2)g<<8;
  else if(n==3)g<<14;
    else if(n%2==0)
		  {A[1]=8;
		   A[0]=1;
			for(i=1;i<=(n-2)/2;i++)
				mul(A,3);
			for(i=A[0];i>=1;i--)
				g<<A[i];
		   }

       else if(n%2!=0)
		   {A[1]=14;
		   A[0]=1;
			for(i=1;i<=(n-3)/2;i++)
				mul(A,3);
			for(i=A[0];i>=1;i--)
				g<<A[i];
		   }
  f.close();
  g.close();
return 0;
}

care e MAREA DIFERENTA?

Prima e sursa mea din concurs si mi-a dat MLE la toate testele.
Cealalta e solutia oficiala(una dintre multe altele).

la problema "Culorile" se rezolva cu o formula simpla
cam asta ar fi tot programul :

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("culori.in");
ofstream g("culori.out");
int main()
{
   int c=5,i,n;
   f>>n;
   for(i=3;i<n;i++)
      c=c+3;
   g<<c*3;
   return 0;
}
regula este ca pentru 3 scanduri sunt : 3 x 3 = 9 combinatii posibile
                    pentru 4 scanduri sunt : 3 x 5 = 15 combinatii posibile
                    pentru 5 scanduri sunt : 3 x 8 = 24 combinatii posibile si etc...astept sa se posteze testele..
Pentru celelalte solutii se iese din timp foarte usor (0,2 secunde e prea putin pentru back-uri sau recursive complicate cu mii de if-uri...)

pai nu e bine. poti sa faci si pe foaie pentru 1, 2, 3 si 4.

Eu am zis sa o fac prima data prin back, dar pt N=25 stateam mult si asteptam degeaba. Dupa aia am luat toate rezulatele de la 1 la 20 din back si le-am descompus in factori primi.

Cazurile speciale erau:
1. N=1  -> g << 5
2. N=2  -> g << 8
3. N=3  -> g << 14

Restul mai trebuia sa pui o singura conditie:

Daca (N%2==0) g <<  8 * 3^(n/2-1)
Altfel g <<  14* 3^(n/2-1)

Cum trebuia facuta prob. "culori" ca sa nu iasa din memorie la clasa a 10-a???
Eu am gasit solutia, am scris-o pe un vector "int" si mi-a iesit din memorie.

Cine se poate uita peste sursa mea sa imi spuna ce gresesc, sau sa-mi dea testele la care iau WA? Multumesc.

exemplu are numai de 1 pe prima linie si nu ma ajuta. daca era si un numar>1 atunci da, ma ajuta foarte mult. mersi oricum.