Problem:


Problem E: Rabbit Plays Games!

うさぎがとあるロールプレイングゲームで遊んでいる. 城に入る直前で, 敵に待ち伏せされていた！

うさぎが操作する主人公1 人と, n 体の敵との戦闘となった. 各キャラクターには4 つの能力値, 体力hi, 攻撃力ai, 防御力di, 敏捷si が定められている. i = 0 は主人公の情報, 1 ≤ i ≤ n は各敵の情報を表す.

戦闘はターン制である. 各ターン, 生き残っているキャラクターが, 敏捷の値が高い順に攻撃を行う. 敵は必ず主人公を攻撃する. 主人公は敵1 体を攻撃するが, どの敵を攻撃するかは毎ターンごとに主人公が選べる.攻撃力a のキャラクターが防御力d のキャラクターに攻撃するとき, max{a − d, 0} のダメージが与えられる. 受けたダメージの合計が体力の値以上になったキャラクターは直ちに戦闘不能になってしまう. 主人公が戦闘不能になったとき, あるいは敵がすべて戦闘不能になったとき, 戦闘は終了する.

Input

1 ≤ n ≤ 40 000

1 ≤ hi, ai, di, si ≤ 1 000 000 000 (整数)

si はすべて異なる.

Output

主人公が必ず戦闘不能になってしまうとき, −1 を出力せよ. そうでないとき, 主人公が受けるダメージの合計の最小値を一行に出力せよ.

Sample Input 1

2
10 3 1 2
2 4 1 3
2 2 1 1

Sample Output 1

4

Sample Input 2

1
1 1 1 1
10000 10000 10000 10000

Sample Output 2

-1



Sample input:
2
10 3 1 2
2 4 1 3
2 2 1 1


Sample output:
4

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
D=[]
A0=[int(x) for x in input().split() ]
ans=0
for i in range(n):
    A.append([int(x) for x in input().split() ])
    d1=max(A[i][1] - A0[2], 0)
    d2=max(A0[1] - A[i][2], 0)
    if d2==0:
        if d1 > 0:
            ans=-1
            break
        else:
            timetokill=0
    else:
        timetokill=A[i][0]//d2 + ( A[i][0]%d2 != 0 ) - ( A0[3] > A[i][3] )
    D.append([d1,timetokill])
D.sort(key=lambda x: x[0], reverse=True)
pasttime=0
if ans==0:
    for d in D:
        pasttime += d[1]
        ans += d[0]*pasttime
if ans > A0[0]:
    ans=-1
print (ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
D=[]
A0=[int(x) for x in input().split() ]
ans=0
for i in range(n):
    A.append([int(x) for x in input().split() ])
    d1=max(A[i][1] - A0[2], 0)
    d2=max(A0[1] - A[i][2], 0)
    if d2==0:
        if d1 > 0:
            ans=-1
            break
        else:
            timetokill=0
    else:
        timetokill=A[i][0]//d2 + ( A[i][0]%d2 != 0 ) - ( A0[3] > A[i][3] )
    D.append([d1,timetokill])
D.sort(key=lambda x: x[0], reverse=True)
pasttime=0
if ans==0:
    for d in D:
        pasttime += d[1]
        ans += d[0]*pasttime
if ans >= A0[0]:
    ans=-1
print (ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
D=[]
A0=[int(x) for x in input().split() ]
ans=0
for i in range(n):
    A.append([int(x) for x in input().split() ])
    d1=max(A[i][1] - A0[2], 0)
    d2=max(A0[1] - A[i][2], 0)
    if d2==0:
        if d1 > 0:
            ans=-1
            break
        else:
            timetokill=0
    else:
        timetokill=A[i][0]//d2 + ( A[i][0]%d2 != 0 ) - ( A0[3] > A[i][3] )
    D.append([d1,timetokill,  A0[3] > A[i][3]])
D.sort(key=lambda x: x[1])
D.sort(key=lambda x: -x[0])
pasttime=0
if ans==0:
    for d in D:
        pasttime += d[1]
        ans += d[0]*pasttime
        pasttime+=d[2]
if ans >= A0[0]:
    ans=-1
print (ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(readline())
    ha, aa, da, sa = map(int, readline().split())
    ans = 0
    S = []
    for i in range(N):
        hi, ai, di, si = map(int, readline().split())
        m0 = max(ai - da, 0)
        if si > sa:
            ans += m0
        m1 = max(aa - di, 0)
        if m1 == 0 and m0 > 0:
            write("-1\n")
            return
        if m0 > 0:
            k = (hi + m1 - 1) // m1
            S.append((k, m0))
    S.sort(key = lambda x: x[0]/x[1])
    cur = 0
    for k, d in S:
        ans += (cur+k-1)*d
        cur += k
    if ans < ha:
        write("%d\n" % ans)
    else:
        write("-1\n")
solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

n = input()
H, A, D, S = map(int, raw_input().split())
ans = 0
flag = False
ls = []
for i in range(n):
    h, a, d, s = map(int, raw_input().split())
    a -= D
    if s < S:
        ans -= max(0, a)
    if A <= d and a > 0:
        flag = True
    elif a > 0:
        turn = h / (A - d)
        if h % (A - d) != 0:
            turn += 1
        ls.append((turn / float(a), turn, a))
if flag:
    print -1
    exit()
ls.sort()
S = 0
for p in ls:
    S += p[1]
    ans += S * p[2]
if ans < H:
    print ans
else:
    print -1