11566 - Let's Yum Cha!
Moderator: Board moderators
11566 - Let's Yum Cha!
I am having hard time understanding the problem statement. From what i understand,
1) There are N+1 persons in total including you.
2) Each person can spend $x at max.
3) Each person spends the same amount of money(I don't understand what 'same amount of money to within one dollar' means).
4) Each person has a favor index for each type of dim sum.
5) Each person can have at most 2 dishes(Both may be of same type) and a maximum of 2 dishes of a particular type of dim sum can be ordered.
6) Tea charge is (N+1)*T dollars total or T dollars for each person. In addition to this, a service charge of 10% of combined cost of dishes and tea charge is charged. The total cost should not be more than the total amount of money the group
could spend.
7) We are asked to maximize the mean favor value of all the persons in the group(essentially total favor value).
Someone please elaborate on points 3 and 6.
1) There are N+1 persons in total including you.
2) Each person can spend $x at max.
3) Each person spends the same amount of money(I don't understand what 'same amount of money to within one dollar' means).
4) Each person has a favor index for each type of dim sum.
5) Each person can have at most 2 dishes(Both may be of same type) and a maximum of 2 dishes of a particular type of dim sum can be ordered.
6) Tea charge is (N+1)*T dollars total or T dollars for each person. In addition to this, a service charge of 10% of combined cost of dishes and tea charge is charged. The total cost should not be more than the total amount of money the group
could spend.
7) We are asked to maximize the mean favor value of all the persons in the group(essentially total favor value).
Someone please elaborate on points 3 and 6.
I am signing an important document!
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
Re: 11566 Let's Yum Cha!
This problem's description is really sucks, if you understand it you can solve it less than 5 minutes.Naani wrote:I am having hard time understanding the problem statement. From what i understand,
You have lots of misinterpretaions, the problem in pseudocode is the following:
Code: Select all
max(i=1,K,order[i]*sum(j=1,N+1,fun[i,j]))/(N+1)
subject to
0<=order[i]<=2 and integers (for i=1..K)
sum(i=1,K,order[i])<=2*(N+1)
let Q=sum(i=1,K,order[i]*cost[i])+T*(N+1) then Q+ceil(Q/10)<=(N+1)*x
Where cost[i] is the cost of the i-th meal
you order exactly order[i] from the i-th meal
fun[i,j] is the i-th meal's favour index of the j-th people
you pay altogether P=Q+ceil(Q/10), and this should be at most (N+1)*x.
Re: 11566 Let's Yum Cha!
Hi,
Any tricky datasets? I keep get wa. Thanks. Here is some of my IO.
Here is my code. It's just simple memorization. Thanks.
Any tricky datasets? I keep get wa. Thanks. Here is some of my IO.
Code: Select all
3 10 5 2
6 7 5 6 9
10 9 10 10 8
3 10 5 2
6 7 5 6 9
10 9 10 2 8
3 10 5 2
6 7 5 6 9
10 2 1 3 8
9 9 3 2
4 7 5 6 9
10 2 1 3 8
0 0 0 0
Code: Select all
16.00
14.00
13.50
10.20
Code: Select all
Thanks! Fixed stupid bug!
Last edited by baodog on Tue Dec 30, 2008 10:22 am, edited 1 time in total.
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
Re: 11566 Let's Yum Cha!
In this line there's a mistake:
Code: Select all
if(x % 10 == 0) return x; else return (x/10)+1;
Re: 11566 - Let's Yum Cha!
more testcases for someone:
output:
enjoy your tea~
Code: Select all
3 9 3 2
4 7 5 6 9
10 2 1 3 8
3 10 5 2
6 7 5 6 9
10 9 10 10 8
3 100 1 2
1 10 10 10 10
2 10 10 10 10
9 4 3 2
4 2 0 0 0 0 0 0 0 0 0
10 1 0 0 0 0 0 0 0 0 0
3 10 5 2
6 7 5 6 9
10 9 10 10 8
3 10 5 2
6 7 5 6 9
10 9 10 2 8
3 10 5 2
6 7 5 6 9
10 2 1 3 8
3 10 0 3
6 0 0 0 0
10 9 10 10 8
7 10 10 10 10
5 10 0 1
10 1 1 1 1 1 2
5 100 0 10
10 0 0 0 0 0 1
10 0 0 0 0 2 3
10 0 0 0 0 0 0
10 0 1 2 0 0 0
10 0 10 4 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 10 0 0 0
10 0 0 0 5 0 1
10 0 0 0 0 5 5
5 100 0 10
10 0 0 0 0 0 1
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 1
9 100 20 10
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8
9 100 20 12
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8
7 5 2 5 8 4 8 1 4 8 1
3 2 3 7 10 3 4 9 3 7 9
9 100 20 20
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8
6 7 0 9 4 9 8 9 5 4 9
7 1 7 1 6 2 8 9 2 8 8
8 1 7 7 7 1 5 5 8 1 2
5 4 10 1 8 6 10 2 9 0 8
3 5 0 10 4 3 6 5 8 2 6
1 7 7 7 2 0 1 1 5 0 5
2 0 7 6 2 6 3 8 7 9 2
5 6 4 7 9 0 5 2 1 6 3
2 7 7 5 9 6 4 8 4 3 0
3 2 3 7 10 3 4 9 3 7 9
0 0 0 0
Code: Select all
17.00
16.00
40.00
0.20
16.00
14.00
13.50
38.50
2.33
16.00
0.67
96.60
104.00
112.60
Re: 11566 - Let's Yum Cha!
Problem, indeed, has quite a tricky statement
I got AC, but I still do not understand about "(to within one dollar)" ![:)](./images/smilies/icon_smile.gif)
During contest I used knapsack-style DP and got WA. Now I found bug and here it is:
For calculating maximal sum, which friends can spend on dim sums, I used next statement:
Just a small fix and AC:
![:roll:](./images/smilies/icon_rolleyes.gif)
![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
During contest I used knapsack-style DP and got WA. Now I found bug and here it is:
For calculating maximal sum, which friends can spend on dim sums, I used next statement:
Code: Select all
int maxmoney = floor(double(x * (N + 1)) / 1.1) - (N + 1) * T;
Code: Select all
int maxmoney = floor(double(x * (N + 1)) / 1.1 + 1e-6) - (N + 1) * T;
![:roll:](./images/smilies/icon_rolleyes.gif)
Re: 11566 - Let's Yum Cha!
Oh for that part, I just copied from the problem statement of 10137 - The Trip...Azrael wrote:Problem, indeed, has quite a tricky statementI got AC, but I still do not understand about "(to within one dollar)"
The problem statement wasn't meant to be confusing. The tea charge and service change issues are real in many Chinese restaurants.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11566 - Let's Yum Cha!
Input:AC output:
Code: Select all
3 9 3 2
4 7 5 6 9
10 2 1 3 8
3 10 5 2
6 7 5 6 9
10 9 10 10 8
3 100 1 2
1 10 10 10 10
2 10 10 10 10
9 4 3 2
4 2 0 0 0 0 0 0 0 0 0
10 1 0 0 0 0 0 0 0 0 0
3 10 5 2
6 7 5 6 9
10 9 10 10 8
3 10 5 2
6 7 5 6 9
10 9 10 2 8
3 10 5 2
6 7 5 6 9
10 2 1 3 8
3 10 0 3
6 0 0 0 0
10 9 10 10 8
7 10 10 10 10
5 10 0 1
10 1 1 1 1 1 2
5 100 0 10
10 0 0 0 0 0 1
10 0 0 0 0 2 3
10 0 0 0 0 0 0
10 0 1 2 0 0 0
10 0 10 4 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 10 0 0 0
10 0 0 0 5 0 1
10 0 0 0 0 5 5
5 100 0 10
10 0 0 0 0 0 1
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 1
9 100 20 10
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8
9 100 20 12
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8
7 5 2 5 8 4 8 1 4 8 1
3 2 3 7 10 3 4 9 3 7 9
9 100 20 20
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8
6 7 0 9 4 9 8 9 5 4 9
7 1 7 1 6 2 8 9 2 8 8
8 1 7 7 7 1 5 5 8 1 2
5 4 10 1 8 6 10 2 9 0 8
3 5 0 10 4 3 6 5 8 2 6
1 7 7 7 2 0 1 1 5 0 5
2 0 7 6 2 6 3 8 7 9 2
5 6 4 7 9 0 5 2 1 6 3
2 7 7 5 9 6 4 8 4 3 0
3 2 3 7 10 3 4 9 3 7 9
0 0 0 0
Code: Select all
17.00
16.00
40.00
0.20
16.00
14.00
13.50
38.50
2.33
16.00
0.67
96.60
104.00
112.60
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 6
- Joined: Mon Feb 17, 2014 12:21 am
Re: 11566 - Let's Yum Cha!
hello i am having quite troubles to solve this problem, i believe i am missing some key data, i readed the various test datas on this section and very few of them give me wrong answer, the problem is that all are really long, so i really cant quite understand why my answer is not optimal.
This is my code:
silly mistake, remember that the number of dishes actually counts on the memoization :3
This is my code:
Code: Select all
AC
Re: 11566 - Let's Yum Cha!
This problem is really difficult (while the main idea of the knapsack behind it is still simple).
I spent a lot of time on it, but it's AC now !![:)](./images/smilies/icon_smile.gif)
If you have difficulties, look at Azrael's answer (the 1e-6 trick).
Without it, my code gives WA, but with it it's finally AC.
This damn floating point precision !
Try this, at least if your answers to the I/O brianfry provided are all right.
I spent a lot of time on it, but it's AC now !
![:)](./images/smilies/icon_smile.gif)
If you have difficulties, look at Azrael's answer (the 1e-6 trick).
Without it, my code gives WA, but with it it's finally AC.
This damn floating point precision !
Try this, at least if your answers to the I/O brianfry provided are all right.
-
- New poster
- Posts: 1
- Joined: Sun Feb 15, 2015 11:30 am
Re: 11566 - Let's Yum Cha!
I really can not understand the problem statement. Can any one please tell me what it's trying to say and how the sample output is 16.00
An explanation of how that output came is really appreciated
An explanation of how that output came is really appreciated