11566 - Let's Yum Cha!

[Naani]

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.

[Robert Gerbicz]

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]

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!

[Robert Gerbicz]

In this line there's a mistake:

Code: Select all

    if(x % 10 == 0) return x; else return (x/10)+1;

[kengood]

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

enjoy your tea~

[Azrael]

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]

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.

[brianfry713]

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

[Rocker3011]

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]

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]

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