Zonal Computing Olympiad 2014, 30 Nov 2013

In ICO School, all students have to participate regularly in SUPW.  There is a different SUPW activity each day, and each activity has its own duration.  The SUPW schedule for the next term has been announced, including information about the number of minutes taken by each activity.

Nikhil has been designated SUPW coordinator.  His task is to assign SUPW duties to students, including himself.  The school's rules say that no student can go three days in a row without any SUPW duty.

Nikhil wants to find an assignment of SUPW duty for himself that minimizes the number of minutes he spends overall on SUPW.

-----Input format-----
Line 1: A single integer N, the number of days in the future for which SUPW data is available.
Line 2: N non-negative integers, where the integer in position i represents the number of minutes required for SUPW work on day i.

-----Output format-----
The output consists of a single non-negative integer, the minimum number of minutes that Nikhil needs to spend on SUPW duties this term 

-----Sample Input 1-----
10
3 2 1 1 2 3 1 3 2 1

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

(Explanation: 1+1+1+1)

-----Sample Input 2-----
8
3 2 3 2 3 5 1 3

-----Sample Output 2-----
5

(Explanation: 2+2+1)

-----Test data-----
There is only one subtask worth 100 marks.  In all inputs:

• 1 ≤ N ≤ 2×105
• The number of minutes of SUPW each day is between 0 and
104, inclusive.

-----Live evaluation data-----
There are 12 test inputs on the server during the exam.

Difficulty: interview

Starter code:

Solutions:
import math
n = int(input())
a=list(map(int,input().split()))
dp = [0 for x in range(n)]
dp[0] = a[0]
dp[1] = a[1]
dp[2] = a[2]
for x in range(3,n):
    dp[x] = a[x] + min(dp[x-1],dp[x-2],dp[x-3])

print(min(dp[-3:]))


# cook your dish here
INT_MAX=1000000000000000000
n=int(input())
ar=list(map(int,input().split()))
br=[0]*1 
br.extend(ar)
del ar

for i in range(n-3,0,-1):
   br[i]=min(br[i+1],br[i+2],br[i+3])+br[i]
    
print(min(br[1:4]))


import sys
def time(i, free):
    if free == 3:
        return sys.maxsize
    elif i == n:
        return 0
    elif mt[i][free] != -1:
        return mt[i][free]
    else:
        mt[i][free] =  min(minutes[i] + time(i+1, 0), time(i+1, free+1))
        return mt[i][free]
 
n = int(input().strip())
minutes = list(map(int, input().strip().split()))
 
sys.setrecursionlimit(3*n)
 
mt = [[-1 for i in range(3)] for j in range(n)]
 
print(time(0, 0))

# cook your dish here
n=int(input())
arr=[int(x) for x in input().split()]
if n<3:
    ans=min(arr)
    print(ans)
else:
    dp=[None for x in range(n)]
    dp[0]=arr[0];dp[1]=arr[1];dp[2]=arr[2]
    for i in range(3,n):
        dp[i]=min(dp[i-1],dp[i-2],dp[i-3])+arr[i]
    print(min(dp[-1],dp[-2],dp[-3]))


# cook your dish here
n=int(input())
arr=list(map(int,input().split()))
i=0
if(n<3):
    print(0)
    return
dp=[n for n in arr]
for i in range(3,n):
    dp[i]=arr[i]+min(dp[i-1],dp[i-2],dp[i-3])
print(min(dp[-1],dp[-2],dp[-3]))

# cook your dish here
import math
n = int(input())
a = [int(i) for i in input().split()]
dp = [0 for i in range(n)]
dp[0] = a[0]
dp[1] = a[1]
dp[2] = a[2]
for i in range(3,n):
    dp[i] = a[i] + min(dp[i-1],dp[i-2],dp[i-3])
ans = min(dp[-3:])
print(ans)


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


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


n = int(input())
nums = list(map(int, input().split()))
if n < 3:
    print(0)
else:
    for i in range(3, n):
        nums[i] = nums[i] + min(nums[i-1], nums[i-2], nums[i-3])
    print(min(nums[-1], nums[-2], nums[-3]))

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


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


# ZOC14002
dp = [-1] * int(1e6)

def solve(nums, n) : 
    
    if n < 2 : return 0
    
    if dp[n] != - 1 : return dp[n]
    
    dp[n] = min( nums[n] + solve(nums, n - 1),
                 nums[n - 1] + solve(nums, n - 2),
                 nums[n - 2] + solve(nums, n - 3)
               )
               
    return dp[n]

        
def main(): 
    from sys import stdin, stdout, setrecursionlimit
    setrecursionlimit(int(5e5))
    N = int(input())
    hours = list(map(int, input().split()))
    solution = solve(hours, N - 1)
    print(solution)
	

main()
    


# ZOC14002
dp = [-1] * int(1e6)

def solve(nums, n) : 
    
    if n < 2 : return 0
    
    if dp[n] != - 1 : return dp[n]
    
    dp[n] = min( nums[n] + solve(nums, n - 1),
                 nums[n - 1] + solve(nums, n - 2),
                 nums[n - 2] + solve(nums, n - 3)
               )
               
    return dp[n]

        
def main(): 
    from sys import stdin, stdout, setrecursionlimit
    setrecursionlimit(int(5e5))
    N = int(input())
    hours = list(map(int, input().split()))
    solution = solve(hours, N - 1)
    print(solution)
	

main()
    


# cook your dish here

N = int(input().strip())
activity_choices = [int(i) for i in input().strip().split(" ")]
stored_values = activity_choices[:3]
for i in range(3, N):
    stored_values.append(activity_choices[i] + min(stored_values[-1], stored_values[-2], stored_values[-3]))
print(min(stored_values[-1], stored_values[-2], stored_values[-3]))



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


dp = [-1] * int(1e6)

def solve(nums, n) : 
    
    if n < 2 : return 0
    
    if dp[n] != - 1 : return dp[n]
    
    dp[n] = min( nums[n] + solve(nums, n - 1),
                 nums[n - 1] + solve(nums, n - 2),
                 nums[n - 2] + solve(nums, n - 3)
               )
               
    return dp[n]

        
def main(): 
    from sys import stdin, stdout, setrecursionlimit
    setrecursionlimit(int(5e5))
    N = int(input())
    hours = list(map(int, input().split()))
    solution = solve(hours, N - 1)
    print(solution)
	

main()
    


dp = [-1] * int(1e6)

def solve(nums, n) : 
    
    if n < 2 : return 0
    
    if dp[n] != - 1 : return dp[n]
    
    dp[n] = min( nums[n] + solve(nums, n - 1),
                 nums[n - 1] + solve(nums, n - 2),
                 nums[n - 2] + solve(nums, n - 3)
               )
               
    return dp[n]

        
def main(): 
    from sys import stdin, stdout, setrecursionlimit
    setrecursionlimit(int(5e5))
    N = int(input())
    hours = list(map(int, input().split()))
    solution = solve(hours, N - 1)
    print(solution)
	

main()
    


import math
n = int(input())
a = [int(i) for i in input().split()]
dp = [0 for i in range(n)]
dp[0] = a[0]
dp[1] = a[1]
dp[2] = a[2]
for i in range(3,n):
    dp[i] = a[i] + min(dp[i-1],dp[i-2],dp[i-3])
ans = min(dp[-3:])
print(ans)

import sys
# import math as mt
# from collections import Counter
# from itertools import permutations
# from functools import reduce
# from heapq import nsmallest, nlargest, heapify, heappop, heappush, heapreplace

def get_inpt(): return sys.stdin.readline().strip()
def get_int(): return int(sys.stdin.readline().strip())
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))

# sys.setrecursionlimit(10**7)
# INF = float('inf')
# MOD1, MOD2 = 10**9+7, 998244353

n = get_int()
arr = get_array()

dp = [0 for _ in range(n)]

dp[-1] = arr[-1]
dp[-2] = arr[-2]
# dp[-3] = min(arr[-1], arr[-2], arr[-3])
dp[-3] = arr[-3]

for i in range(n-4, -1, -1):
   
   dp[i] = arr[i] + min(dp[i+1], dp[i+2], dp[i+3])
   
print(min(dp[0], dp[1], dp[2]))

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

from sys import stdin, stdout
import math,sys,heapq
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
from os import path
import random
import bisect as bi
def yes():print('YES')
def no():print('NO')
if (path.exists('input.txt')): 
    #------------------Sublime--------------------------------------#
    sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
    def I():return (int(input()))
    def In():return(map(int,input().split()))
else:
    #------------------PYPY FAst I/o--------------------------------#
    def I():return (int(stdin.readline()))
    def In():return(map(int,stdin.readline().split()))
#sys.setrecursionlimit(1500)
def dict(a):
    d={} 
    for x in a:
        if d.get(x,-1)!=-1:
            d[x]+=1
        else:
            d[x]=1
    return d
def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bi.bisect_left(a, x)
    if i != len(a):
        return i
    else:            
        return -1

def main():
    try:
        n=I()
        l=list(In())
        dp=[0 for x in range(n)]
        for x in range(n):
            if x<3:
                dp[x]=l[x]
            else:
                dp[x]=min(dp[x-1],dp[x-2],dp[x-3])+l[x]
        print(min(dp[-1],dp[-2],dp[-3]))
    except:
        pass
        
M = 998244353
P = 1000000007
 
def __starting_point():
    #for _ in range(I()):main()
    for _ in range(1):main()
__starting_point()

n = int(input())
a = list(map(int, input().split()))
for i in reversed(range(0,n-3)):
    a[i] += min(a[i+1],a[i+2],a[i+3])
print(min(a[:3]))

from sys import stdin,setrecursionlimit
setrecursionlimit(10**6)
def fn(pos):
    if pos>=n:return 0
    if pos in dp:return dp[pos]
    dp[pos]=a[pos]+min(fn(pos+1),fn(pos+2),fn(pos+3))
    return dp[pos]
for _ in range(1):#int(stdin.readline())):
    n=int(stdin.readline())
    a=list(map(int,stdin.readline().split()))
    dp={}
    if n<=2:
        print(min(a))
        continue
    print(min(fn(0),fn(1),fn(2)))

from sys import stdin,stdout
def fn(pos):
    if pos>=n:return 0
    if pos in dp:return dp[pos]
    op1=op2=op3=float('inf')
    op1=a[pos]+fn(pos+3)
    if pos+1<n:op2=a[pos+1]+fn(pos+3)
    if pos+2<n:op3=a[pos+2]+fn(pos+3)
    dp[pos]=min(op1,op2,op3)
    return dp[pos]
for _ in range(1):#int(stdin.readline())):
    n=int(stdin.readline())
    a=list(map(int,stdin.readline().split()))
    # print(dp)
    dp=[0]*n
    dp[0]=a[0]
    if n==1:
        print(dp[0])
        continue
    dp[1]=a[1]
    if n==2:
        print(min(dp))
        continue
    dp[2]=a[2]
    if n==3:
        print(min(dp))
        continue
    for i in range(3,n):
        dp[i]=min(dp[i-3],dp[i-1],dp[i-2])+a[i]
    print(min(dp[-1],dp[-2],dp[-3]))