683 Piata

[•DITzoneC]

Aici puteţi discuta despre problema Piata.

[•jean]

f(19)=1 sau 10

[•gabitzish1]

10

[•jean]

ms eu luam q 1

[•Dj_Andrei]

Killed by signal 11(SIGSEGV) ce greseala e asta?   

[•gabor_oliviu1991]

iesi din limitele unui vector... probabil ai declarat vectori prea mici pentru limitele problemei.

[•vlad_oltean]

ma poate ajuta cineva?  iau WA pe testul 9, chiar nu inteleg de ce, si mi-e un pic cam greu sa fac debug pe un test de 40 000   

fac cam asa:

Cod:

	scanf("%d%d%d%d%d",&n,&y1,&x1,&y2,&x2);
	for(int i=1;i<=n;i++)
		v[i]=f(i);
	while(y1>1)  //duc dreptunghiul cu suma pe prima linie
	{	x1--; x2--;
		y1--; y2--;
	}
	for(int i=x1;i<=x2;i++)
		s+=elem(i);
	suma=s;
	for(int i=1;i<y2;i++)
	{	s-=elem(x2);
		s+=elem(x1-1);
		suma+=s;
		x1--; x2--;
	}
	
	printf("%ld",suma);

unde elem(i) e o functie care returneaza v[ i ] daca i e in limita vectorului (1->n) sau corespondentul lui i in vector, daca e in afara limitelor

Cod:

inline int elem(int x)
{	int t;
	if(x>0&&x<=n)	//e clasic
		return v[x];
	else
	{	if(x<=0)
		{	while(x<=0)
			{	t=1-x;
				x=n-t+1;
			}
			return v[x];
		}
		else
		{	while(x>n)
			{	t=x-n;
				x=t;
			}
			return v[x];
		}
	}
}

[•norb3rt00]

Imi poate da cnva o idee cum as putea optimiza programul meu sa mearga pe testul 7? Presupun ca n-ul este maxim si dreptunghiul maxim,dar tot nu inteleg cear putea fi problema

Cod:

int suma(int x){
	int s=0;
	while (x>0){s=s+x%10;
				x=x/10;
	}
	return s;
}
int main (){
	int i,iT,jT,iM,jM,n,j,poz;
	long s=0;
	short int x[40000];
	ifstream f("piata.in");
	ofstream g("piata.out");
	f>>n>>iT>>jT>>iM>>jM;
	for (i=1;i<=n;i++)
		x[i]=suma(i);
	for (i=iT;i<=iM;i++){
		for (j=jT;j<=jM;j++){
			if (j+1-i<1) poz=n-(i-j-1);
				else poz=j+1-i;
			s=s+x[poz];}
	}
		g<<s;
	g.close();
return 0;
}

[Editat de moderator]Foloseste tagul [ code ][ /code ] cand postezi cod sursa.

[•gabitzish1]

Incearca sa te folosesti de faptul ca liniile sunt permutari circulare ale numerelor f(x). Asta inseamna ca la suma aia tu aduni acelasi f(x) de mai multe ori si pierzi ceva timp.

Se poate calcula pentru fiecare numar de cate ori il ai in dreptunghiul ala, si asa il aduni doar o data inmultit cu ceva.

[•chibicitiberiu]

Iau 90 puncte pe solutia asta...

Cod:

#include<fstream>
using namespace std;

int *arr;
int n;

int f(int nr)
{
	int sum;

	for (sum = 0; nr > 0; nr /= 10)
		sum+=nr%10;
	return sum;
}

void set()
{
	for (int i = 0; i < n; i++)
		arr[i] = f(i+1);
}

int main()
{
	int mi, mj, ti, tj; int p;
	long sum = 0;

	ifstream in ("piata.in");
	in>>n;
	in>>ti>>tj;
	in>>mi>>mj;
	in.close();

	arr = new int[n+1];
	set();

	for (int i = ti; i <= mi; i++)
		for (int j = tj; j <= mj; j++) {
			p = j - i; while (p<0) p+=n;
			sum += (long) arr[p];
		}

	ofstream out ("piata.out");
	out<<sum;
	out.close();

	delete[] arr;
	return 0;
}

Imi iese din timp la testul 7... are cineva vreo idee de optimizare?

Incearca sa te folosesti de faptul ca liniile sunt permutari circulare ale numerelor f(x). Asta inseamna ca la suma aia tu aduni acelasi f(x) de mai multe ori si pierzi ceva timp.

Se poate calcula pentru fiecare numar de cate ori il ai in dreptunghiul ala, si asa il aduni doar o data inmultit cu ceva.

Si sugerezi ca numarand de cate ori apare un nr este mai eficient decat sa il adun de atatea ori?

[•gabitzish1]

Nu am sugerat sa numeri de cate ori apare, ci sa calculezi de cate ori apare.
Un numar va aparea pe diagonala sau paralel cu diagonala, si tu stii unde intra si unde iese din dreptunghiul ala, deci se poate calcula cate pozitii ocupa in dreptunghi.

[•doruletz]

50 de puncte   cu WA pe 5 teste. La teste mici pe care le-am verificat usor pe hartie imi da corect... nu stiu ce are.
Pun aici cateva teste random si rezultatul pe care il da programul meu, in caz ca ma poate ajuta cineva
300
1 1
10 10
Raspuns: 874

Cu riscul de a ma repeta spun ca astea sunt doar niste teste random. Exista ceva cazuri speciale la problema asta? De ce pot sa iau WA?

Multumesc anticipat!  

LE: Am gasit o eroare la testul:
1800
249 100
249 250
Mie imi da 1728 si trebuie sa dea 2612. O sa vad care e problema. Multumesc oricum 

[•chibicitiberiu]

Nu am sugerat sa numeri de cate ori apare, ci sa calculezi de cate ori apare.
Un numar va aparea pe diagonala sau paralel cu diagonala, si tu stii unde intra si unde iese din dreptunghiul ala, deci se poate calcula cate pozitii ocupa in dreptunghi.

Am incercat asa, dar chiar si pentru exemplu mergea muuult mai greu...
EDIT: Cred ca e din cauza Visual Studio... si originalul vad ca merge tot la fel de greu...

[•gabitzish1]

Cred ca nu ai incercat cum trebuie
Sa zicem ca ai un dreptungi de N * M pt care tre sa calculezi suma. Solutia ta, are complexitate O(N*M) iar a mea are O(N+M), nu are cum sa mearga mai greu...   
Iei pe rand elementele de pe prima linie, si vezi daca ajung sa iasa prin stanga sau pe jos, apoi cele de pe ultima coloana, si vezi acelasi lucru...ti'am zis cam multe, mai incearca.

[•myshu]

daca am f(19)=10 cat am in patratul respectiv eu cand fac suma adun 10 sau 1?

[•gabitzish1]

f(19) = 10 intotdeauna, inseamna ca la suma aduni 10.
Daca ai aduna 1, inseamna ca tu ai aduna la suma f(f(19)), ceea ce e gresit.

[•myshu]

pai in enunt zice "sa determine suma cifrelor numerelor aflate pe portiunea dreptunghiulara"
adica suma cifrelor lui f(19)
adica suma cifrelor lui 10
sau nu pricep eu bine?

L.E. intradevar am luat 100 daca calculam suma numerelor aflate pe portiune si nu suma cifrelor aflate pe portiune deci cred ca enuntul ar trebui modificat pentru ca se poate intelege gresit cerinta

[•gabitzish1]

Ai dreptate, enuntul e putin ciudat formulat, dar exemplul clarifica treaba.

[•VisuianMihai]

Daca scriu
int *a;
a = new int[n+1]; imi da memory limit exceed... daca declar vectorul normal a[40000] nu imi da. Imi puteti spune de ce?

[•tudorgalatan]

Știe cineva cum aș putea optimiza această sursă?

Cod:

    for (i=1; i<=n; i++)
        soom[i] = f(i);
    for (i=iT; i<=iM; i++)
        for (j=jT; j<=jM; j++)
            if (j >= i)
                sum += soom[j-i+1];
            else
                sum += soom[n+j-i+1];

Iau 90 de puncte folosind această metodă, cu un singur TLE.