## 11566 - Let's Yum Cha!

Moderator: Board moderators

Naani
New poster
Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India
Contact:

### 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.
I am signing an important document!

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 11566 Let's Yum Cha!

Naani wrote:I am having hard time understanding the problem statement. From what i understand,
This problem's description is really sucks, if you understand it you can solve it less than 5 minutes.
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.
``````

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### Re: 11566 Let's Yum Cha!

Hi,

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
``````
Here is my code. It's just simple memorization. Thanks.

Code: Select all

``````Thanks! Fixed stupid bug!
``````
Last edited by baodog on Tue Dec 30, 2008 10:22 am, edited 1 time in total.

Robert Gerbicz
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;
``````

kengood
New poster
Posts: 7
Joined: Fri Oct 31, 2008 6:25 am
Location: Hong Kong

### Re: 11566 - Let's Yum Cha!

more testcases for someone:

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
``````
output:

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
``````

Azrael
New poster
Posts: 1
Joined: Sat Dec 27, 2008 4:12 pm

### 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)"
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;``
Just a small fix and AC:

Code: Select all

``int maxmoney = floor(double(x * (N + 1)) / 1.1 + 1e-6) - (N + 1) * T;``

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### Re: 11566 - Let's Yum Cha!

Azrael wrote:Problem, indeed, has quite a tricky statement I got AC, but I still do not understand about "(to within one dollar)"
Oh for that part, I just copied from the problem statement of 10137 - The Trip...

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11566 - Let's Yum Cha!

Input:

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
``````
AC output:

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!

Rocker3011
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:

Code: Select all

``````AC
``````
silly mistake, remember that the number of dishes actually counts on the memoization :3

damien_g
New poster
Posts: 8
Joined: Sun Oct 05, 2014 5:53 pm

### 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 !

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.

abhisek104
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