11450 - Wedding shopping

Moderator: Board moderators

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

11450 - Wedding shopping

I think this problem can be solved using dynamic programming. However, I haven't been able to find the recurrent relation.

Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Samiul
New poster
Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

Re: 11450 - Wedding shopping

You are given the amount of money, which is <= 200. So you can create a table which has c rows and m columns and dp on it.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 11450 - Wedding shopping

I am trying DP. Can you give me some test cases... getting WAs. thanks.
[EDIT] stupid me... I 've found the error.
regards,
nymo

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:

Re: 11450 - Wedding shopping

I use DP, but can't understand why WA... plz give some I/O...

Code: Select all

``````ACC... :)

``````
Last edited by joy on Fri Jul 04, 2008 8:31 am, edited 1 time in total.
form kisui na ... class tai asol....
iF U hv d class u get the form....

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 11450 - Wedding shopping

Joy, you can overwrite some positions in the following code fragment...

Code: Select all

``````for(j=0; j<=sum-m; j++)
if(a[j]==i)
a[j+m]=i+1;
``````
regards,
nymo

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Contact:

Re: 11450 - Wedding shopping

thanks...
good problem
form kisui na ... class tai asol....
iF U hv d class u get the form....

sabir
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am

Re: 11450 - Wedding shopping

i am using dp but get wa.Give me some i/o.
An offer u can not refuse.

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11450 - Wedding shopping

sabir wrote:i am using dp but get wa.Give me some i/o.
Try this input:

Code: Select all

``````7
100 4
3 8 6 4
2 5 10
4 1 3 3 7
4 50 14 23 8
20 3
3 4 6 8
2 5 10
4 1 3 5 5
5 3
3 6 4 8
2 10 6
4 7 3 1 7
6 3
2 1 2
2 3 5
2 1 0
200 3
2 100 100
2 97 99
3 2 4 1
20 3
3 4 6 8
2 5 10
4 1 3 5 6
200 20
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 181 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 180``````
Correct output is:

Code: Select all

``````75
19
no solution
6
200
20
200
``````
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

sabir
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am

Re: 11450 - Wedding shopping

Thnx andmej for ur I/O.My program give same output as your.But WA.Do u or any one else have more I/O ?
An offer u can not refuse.

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11450 - Wedding shopping

Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

sabir
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am

Re: 11450 - Wedding shopping

i found error in my code.But now i am getting TLE.Plz help me.Here is my code

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

#define sz 30

long cost[sz][sz];
bool dup[sz][210],finish;
long type[sz],m,c,count,max;

void check(long node)
{
long i,temp;

node++;

if(node==c)//last row
{
for(i=type[node]-1;i>=0;i--)
{
if(count+cost[node][i]<=m)
{
temp=count+cost[node][i];
if(temp>max)
{
max=temp;
}
}
}
}

for(i=type[node]-1;i>=0;i--)
{
if(count+cost[node][i]<=m)
{
count=count+cost[node][i];
check(node);
count=count-cost[node][i];
}
}
}

int main()
{

long tcase,n,d,i,j,w,k;
bool tag;

scanf("%ld", &tcase);

while(tcase--)
{
max=0;
count=0;
finish=false;

scanf("%ld %ld", &m, &c);

for(i=1;i<=c;i++)
{
scanf("%ld", &n);

for(j=1,d=0;j<=n;j++)
{
scanf("%ld", &w);
tag=true;

for(k=0;k<d;k++)//check duplicate tata
{
if(cost[i][k]==w)
{
tag=false;
break;
}
}
if(tag==true)
{
cost[i][d]=w;
d++;
}
}

type[i]=d;//number column in ith row

}

for(i=0;i<type[1];i++)//first row
{
count=cost[1][i];
check(1);
}

if(max==0)
{
printf("no solution\n");
}
else
{
printf("%ld\n", max);
}

}

return 0;
}

``````
An offer u can not refuse.

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11450 - Wedding shopping

Code: Select all

``````10 3
1 1
2 2 2
1 10

``````

Code: Select all

``````Output is
no solution
``````

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

Re: 11450 - Wedding shopping

here are some cases for what my code failed,after fixing these I got accepted.. ..I'm posting these case here for them who are still struggling with it..

Code: Select all

``````4
4 3
2 2 2
2 1 1
2 1 3
4 3
2 2 2
2 1 1
2 3 1
6 3
2 2 5
2 2 4
2 2 3
7 3
2 1 5
2 3 3
2 2 4
``````
Output:

Code: Select all

``````4
4
6
6
``````

ankush_kapoor
New poster
Posts: 2
Joined: Sat Apr 18, 2015 4:56 pm

Re: 11450 - Wedding shopping

i dont know why i am getting wa ,my code is passing all the inputs mentioned in the problem and in this forum.
heres my code sumone pls tell me whts wrong in it

Code: Select all

``````#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int b,n,g[25][25],dp[210][30];
int rec(int budgetleft,int garment)
{
if(garment==n)
return 0;
if(dp[garment][budgetleft]!=0)
{
return dp[garment][budgetleft];
}
int m=g[garment][0],flag=1;
for(int i=1;i<=m;i++)
{
if(budgetleft-g[garment][i]>=0)
{
dp[garment][budgetleft]=max(dp[garment][budgetleft],rec(budgetleft-g[garment][i],garment+1)+g[garment][i]);
if(dp[garment][budgetleft]>0)
flag=0;
}
}
if(flag==1)
{
return -1000000000;
}

return dp[garment][budgetleft];
}
int main()
{

int t,maxi;
scanf("%d",&t);
while(t--)
{
for(int i=0;i<210;i++)
{
for(int j=0;j<30;j++)
dp[i][j]=0;
}
scanf("%d%d",&b,&n);
for(int i=0;i<n;i++)
{
scanf("%d",&g[i][0]);
{
for(int j=1;j<=g[i][0];j++)
{
scanf("%d",&g[i][j]);
}
}
}
maxi=rec(b,0);
if(maxi<=0)
{
printf("no solution\n");
}
else
{
printf("%d\n",maxi);
}
}
return 0;
}``````
Last edited by brianfry713 on Fri Jun 19, 2015 7:03 am, edited 1 time in total.