とてもシンプルな問題。
概要
- $n, a, b, k$が与えられる。
- n体のそれぞれ$h1, h2, \cdots ,hn$の体力を持つ
- 攻撃力aのあなたと、攻撃力bのライバルがいる。
- あなたは攻撃する敵を任意に選び、あなた->ライバルの順番に敵が倒れる(hp <= 0になる)まで攻撃を続ける
- あなたは全部でk回だけ、ライバルの行動をスキップできる(これをスキップと呼ぶ)
- あなたは最大で何体の敵にとどめを刺せるか？
例と考え方
- パラメータ: 6 2 3 3
- 敵: 7, 10 50 12 1 8 まず、1ターン(自分と相手の攻撃1回ずつ)で変動する敵のhpはa + bであるため、相手が倒れる直前のターンまでのダメージを引く、つまり、各hpをmod (a + b) = mod 5する。
- modした敵のhp: 2, 0, 0, 2, 3 12について例をとると、1ターン目、12 - 2 - 3 = 7 ⇒ 2ターン目、7 - 2 - 3 = 2になっているといった次第である。ところで、hp=0の値を5に変える。なぜなら、各ターンは相手のターンで終わるため、modをとって、hp = 0 となるケースは相手が倒してしまっているからである。
- modした敵のhp: 2, 5, 5 2, 3 この中で、hp <= a = 2の値を削り、得点とする。これらの敵は次のターンで必然的に倒せるからである。残りをソートすると
- 残りの敵: 3, 5, 5 となり、通常であればこれらの敵は、相手に倒される。しかし、各敵は、a + (a*k) >= 残りhpとなる最小のkのスキップを行えば倒すことができる。 残りの敵は倒すことができない。
実装
n, a, b, k = map(int,input().split())
odat = list(map(int, input().split()))
point = 0
dat = []
x = a + b # 1ターンで減る体力
for i in range(n):
if 0 < (odat[i] % x) <= a: # 確実に倒せる敵
point += 1
continue
# 倒せなかった敵はその数をリストに追加(0はa+bに変換)
sonota = odat[i] % x
dat.append(x if sonota == 0 else sonota)
# ソートする
dat.sort()
import math
for i in range(len(dat)):
# 必要となるkを計算する
needk = math.ceil(dat[i] / a) - 1
# まだスキップ回数が余っているなら使う
if needk <= k:
k -= needk
point += 1
else:
# スキップ回数が足りないなら終了
# ソートしているのでこれより後の敵を倒せるわけがないから
break
print(point)