Friends times.
This is a review article for beginners of competition professionals.
The solution I write here is written while looking at the commentary and other people's submissions. It may not be what you actually submitted.
It is a question to answer the number of attacks required to reduce the physical strength H with the attack power A.
The answer is to round up H / A. I used math.ceil () for the round-up process.
import math
H, A = map(int, input().split())
print(math.ceil(H/A))
By the way, I heard that math.ceil () can cause an error when the number is too large. It's okay to write something like (H + A-1) // A, but I didn't like it, so I looked it up lightly.
The following writing method introduced in this article may be smart.
H, A = map(int, input().split())
print(-(-H//A))
How to write -(-H // A). Truncation processing with a negative number seems to be the same processing as rounding up, such as -0.1 → -1. By the way, I've seen it in other answers. Should I use this as much as possible in the future?
It is a question to answer whether you can cut off your physical strength $ H $ by making full use of the power $ A_i $ technique.
If the total value of the special move is greater than or equal to the physical strength,'Yes' is output.
H, N = map(int, input().split())
A = list(map(int, input().split()))
if H <= sum(A):
print('Yes')
else:
print('No')
When defeating monsters by making full use of the techniques of "doing 1 damage" (unlimited number of times) and "killing instantly" (up to K times), it is a problem to answer the number of normal attacks.
Arrange the HP of monsters in order, and exclude K monsters in descending order. The answer is the total number of remaining HP.
Note that K may be more frequent than N (one loss).
N, K = map(int, input().split())
H = list(map(int, input().split()))
H.sort()
print(sum(H[:max(N-K, 0)]))
Postscript: Taking a negative value for the array index in python will behave specially.
a = [0, 1]
print(a[2:]) #The protruding index is passed through
# []
print(a[-1:]) #Overhanging indexes are counted in the opposite direction
# [1]
I added the processing of max to avoid this specification, but if you write it as follows, you don't need to compare N and K.
N, K = map(int, input().split())
H = list(map(int, input().split()))
H.sort(reverse=True)
print(sum(H[K:]))
It is a problem to answer the number of attacks required for a monster that splits (truncated) by halving HP when attacking.
First, HP always truncates, so even if the value $ H $ given is converted to $ 2 ^ {k-1} $ (but $ 2 ^ {k-1} \ leq H <2 ^ k $) It will be the same number of times.
So let's count the number of attacks against monsters with $ 2 ^ {k-1} $ HP.
First, attack a monster with HP of $ 2 ^ {k-1} $. This is once.
Next, two monsters with HP of $ 2 ^ {k-2} $. This is twice.
Next is a $ 2 ^ 2 $ monster with $ 2 ^ {k-3} $, this is $ 2 ^ 2 $ times.
...
This is repeated, and when you finally hit a $ 2 ^ {k-1} $ monster with HP1 for $ 2 ^ {k-1} $ times, you win.
Let's make it a mathematical formula.
If you want to follow the conversion here properly, please use the formula of the sum of geometric progressions.
You can get the answer by "replace the value with $ 2 ^ {k-1} $" and "output $ 2 ^ {k} -1 $". I wrote the code below.
H = int(input())
k = 0
while H:
H //= 2
k += 1
print(2**k-1)
The magic power $ A_i $ and the consumption magic power $ B_i $ are passed. It is a question to answer as little magic power as possible to scrape off the given H.
I submitted it in a simple DP and it passed. Just store the minimum magic power consumed for each HP value in the array and update the minimum value in order. I'm getting used to dynamic programming.
H, N = map(int, input().split())
magic = [tuple(map(int, input().split())) for _ in range(N)]
DP = [0] + [10**9]*H
for h in range(H):
for damage, mp in magic:
DP[min(h + damage, H)] = min(DP[min(h + damage, H)], DP[h] + mp)
print(DP[H])
However, only PyPy3 passed this, and TLE came out in Python3. Looking at what happened with python, there was an answer that speeded up by using comprehension notation. I will rewrite it.
H, N = map(int, input().split())
magic = [tuple(map(int, input().split())) for _ in range(N)]
DP = [0] * (H+10**4)
for h in range(1, H+1):
DP[h] = min(DP[h - damage] + mp for damage, mp in magic)
print(DP[H])
Note that the meaning of h, which is turned by for, is different from the previous code. Now it passed in python.
That's all for this article. Even though it was a past contest, I am happy that it was the first time I was able to solve the E question on my own.
Recommended Posts