Sunt de acord cu Daniel, la primele doua probleme merge o rezolvare in O(n) cu hash-uri ...

Toate mi se par foarte interesante.  M-ar mai interesa si algoritmii folositi in industria jocurilor .

si pe mine m-ar interesa 

Imi poate da cineva niste indicatii ? ... eu m-am gandit sa sortez punctele in functie de unghiu care il formeaza cu punctul B si axa Ox iar apoi sa determin unghiul segmentului BG cu Ox astfel incat numarul de puncte de-o parte si de alta sa fie echilibrat si acelasi lucru sa-l fac cu punctul C.

stie careva varianta online pentru probele de pregatire a lotului ?

rezolvarea in O(N^2) consta in a declara un vector s cu semnificatia : s[ i ] = nr de siruri de lungime i cu elemente din multimea {1,..,i} ??

Later edit: Imi poate da careva un indiciu pt rezolvarea in O(n^2) ?

eu am rezolvat problema folosind o matrice opt(i,j) = nr de siruri 2-3 monotone de lungime i cu valori din multimea {1,2,...,j}, complexitate O(n^3). M-am mai gandit si in felul urmator: opt(i,j) = nr de siruri 2-3 monotone de lungime i cu ultimul element j ...
oare asa pot ajunge la O(n^2) ?

Editat de moderator : Nu mai posta de mai multe ori consecutiv. Editeaza-ti posturile anterioare.

la problema aceasta care este complexitatea dorita ?

o intrebare am ... rezolvarea cu PD se bazeaza tot pe faptul ca trebuie gasita partitia cu cmmc maximal nu ?

Problema : sa se afle ordinul maxim al unei permutari din multimea Sn.

M-am gandit ca defapt trebuie sa aflu partitia numarului n astfel incat cmmc al numerelor a1 + a2 + ... ak = n sa fie maximal

Dupa mai multe exemple am observat ca cmmc-ul acestor numere este maximal cand numerele sunt relativ prime ...

am incercat sa fac un backtracking care tine cont de relatia intre numere ...
 
Se poate mai eficient ?   Sa pornesc de la n = 1 si sa construiesc partitia ... ?

poate cineva sa-mi recomande niste carti utile despre teoria grafurilor de preferabil in lb romana

multumesc

[o]

am o intrebare: sa zicem ca am structura urmatoare.
struct nod{char nume[10],materie[10]; float nota,medie; nod* adr;};
si acum vreau sa ordonez o lista dupa medie,atunci ar trebui sa interschimb si celalalte informatii deci ar trebui practic sa interschim nodurile,legaturile ca ar sunt prea multe informatii pentru a le interschimba pe fiecare cu cele ale nodului respectiv.

n-ar fi mai bine sa fac o structura sa zic : struct elev{char nume[10],materie[10]; float nota,medie;};
si apoi : struct nod{ elev info; nod* adr;};  

??si daca tre sa inversez nodurile ma poate ajuta careva nitzel......asa as stii cum sa fac da mi se pare..
ex pt nodurile :     o->o->o->o->o

prb suna cam asa :se dau n numere.Sa se stearga elementele care pot fi scrise ca suma a celorlalte elemente din sir.

m-am tot gandit la ea si inca o fac:P ....m-ar ajuta daca ordonez lista ? (ma rog pe parcurs ce o creez sa o si ordonez)
multumesc anticipat

pt 4 elemente: 1 1 2 2 ===>lista cu elem pare: 1 2 2 si lista cu elem impare 1


.....am gasit greseala.......acuma merge.....multumesc oricum

alea nu-s prb....probabil am copiat si main-u din greseala....functia de generare a unei liste imi merge...da asta parimpar nu...

nu stiu ce gresesc la prb asta....
prb: se da o lista .Sa se creeze 2 liste .Una cu elementele pare si alta cu cele impare a listei initiale.

Cod:

#include<iostream.h>
#include<conio.h>



struct nod{int info;
	   nod* adr;};


void sterge(nod* &first,nod* p){//fctia are ca parametrii first= adresa primului nod dintr-o lista si un pointer p=contine  
                                              adresa nodului precedent celui care va fi sters(am scris first de tip referinta ca poate se modifica
                                              adresa primului nod)
nod* a;

if(p==NULL)
{a=first;
first=first->adr;
delete a;
}
else
{a=p->adr;
p->adr=a->adr;
delete a;}}


nod* parimpar(nod* &first){//aici impart cele 2 liste .Elementele pare le tin in lista asta ,modific firstu daca ii cazu ,iar elem. impare
                                     //le bag intr-o lista noua

nod* p,*firstq,*q;
p=first;
firstq=NULL;
if(p->info%2)               //verific daca nu cumva lista incepe cu val impare(pe care o sa le bag intr-o lista noua si le sterg din lista 
                                //initiala; s-ar putea sa se modifice first-u listei cu elem pare.
while(p->info%2){
q=new nod;
q->info=p->info;
q->adr=firstq;
firstq=q;
sterge(first,NULL);
p=first;}

while(p->adr!=NULL){    //parcurg lista mai departe...daca gasesc elem pare trec mai departe,altfel cred un nou nod in lista cu 
                                //elemente impare si sterg elem impar din lista initiala(care va fi cea cu elem pare)
if(p->adr->info%2==0)
p=p->adr;
else
{
q=new nod;
q->info=p->adr->info;
q->adr=firstq;
firstq=q;
sterge(first,p);}
}

return firstq;}


nod *a,*b;
int n;

void main(){
clrscr();

cin>>n;
a=gen(n);
b=parimpar(a);
cout<<"primu sir  ";
afisare(a);
cout<<endl;
afisare(b);

multumesc mult....pt ambele posturi...m-am lamurit

am o intrebare.....am inceput recent pointerii la sc.....profu ne-a explicat bine......da am cateva intrebari....

daca am char s[5]="info",*p;

*p=s[0]// aici pointerul p retine adresa lui s[0] ? e bine?

ma deruteaza nitzel ca am invatat ca daca pun * inaintea unei variabile care tine adresa unei valori atunci * returneaza valoarea acea.. si daca avem sa zicem p=&x atunci p=adresa valorii ;
 

si este vreo diferenta aici:  int *p;
......
....
...
p++; sau *p++; ??

vreau sa spun ca fac pasii de la lee ..numai ca la pasul cand trebuie sa scot un element din coada....il scot pe cel cu taxa cea mai mica pana atunci ....nu pe ultimu-l explorat

am o intrebare ii bine daca as face asa "bag primu element in coada....apoi parcurg matricea si scot primu element din coada....si ii verific vecinii pe care ii bag in coada(bineinteles directiile in care se poate merge)....si cand revin iarasi la pasu cu scoaterea unui elem din coada....il aleg pe cel care are o taxa mai mica s.a.m.d pana ajung la poz finala".

am gasit si rezolvarea da ii in pascal si n-o inteleg in totalitate.....

da......

am o intrebare la problema asta daca o stie carevea de la oji 2003 acea cu taxe...vroiam sa intreb.....pt rezolvare mi-ar trebui 2 matrici si fac in fel acesta? adica introduc prima poz in coada....apoi parcurg matricea si incep sa verific vecinii care ii bag in coada si il aleg pe acela care ia taxa mai mica...?:-/

nu inteleg cum se poate folosi cautarea binara aici....?

ok.....

ma puteti clarifica careva?

Cod:

//pun pozitia initiala, poarta de intrare, in coada}
  IncC = SfC = 0; C[IncC] = x; \\si aici C[sfC++] ?
  //parcurg parcul
  while (IncC <=SfC && A[ox][oy]==-2)
    {
      //extrag un element din coada
      x = C[IncC++]; \\aici nu ar trebui sa fie sfC++ ??
      //ma deplasez in cele patru directii posibile
      for (k=1; k<=4; k++)
        {
          y.l = x.l + dx[k];  y.c = x.c + dy[k];
          //y - urmatoarea pozitie in directia k
          if (A[y.l][y.c]==-2)
          //y- pozitie libera cu distanta minima necalculata
            {
             A[y.l][y.c] = A[x.l][x.c]+1;
              //inserez pozitia y in coada
              C[++SfC] =y;

ca asa la inceput incC=0 si dupaia il incrementeaza....pai nu iese din while?


asta ii rezolvarea de la oji 2007 parca...

Editat de moderator: Folostesta tagul [ code ] cand postezi cod sursa.