Nu mai posta surse ca sa le verifice altii. Ia cateva exemple, fa un generator, etc. si apoi posteaza pe forum.

Ok, scuzele mele.

Am gasit problema, afisam un nullbyte la sfarsitul sirului.

Cod:

...

am nevoie de putin ajutor  . Nu inteleg de ce iau incorect pe toate testele...

daca generez exemplul folosind paint numarul de puncte negre difera la unele caractere ...

nu... daca folosesti Arial Black, font-size 18 fara bold/italic numarul de pixeli nu se schimba, indiferent de marimea imaginii.

Ma refeream la faptul ca uni (cum e cazul meu) nu au windows.

da, asa e

Nu toata lumea putea folosi acel program.

Help-ul doc... dar oricum ai dreptate, pentru ca nu erai obligat sa iei acel program...
cel mai bine ar fi fost sa fie specificat in cerita ca font,font-size,inclinarea raman neschimbate. Sau sa nu fi ramas neschimbate sa fie problema mai grea

Cifrele vor avea tot timpul aceeasi dimensiune?

DA

Pai prin asta practic s-a dar rezolvarea problemei... mi se parea mai ok daca nu se raspundea la intrebare. Cine a citit help-ul de la acel program trebuia sa se prinda singur de chestia asta, tinand cont ca era acelasi font si font-size pentru orice input...

Am gresit cu ceva sau dece mi-ai pus " " la citatul ala ?
Multumesc sa fie ..  succes tuturor 

Probabil se pentru ca trebuia sa pui "or sa fie".  Acum de cand cu doom nou  e posibil sa se adminta si asa. Nu stiu sigur ca ne-au zapacit de tot.

Da ai dreptate nu am fost destul de atent cand am citit programul, my bad 

Ma refeream la solutia cu cautare binara descrisa mai sus tot de mine (deci tot nu ai citit topicul cu atentie)

Inca l-am citit 

tu ai zis asa:
Astfel am ajuns la o complexitate de log2(MAX) * log3(MAX) * log5(MAX), unde MAX este o valoare mai mare decat al 1500-lea nr de forma 2^x * 3^y * 5^z, cred ca 2 miliarde ar fi de ajuns.

log2(MAX) * log3(MAX) * log5(MAX),MAX=2.000.000.000 > n. La un calcul rapid ar iesi in jur de 8000. Adica mai mare chiar decat N logN

Scuza-ma daca gresesc, logaritmii nu mi-au placut niciodata 

Citeste si tu mai atent ce s-a discutat inainte.
In primul rand s-a spus deja o solutie mai rapida de o(n).
In al doilea rand solutia ta e gresita. E gresita din acelasi motiv pe care l-am zis eu mai sus cand explicam de ce aceasta problema nu e un caz particular al problemei numar2.

Am citit discutia destul de bine inainte sa postez.
Insa tu nu mi-ai citit programul la fel de bine.

Si la care solutie te referi ca e mai rapida decat O(n)? cea cu heap?

Cod:

v[1]=poz[2]=poz[3]=poz[5]=1;
pt i->2,n executa
v[i]=minim(v[poz[2]]*2,v[poz[3]]]*3,v[poz[5]]*5);
if(v[poz[2]]*2==v[i])poz[2]++;
if(v[poz[3]]*3==v[i])poz[3]++;
if(v[poz[5]]*5==v[i])poz[5]++;
sfarsit;

Sa il explic:
initial p2=p3=p5=v[1]=1;
v[2]=minim(1*2,1*3,1*5)=2; p2=2;
v[3]=minim(2*2,1*3,1*5)=3;p3=2;
v[4]=minim(2*2,2*3,1*5)=4;p2=3;
v[5]=minim(3*2,2*3,1*5)=5;p5=2;
v[6]=minim(3*2,2*3,2*5)=6;p2=4;p3=3;
v[7]=minim(4*2,3*3,2*5)=8;p2=5;
v[8]=minim(5*2,3*3,2*5)=9;p3=4;
v[9]=minim(5*2,4*3,2*5)=10;p2=6;p5=3;
v[10]=minim(6*2,4*3,3*5)=12;p2=7;p3=5;
v[11]=minim(7*2,5*3,3*5)=15;p3=6;p5=4;
etc...

de asemenea am m-as putea baza decat pe p2 si p3 si la p5 sa adaug decat puterile lui 5, dar n-are rost pt ca n e mic.

PS: tinand cont ca esti moderator ar trebui sa fi mai prietenos :p

La problema Cerc mergea si greedy si putea fi rezolvata in O(N log N) astfel. Pentru fiecare dreapta, cercul i, aflat la distanta D_i = sqrt(X_i^2 + Y_i^2) de origine, ocupa intervalul (D_i - R_i, D_i + R_i). Pentru a determina numarul de cercuri exterioare 2 cate 2 este corect sa alegi la fiecare pas intervalul cu capatul din dreapta cel mai mic si care nu se intersecteaza cu nici un alt interval deja ales. Poti determina usor numarul, sortand intervalele crescator dupa capatul al doilea.

Adica precum problema "standard" programarea spectacolelor, nu?

problema 1 se poate rezolva in O(n).

completam un vector 'v' de la 1->n unde v[ i ] reprezinta al i-lea numar din sirul dorit.

Cod:

v[1]=poz[2]=poz[3]=poz[5]=1;
pt i->2,n executa
v[i]=minim(v[poz[2]]*2,v[poz[3]]]*3,v[poz[5]]*5);
if(v[poz[2]]*2==v[i])poz[2]++;
if(v[poz[3]]*3==v[i])poz[3]++;
if(v[poz[5]]*5==v[i])poz[5]++;
sfarsit;

problema se poate generaliza pentru m numere, nu doar 2,3,5.

pentru asta trebuie sa apelezi c:\..cale..\firefox.exe www.infoarena.ro. Cum apelezi un executabil din cpp chiar nu stiu. Dar trebuie sa se poata pentru ca se poate in php care e facut in c.

  Felicitari. Si eu merg tot pentru prima data  .

Am o intrebare: Lotul bucurestiului o sa faca pregatire speciala cum e la alte materii?

Da, era. Coordonatele erau pana la 1000, iar 1000*1000 = 1.000.000, care iese din int (maxint = 32.000).

dar int*int==int*int, nu? adica 1234*10000==12340*1000 returneaza 1, nu?

mda, sunt dobitoc 

[cerc]

La problema cerc (clasele XI-XII) am folosit x1/y1=x2/y2 (x1*y2=x2*y1) pentru pct a iar pt b si c am folosit programare dinamica. Am luat fiecare dreapta in parte si pentru fiecare am retinut in vector numarul maxim de cercuri exterioare ce se pot forma cu cercul i si cercurile precedente. Complexitatea ar fii cam o(m*n*log(n)) (cred... nu calculez prea bine complexitatea  ) Am luat 28 de puncte la problema asta  desi nu a iesit din timp. Intrebarea este: era posibil sa iasa din int? In total am luat 128 de puncte si pana maine stau ca pe jar sa vad daca ma calific  Daca aveti vreo stire inainte de maine anuntati-ma, va rog, si salvati-ma de 24 de ore in care ma gandesc numai la asta 

100. da, de la matrice era. Nu ma gandisem la asta. Merci mult.

Nu fac cu unsir de nr de la 0 la 2^n-1 pentru ca stiu de la permutari ca e mai performat cu vector deoarece faci mai putine operatii la adaugare de unitate decat la conversie in baza 2.

Am comparat timpii de la testul meu cu alte teste si la majoritatea am iesit in avantaj. Probabil daca mai lucrez la el o sa obtin timpi mai buni. dar nu are rost )

Ok. Ideea algoritmului:

Iau toate posibilitatie de comutare a linilor. In loc sa folosesc un backtracking, folosesc un vector sol de n elemente (n nr de linii). Vectorul sol este initial 0,0,0... Apoi, pentru a  genera toate posibilitatile consider vectorul sol drept un numar un baza 2. Si la fiecare pas adaug 1 in sol[0] (consider ca numarul este scris invers). La fiecare solutie (adica dupa ce am adaugat 1) iau modul de suma pe fiecare coloana si o adaug la max2(suma matricei pentru sol respectiva). Iau modul pentru ca in cazul in care suma este negativa eu as avea posibilitatea sa comut acea coloana, pentru ca suma sa fie maxima. De fiecare data verific max2 cu max(suma maxima generala) si modific max(dupa caz).

Cam asta este explicatia algoritmului...

Cod:

Cod:

#include<stdio.h>
long mat[16][16];
long max =-1099999999;
int sol[16];
int n,m;
void citire()
{
	freopen("flip.in","r",stdin);
   scanf("%d",&n);
   scanf("%d",&m);
   for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
         scanf("%ld",&mat[i][j]);
}

long suma_col(int col)
{
	long s=0;int x;
   for(int i=1;i<=n;i++)
      {
         if(sol[i])x=-1;
         else x=1;
         s+=mat[i][col]*x;
      }
   if(s>0)return s;
   else return -s;
}

void do_max()
{
   int i;
   long max2=0;
   for(i=1;i<=m;i++)
      max2+=suma_col(i);
   if(max2>max)max=max2;
}
int add2sol()
{
   int poz=1;
   while(sol[poz]!=0)
      sol[poz++]=0;
   sol[poz]=1;
   //printf("poz: %d ; ",poz);
   return poz<=n;
}
void tip_sol()
{
   for(int i=1;i<=n;i++)printf("%d ",sol[i]);
   printf("\n");
}
int main()
{
   freopen("flip.out","w",stdout);
   citire();
   do
   {
      //tip_sol();
      do_max();
   }
   while(add2sol());
   printf("%ld",max);
   return 0;
}

Pct:

Cod:

Test  	Timp executie  	Memorie folosita  	Mesaj 	Punctaj/test
1	0ms	8kb	Ok!					10
2	0ms	8kb	Ok!					10
3	0ms	8kb	Ok!					10
4	8ms	204kb			Raspuns gresit		0
5	4ms	8kb	Ok!					10
6	56ms	208kb	Ok!					10
7	32ms	204kb	Ok!					10
8	604ms	184kb			Time limit exceeded.	0
9	0ms	8kb			Raspuns gresit		0
10	548ms	176kb			Time limit exceeded.	0
Punctaj total	60

Ideea e ca algoritmul meu are o complexitate mai mica decat cel cu backtracking dar nu reusesc sa iau decat 60pct...
L-am verificat, si reverificat, si tot asa pana m-am dat batut...
Va rog daca vedeti unde ar putea gresi sa-mi spuneti

Merci, Sorin