11450 - Wedding shopping
Moderator: Board moderators
11450 - Wedding shopping
I think this problem can be solved using dynamic programming. However, I haven't been able to find the recurrent relation.
Any advice?
Any advice?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
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.
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.
[EDIT] stupid me... I 've found the error.
regards,
nymo
nymo
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....
iF U hv d class u get the form....
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
nymo
Re: 11450 - Wedding shopping
thanks...
good problem![:P](./images/smilies/icon_razz.gif)
good problem
![:P](./images/smilies/icon_razz.gif)
form kisui na ... class tai asol....
iF U hv d class u get the form....
iF U hv d class u get the form....
Re: 11450 - Wedding shopping
Try this input:sabir wrote:i am using dp but get wa.Give me some i/o.
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
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
Are you dreaming right now?
http://www.dreamviews.com
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.
Re: 11450 - Wedding shopping
Post your code, I'll try to help you find your bug ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
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.
Re: 11450 - Wedding shopping
Code: Select all
10 3
1 1
2 2 2
1 10
Code: Select all
Output is
no solution
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..
Output:
![:)](./images/smilies/icon_smile.gif)
![:P](./images/smilies/icon_razz.gif)
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
Code: Select all
4
4
6
6
-
- 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
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.
Reason: Added code blocks
Reason: Added code blocks
-
- New poster
- Posts: 2
- Joined: Sat Apr 18, 2015 4:56 pm
Re: 11450 - Wedding shopping
got acc silly mistake ![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)