[PYTHON] Investigate an efficient procedure to increase the sensitivity of a female knight by 3.5 billion times by dynamic programming
It's Christmas. Congratulations to Taimanin! When I was looking into Twitter energetically, I saw the following tweets.
From the definition of "sensitivity 3000 times", it seems that the initial value is 1 instead of 0, but it seems to be convenient for calculation. Anyway, it's easy to brute force $ 5! = 120 $.
import itertools
def kusuri(kando, s):
if s == 'A':
return kando/2
if s == 'B':
return kando - 900
if s == 'C':
return kando + 2000
if s == 'D':
return kando * 5
if s == 'E':
return kando + 500
def main():
chars = "ABCDE"
for c in list(itertools.permutations(chars, 5)):
kando = 0
for cc in c:
kando = kusuri(kando,cc)
if kando == 3000:
print(c)
Output
('B', 'C', 'D', 'E', 'A')
('C', 'A', 'B', 'E', 'D')
('C', 'A', 'E', 'B', 'D')
('C', 'B', 'D', 'E', 'A')
These four ways are the answers. The calculation is completed in an instant.
Minimum sensitivity and maximum sensitivity
Let's find the minimum and maximum of the final sensitivities, and the order at that time.
def min_max():
chars = "ABCDE"
min_kando = 0
max_kando = 0
for c in list(itertools.permutations(chars, 5)):
kando = 0
for cc in c:
kando = kusuri(kando,cc)
if kando < min_kando:
min_kando = kando
if max_kando < kando:
max_kando = kando
for c in list(itertools.permutations(chars, 5)):
kando = 0
for cc in c:
kando = kusuri(kando,cc)
if kando == min_kando:
print("The least sensitive combination:",end="")
print(c)
if kando == max_kando:
print("The most sensitive combination:",end="")
print(c)
min_max()
Output
The least sensitive combination:('A', 'B', 'D', 'C', 'E') -2000.0
The least sensitive combination:('A', 'B', 'D', 'E', 'C') -2000.0
The most sensitive combination:('A', 'C', 'E', 'D', 'B') 11600.0
The most sensitive combination:('A', 'E', 'C', 'D', 'B') 11600.0
Whether you're aiming for the lower or the higher, the theory is to waste A (the drug that halves), spend all the addition resources (or subtraction resources), and then multiply it by five. It seems. Well, in words, it seems like that.
3.5 billion times
By the way, there seems to be an example in which the sensitivity has been increased 3.5 billion times in the world. (* It seems to be a different game from a certain Taimanin)
** 3.5 billion ** ... I can't fit into such a large number int type.
If there is no upper limit to the orcs' medicines, which combination is effective for achieving a sensitivity of 3.5 billion? I know that if you continue to give C medicine, it will reach 3.5 billion at $ 3,500,000,000 / 2,000 = $ 1,750,000, but there seems to be a slightly more efficient combination.
Since the drug of D (5 times) is too powerful, it seems better to use the drug of D as much as possible (such an algorithm is called greedy algorithm), but in the middle, divide 3.5 billion by the exponent of 5 You have to put it on a "rail" like this. Is it better to use the medicines A and B in a small number and put it on the rail, or is it better to increase it to some extent and then put it on the rail? It is impossible to check by hand calculation, and even if you brute force, the amount of calculation is too large and the sun goes down.
Dynamic programming
In such cases, use ** dynamic programming **. To put it simply, it is a calculation method that fills the table while leaving a memo of the previous calculation. If you always accumulate the best moves, you can cover the table with the best moves. This time, the numerical value (labor) to be compared is one-dimensional, but I want to record the order of which drug was selected as accompanying information, so I will prepare a two-dimensional table.
def ikisugi():
inf = pow(10,9)
dp = []
max_kando = 3000+10
for i in range(max_kando):
dp.append([])
dp[i].append(inf)
dp[i].append('')
dp[0][0] = 0
dp is the table that records the results. Record the number of steps on the first line and the order on the second line. We have assigned $ 1,000,000,000 $ as the initial value, which means that it is "blind". (The "best move" candidate derived from a blind hand is over $ 1,000,000,000, so a minimum comparison cannot make it the best move.)
The rest will fill this. If you only use C, D, and E drugs, you can fill the table in one way, but A and B drugs reduce the sensitivity, so the table is filled in the opposite direction. I don't see many of these problems, probably because I'm a beginner in competition pros, but is there something with a fixed name? For the time being, we will call it bidirectional DP here.
A function of DP (direction of increasing sensitivity) starting from the left.
def left_dp(dp,max_kando):
inf = pow(10,9)
for i in range(500,max_kando):
C = dp[i-2000][0]+1
if i < 2000:
C = inf
D = dp[int(i/5)][0]+1
if i%5 > 0:
D = inf
E = dp[i-500][0]+1
if min(C,D,E) >= dp[i][0]:
continue
if min(C,D,E) == C:
dp[i][0] = C
dp[i][1] = dp[i-2000][1] + 'C'
if min(C,D,E) == D:
dp[i][0] = D
dp[i][1] = dp[int(i/5)][1] + 'D'
if min(C,D,E) == E:
dp[i][0] = E
dp[i][1] = dp[i-500][1] + 'E'
return dp
A function of DP (the direction in which sensitivity decreases) starting from the right.
def right_dp(dp,max_kando):
inf = pow(10,9)
for i in reversed(range(1,int(max_kando/2))):
A = dp[i*2][0]+1
B = dp[i+900][0]+1
if min(A,B) >= dp[i][0]:
continue
if min(A,B) == A:
dp[i][0] = A
dp[i][1] = dp[i*2][1] + 'A'
if min(A,B) == B:
dp[i][0] = B
dp[i][1] = dp[i+900][1] + 'B'
return dp
After that, just repeat this from the left, from the right, from the left, and so on, and the table should be filled. Trial hit with sensitivity up to 3000.
def ikisugi():
inf = pow(10,9)
dp = []
max_kando = 3000+10
for i in range(max_kando):
dp.append([])
dp[i].append(inf)
dp[i].append('')
dp[0][0] = 0
for i in range(5):
dp = left_dp(dp,max_kando)
dp = right_dp(dp,max_kando)
for i,dps in enumerate(dp):
if dps[0] < inf:
print(dps,i)
ikisugi()
result.
[0, ''] 0
[5, 'EEBAA'] 25
[4, 'EEBA'] 50
[6, 'CBAEBA'] 75
[3, 'EEB'] 100
.
.
.
[7, 'CBEAACE'] 2900
[7, 'EACBEAC'] 2925
[7, 'EACBBCE'] 2950
[7, 'EAEADBC'] 2975
[3, 'CEE'] 3000
feel well. In the case of bidirectional DP, you don't know how many times you should repeat the zigzag. For the time being, the survey was discontinued when the results did not change even if the number was increased, so I don't think there is a problem with the results.
By the way, if you raise max_kando to ** 3.5 billion ** as it is, the amount of calculation will explode. As mentioned above, let's look at the numbers that have been continuously divided by 3.5 billion to 5. Starting with the number divided by 5 to the 4th power, max_kando is just over 5.6 million. This is a realistic calculation time.
for i in range(4,10):
j = pow(5,i)
k = int((3500000000/j))
print(dp[k],k)
Output
[10, 'CDBDBDEEDD'] 5600000
[9, 'CDBDBDEED'] 1120000
[8, 'CDBDBDEE'] 224000
[8, 'CDBDCBBB'] 44800
[1000000000, ''] 8960
[1000000000, ''] 1792
You can see that we are already on the rails from $ 22,400 $ and only multiply by 5 after that. Therefore, the minimum procedure to bring a female knight to sensitivity ** 3.5 billion ** with oak medicine is
CDBDBDEEDDDDDD
It turned out to be. You can do it in just 14 steps!
Below, check.
C 2000
D 10000
B 9100
D 45500
B 44600
D 223000
E 223500
E 224000
D 1120000
D 5600000
D 28000000
D 140000000
D 700000000
D 3500000000
Recommended Posts