OJI 2012

[•setare333]

probabil ca da...

[•Theory]

Pai nu e buna solutia aia. Solutia buna e dinamica. + numere mari (din pacate..).

Mergea si cu o formula doar ca nu cea scris mai sus..pe testele mici iti dadea corect:

int aflu()
{
    int moduri=1;
    for(int k=2;k<=n;k++)
    {
        switch(ultim)
        {
            case 1:{ultim=2;break;}
            case 2:{if(k==n)moduri*=2;else moduri*=3;ultim=2;k++;break;}
            case 3:{moduri*=2;ultim=2;break;}
        }
    }
    return moduri;
}
int main()
{
    in>>n;
    ultim=1;
        total+=2*aflu();
    ultim=2;
        total+=2*aflu();
    ultim=3;
        total+=aflu();
    out<<total;
    return 0;
}

Da intr-adevar subiectele de la a X a nu au fost prea grele ,cel putin problema asta.

[•klamathix]

Din nou. Cat ai luat cu asta?  
L.E: De fapt asta aduce a recurenta de la dinamica. Cred ca e ok. Dar nu e formula.

[•alexalbu95]

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)

[•Oancea.Catalin]

Eu am facuto cu umpic de dinamica...retineai pt fiecare culare nr de garduri care se pot termina in culoare x, unul actual si unul precedent(de fiecare data il actualizai ca sa iti intre in memroie)-pt ca nu aveai nevoie decat de nr de culori de la precedenta vopsire...implementai pe numere mari si cred ca puteai sa iei 100 daca erai atent...eu am lua doar 80:(...oricum citisem undeva ca daca ai sub 50 de puncte nu te califici la clasa 5-12....si astra ar fi greu de crezut..oricum eu sunt din bucuresti si ma cam oftic

Nu trebuie sa ai peste 50 de puncte pt calificare. Sunt judete unde nu s-au depasit 40 de puncte si exista elevi calificati la ONI si cu 18 puncte.  Aici te poti uita. (Un exemplu: Teleorman - merg la ONI toti care nu au luat 0 puncte) ...seems legit

[•pauldb]

Un scop al Olimpiadei este si acela de a populariza informatica in randul elevilor din intreaga tara. Daca ai spirit competitiv, participa la Algoritmiada, .campion, topcoder, codeforces, etc.

[•marcu.iulian13]

Salut! Vreau si eu sa aflu cum e cu contestatiile... Adica se fac maine? Intre ce ore? Eu nu am fost anuntat despre contestatii in sala de concurs si vreau sa ma lamuresc. Multumesc!

[•alexalbu95]

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

[•dushmi]

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

[•flaviusc11]

Nu stiti la facultate este olimpiada si pentru studenti? Sunt in clasa a XII-a si abia am prins gustul olimpiadei. Imi pare rau ca nu m-am apucat sa lucrez intens mai devreme. Imi place foarte mult sa codez.

[•psycho21r]

Cel mai scurt drum dintre două puncte în plan se obţine pe linie dreaptă. Astfel dacă eliminăm porţiunile de traversare a pistelor de biciclete, traseul lui Gigel către prietenul lui trebuie să fie un segment. Această lungime se calculează cu teorema lui Pitagora, la care se adaugă lungimile de traversare orizontală şi verticală.
Soluţia nu este unică de fiecare dată! Dacă traseul lui Gigel intersectează punctul de intâlnire a două piste de biciclete, numărul soluţiilor se dublează, fiindcă Gigel poate traversa zona în două moduri: orizontal-vertical sau vertical-orizontal. În ambele cazuri două laturi alăturate  ale aceluiaşi dreptunghi, deci ambele sunt soluţii corecte. Astfel, numărul soluţiilor distincte pentru orice teste de intrare este o putere a lui 2.

Baftă pe mai departe celor care s-au calificat, ne vedem la anul.

[•alexalbu95]

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 ?

[•dushmi]

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 ?

In general, pentru a vedea cati MB ocupa un vector poti sa folosesti urmatoarea comanda:

Cod:

printf("%lf", 1.0 * sizeof(a) / 1024 / 1024);

unde a este vectorul pentru care vrei sa vezi ce dimensiune ocupa (orientativ) .

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.

[•alexalbu95]

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.

[•visanr]

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.

[•alexalbu95]

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.

[•visanr]

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.

[•alexalbu95]

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.

[•dushmi]

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.

O solutie ar fi asta:

Cod:

#include <ctime>

...

int main() {
    clock_t t1, t2;

    t1 = clock();

    //program

    t2 = clock();

    double diff = 1.0 * t2 - 1.0 * t1;

    printf("%lf", diff / CLOCKS_PER_SEC);

    return 0;
}

[•visanr]

Pai <ctime>, 2 variabile double, start si stop, unde vrei sa inceapa sa contorizeze start=clock(), unde sa se opreasca stop=clock si apoi printf("%lf", (stop-start)/CLOCKS_PER_SEC).



LE:seamana cu ce a scris Mihai mai sus

[•dornescuvlad]

Foarte inspirat autorul de la problema 'parc' (Sa copieze o problema dintr-o carte prafuita de mate si s-o propuna la OJI, in loc sa propuna un graf, un arbore, UN CEVA sa puteti departaja concurentii corect ... Nu-i de mirare ca au fost multe surprize ... neplacute din pacate

[•S7012MY]

Foarte inspirat autorul de la problema 'parc' (Sa copieze o problema dintr-o carte prafuita de mate si s-o propuna la OJI, in loc sa propuna un graf, un arbore, UN CEVA sa puteti departaja concurentii corect ... Nu-i de mirare ca au fost multe surprize ... neplacute din pacate

De unde a copiat-o ?

Departajarea chiar ca a fost proasta.

[•Cosmin]

Dornescule am citit problema parc si pare foarte ok. Ca are o sursa sau alta de inspiratie nu schimba faptul ca e o problema draguta.

Ce legatura are asta cu suprizele tale?

[•klamathix]

Dornescule am citit problema parc si pare foarte ok. Ca are o sursa sau alta de inspiratie nu schimba faptul ca e o problema draguta.

Ce legatura are asta cu suprizele tale?

Problema e ok, si mi s-ar fi parut misto sa apara la un SRM/runda de Codeforces. Dar la judeteana, intr-un asemenea set, mi se pare ca face o departajare proasta. Si asta e destul de evident pentru toata lumea..

[•Cosmin]

Vad scoruri foarte variate la ambele probleme la 11-12. Ai doua probleme pe care poti departaja, ambele cu ceva punctaje intermediare. Problemele nu au fost super dure. Au avut subpuncte pe care puteai lua puncte chiar daca nu le faceai pe amandoua. Nu stiu ce vreti mai mult de atat.

Tot timpu se poate mai bine da hai sa nu avem pretentii sa se lucreze la problemele de OJI cate un an inainte de concurs ca sa fie balansate perfect.