mahmoud_arafa's blog

By mahmoud_arafa, 10 years ago, In English

Hi.

I was trying to solve this problem. Here is the problem link.

If n = 4, k = 0, the apples are of weight 1, 2, 3, 4.

If he eats apple #1:

If apple #1 is sweet, then he must eat apples of total weight 1.

If apple #2 is sweet, then the total weight is 3.

If apple #3 is sweet, then the total weight is 6.

If apple #4 is the sweet one, then he must must eat apples of total weight 6 also.(because he will know the answer regardless of the taste of apple #3)

Then we have total answer of: 1 + 3 + 6 + 6 = 16.

Why the answer in this case is equal to 13?

Thanks in advance.

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The best giant strategy in this case is to eat the first apple, then, if necessary, to eat the third apple:

If apple #1 is sweet he will eat only the first one -> total weight = 1

If apple #2 is sweet he will eat the first (bitter) then the third (sour) — so he now know the second one is sweet -> total weight = 4

If apple #3 is sweet he will eat the first (bitter) then the third (sweet) -> total weight = 4

If apple #4 is sweet he will eat the first (bitter) then the third (bitter) -> total weight = 4

So the answer is (it is actually misprinted in the statement as "1+3+3+3=13")

1 + 4 + 4 + 4 = 13