Re: Competitive Programming Life Starting from Zero Chapter 1.3 "Sedo Tea"

Learning report

ABC154 I was full of participation, but I didn't have this week orz So I will solve the past questions this time as well !!

Last time I solved the B problem, and the next one was the C problem, but it was unexpectedly difficult, and for the past 5 days I was trying to solve the problems up to A-C.

Along the way, I noticed that the problem was colored according to the difficulty level (slow). If you look at the color, the problem that I was happy to receive AC is gray ()

In other words, my current ability is gray ...

Let's solve the tea problem !!!!

Challenge tea

So, here is the problem to be solved this time

This is brown ... my fingers don't move. Let's take a look at an output example for the time being.

I see !! Once you replace the number in this probability formula with an appropriate variable (i for the roll, j for the number of times you swing the coin),

1/i*(0.5**j)

If you repeat this formula in a sentence and add it up, you will be asked for an answer !!

N,K = map(int,input().split())
ans = 0
for i in range(1,N+1):
  j = 0
  point = i
  while point < K:
    point *= 2
    j += 1
  ans += (1/N)*(0.5**j)
print(ans)

You got AC with this !!

I wrote it briefly in the article, but it took me an hour to solve it. I have to think more and write the code ... Also, it seems that you need to know various things such as binary search and dynamic programming in order to solve problems of higher difficulty, so I will also learn that. It looks like a flat tire ()

Thank you for reading. The next update is likely to be after ABC154, but please read it again if you like.