Problem:
 Max Score: 350 Points   Problem Statement There are N buildings along the line. The i -th building from the left is colored in color i , and its height is currently a_i meters. Chokudai is a mayor of the city, and he loves colorful thigs. And now he wants to see at least K buildings from the left.  You can increase height of buildings, but it costs 1 yens to increase 1 meters. It means you cannot make building that height is not integer. You cannot decrease height of buildings. Calculate the minimum cost of satisfying Chokudai's objective. Note: "Building i can see from the left" means there are no j exists that (height of building j ) ≥ (height of building i ) and j < i .       Input Format   N  K  a_1  a_2  a_3 ... a_N       Output Format Print the minimum cost in one line. In the end put a line break.    Constraints   1 ≤ K ≤ N ≤ 15  1 ≤ a_i ≤ 10^9     Scoring Subtask 1 [ 120 points]   N = K  Subtask 2 [ 90 points]   N ≤ 5  a_i ≤ 7  Subtask 3 [ 140 points]   There are no additional constraints.        Sample Input 1  5 5
3949 3774 3598 3469 3424    Sample Output 1  1541 The optimal solution is (height of buildings from the left) = [3949, 3950, 3951, 3952, 3953] .      Sample Input 2  5 3
7 4 2 6 4    Sample Output 2  7 The optimal solution is (height of buildings from the left) = [7, 8, 2, 9, 4] .

Solution (Python):
N, K = list(map(int, input().split()))
height = list(map(int, input().split()))
height2=height.copy()
ans = 10 ** 100









for i in range(2 ** N):
    cost = 0
    height2 = height.copy()
    if bin(i).count("1")==K:
        for j in range(1,N):
            if i >> j & 1:
                    tarou=max(height2[:j])
                    if height2[j]<=tarou:
                        cost+=tarou-height2[j]+1
                        height2[j]=tarou+1
        
        
        
        if ans > cost:
            ans = cost

print(ans)

Solution (Python):
N, K = list(map(int, input().split()))
height = list(map(int, input().split()))
height2=height.copy()
ans = 10 ** 10









for i in range(2 ** N):
    cost = 0
    height2 = height.copy()
    if bin(i).count("1")==K:
        for j in range(1,N):
            if i >> j & 1:
                    tarou=max(height2[:j])
                    if height2[j]<=tarou:
                        cost+=tarou-height2[j]+1
                        height2[j]=tarou+1
        if N==K:
            print(cost)
            exit()
        if ans > cost:
            ans = cost

print(ans)

Solution (Python):
N, K = list(map(int, input().split()))
height = list(map(int, input().split()))
height2=height.copy()
ans = 10 ** 10
if N==K:
    cost=0
    for i in range(1,N):
        tarou=max(height2[:i])
        if tarou>=height2[i]:
            cost+=tarou-height2[i]+1
            height2[i]=tarou+1
    print(cost)
    exit()
for i in range(2 ** N):
    cost = 0
    height2 = height.copy()
    if bin(i).count("1")==K:
        for j in range(1,N):
            if i >> j & 1:
                if N==K:
                    if height2[j-1]>=height2[j]:
                            cost+=height2[j-1]-height2[j]+1
                            height2[j]+=height2[j-1]-height2[j]+1
                else:
                    tarou=max(height2[:j])
                    if height2[j]<=tarou:
                        cost+=tarou-height2[j]+1
                        height2[j]=tarou+1

        if ans > cost:
            ans = cost

print(ans)

Solution (Python):
N, K = list(map(int, input().split()))
height = list(map(int, input().split()))
ans = 10 ** 10
if N==K:
    cost=0
    for i in range(1,N):
        if height[i-1]>=height[i]:
            cost+=height[i-1]-height[i]+1
            height[i]+=height[i-1]-height[i]+1
    print(cost)
    exit()
for i in range(2 ** N):
    count=1
    cost = 0
    height2 = height.copy()
    for j in range(N):
        if i >> j & 1:
            if j!=0:
                tarou=max(height2[:j])
                if height2[j]<=tarou:
                    cost+=tarou-height2[j]+1
                    height2[j]+=tarou-height2[j]+1
                    count+=1
                else:count+=1
    
    
    
    
    
    if ans > cost and count >= K:
        ans = cost

print(ans)

Solution (Python):


from itertools import combinations

N,K=map(int,input().split())
a=list(map(int,input().split()))

minc=10**12
ai=[i for i in range(N)]
for i in combinations(ai,K):
    ac=a[:]
    cost=0
    i=list(i)
    for j in range(1,K):
        costt=max(max(ac[:i[j]])-ac[i[j]]+1,0)
        ac[i[j]]+=costt
        cost+=costt
    minc=min(cost,minc)
print(minc)

Solution (Python):
n, k = map(int, input().split())

a = list(map(int, input().split()))

min_cost = float("inf")
for i in range(2**n):
    if bin(i).count("1") != k or not i & 1:
        continue

    min_h = a[0]
    cost = 0
    for j in range(1, n):
        if i >> j & 1:
            min_h += 1
            cost += max(0, min_h-a[j])

        min_h = max(min_h, a[j])

    min_cost = min(min_cost, cost)

print(min_cost)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))






result=10**100
for i in range(2**(n-1)):
    
    if str(bin(i)).count("1")>=k-1:
        
        bk=a[0]
        cost=0
        for j in range(n-1):
            if i>>j&1:
                if bk<a[j+1]:
                    bk=a[j+1]
                else:
                    bk+=1
                    cost+=(bk-a[j+1])
            else:
                bk=max(bk,a[j+1])
                
        result=min(cost,result)
print(result)

Solution (Python):
import itertools

n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
ans=[]

for li in itertools.product([0,1], repeat=n-1):
  if li.count(1) < k-1:
    continue
  cost,height=0,A[0]
  for i in range(1,n):
    if height < A[i]:
      height=A[i]
      continue
    if li[i-1]:
      cost += (height-A[i]+1)
      height += 1 
  ans.append(cost)
  
print(min(ans))

Solution (Python):
import sys
from collections import deque
import copy
def main():
    N, K = map(int, input().split())
    a = [int(i) for i in input().split()]
    ans = 10 ** 11
    for i in range(1 << N):
        now = a[0]
        count = 0
        copy_a = copy.copy(a)
        for j in range(1, N):
            if i >> j & 1:
                count += max(now + 1 - a[j], 0)
                copy_a[j] = max(now + 1, a[j])
            now = max(now, copy_a[j])
        now = 0
        color = 0
        for j in range(N):
            if now < copy_a[j]:
                color += 1
                now = copy_a[j]
        if color >= K:
            ans = min(ans, count)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import combinations
N, K = map(int, input().split())
A = list(map(int, input().split()))
mn = 10**18
for B in combinations(range(1,N),K-1):
    mx = A[0]
    score = 0
    for n in range(1,N):
        if n in B:
            if A[n] <= mx:
                mx += 1
                score += (mx - A[n])
            else:
                mx = A[n]
        else:
            mx = max(mx, A[n])
    mn = min(mn, score)
print (mn)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))

ans=10**100
for i in range(2**(N-1)):
  bit=format(i,'0'+str(N)+'b')
  bit=list(map(int,bit))
  maxh=A[0]
  price=0
  color=1
  for n in range(N):
    if n==0:continue
    elif bit[n]==0:
      if A[n]>maxh:
        color+=1
        maxh=A[n]
    else:
      if A[n]<=maxh:
        maxh+=1
        price+=maxh-A[n]
        color+=1
      else:
        color+=1
        maxh=A[n]
  if color>=K and price<=ans:
    ans=price
print(ans)

Solution (Python):
from itertools import combinations

N, K = map(int, input().split())

a = list(map(int, input().split()))
sub_a = {0}
a_first = a[0]

res = 10**11 

for j in range(N):
    if a_first < a[j]:
        sub_a.add(j)
        a_first = a[j]

colors = len(sub_a) 
not_sub_a = {i for i in range(N)} - sub_a


for k in combinations(not_sub_a, K - colors):
    cost = 0
    test_a = []
    for i in range(N):
        if i in sub_a or i in k:
            test_a.append(a[i]) 
    for i in range(len(test_a)-1):
        if test_a[i] >= test_a[i+1]:
            cost += test_a[i] - test_a[i+1] +1
            test_a[i+1] = test_a[i] + 1
    res = min(res, cost)

print(res)

Solution (Python):
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for comb in combinations(range(1, N), K - 1):
        included = set(comb)
        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if i in included:
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for comb in combinations(range(1, N), K - 1):
        included = set(comb)
        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if i in included:
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for comb in combinations(range(1, N), K - 1):
        included = [False] * N
        for i in comb:
            included[i] = True

        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if included[i]:
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for bit in range(1 << N):
        if (not (bit & 1)) or bin(bit).count('1') != K:
            continue

        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if bit & (1 << i):
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for comb in combinations(range(1, N), K - 1):
        included = [False] * N
        for i in comb:
            included[i] = True

        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if included[i]:
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for bit in range(1 << N):
        if (not (bit & 1)) or bin(bit).count('1') != K:
            continue

        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if bit & (1 << i):
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = float("inf")
for i in range(1,2**n):
    l = [j for j in range(n) if i>>j&1]
    if l[0] != 0 or len(l) != k:
        continue
    m = 0
    s = 0
    for j in range(n):
        if (j in l) and (a[j] <= m):
            s += m+1-a[j]
            m += 1
        m = max(m,a[j])
    
    ans = min(ans,s)

print(ans)

Solution (Python):

from itertools import product


def main():
    N, K = list(map(int, input().split()))
    a = list(map(int, input().split()))
    find = 0
    for i in range(1, N):
        if a[i-1] < a[i]:
            find += 1
    if find >= K:
        print(0)
        return

    first = a.pop(0)

    ans = float('inf')

    for bits in product((0, 1), repeat=N-1):
        build = a.copy()
        changeBuild = bits
        find = 1
        score = 0
        if sum(changeBuild) == 0:
            continue
        for i, v in enumerate(changeBuild):
            if i == 0:
                nowmax = first
            else:
                maxbuild = max(build[:i])
                nowmax = max(first, maxbuild)

            if v == 1 and nowmax >= build[i]:
                score += nowmax-build[i]+1
                build[i] = nowmax+1
            if i == 0 and first < build[i]:
                find += 1
            if i >= 1 and nowmax < build[i]:
                find += 1
        if find >= K:
            ans = min(ans, score)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import combinations

N, K = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))

min_cost = 10 ** 12
for indexes in combinations(range(N), r=K):
    indexes = set(indexes)
    highest = 0
    cost = 0
    for i in range(N):
        height = A[i]
        if i in indexes and height <= highest:
            dh = highest - height + 1
            cost += dh
            height += dh
        highest = max(highest, height)
    min_cost = min(min_cost, cost)

print(min_cost)

Solution (Python):
import copy

N,K = map(int,input().split())
A = list(map(int,input().split()))

ans = [10 ** 12 for i in range(2 ** (N - 1))]
seen = 1  

for i in range(2 ** (N - 1)):
  AA = copy.deepcopy(A)
  cost = 0
  s = str(bin(i))[2:]
  if s.count("1") >= K:
    continue
    
  for j in range(N - 1):
    m = max(AA[:j + 1])
    a = AA[j + 1]
    if ((i >> j) & 1) and a <= m:
      cost += (m - a + 1)
      AA[j + 1] = m + 1
  
  if len([AA[i] for i in range(1,N) if AA[i] > max(AA[:i])]) >= K - 1:
    ans[i] = cost
    
    
print(min(ans))

Solution (Python):
import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))

money = 10 ** 12

for i in range(2 ** N):
  B = copy.copy(A)
  
  count = 0
  money2 = 0
  for j in range(N):
    if ((i >> j) & 1):
      count += 1
      if j != 0:
        x = max(0, max(B[:j]) - B[j] + 1)
        if x != 0:
          B[j] = max(B[:j]) + 1
        money2 += x
        
  if count >= K:
    money = min(money, money2)
      
print(money)

Solution (Python):
import sys, itertools
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    a = LI()
    ans = INF
    for i in range(2**N):
        cost_sum = 0
        cnt = 0
        prev_height = 0
        for j in range(N):
            if (i>>j)&1:
                if a[j]<=prev_height:
                    cost_sum += (prev_height+1)-a[j]
                    prev_height += 1
                else:
                    prev_height = a[j]
                cnt += 1
            prev_height = max(a[j], prev_height)
        if cnt>=K:
            ans = min(cost_sum, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
from itertools import combinations
import sys

N, K = map(int, input().split())
A = list(map(int, input().split()))
Com = []
for i in range(N):
    Com.append(i)


ans = float('inf')
for com in combinations(Com, K):
    anscom = 0
    thread = 0
    for i, a in enumerate(A):
        if i not in com:
            thread = max(thread, a)
        else:
            if thread < a:
                thread = a
            else:
                anscom += thread + 1 - a
                thread += 1
    ans = min(ans, anscom)
print(ans)

Solution (Python):
n , k = map(int, input().split())
x = list(map(int,input().split()))
b = [list(map(int,bin(x)[2:].zfill(n))) for x in range(2**n)]
h = [0]*n

def check(li,n,k):
    c=1
    hi=li[0]
    for i in range(1,n):
        if li[i]>hi:
            c+=1
            hi=li[i]
    if c>=k:
        return True
    else:
        return False

for i in range(1,n):
    h[i]=max(h[i-1],x[i-1])

mi = float('inf')
for bit in b:
    ans = 0
    s1=0
    x2=x.copy()
    if bit[0]==1:
        for i in range(n):
            if bit[i]==1:
                s2=x[i]
                if s2<=s1:
                    ans+=s1-s2+1
                    s2=s1+1
                if s2<=h[i]:
                    ans += h[i]-s2+1
                    s2=h[i]+1
                s1=s2
                x2[i]=s2
            else:
                x2[i]=x[i]
    if check(x2,n,k):
        mi=min(mi,ans)

print(mi)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = float("inf")
 
for i in range(2**n):
    highest = a[0]
    color = 1
    money = 0
    for j in range(1,n):
        if a[j] > highest:
            color += 1
            highest = a[j]
        elif (i>>j)&1:
            color += 1
            highest = highest + 1
            money += highest - a[j]
        
    if color >= k:
        ans = min(ans,money)
print(ans)

Solution (Python):
import sys


input = sys.stdin.readline



def make(i, l):
    if i == N:
        return [l]
    else:
        lc = l[:]
        l.append(False)
        lc.append(True)
        return make(i+1, l) + make(i+1, lc)


def main():
    ans = 15*10**10
    for tf in make(1, [False]):
        peak = A[0]
        count = 1
        cost = 0
        for i in range(1, N):
            if count == K:
                break
            if tf[i]:
                count += 1
                if peak >= A[i]:
                    cost += peak - A[i] + 1
                    peak += 1
                else:
                    peak = A[i]
            else:
                if A[i] > peak:
                    peak = A[i]
                    count += 1
        if count == K:
            ans = min(ans, cost)
    print(ans)


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    main()

Solution (Python):
N,K = map(int,input().split())
a = list(map(int, input().split()))

import itertools
import sys
list_n = itertools.combinations(range(N),K)
ans = 1000000000000000
for i_list in list_n:
    a_i = a.copy()
    cost = 0
    for index in i_list:
        if not index == 0:
            m_index = max(a_i[:index])
        else:
            m_index = 0
        if m_index >= a_i[index]:
            cost += m_index - a_i[index] + 1
            
            a_i[index] = a_i[index] + m_index - a_i[index] + 1   
    ans = min(ans, cost)
    
print(ans)

Solution (Python):
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,k=n1()
a=n1()

import itertools
ite=itertools.combinations(range(n),k)

ans=10**20
for line in ite:
    c=0
    b=a.copy()
    for i in range(1,k):
        if b[line[i]]<=b[line[i-1]]:
            plus=b[line[i-1]]-b[line[i]]+1
            b[line[i]]+=plus
            c+=plus
    ok=1
    for i in range(1,n):
        if b[i-1]<b[i]:
            ok+=1
        else:
            b[i]=b[i-1]
    if ok>=k:
        ans=min(ans,c)
print(ans)

Solution (Python):
 
N,K=map(int,input().split())
lists=list(map(int,input().split()))

import itertools
seq=[i for i in range(1,N)]
D=list(itertools.combinations(seq,K-1))

answer=float("inf")

def cal(D):
    money=0
    now_height=lists[0]
    K=set(D)
    for i in range(1,N):
        if now_height>=lists[i]:
            if i in K:
                money+=(now_height+1-lists[i])
                now_height+=1
            else:
                
                pass
            
        elif now_height<lists[i]:
            if i in K:
                money+=0
                now_height=lists[i]
            else:
                
                money+=(lists[i]+1-now_height)
                now_height+=1
    return money
for que in D:
    answer=min(answer,cal(que))
print(answer)

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))

if N == 1:
    cost = 0
else:
    cost = 10 ** 11

for i in range(2 ** (N - 1)):
    r = str(format(i, 'b')).zfill(N - 1)
    ma = a[0]
    k = 1
    p = 0
    for j in range(N - 1):
        if r[j] == '1':
            k += 1
            if a[1 + j] > ma:
                ma = a[1 + j]
            elif a[1 + j] <= ma:
                p += ma - a[1 + j] + 1
                ma = ma + 1
        elif r[j] == '0':
            if a[1 + j] > ma:
                ma = a[1 + j]
    if k >= K and p < cost:
        cost = p

print(cost)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = float("inf")

for i in range(2**n):
    highest = a[0]
    color = 1
    money = 0
    for j in range(1,n):
        if a[j] > highest:
            color += 1
            highest = a[j]
        elif (i>>j)&1:
            color += 1
            highest = highest + 1
            money += highest - a[j]
        
    if color >= k:
        ans = min(ans,money)
print(ans)

Solution (Python):
n,k = list(map(int, input().split()))
a=list(map(int, input().split()))

ans=[]
for i in range(1<<n):
    
    if bin(i).count("1")==k:
        cst=0
        use=a.copy()
        for u in range(1,n):
            if(i>>u&1):
                left_max=max(use[:u])
                cst+=left_max-use[u]+1 if left_max>=use[u] else 0
                use[u]= max(left_max+1, use[u])
        ans.append(cst)
print(min(ans))

Solution (Python):


import sys

N, K = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))


def dfs(height=a[0], cost=0, target=K, can_see=1, i=1):
    if can_see == target:
        return cost

    
    if i == len(a):
        return float('inf')

    
    if height >= a[i]:
        cost1 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i + 1)
    else:
        cost1 = dfs(height=a[i], cost=cost, target=K, can_see=can_see + 1, i=i + 1)
    

    
    cost += max(0, height + 1 - a[i])
    can_see += 1
    height = max(a[i], height + 1)
    cost2 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i + 1)
    

    return min(cost1, cost2)


print(dfs(a[0], cost=0, target=K, can_see=1, i=1))

Solution (Python):


import sys

N, K = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))


def dfs(height=a[0], cost=0, target=K, can_see=1, i=1):
    if can_see == target:
        return cost

    
    if i == len(a):
        return float('inf')

    
    if height >= a[i]:
        cost1 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i + 1)
    else:
        cost1 = dfs(height=a[i], cost=cost, target=K, can_see=can_see + 1, i=i + 1)
    

    
    cost += max(0, height + 1 - a[i])
    can_see += 1
    height = max(a[i], height + 1)
    cost2 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i + 1)
    

    return min(cost1, cost2)


print(dfs(a[0], cost=0, target=K, can_see=1, i=1))

Solution (Python):


import sys

N, K = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))

if K == 0:
    sys.exit()

def dfs(height=a[0], cost=0, target=K, can_see=1, i=1):
    if can_see == target:
        
        
        
        return cost

    
    if i == len(a):
        return float('inf')

    
    if height >= a[i]:
        cost1 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i+1)
    else:
        cost1 = dfs(height=a[i], cost=cost, target=K, can_see=can_see+1, i=i+1)
    

    
    cost += max(0, height + 1 - a[i])
    height = max(a[i], height + 1)
    cost2 = dfs(height=height, cost=cost, target=K, can_see=can_see+1, i=i+1)
    

    return min(cost1, cost2)


print(dfs(a[0], cost=0, target=K, can_see=1, i=1))

Solution (Python):


import sys

N, K = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))

if K == 0:
    sys.exit()

def dfs(height=a[0], cost=0, target=K, can_see=1, i=1):
    if can_see >= target:
        
        
        
        return cost

    
    if i == len(a):
        return float('inf')

    
    if height >= a[i]:
        cost1 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i+1)
    else:
        cost1 = dfs(height=a[i], cost=cost, target=K, can_see=can_see+1, i=i+1)
    

    
    cost += max(0, height + 1 - a[i])
    height = max(a[i], height + 1)
    cost2 = dfs(height=height, cost=cost, target=K, can_see=can_see+1, i=i+1)
    

    return min(cost1, cost2)


print(dfs(a[0], cost=0, target=K, can_see=1, i=1))

Solution (Python):


 
import sys
 
N, K = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))
 
ans = float('inf')
for i in range(2 ** (N - 1)):
    bit = [(i >> j) & 1 for j in range(N - 1)]  
 
    can_see = 0
    cost = 0
    height = a[0]
    for j, b in enumerate(bit):
        if (b == 1) & (height >= a[j+1]):
            cost += height - a[j + 1] + 1
            height = height + 1
            can_see += 1
        elif (b == 1):
            height = a[j + 1]
            can_see += 1
        elif height < a[j + 1]:
            can_see += 1
        height = max(height, a[j + 1])
 
    if can_see >= K-1:
        ans = min(ans, cost)
 
print(ans)

Solution (Python):



import sys

N, K = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))

ans = float('inf')
for i in range(2 ** (N - 1)):
    bit = [(i >> j) & 1 for j in range(N - 1)]  

    can_see = 0
    cost = 0
    height = a[0]
    for j, b in enumerate(bit):
        if (b == 1) & (height >= a[j + 1]):
            cost += height - a[j + 1] + 1
            height = height + 1
            can_see += 1
        elif (b == 1):
            height = a[j + 1]
            can_see += 1
        elif height < a[j + 1]:
            can_see += 1
        height = max(a[j + 1], height)

    if can_see >= K - 1:
        ans = min(ans, cost)

print(ans)

Solution (Python):



import sys

N, K = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))

ans = float('inf')
for i in range(2 ** (N - 1)):
    bit = [(i >> j) & 1 for j in range(N - 1)]  

    can_see = 0
    cost = 0
    height = a[0]
    for j, b in enumerate(bit):
        if (b == 1) & (height >= a[j + 1]):
            cost += height - a[j + 1] + 1
            height = height + 1
            can_see += 1
        elif (b == 1):
            height = a[j + 1]
            can_see += 1
        elif height < a[j + 1]:
            can_see += 1
            height = a[j + 1]

    if can_see >= K - 1:
        ans = min(ans, cost)

print(ans)

Solution (Python):



import sys

N, K = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))

ans = float('inf')
for i in range(2 ** (N - 1)):
    bit = [(i >> j) & 1 for j in range(N - 1)]  

    can_see = 0
    cost = 0
    height = a[0]
    for j, b in enumerate(bit):
        if (b == 1) & (height >= a[j + 1]):
            cost += height - a[j + 1] + 1
            height = height + 1
            can_see += 1
        elif (b == 1) & (height < a[j + 1]):
            height = a[j + 1]
            can_see += 1
        elif height < a[j + 1]:
            can_see += 1
            height = a[j + 1]

    if can_see >= K - 1:
        ans = min(ans, cost)

print(ans)

Solution (Python):


import sys

N, K = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))


def dfs(height=a[0], cost=0, target=K, can_see=1, i=1):
    if can_see >= target:
        
        
        
        return cost

    
    if i == len(a):
        return float('inf')

    
    if height >= a[i]:
        cost1 = dfs(height=height, cost=cost, target=K, can_see=can_see, i=i+1)
    else:
        cost1 = dfs(height=a[i], cost=cost, target=K, can_see=can_see+1, i=i+1)
    

    
    cost += max(0, height + 1 - a[i])
    height = max(a[i], height + 1)
    cost2 = dfs(height=height, cost=cost, target=K, can_see=can_see+1, i=i+1)
    

    return min(cost1, cost2)


print(dfs(a[0], cost=0, target=K, can_see=1, i=1))

Solution (Python):
n,k = map(int, input().split()) 
a_list = list(map(int, input().split())) 

min_cost = 10**15
for i in range(2 ** n):
    see_a_ids = []
    for j in range(n):
        if ((i >> j) & 1):
            see_a_ids.append(j)
    
    if len(see_a_ids) < k:
        continue

    curr_max_h = 0
    curr_cost = 0
    for a_i in range(n):
        if a_i in see_a_ids:
            if a_list[a_i] <= curr_max_h:
                h_plus = curr_max_h + 1 - a_list[a_i]
                curr_cost += h_plus
                curr_max_h = curr_max_h+1
            else:
                curr_max_h = a_list[a_i]
        else:
            curr_max_h = max(curr_max_h, a_list[a_i])
    min_cost = min(min_cost, curr_cost)
print(min_cost)

Solution (Python):
import itertools

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
max_h = 0
for i, num in enumerate(a):
    b.append(max_h)
    max_h = max(max_h, num)

ans = 9999999999999999999999
for lst in itertools.combinations(range(1, n), k - 1):
    total = 0
    before = a[0]
    for num in lst:
        if a[num] <= b[num] or a[num] <= before:
            total += max(b[num], before) - a[num] + 1
            before = max(b[num], before) + 1
            
    ans = min(ans, total)
print(ans)