Page 1 of 1
11369 - Shopaholic
Posted: Mon Dec 10, 2007 10:18 pm
by 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;
}
Posted: Tue Dec 11, 2007 12:30 am
by 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
RTE 11369 - Shopaholic
Posted: Tue May 20, 2008 12:47 am
by mukit
I'm getting RTE
Please help
Thank's in advance.
Re: 11369 - Shopaholic
Posted: Tue May 27, 2008 5:37 pm
by mukit
ok , i got my point and got AC now.
It was a silly mistake.
Re: 11369 - Shopaholic
Posted: Tue Jun 16, 2009 9:01 pm
by 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;
}
Re: 11369 - Shopaholic
Posted: Wed Jun 17, 2009 9:09 am
by 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);
}
Re: 11369 - Shopaholic
Posted: Fri Dec 18, 2009 12:26 pm
by 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");
}
}
Re: 11369 - Shopaholic
Posted: Tue Nov 09, 2010 12:19 am
by 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
Re: 11369 - Shopaholic
Posted: Thu Oct 27, 2011 8:42 pm
by tanim_89
cut after ac ...
Re: 11369 - Shopaholic
Posted: Fri Jun 27, 2014 8:49 am
by uDebug
Replying to follow the thread.