11369 - Shopaholic

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
scott1991
New poster
Posts: 28
Joined: Fri Dec 07, 2007 11:41 pm

11369 - Shopaholic

Post by scott1991 » Mon Dec 10, 2007 10:18 pm

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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Dec 11, 2007 12:30 am

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
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh
Contact:

RTE 11369 - Shopaholic

Post by mukit » Tue May 20, 2008 12:47 am

I'm getting RTE :oops:
Please help

Code: Select all

cut after AC
Thank's in advance.
Last edited by mukit on Tue May 27, 2008 5:39 pm, edited 1 time in total.

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh
Contact:

Re: 11369 - Shopaholic

Post by mukit » Tue May 27, 2008 5:37 pm

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

farhan_iut
New poster
Posts: 4
Joined: Mon Jun 08, 2009 11:52 pm

Re: 11369 - Shopaholic

Post by farhan_iut » Tue Jun 16, 2009 9:01 pm

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

			

		


User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11369 - Shopaholic

Post by sohel » Wed Jun 17, 2009 9:09 am

@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
New poster
Posts: 3
Joined: Fri Dec 18, 2009 12:09 pm

Re: 11369 - Shopaholic

Post by atanu-cse » Fri Dec 18, 2009 12:26 pm

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11369 - Shopaholic

Post by Shafaet_du » Tue Nov 09, 2010 12:19 am

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
New poster
Posts: 1
Joined: Thu Jan 13, 2011 6:15 pm

Re: 11369 - Shopaholic

Post by tanim_89 » Thu Oct 27, 2011 8:42 pm

cut after ac ... :)

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11369 - Shopaholic

Post by uDebug » Fri Jun 27, 2014 8:49 am

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 113 (11300-11399)”