Zonal Computing Olympiad 2012, 26 Nov 2011

It's dinner time in Castle Camelot, and the fearsome Knights of the Round Table are clamouring for dessert. You, the chef, are in a soup.  There are N knights, including King Arthur, each with a different preference for dessert, but you cannot afford to make desserts for all of them.

You are given the cost of manufacturing each Knight's preferred dessert–since it is a round table, the list starts with the cost of King Arthur's dessert, and goes counter-clockwise.

You decide to pick the cheapest desserts to make, such that for every pair of adjacent Knights, at least one gets his dessert. This will ensure that the Knights do not protest.<p>A strange feature of the Knights is that they will not complain about not getting dessert unless they get support from both their neighbours.  So, you decide to pick the cheapest desserts to make, such that for every pair of adjacent Knights, at least one gets his dessert.</p>

What is the minimum cost of tonight's dinner, given this condition?

For instance, suppose there are 5 Knights and their desserts cost 1, 2, 1, 2 and 2.  In this case, the minimum cost is 4, which you can achieve by feeding the first, third and fourth (or fifth) Knights.  

-----Input format-----
There are 2 lines of input.  The first line contains a single integer N, the number of seats at the table. The next line contains N space separated integers, each being the cost of the dessert of a Knight, listed in counterclockwise order around the table, starting with King Arthur.

-----Output format-----
The output should be a single line containing a single integer, the minimum possible cost for you, the chef.

-----Testdata-----
Each Knight's dessert costs strictly more than 0 and strictly less than 1000.  You may assume that 1 ≤ N ≤ 106.  In 30% of the test cases, 1 ≤ N ≤ 103.

- Subtask 1 (30 marks)
- Subtask 2 (70 marks)

-----Sample Input-----
5
1 2 1 2 2

-----Sample Output-----
4

Difficulty: interview

Starter code:

Solutions:
n=int(input())
ar=list(map(int,input().split()))
dp=[0]*n 
dp[0]=ar[0]
dp[1]=ar[1]
for i in range(2,n):
    dp[i]=min(dp[i-2],dp[i-1])+ar[i]
    
ar.reverse()
#print(ar)
dp1=[0]*n 
dp1[0]=ar[0]
dp1[1]=ar[1]
for i in range(2,n):
    dp1[i]=min(dp1[i-2],dp1[i-1])+ar[i]
print(min(dp[-1],dp1[-1]))

n=int(input())
arr=list(map(int,input().split()))
# if(n==1):
#     print(arr[-1])
# elif(n==2):
#     print(min(arr))
# else:
if(n>0):
    dp=[0 for i in range(n)]
    dp[0]=arr[0]
    dp[1]=arr[1]
    for i in range(2,n):
        dp[i]=arr[i]+min(dp[i-1],dp[i-2])
    comp=(dp[-1])
    dp[1]+=dp[0]
    for i in range(2,n-1):
        dp[i]=arr[i]+min(dp[i-1],dp[i-2])
    print(min(comp,dp[n-2]))
    
    
# [3,2,3,4,5,5]
# [3,2,1,2,2,1]


# cook your dish here
def fun(arr,n):
    cost = [0]*n 
    cost[n-1] = arr[n-1]
    if(n>=2):
        cost[n-2] = arr[n-2]
        for i in range(n-3,-1,-1):
            cost[i] = min(cost[i+1],cost[i+2]) + arr[i]
    return cost[0]
    
n = int(input())
a = list(map(int,input().split()))
b = list(reversed(a))

print(min(fun(a,n),fun(b,n)))


# cook your dish here

import math

N = int(input().strip())
costs = [int(i) for i in input().strip().split(" ")]
stored_val_1 = [costs[0], costs[0] + costs[1]]
stored_val_2 = [math.inf, costs[1]]
for idx, cost in enumerate(costs[2:]):
    stored_val_1.append(cost + min(stored_val_1[-1], stored_val_1[-2]))

for idx, cost in enumerate(costs[2:]):
    stored_val_2.append(cost + min(stored_val_2[-1], stored_val_2[-2]))

print(min(stored_val_1[-1], stored_val_1[-2], stored_val_2[-1]))



#=''
import sys
input=sys.stdin.readline
n=int(input())
l=input().split()
li=[int(i) for i in l]
if(n==1):
    print(0)
    return
if(n==2):
    print(min(li))
    return
if(n==3):
    li.sort()
    print(li[0]+li[1])
    return
z=list(li[1:])
ans=li[0]
k=len(z)
dp=[[0 for i in range(2)]for i in range(k)]
dp[0][1]=z[0]
dp[1][0]=z[0]
dp[1][1]=z[1]
for i in range(2,k):
    dp[i][0]=z[i-1]+min(dp[i-2][0],dp[i-2][1])
    dp[i][1]=z[i]+min(dp[i-1][0],dp[i-1][1])
ans=ans+min(dp[-1][0],dp[-1][1])
z=list(li[2:-1])
ok=li[1]+li[-1]
k=len(z)
if(k>=2):
    dp=[[0 for i in range(2)]for i in range(k)]
    dp[0][1]=z[0]
    dp[1][0]=z[0]
    dp[1][1]=z[1]
    for i in range(2,k):
        dp[i][0]=z[i-1]+min(dp[i-2][0],dp[i-2][1])
        dp[i][1]=z[i]+min(dp[i-1][0],dp[i-1][1])
    ok=ok+min(dp[-1][0],dp[-1][1])
print(min(ans,ok))


# cook your dish here
import sys
input=sys.stdin.readline
n=int(input())
l=input().split()
li=[int(i) for i in l]
if(n==1):
    print(0)
    return
if(n==2):
    print(min(li))
    return
if(n==3):
    li.sort()
    print(li[0]+li[1])
    return
z=list(li[1:])
ans=li[0]
k=len(z)
dp=[[0 for i in range(2)]for i in range(k)]
dp[0][1]=z[0]
dp[1][0]=z[0]
dp[1][1]=z[1]
for i in range(2,k):
    dp[i][0]=z[i-1]+min(dp[i-2][0],dp[i-2][1])
    dp[i][1]=z[i]+min(dp[i-1][0],dp[i-1][1])
ans=ans+min(dp[-1][0],dp[-1][1])
z=list(li[1:-1])
ok=li[1]+li[-1]
k=len(z)
if(k>=2):
    dp=[[0 for i in range(2)]for i in range(k)]
    dp[0][1]=z[0]
    dp[1][0]=z[0]
    dp[1][1]=z[1]
    for i in range(2,k):
        dp[i][0]=z[i-1]+min(dp[i-2][0],dp[i-2][1])
        dp[i][1]=z[i]+min(dp[i-1][0],dp[i-1][1])
    ok=ok+min(dp[-1][0],dp[-1][1])
print(min(ans,ok))


# cook your dish here
import sys
input=sys.stdin.readline
n=int(input())
l=input().split()
li=[int(i) for i in l]
if(n==1):
    print(0)
    return
if(n==2):
    print(min(li))
    return
if(n==3):
    li.sort()
    print(li[0]+li[1])
    return
z=list(li[1:])
ans=li[0]
k=len(z)
dp=[[0 for i in range(2)]for i in range(k)]
dp[0][1]=z[0]
dp[1][0]=z[0]
dp[1][1]=z[1]
for i in range(2,k):
    dp[i][0]=z[i-1]+min(dp[i-2][0],dp[i-2][1])
    dp[i][1]=z[i]+min(dp[i-1][0],dp[i-1][1])
ans=ans+min(dp[-1][0],dp[-1][1])
print(ans)


# cook your dish here
n=int(input())
array=list(map(int, input().split()))
array2=array.copy()
if n==1:
    print(array)
elif n==2:
    print(min(array[0],array[1]))
else:
    array[1]+=array[0]
    for i in range(2,n):
        array[i]+=min(array[i-1],array[i-2])
    minimo=min(array[-1],array[-2])
    array2[2]+=array2[1]
    for i in range(3,n):
        array2[i]+=min(array2[i-1],array2[i-2])
    print(min(minimo, array2[-1]))

# cook your dish here
n=int(input())
l=list(map(int,input().split()))
d=l.copy()
for i in range(2,n):
    mini=min(d[i-1],d[i-2])
    d[i]+=mini
f=l.copy()
f=f[::-1]
for i in range(2,n):
    mini=min(f[i-1],f[i-2])
    f[i]+=mini
print(min(f[-1],d[-1]))

# cook your dish here

n=int(input())
l=list(map(int,input().split()))
d=l.copy()
for i in range(2,n):
    mini=min(d[i-1],d[i-2])
    d[i]+=mini
f=l.copy()
f=f[::-1]
for i in range(2,n):
    mini=min(f[i-1],f[i-2])
    f[i]+=mini
print(min(f[-1],d[-1]))

n=int(input())
l=list(map(int,input().split()))
d=l.copy()
for i in range(2,n):
    mini=min(d[i-1],d[i-2])
    d[i]+=mini
f=l.copy()
f=f[::-1]
for i in range(2,n):
    mini=min(f[i-1],f[i-2])
    f[i]+=mini
print(min(f[-1],d[-1]))

n=int(input())
l=list(map(int,input().split()))
d=l.copy()
d.append(0)
for i in range(2,n+1):
    mini=min(d[i-1],d[i-2])
    d[i]+=mini
if(d[-1]==d[-2]):
    print(d[-1])
else:
    f=l.copy()
    f.append(0)
    c=l[0] 
    for i in range(3,n+1):
        mini=min(f[i-1],f[i-2])
        f[i]+=mini
    if(f[-1]==f[-3]):
        print(f[-1]+c)
    else:
        print(d[-1])

n=int(input())
l=list(map(int,input().split()))
d=l.copy()
d.append(0)
for i in range(2,n+1):
    mini=min(d[i-1],d[i-2])
    d[i]+=mini
if(d[-1]==d[-2]):
    print(d[-1])
else:
    f=l.copy()
    f.append(0)
    c=l[0]
    for i in range(3,n+1):
        mini=min(f[i-1],f[i-2])
        f[i]+=mini
    if(f[-1]==f[-3]):
        print(f[-1]+c)
    else:
        print(f[-2])

n=int(input())
l=list(map(int,input().split()))
d=l.copy()
d.append(0)
c=d[0]
for i in range(3,n+1):
    mini=min(d[i-1],d[i-2])
    d[i]+=mini
print(c+d[-1])

n = int(input())
a = list(map(int, input().split()))
if n==1:
    print(a[0])
elif n==2:
    print(min(a[0],a[1]))
else :
    dp = [0]*n
    dp[0] = a[0]
    dp[1] = a[1]
    for i in range(2,n):
        dp[i] = a[i] + min(dp[i-2], dp[i-1])
    result1 = dp[n-1]
    dp = [0]*n
    dp[n-1] = a[n-1]
    dp[n-2] = a[n-2]
    for i in range(n-3,-1,-1):
        dp[i] = a[i] + min(dp[i+2], dp[i+1])
    result = min(dp[0], result1)
    print(result)


n = int(input())
a = list(map(int, input().split()))
if n==1:
    print('-1')
elif n==2:
    print(min(a[0],a[1]))
else :
    dp = [0]*n
    dp[0] = a[0]
    dp[1] = a[1]
    for i in range(2,n):
        dp[i] = a[i] + min(dp[i-2], dp[i-1])
    result1 = dp[n-1]
    dp = [0]*n
    dp[n-1] = a[n-1]
    dp[n-2] = a[n-2]
    for i in range(n-3,-1,-1):
        dp[i] = a[i] + min(dp[i+2], dp[i+1])
    result = min(dp[0], result1)
    print(result)


n = int(input())
a = list(map(int, input().split()))
if n==1:
    print('0')
elif n==2:
    print(min(a[0],a[1]))
else :
    dp = [0]*n
    dp[0] = a[0]
    dp[1] = a[1]
    for i in range(2,n):
        dp[i] = a[i] + min(dp[i-2], dp[i-1])
    result1 = dp[n-1]
    dp = [0]*n
    dp[n-1] = a[n-1]
    dp[n-2] = a[n-2]
    for i in range(n-3,-1,-1):
        dp[i] = a[i] + min(dp[i+2], dp[i+1])
    result = min(dp[0], result1)
    print(result)


# cook your dish here
import sys

N=int(sys.stdin.readline())
A=[int(i) for i in sys.stdin.readline().split()]

dp1=[]
dp2=[]

for i in range(N+1):
    dp1.append([-1,-1])
    dp2.append([-1,-1])

# dp1 initializations    
dp1[0][0]=0
dp1[0][1]=0
dp1[1][0]=0
dp1[1][1]=2e9

# dp2 initializations
dp2[0][0]=0
dp2[0][1]=0
dp2[1][0]=2e9
dp2[1][1]=A[0]

for x in range(2,N+1):
    dp1[x][0]=dp1[x-1][1]
    dp1[x][1]=min(dp1[x-1][0],dp1[x-1][1])+A[x-1]
    
    dp2[x][0]=dp2[x-1][1]
    dp2[x][1]=min(dp2[x-1][0],dp2[x-1][1])+A[x-1]

ans=min(min(dp1[N][1],dp2[N][0]),dp2[N][1])
print(ans)
    


def solve(array):
    N = len(array)
    dp = [array[0], array[1]]
    for i in range(2, N):
        dp.append(array[i] + min(dp[i - 2], dp[i - 1]))
    return dp[N - 1]

N = int(input())
costs = list(map(int, input().split()))

if N == 1:
    print(0)
elif N == 2:
    print(min(costs))
else:
    print(min(solve(costs), solve(costs[-1::-1])))


import sys
read = sys.stdin.readline
n = int(read())
a = list(map(int , read().split()))
b = [i for i in a]
boola = [False for i in range(n)]
#ans = 0
for i in range(2,n):
    a[i] += min(a[i-1],a[i-2])
#print(*boola)
b.reverse()
for i in range(2,n):
    b[i] += min(b[i-1],b[i-2])
#x = min(a[-1],a[-2])
#y = min(b[-1],b[-2])
print(min(a[-1],b[-1]))

# cook your dish here
import copy
N = int(input())
list1 = list(map(int,input().split()))
list2 = copy.deepcopy(list1)
for i in range(len(list1)-3,-1,-1):
    list1[i] += min(list1[i+1],list1[i+2])
for j in range(2,len(list2)):
    list2[j] += min(list2[j-1],list2[j-2])
answer = min(list1[0], list2[-1])
#print(list1,list2)
print(answer)

#this time it will work
try:
    n = int(input())
    l = list(map(int , input().split()))
except:
    return
ans = [0] * n
anss = [0] * n
ans[0] = l[0]
ans[1] = l[1]
for i in range(2,n):
    ans[i] = min(ans[i-1],ans[i-2]) + l[i]
l.reverse()
anss[0] = l[0]
anss[1] = l[1]
for i in range(2,n):
    anss[i] = min(anss[i-1],anss[i-2]) + l[i]
print(min(ans[-1],anss[-1]))



# cook your dish here
n = int(input())
cost = list(map(int, input().split()))
def func(arr,n):
    a = [0]*n 
    a[0] = arr[0]
    a[1] = arr[1]
    for i in range(2,n):
        a[i] = arr[i] + min(a[i-1],a[i-2])
    return a[-1]
ans1 = func(cost,n)
cost.reverse()
ans2 = func(cost,n)
print(min(ans1,ans2))

n = int(input())
cost = list(map(int, input().split()))
def func(arr,n):
    a = [0]*n 
    a[0] = arr[0]
    a[1] = arr[1]
    for i in range(2,n):
        a[i] = arr[i] + min(a[i-1],a[i-2])
    return a[-1]
ans1 = func(cost,n)
cost.reverse()
ans2 = func(cost,n)
print(min(ans1,ans2))