Problem:


Problem C : War

A国とB国という２つの国が戦争をしている。A国の軍人であるあなたはn人の兵士を率いて、B国の領土を占領する事になった。

B国の領土は２次元グリッドで表されている。あなたが最初に占領する場所は二次元グリッド上のある１マスである。
あなたが率いている兵士たちは、それぞれh_iの体力を持っている。
それぞれの兵士は体力を1を消費して移動することができる。
現在いるマスを(a,b)とすると、(a+1,b),(a-1,b),(a,b+1),(a,b-1)の4方向を移動先として選ぶことが可能である。
兵士は体力が0になったらそこから動くことができなくなる。
一人以上の兵士が通過したマスはすべて占領することができる。

あなたの仕事は、最大でいくつのマスを占領することができるかを求めることである。

ただし、この２次元グリッドのサイズは無限に広いとすること。

Input

入力は以下のフォーマットで与えられる。

n
h1
.
.
.
hn

入力は以下の制約を満たす

1 ≤ n ≤ 500

1 ≤ hi ≤ 10,000,000

Output

答えの値を１行に出力せよ

Sample Input 1

2
5
5

Sample Output 1

11

Sample Input 2

10
10
10
10
10
10
10
10
10
10
10

Sample Output 2

93

Sample Input 3

5
1
2
3
4
5

Sample Output 3

15



Sample input:
2
5
5


Sample output:
11

Submission status: Wrong Answer

Solution code:
# Edit: 2014/09/09
# Lang: Python3
# Time: .00s

from itertools import product
from math import factorial

if __name__ == "__main__":

    n = int(input())
    # print("n:",n)
    hl = []

    for i in range(n):
        hl.append(int(input()))
    #print(hl)

    #hl = [5, 5]
    #hl = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
    # hl = [1,2,3,4,5]
    #hl = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    i = 0
    ans = 1

    """
    for h in hl:
        d = i//4
        a = h-d
        if a<0:
            a=0
        ans += a
        i+=1
    """

    for i, h in enumerate(hl):  #return index, value
        d = i // 4
        a = h - d
        if a < 0:
            a = 0
        ans += a
    print(ans)

Submission status: Wrong Answer

Solution code:
# Edit: 2014/09/14
# Lang: Python3
# Time: .00s

if __name__ == "__main__":

    n = int(input())
    # print("n:",n)
    hl = []

    for i in range(n):
        hl.append(int(input()))
    # print(hl)

    # hl = [5, 5]
    # hl = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
    # hl = [1,2,3,4,5]
    #hl = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    i = 0
    d = 0
    ans = 1

    for i, h in enumerate(hl):  # return index, value
        #d = i // 4
        a = h - d
        if a < 0:
            a = 0
        ans += a
        if i % 4 == 3:
            d += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
# Edit: 2014/09/14
# Lang: Python3
# Time: .00s

if __name__ == "__main__":

    n = int(input())
    # print("n:",n)
    hl = []

    for i in range(n):
        hl.append(int(input()))
    # print(hl)

    # hl = [5, 5]
    # hl = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
    # hl = [1,2,3,4,5]
    #hl = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    i = 0
    d = 0
    ans = 1

    sorted(hl,reverse=True)

    for i, h in enumerate(hl):  # return index, value
        #d = i // 4
        a = h - d
        if a < 0:
            a = 0
        ans += a
        if i % 4 == 3:
            d += 1
    print(ans)
    #print(type(ans))

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
ans=1
A=[]
for i in range(N):
    A.append(int(raw_input()))
A.sort()
base=0
for i in range(N):
    if i==2:
        base += 1
        ans  += 1
    elif (i-2)%4==2 and i!=0:
        ans+=1
    elif (i-2)%4==0 and i!=0:
        base += 1 
        ans  += 1
    ans+=A.pop(0)-base
print ans

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
A=[]
for i in range(N):
    A.append(int(raw_input()))
A.sort()
B=[x/4 for x in range(N+2)][2:]
C=[]
for i in range(N):
    if A[i]-B[i]>=0: C.append(A[i]-B[i])
ans=sum(C)+(len(C)-1)/2+1
print ans

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
A=[]
for i in range(N):
    A.append(int(raw_input()))
A.sort()
B=[x/4 for x in range(N+2)][2:]
C=[]
for i in range(N):
    if A[i]-B[i]>=0: C.append(A[i]-B[i])
D=[x%4<2 for x in range(len(C[2:]))]
ans=sum(C)+sum(D)+1
print ans

Submission status: Wrong Answer

Solution code:
N=int(raw_input())
A=[]
for i in range(N):
    A.append(int(raw_input()))
A.sort()
B=[x/4 for x in range(N+2)][2:]
C=[]
j=0
for i in range(N):
    if A[i]-B[j]>=0:
        C.append(A[i]-B[j])
        j+=1
D=[x%4<2 for x in range(len(C[2:]))]
ans=sum(C)+sum(D)+1
print ans

Submission status: Accepted

Solution code:
# AOJ 1502: War
# Python3 2018.7.13 bal4u

n = int(input())
ans = 1
h = [0]*126
for i in range(n):
	v = int(input())
	if v <= 125: h[v] += 1
	ans += v
s = 0
for i in range(1, 126):
	s += h[i-1]
	if n > s+4*i: ans -= n-(s+4*i)
print(ans)

Submission status: Accepted

Solution code:
# Edit: 2014/09/14
# Lang: Python3
# Time: .00s

if __name__ == "__main__":

    n = int(input())
    # print("n:",n)
    hl = []

    for i in range(n):
        hl.append(int(input()))
    # print(hl)

    # hl = [5, 5]
    # hl = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
    # hl = [1,2,3,4,5]
    # hl = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    i = 0
    d = 0
    ans = 1

    hl = sorted(hl, reverse=True)

    for i, h in enumerate(hl):  # return index, value
        #d = i // 4
        a = h - d
        if a < 0:
            a = 0
        ans += a
        if i % 4 == 3:
            d += 1
    print(ans)
    #print(type(ans))

Submission status: Accepted

Solution code:
a=sorted([int(input()) for _ in [0]*int(input())])
c=b=0
for i in range(len(a)-1,-1,-1):
    if a[i]<c//4:continue
    else:b+=a[i]-c//4
    c+=1
print(b+1)

Submission status: Accepted

Solution code:
a=sorted([int(input()) for _ in [0]*int(input())])
c=b=0
for i in range(len(a)-1,-1,-1):
    if a[i]>=c//4:b+=a[i]-c//4
    c+=1
print(b+1)

Submission status: Accepted

Solution code:
n = int(input())
h_lst = sorted([int(input()) for _ in range(n)])


def solve():
    ans = 1
    cnt = 0
    while h_lst:
        for _ in range(4):
            if h_lst:
                add = h_lst.pop() - cnt
                if add <= 0:return ans
                ans += add
            else:
                return ans
        cnt += 1
    return ans


print(solve())

Submission status: Runtime Error

Solution code:
    n = int(input())
    # print("n:",n)
    hl = []

    for i in range(n):
        hl.append(int(input()))
    #print(hl)

    #hl = [5, 5]
    #hl = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
    # hl = [1,2,3,4,5]
    #hl = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    i = 0
    ans = 1

    """
    for h in hl:
        d = i//4
        a = h-d
        if a<0:
            a=0
        ans += a
        i+=1
    """

    for i, h in enumerate(hl):  #return index, value
        d = i // 4
        a = h - d
        if a < 0:
            a = 0
        ans += a
    print(ans)