Nil_paracetamol's blog

By Nil_paracetamol, history, 4 years ago, In English
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hint: the function is decreasing at odd number of cups. and the function is constant at even number of cups. Look at this graph:

![ ](2)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's deal with the base case first. Let avg=(h+c)/2. Now temperature will never go below this. So if t<=avg, the answer is 2. Now, for all even no. of moves answer be average and for odd, the answer will tend towards avg. The temperature function after 'x+1' cups of hot water will be — ((x+1)*h + x*c )/(2*x+1). we can see that this tends to 'avg' as x tends to inf. Note here that the total moves are 2*x+1 which is always odd. Let's denote the total moves by 'n'(2*x+1). When n=1, temp is h, and as n increases, temp. keeps decreasing and tends to avg. (At n=inf, temp=avg).Now let's do binary search on the value of x. For some x, 't' will lie between temp at x and x+1. So low=0,hi=(some high value). We will calculate the value at mid and mid+1. I think further approach should be clear. If not, feel free to ask. Here is an implementation of above explained method:- 81782877

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why did you do "h=(h-beg)" in your code?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      That part is just to shift the average. Like in physics you subtract C.O.M. to see in respect of C.O.M. You can actually solve it without shifting average.