Write a simple greedy algorithm in Python

Greedy algorithm

The greedy algorithm is a method in which a certain standard is set and the optimum solution is continuously selected on the spot to find the optimum solution. I think it is effective when finding the optimum solution to some extent in a short time. Since the greedy algorithm itself is used in a broad sense, it is difficult to use it in such cases, but personally

--A solution seems to be obtained by fixing one value A and comparing it with another value (B, C ...).

I think it can be used at any time.

This issue

AtCoder's B --Magic 2 will be solved by the greedy algorithm.

** Problem statement ** Mr. M has the following three cards.

--A red card with the integer A written on it --Green card with integer B written on it --Blue card with the integer C written on it

Since he is a genius wizard, he can perform the following operations up to K times.

--Choose one of the three cards and double the written integer.

After performing the operation, if the following conditions are met at the same time, the magic is successful.

--The integer written on the green card is truly larger than the integer written on the red card. --The integer written on the blue card is truly larger than the integer written on the green card.

Determine if you can succeed in magic.

** Constraints **

• 1≤A,B,C≤7
• 1≤K≤7 --All inputs are integers

In short, it is considered that you should achieve red <green and green <blue within K times. In this problem, the condition can be met if the number of times green is doubled to red + the number of times blue is doubled to exceed green is less than or equal to K.

If you say fix one value earlier, this problem

--Fix the red value for comparison

I think it will be easier to solve.

Your answer

B-Magic2.py

nums = input().split() #A,B,Enter C

A = int(nums[0])
B = int(nums[1])
C = int(nums[2])

K = input() #Enter K
k = int(K)

cnt = 0 #If the number of times is less than k, magic will succeed, so define an integer cnt for comparison.

while A >= B: #Record the number of times B is doubled and becomes A or more
    cnt += 1
    B *= 2

while B >= C:  #Record the number of times C is doubled and becomes B or more
    cnt += 1
    C *= 2


if cnt <= k:
    print("Yes")
else:
    print("No")

7 4 2    #A,B,C input
3        #K input
No       #output

At the end (writing notes)

When it becomes a difficult problem with AtCoder, even if I transfer the condition of the problem as it is, I can not reach the answer, so I thought that both reading comprehension and mathematical thinking ability of the problem are necessary. It feels like I've been ignoring Japanese until high school. Oh I want reading comprehension ...

Reference article

https://studyhacker.net/reading-comprehension

https://www.naganomathblog.com/entry/2018/08/21/071918