Eu am cumparat-o acum 2 luni de aici: http://www.byblos.ro/?pg=book&isbn=9739753477 . Costa 89 Ron cu tot cu taxele postale. Daca vrei sa intrebi daca o mai au disponibila o poti intreba pe Ionescu Klara la email-ul [email protected]

Salut. Eu am folosit manualul lui Tudor Sorin.
http://www.ls-infomat.ro/manuale--de-informatica/m11in2006/
Mi-a fost de ajutor si culegerea: Programarea in limbajul C/C++ pentru liceu. Volumul al III-lea, Emanuela Cerchez, Marinel Serban
http://www.comandacarti.ro/carte/programarea-in-limbajul-cc-pentru-liceu-volumul-al-iii-lea--i18302

Stie cineva daca se organizeaza ONI By Net anul asta?

Multumesc.

Asa scrie in regulament:

Complementar etapei naționale a Olimpiadei de Informatică, se va organiza olimpiada online (InfONline), la care pot participa elevii care nu s-au calificat la etapa naţională a Olimpiadei de Informatică. Olimpiada online (InfONline) va utiliza subiectele şi testele de evaluare de la etapa națională a Olimpiadei de Informatică, după o metodologie specifică, care va fi publicată pe site-ul central al olimpiadei.

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.

Am citit de curiozitate problemele de la celelalte clase si nu se compara ca si grad de dificultate cu cele de a XI-a si a XII-a. Sunt de acord ca ei sunt mai mici dar totusi e cam mare diferenta. La a 9-a, la prima problema, la prima cerinta, faci doar o suma a elementelor din vector si ai 20p asigurat.
Acest lucru este confirmat si aici: http://olimpiada.info/oji2012/index.php?cid=statistici . Media primilor 50 din clasamentul national la clasa a 9-a este de 137p, in timp ce la clasa a XI-XII-a este de aproximativ 70p. Deci nu mi se pare ok sa fie asa mare diferenta. E dubla diferenta dintre a 9-a si a XII-a.

Poti sa desenezi ? nu se cerea numarul de drumuri minime ? eu ma gandeam ca te poti duce doar in dreapta sau in sus ca altfel te departezi.

In cazul de mai sus am mers ori in sus ori in dreapta. Vezi ca punctul P(i,j) are coordonatele pe Ox i si pe Oy j. Deci punctul P[i,j] este pe linia j coloana i.

A doua problema cred ca se rezolva asa:
Vad cate piste de biciclete am pe orizontala si cate pe verticala intre punctele A si B cu tot cu lungimile lor (pentru exemplul dat 2+2+3=7), iar apoi iau o submatrice care contine doar pietonalele dintre punctul A si punctul B Pentru exemplu dat o matrice de forma C[2][4] (4 linii si 2 coloane) si calculez distanta minima de la punctul A la B in aceasta matrice, distanta ce o calculez cu teorema lui Pitagora(in acest caz distanta este 4.4721359). Acum adun lungimea minima de pe piste cu lungimea minima de pe pietonale si obtinem rezultatul dorit: 7+4.4721359=11.4721359).

Ideea am avut-o mai tarziu si nu am mai avut timp sa implementez. Am luat doar cazurile speciale cand cei 2 se afla pe aceeasi linie si respectiv pe aceeasi coloana.

Asa am facut si eu. La cerinta a 2-a m-am gandit ca rasp e 1 sau 2. Raspunsul e 1 atunci cand un interval se termina la destinatie. Cum se demonstreaza corectitudinea ?

Pot fi mai multe raspunsuri, nu doar 1 si 2. De exemplu in matrice daca pleca de la A(2,2) putea avea urmatoarele trasee de lungime minima:
(2,2)->(2,4)->(4,4)->(5,7)->(8,7)
(2,2)->(4,2)->(4,4)->(5,7)->(8,7)
(2,2)->(3,2)->(3,3)->(4,3)->(4,4)->(5,7)->(8,7)
si lista poate continua.

A doua problema cred ca se rezolva asa:
Vad cate piste de biciclete am pe orizontala si cate pe verticala intre punctele A si B cu tot cu lungimile lor (pentru exemplul dat 2+2+3=7), iar apoi iau o submatrice care contine doar pietonalele dintre punctul A si punctul B Pentru exemplu dat o matrice de forma C[2][4] (4 linii si 2 coloane) si calculez distanta minima de la punctul A la B in aceasta matrice, distanta ce o calculez cu teorema lui Pitagora(in acest caz distanta este 4.4721359). Acum adun lungimea minima de pe piste cu lungimea minima de pe pietonale si obtinem rezultatul dorit: 7+4.4721359=11.4721359).

Ideea am avut-o mai tarziu si nu am mai avut timp sa implementez. Am luat doar cazurile speciale cand cei 2 se afla pe aceeasi linie sau coloana, sau cazul in care intre ei nu se afla nicio pista.

Cum a fost la olimpiada? Cum vi s-au parut subiectele?
La clasele XI-XII, la problema "blis", partea a 2-a, cum ati impartit subsecventele?

Imi poate explica cineva cum elimin subarborii care nu contin nici un nod special? Stiu ca se face cu o parcurgere, dar tot nu ii dau de capat.
Dau karma la cine ma ajuta!

Astazi am revenit asupra acestei probleme si am incercat sa folosesc clasa set. Dar nu inteleg de ce nu da rezultatul corect.

Cod:

#include<cstdio>
#include<set>
using namespace std;
int n,m,k,lmax;
int a[310][310];
void citire()
{
	freopen("submatrix.in","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	int i,j;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			scanf("%d",&a[i][j]);
}
void calculez()
{
	set<int>det;
	int i,j,l,q,r,dif=0,x;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
		  {
		      l=0;
		      do
		      {
		          for(q=i;q<=i+l&&q<=n;++q)
		             x=a[j+l][q], det.insert(x);
		          for(r=j;r<=j+l&&r<=m;++r)
                             x=a[i+l][r],det.insert(x);
                          dif=det.size();
                          if(dif<=k && l>lmax)
                               lmax=l;
                          ++l;
		      }
		      while((l<n&&l<m) &&(dif<=k));
		      det.clear();
		  }
    freopen("submatrix.out","w",stdout);
    printf("%d\n",lmax+1);
}
int main()
{
	citire();
	calculez();
	return 0;
}

E bun rationamentul?

Multumesc mult de raspuns. Eu de vreo 3 saptamani am invatat sa folosesc STL-ul cum trebuie, dar nu eram sigur daca merge si la olimpiada. Dar de-acum stiu.
Succes tuturor la OJI!!!

Aici http://infoarena.ro/forum/index.php?topic=7289.msg53430#msg53430 a intrebat cineva daca avem voie sa folosim STL-ul si nu i s-a dat un raspuns concret. Avem voie sa-l folosim? De exemplu sortarea din STL, sau implementarea heapurilor (make_heap, etc) le putem folosi?

Foarte buna ideea. Astfel, daca am rezolvat o problema, pot vedea si alte idei de rezolvare a problemei plus multe alte lucruri.

Multumesc foarte mult. Asta era problema. Nu am fost atent si am luat 0 puncte in loc de 100. Altadata voi fi mai atent.

Poate ma lamureste si pe mine cineva cu ce gresesc in algoritmul urmator. Merge pe 6 teste din cele 10. Ideea algoritmului este de a afla toate subsecventele crescatoare din sir. Daca gasesc o subsecventa crescatoare in sir, atunci cumpar cat pot de multe actiuni la inceputul subsirului crescator, si le vand pe toate (actiunile) la sfarsitul subsirului.

Cod:

#include <cstdio>
#include <vector>
using namespace std;
int main()
{
    int i, x, n;
    long long s,s_init,s_rest=0;

    freopen( "bursa.in", "r", stdin );
    freopen( "bursa.out", "w", stdout );

    scanf("%d", &n );
    scanf("%lld",&s);
    s_init=s;
    vector<int>v;
    vector<int>::iterator it;
    for( i = 0; i < n; i++ )
        scanf("%d", &x), v.push_back( x );
    i=0;
    while(i<n)  
    {
        int p=i;                                //retin indicele subsecventei
            while( (i<n-1) && (v[i]<=v[i+1]))   //cat timp subsecventa este crescatoare inaintez in vector
            {
                i=i+1;
            }

        if(p!=i)                          //daca exista subsecventa crescatoare atunci cumpar cat pot de multe actiuni la inceputul subsecventei
          {                               // si le vand pe toate la sfarsitul subsecventei crescatoare
              int nr_act,val_act;
              s=s+s_rest;                  //suma totala
              nr_act=s/v[p];            //nr actiunilor cumparate
              s_rest=s-nr_act*v[p];  //determin restul din suma ramas dupa cumpararea actiunilor
              val_act=nr_act*v[i];   //determin valoarea actiunilor la sfarsitul subsecventei crescatoare adica dupa i-p zile
              s=val_act + s_rest;   //suma care o am la sfarsitul subsecventei crescatoare dupa vinderea actiunilor este val_act + restul ramas
              s_rest=0;               //restul l-am pus in suma mai inainte deci devine 0
          }
        i=i+1;                         //inaintez in vector
    }
    printf("%d\n", s-s_init);    //afisez profitul, adica suma modificata - suma initiala
    return 0;

}

Acesta este cel mai tare concurs de informatica la care am participat vreodata! E primul concurs la care vad ca este imposibil de luat punctaj maxim! Imi place foarte mult acest sistem de notare si penalizare, dar mai ales faptul ca poti vedea pe cateva teste rezultatele si astfel ai ocazia sa corectezi ce ai gresit (chiar daca iti scade din punctaj, dar e mai bine decat 0 puncte in caz ca ai fi lasat greseala).
Felicitari echipei organizatoare!

Buna. Am rezolvat aceasta problema insa pe evaluator obtin doar 52 de puncte. La primele 2 teste obtin punctaj maxim, dar la urmatoarele 8 teste obtin 4 puncte/test. M-am uitat peste solutia oficiala si daca iau de acolo functia drum si o introduc in algoritmul meu obtin 100 puncte. Deci problema este la functia drum. Stiu ca se putea rezolva mai simplu fara cele 2 for-uri, dar eu cred ca ar trebui sa mearga si asa. Nu inteleg ce am gresit. Ma poate ajuta cineva?

Cod:

void drum(int niv, int l, int c)
{
    int t_g, gasit=0,i,j, NR;
    NR=(niv*(niv-1)*(2*niv-1))/6 + (l-1)*niv + c;
    printf("%d ", NR);
    t_g=t[niv][l][c]-a[niv][l][c];
    for(i=1;i<=niv+1 && !gasit; i++)
      for(j=1;j<=niv+1 && !gasit; j++)
        if(t_g==t[niv+1][i][j])
          {
              gasit=1;
              if(niv+1<k)
                drum(niv+1,i,j);
              else
                {
                    NR=(niv+1)*niv*(2*niv+1)/6 + (i-1)*(niv+1) + j;
                    printf("%d\n", NR);
                }
          }
}

Va rog frumos, ma poate ajuta cineva?

Multumesc de raspuns. Voi incerca sa rezolv asa, dar nu acum.

Eu de ce iau doar 70 de puncte pe urm sursa?

Cod:

#include<cstdio>
using namespace std;
int lb[175][175],n;
void drum(int k, int l, int c)
{
 if(l+1<n)
if(lb[l+1][c]>k+1)
  { lb[l+1][c]=k+1;
    drum(k+1,l+1,c); }
if(l>0)
if(lb[l-1][c]>k+1)
  { lb[l-1][c]=k+1;
    drum(k+1,l-1,c); }
if(c+1<n)
if(lb[l][c+1]>k+1)
  { lb[l][c+1]=k+1;
    drum(k+1,l,c+1); }
if(c>0)
if(lb[l][c-1]>k+1)
  { lb[l][c-1]=k+1;
    drum(k+1,l,c-1); }
}
int main()
{ freopen("alee.in","r", stdin);
  freopen("alee.out","w",stdout);
    int aux,m,i,j,x,y,x2,y2;
    scanf("%d %d",&n,&m);
   aux=n*n;
for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    lb[i][j]=aux;
for(i=1;i<=m;i++)
  { scanf("%d %d",&x,&y);
    lb[x-1][y-1]=-1;}
    scanf("%d %d %d %d",&x,&y,&x2,&y2);
lb[x-1][y-1]=1;
drum(1,x-1,y-1);
printf("%d\n", lb[x2-1][y2-1]);
return 0;
}

Dacă ai citi cu atenție enunțul, ai putea observa următoarea restricție:

Numerele din fişierul de intrare se vor incadra pe 32 de biţi cu semn.

      Am citit enuntul cu atentie, dar nu stiam ce inseamna ca datele se vor incadra pe 32 de biti cu semn. Intre timp m-am documentat. Cred ca din cauza asta luam 0 puncte(pe testele oficiale valorile matricei nu erau mai mari de 100, in schimb aici datele sunt de tip int, adica pana la 2147483647).
      Oricum, multumesc tuturor pentru raspunsuri. M-am luminat putin.

Ok...dar totusi cum sa ies din memoria alocata, care este de 16 MB, daca am declarat 2 matrici [301][301] si 2 vectori de 9000 componente? astea nu ocupa mai mult de 1,5 MB.... apropo pe testele oficiale valorile matricei erau mici, aici sunt mai mari de 9000?

Pe testele oficiale programul meu ia 30 de puncte. De ce aici iau 0 puncte?

Mersi. Eu nu vazusem mesajul de mai sus, ca mai era dat odata. Iti multumesc inca odata.

da-mi un link , te rog frumos, caci nu gasesc deocamdata.