infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Martie 18, 2008, 11:47:54


Titlul: 683 Piata
Scris de: Adrian Diaconu din Martie 18, 2008, 11:47:54
Aici puteţi discuta despre problema Piata (http://infoarena.ro/problema/piata).

Titlul: Răspuns: 683 Piata
Scris de: FMI - Petcu Ion Cristian din Octombrie 18, 2008, 11:05:10
f(19)=1 sau 10 #-o

Titlul: Răspuns: 683 Piata
Scris de: Gabriel Bitis din Octombrie 18, 2008, 11:24:45
10

Titlul: Răspuns: 683 Piata
Scris de: FMI - Petcu Ion Cristian din Octombrie 18, 2008, 11:49:22
ms eu luam q 1 :aha:

Titlul: Răspuns: 683 Piata
Scris de: Andrei Tudora din Februarie 16, 2009, 21:41:00
Killed by signal 11(SIGSEGV) ce greseala e asta?   :sad:

Titlul: Răspuns: 683 Piata
Scris de: gaboru corupt din Februarie 16, 2009, 21:52:19
iesi din limitele unui vector... probabil ai declarat vectori prea mici pentru limitele problemei.

Titlul: Răspuns: 683 Piata
Scris de: Vladimir Oltean din Martie 16, 2009, 12:54:57
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   :-k

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];
		}
	}
}

Titlul: Răspuns: 683 Piata
Scris de: Stefan Norbert din Februarie 16, 2010, 20:03:04
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.

Titlul: Răspuns: 683 Piata
Scris de: Gabriel Bitis din Februarie 17, 2010, 08:50:17
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.

Titlul: Răspuns: 683 Piata
Scris de: Chibici Tiberiu din Martie 05, 2010, 09:07:02
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? :-k

Citat din mesajul lui: Gabriel Bitis din Februarie 17, 2010, 08:50:17
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?

Titlul: Răspuns: 683 Piata
Scris de: Gabriel Bitis din Martie 05, 2010, 10:05:18
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.

Titlul: Răspuns: 683 Piata
Scris de: Petrican Teodor din Martie 05, 2010, 13:26:59
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? :-k :sad:

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  :wink:

Titlul: Răspuns: 683 Piata
Scris de: Chibici Tiberiu din Martie 05, 2010, 19:24:24
Citat din mesajul lui: Gabriel Bitis din Martie 05, 2010, 10:05:18
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...

Titlul: Răspuns: 683 Piata
Scris de: Gabriel Bitis din Martie 05, 2010, 23:39:00
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...   :wink:
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.

Titlul: Răspuns: 683 Piata
Scris de: Spatariu Mihai-Constantin din Octombrie 22, 2010, 07:46:44
daca am f(19)=10 cat am in patratul respectiv eu cand fac suma adun 10 sau 1? :-k

Titlul: Răspuns: 683 Piata
Scris de: Gabriel Bitis din Octombrie 22, 2010, 08:55:11
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.

Titlul: Răspuns: 683 Piata
Scris de: Spatariu Mihai-Constantin din Octombrie 22, 2010, 23:09:37
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

Titlul: Răspuns: 683 Piata
Scris de: Gabriel Bitis din Octombrie 24, 2010, 20:34:03
Ai dreptate, enuntul e putin ciudat formulat, dar exemplul clarifica treaba.

Titlul: Răspuns: 683 Piata
Scris de: Mihai Visuian din Septembrie 25, 2011, 11:59:38
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?

Titlul: Răspuns: 683 Piata
Scris de: Roman Tudor din Februarie 25, 2016, 11:29:59
Ș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.


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines