Official

C - Triple Attack Editorial by en_translator


Let us call the frontmost enemy with health \(1\) or more simply “the next enemy.”

If the next enemy has a health of \(5\) or greater, then we can reduce the health of the next enemy by \(5\) regardless of current \(T\). This set of three actions is repeated \(\lfloor\frac{H}{5}\rfloor\), where \(H\) is the health of the next enemy. By processing this repetition at once and simulating the other parts naively, the answer can be found in a total of \(O(N)\) time.

Sample code (Python)

N = int(input())
A = list(map(int,input().split()))
T = 0
for a in A:
  num = a//5
  T += num*3
  a -= num*5
  while a>0:
    T+=1
    if T%3==0:
      a-=3
    else:
      a-=1

print(T)

posted:
last update: