11369 - Shopaholic

[scott1991]

I have written some code for this but keep getting an unhandles exception on my pc. i have not submitted yet as it doesn't work. Does anyone know why? thanks. Scott

Code: Select all

// Shopaholic - 11369.cpp : Defines the entry point for the console application.
#include <iostream>
int main ()
{
	int Swap,saveing=0,x,ii,t,noi,i=0;
	int* costofitems = new int [noi+10];
	
	scanf("%d",&t);
	for (t;t>0;t--)
	{
		scanf("%d",&noi);
		for(i;i<noi;i++)
		{
			scanf("%d",costofitems[i]);
		}
        
		for(x=0; x<noi-1; x++)
		{
			for(ii=0; ii<noi-1; ii++) 
			{
				if (costofitems[ii] < costofitems[ii + 1]) 
				{ 
					Swap = costofitems[ii + 1]; 
					costofitems[ii + 1] = costofitems[ii]; 
					costofitems[ii] = Swap; 
				} 
			}
		}
		for(x=2;x<noi;x+=3)
		{saveing+=costofitems[x];}
		printf("%d\n",saveing);
	}
	return 0;
}

[rio]

Few points to fix in the coding.

Code: Select all

   int Swap,saveing=0,x,ii,t,noi,i=0;
   int* costofitems = new int [noi+10];

Using noi+10 for size of costofitems, but variable noi is not initialized. This is very dangerous.

Code: Select all

      for(i;i<noi;i++)
      {
         scanf("%d",costofitems[i]);
      } 

In the for, i is not initialized. And also, arguments of scanf() must be an address.

Code: Select all

      for(x=0; x<noi-1; x++)
      {
         for(ii=0; ii<noi-1; ii++)
         {
            if (costofitems[ii] < costofitems[ii + 1])
            {
               Swap = costofitems[ii + 1];
               costofitems[ii + 1] = costofitems[ii];
               costofitems[ii] = Swap;
            }
         }
      } 

n is maximum 20,000, so bubble sort (O(n^2)) would cause TLE.

-----
Rio

[mukit]

I'm getting RTE
Please help

Code: Select all

cut after AC

Thank's in advance.

[mukit]

ok , i got my point and got AC now.
It was a silly mistake.

[farhan_iut]

i hv solved the problem bt it shows "time limit exceed"... wht is the problm..?

Code: Select all

#include<stdio.h>

int main(){
	int a,b,c,d,e[20000],t,j,f;
#ifndef ONLINE_JUDGE
	freopen("11369.txt","r",stdin);
#endif
	while(scanf("%d",&a)==1){
		for(f=0;f<a;f++){
			scanf("%d",&b);
			for(c=0;c<b;c++)
				scanf("%d",&e[c]);
				
			for(c=0;c<b;c++)
				for(d=b-1;d>=c;d--){
					if(e[d-1]<e[d]){
						t=e[d-1];
						e[d-1]=e[d];
						e[d]=t;
					}
				}
			j=0;
			for(c=1;c<=b;c++)
				if(c%3==0)
					j=j+e[c-1];
			printf("%d\n",j);
		}
	}
	return 0;
}

			

		

[sohel]

@farhan_iut:
Looks like you are using 'bubble sort' to sort the integers which has a complexity of O(n^2). For this problem, n can be as big as 20000 and thus n^2 could be a little too costly.
You can use the sort() function defined in <algorithm> for sorting integers with O(n log n) and that should pass the time limit.

Sample Code

Code: Select all

#include<algorithm>
using namespace std;
int main() {
  int A[5] = {2, 4, 0, 1, 5};
  sort(A, A+5);
}

[atanu-cse]

can anyone please help me with this???? it says WA.

=========================================================

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
long int a[20005];
int main()
{
freopen("D://test.txt","r",stdin);
freopen("D://out.txt","w",stdout);
long int n,c,i,j,k,t,v,m,add;

scanf("%ld",&n);

for(i=0;i<n;i++)
{
scanf("%ld",&c);
for(j=1;j<=c;j++)
{
scanf("%ld",&a[j]);
}
sort(a,a+c+1);


m=n%3;
add=0;
for(j=c;j>m;j=j-3)
{
add=add+a[j-2];
}
if(m==2)
add=add+a[1];
if(c>=3)
printf("%ld\n",add);
else
printf("0\n");
}

}

[Shafaet_du]

easy problem when you understand the statement. Greedily choose the current best one. it should be a piece of cake.

Code: Select all

1
10
10 20 30 40 50 60 70 80 90 100

output

Code: Select all

150

[tanim_89]

cut after ac ...

[uDebug]

Replying to follow the thread.