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):

import sys
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

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



ans = 1000000000 * 15 * 15
for x in range(2 ** N):
    bi = bin(x)[2::][::-1]
    bi = bi + ( "0" * (N - len(bi)) )
    higest = A[0]
    bilging = 1
    cost = 0
    for index , a in enumerate(A[1::]) :
        if bi[index+1] == "1" and a <= higest:
            diff = higest - a 
            cost += diff + 1
            higest = a + diff + 1
            bilging += 1
        
        if higest < a :
            bilging += 1
            higest = a
    if bilging >= K:
        ans = min(ans , cost)
print(ans)

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
 
n,k = LI()
a = LI()

min_val = 20000000000
for i in range(1 << (n-1)):
    count = 0
    val = 0
    pre = a[0]
    for j in range(n-1):
        if(i & (1 << j)):
            count += 1
            if(pre >= a[j+1]):
                val += pre - a[j+1] + 1
                pre = pre + 1
        if(pre < a[j+1]):
            pre = a[j+1]

    if(count >= k-1):
        if(min_val > val):
            min_val = val

print(min_val)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=float("inf")
for i in range(2**n):
    bit=[(i>>j)&1 for j in range(n)]
    if sum(bit)==k and bit[0]:
        cost=0
        kijun=a[0]
        for j in range(1,n):
            if not bit[j]:
                kijun=max(kijun,a[j])
            elif a[j]>=kijun+1:
                kijun=a[j]
            else:
                cost+=kijun+1-a[j]
                kijun+=1
        ans=min(ans,cost)
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=float("inf")
for i in range(2**n):
    bit=[(i>>j)&1 for j in range(n)]
    if sum(bit)==k and bit[0]==1:
        cost=0
        kijun=a[0]
        for j in range(1,n):
            if bit[j]==0:
                kijun=max(kijun,a[j])
            elif a[j]>=kijun+1:
                kijun=a[j]
            else:
                cost+=kijun+1-a[j]
                kijun+=1
        ans=min(ans,cost)
print(ans)

Solution (Python):
def LI(): return list(map(int,input().split()))
N,K = LI()
a = LI()
ans = float('INF')
for i in range(2**(N-1)):
    bit = [i>>j&1 for j in range(N-1)]
    if K-1!=sum(bit):
        continue
    cost,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
            continue
        if a[k+1]>=kijun+1:
            kijun = a[k+1]
            continue
        cost += (kijun+1)-a[k+1]
        kijun += 1
    ans = min(ans,cost)
print(ans)

Solution (Python):
import itertools

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

amin=10**9*20
for i in itertools.product([0,1], repeat=n):
    if sum(i)==k:
        hs=a[0]
        acnt=0
        h=[]
        for j in range(n):
            if i[j]==1 and j>0:
                if hs>=a[j]:
                    acnt+=hs-a[j]+1
                    hs=hs+1
            if hs<a[j]:
                hs=a[j]
            h.append(hs)

        amin=min(amin,acnt)
        
print(amin)

Solution (Python):
from itertools import product

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

ans = 10 ** 20
for bit in product([0, 1], repeat=n):
    if sum(bit) != k or bit[0] == 0:
        continue
    cnt = 0
    tmp = a[0]
    for i, v in enumerate(bit):
        if v == 1:
            if i != 0:
                cnt += max(tmp + 1 - a[i], 0)
                tmp = max(tmp + 1, a[i])
        else:
            tmp = max(tmp, a[i])
    ans = min(ans, cnt)
print(ans)

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

ans = 10**18
for i in range(1<<N):
    cnt = 0
    cost = 0
    mini = 0
    for j in range(N):
        J = As[j]
        if (i>>j)&1:
            cnt += 1
            if mini>=J:
                cost += mini+1-J
                mini += 1
        mini = max(mini, J)
        if cnt>=K:
            ans = min(ans, cost)
print(ans)

Solution (Python):
def main():
    import copy
    n, k  = map(int, input().split())
    takasa_lis = list(map(int, input().split()))
   
    ans = 10**200
    
    for i in range(0, 2 ** n, 2):
        test_lis = copy.deepcopy(takasa_lis)
        cnt = 0
        building_cost = 0
        for j in range(1, n):
            if ((i>>j) & 1):
                cnt += 1
                building_cost += max(max(test_lis[0:j]) - test_lis[j] + 1, 0)
                test_lis[j] = max(max(test_lis[0:j])+1, test_lis[j])
            else:
                if test_lis[j] > max(test_lis[0:j]):
                    cnt += 1
        if cnt >= k-1 and ans > building_cost:
            ans = building_cost
    
    print(ans)


    


if __name__ == "__main__":
    main()

Solution (Python):


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

def solve(idx):
    ret = 0
    tmpmax = A[0]
    for i in range(1, idx[-1]+1):
        if A[i] <= tmpmax:
            if i in idx:
                ret += tmpmax - A[i] + 1
                tmpmax += 1
        else:
            tmpmax = A[i]
    return ret

ans = 10**18
for i in range(1<<N):
    idx = []
    for j in range(N):
        if i>>j&1:
            idx.append(j)
    if len(idx)==K and idx[0]==0:
        ans = min(ans, solve(idx))

print(ans)

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

ans = float('inf')
for i in range(2 ** n):
    res = 0
    cnt = 0
    prev_build = buildings[0]
    for j in range(n):
        if (i >> j) & 1 == 1:
            cnt += 1
            if prev_build >= buildings[j] and not j == 0:
                res += ((prev_build + 1) - buildings[j])
                prev_build = prev_build + 1
            else:
                prev_build = buildings[j]
        else:
            if prev_build < buildings[j]:
                prev_build = buildings[j]

    if cnt == k:
        ans = min(ans, res)

print(ans)

Solution (Python):
n,k=map(int,input().split())
a=tuple(map(int,input().split()))
if k==1 or n==1:
    print(0)
    exit()
m=pow(10,12)
l=len(a)-1
for i in range(2**(n-1)):
    cnt=1
    h=a[0]
    num=0
    for j in range(l):
        if (i>>j)&1:
            num+=max(0,h-a[j+1]+1)
            if a[j+1]<=h:
                h+=1
            else:
                h=a[j+1]
            cnt+=1
        else:
            if a[j+1]>h:
                cnt+=1
                h=a[j+1]
    if cnt>=k:
        m=min(m,num)
print(m)

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

candidate = [[0], [1]]
while True:
    temp = []
    for c in candidate:
        temp.append(c + [0])
        temp.append(c + [1])
    candidate = temp
    if len(temp[0]) == N:
        break

ans = float('inf')
for c in candidate:
    if sum(c) != K:
        continue
    high = a[0]
    temp = 0
    for i, value in enumerate(c):
        if i == 0:
            continue
        if value == 1 and a[i] <= high:
            high += 1
            temp += high - a[i]
        high = max(high, a[i])


    ans = min(ans, temp)

print(ans)

Solution (Python):
def get_building(i, N):
    ans = [0]*N
    ans[0] = 1
    for ind in range(1, N):
        if i % 2 == 0:
            ans[ind] = 1
        i //= 2
    return ans

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

ans = -1
for i in range(2**(N-1)):
    see_building = get_building(i, N)

    counter = 1
    now_height = a[0]
    cost = 0
    for j in range(1, N):
        if see_building[j] == 1:
            counter += 1
            if a[j] <= now_height:
                cost += (now_height - a[j]) + 1
                now_height += 1
            else:
                now_height = a[j]
        else:
            now_height = max(now_height, a[j])
    
    if counter >= K:
        if ans == -1:
            ans = cost
        else:
            ans = min(ans, cost)

print(ans)

Solution (Python):
import sys 
input = sys.stdin.readline

n, k = map(int, input().split())
an = list(map(int, input().split()))

min_cost = 10**11
for i in range(2**n):
    height = 0
    k_count = 0
    cost = 0
    for j in range(n):
        if (i>>j) & 1:
            if an[j] <= height:
                cost += height - an[j] + 1
                height += 1
            else:
                height = an[j]
            k_count += 1
        height = max(height, an[j])
    if k_count >= k:
        min_cost = min(min_cost, cost)

print(min_cost)

Solution (Python):

def main():
    N, K = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    cost = float('inf')
    for i in range(2**N):
        b = a.copy()
        costtmp = 0
        for j in range(N):
            if (i>>j) & 1:
                maxb = max(b[:j+1])
                if maxb >= a[j+1]:
                    costtmp += maxb + 1 - a[j+1]
                    b[j+1] = maxb + 1
        check = 0
        for k in range(1, N+1):
            maxbk = max(b[:k])
            if maxbk < b[k]:
                check += 1
        if check >= K:
            cost = min(cost, costtmp)
        
    print(cost)


if __name__ == "__main__":
    main()

Solution (Python):
def LI(): return list(map(int,input().split()))
N,K = LI()
a = LI()
ans = float('INF')
for i in range(2**(N-1)):
    bit = [i>>j&1 for j in range(N-1)]
    if K-1!=sum(bit):
        continue
    cost,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
            continue
        if a[k+1]>=kijun+1:
            kijun = a[k+1]
            continue
        cost += (kijun+1)-a[k+1]
        kijun += 1
    ans = min(ans,cost)
print(ans)

Solution (Python):
def LI(): return list(map(int,input().split()))
N,K = LI()
a = LI()
ans = float('INF')
for i in range(2**(N-1)):
    bit = [i>>j&1 for j in range(N-1)]
    if K-1!=sum(bit):
        continue
    cost,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
        else:
            if a[k+1]>=kijun+1:
                kijun = a[k+1]
                continue
            cost += (kijun+1)-a[k+1]
            kijun += 1
    ans = min(ans,cost)
print(ans)

Solution (Python):
def LI(): return list(map(int,input().split()))
N,K = LI()
a = LI()
ans = float('INF')
for i in range(2**(N-1)):
    bit = [i>>j&1 for j in range(N-1)]
    if K-1!=sum(bit):
        continue
    temp,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
        else:
            if a[k+1]>=kijun+1:
                kijun = a[k+1]
                continue
            temp += (kijun+1)-a[k+1]
            kijun += 1
    ans = min(ans,temp)
print(ans)

Solution (Python):
from itertools import product

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

ans = 10 ** 20
for bit in product([0, 1], repeat=n):
    if sum(bit) != k or bit[0] == 0:
        continue
    cnt = 0
    tmp = a[0]
    for i, v in enumerate(bit):
        if v == 1:
            if i != 0:
                cnt += max(tmp + 1 - a[i], 0)
                tmp = max(tmp + 1, a[i])
        else:
            tmp = max(tmp, a[i])
    ans = min(ans, cnt)
print(ans)

Solution (Python):
def LI(): return list(map(int,input().split()))
N,K = LI()
a = LI()
ans = float('INF')
for i in range(2**(N-1)):
    bit = [i>>j&1 for j in range(N-1)]
    if K-1!=bit.count(1):
        continue
    temp,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
        else:
            if a[k+1]>=kijun+1:
                kijun = a[k+1]
                continue
            temp += (kijun+1)-a[k+1]
            kijun += 1
    ans = min(ans,temp)
print(ans)

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

def f(p):
    ret = 0
    ma = 0
    for i, a in enumerate(A):
        if p[i] == 1:
            if ma == 0:
                pass
            else:
                if ma >= a:
                    ret += ma - a + 1
                    ma += 1
        ma = max(ma, a)
    return ret

ans = 10 ** 20
for comb in combinations(range(N), K):
    p = [1 if i in comb else 0 for i in range(N)]
    
    
    ans = min(ans, f(p))

print(ans)

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

def f(p):
    ret = 0
    ma = 0
    for i, a in enumerate(A):
        if p[i] == 1:
            if ma == 0:
                pass
            else:
                if ma >= a:
                    ret += ma - a + 1
                    ma += 1
        ma = max(ma, a)
    return ret

ans = 10 ** 20
for p in product(range(2), repeat=N):
    if sum(p) < K: continue
    
    ans = min(ans, f(p))

print(ans)

Solution (Python):
cin = open(0).read().strip().split('\n')
n, k = map(int, cin[0].split(' '))
a = list(map(int, cin[1].split(' ')))

ret = float('inf')
for idx in range(2**(n)):
    colors = 0
    res = 0
    left = 0
    for i in range(n):
        if (idx>>i) & 1:
            colors += 1
            res += max(left+1 - a[i] , 0)
            left = max(a[i], left+1)
        else:
            colors += 1 if left < a[i] else 0
            left = max(left, a[i])


    if colors >= k:
        ret = min(ret, res)

print(ret)

Solution (Python):
cin = open(0).read().strip().split('\n')
n, k = map(int, cin[0].split(' '))
a = list(map(int, cin[1].split(' ')))

ret = float('inf')
for idx in range(2**(n)):
    colors = 0
    res = 0
    left = 0
    for i in range(n):
        if (idx>>i) & 1:
            colors += 1
            res += max(left+1 - a[i] , 0)
            left += 1
        
        

        left = max(a[i], left)

    if colors >= k:
        ret = min(ret, res)

print(ret)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 10 ** 20
for i in range(2 ** n):
    total = 0
    data = a.copy()
    highest = a[0] - 1
    cnt = 0
    for j in range(n):
        if i >> j & 1:
            cnt += 1

    if cnt == k:
        for j in range(n):
            if i >> j & 1:
                if highest >= data[j]:
                    total += highest - data[j] + 1
                    data[j] = max(highest + 1, data[j])
            highest = max(highest, data[j])
        ans = min(ans, total)
        
    
print(ans)

Solution (Python):

import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() 


def getCost(selects, a):
    cost = 0
    pre = a[0]
    for i in range(1,len(a)):
        if i in selects:
            costi = max(0, pre-a[i]+1)
            cost += costi
            if costi > 0:
                pre = pre+1
        pre = max(pre,a[i])
    return cost


def main():
    n,k = na()
    a = na()
    ans = float('inf')
    for i in range(pow(2,n)):
        selects = []
        for j in range(n):
            if ((i>>j) & 1):
                selects += [j]
        if len(selects) != k:
            continue
        ans = min(ans, getCost(selects,a))
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
k-=1
n-=1
c=(1<<k)-1
b=10**18
while c<1<<n:
    w=a[0]
    t=0
    f=1
    for i in range(n):
        if c>>i&1:
            t+=max(0,w-a[i+1]+1)
            w=max(a[i+1],w+1)
        else:
            if a[i+1]>w:
            	f=0
            	break
    if f:
        b=min(b,t)
    x=c&-c
    y=c+x 
    c=((c&~y)//x>>1)|y 
print(b)

Solution (Python):
n,k=map(int,input().split())
if k==1:
    print(0)
    exit()
a=list(map(int,input().split()))
k-=1
n-=1
c=(1<<k)-1
b=10**18
while c<1<<n:
    w=a[0]
    t=0
    f=1
    for i in range(n):
        if c>>i&1:
            t+=max(0,w-a[i+1]+1)
            w=max(a[i+1],w+1)
        else:
            if a[i+1]>w:
            	f=0
            	break
    if f:
        b=min(b,t)
    x=c&-c
    y=c+x 
    c=((c&~y)//x>>1)|y 
print(b)

Solution (Python):



def solve():
    import copy

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

    if K == 1:
        print(0)
        return

    
    ans = float("inf")
    for bit in range(2**(N-1)):  
        tmpAs = copy.deepcopy(As)
        highest = tmpAs[0]
        total = 0
        see = 1  
        for i in range(N-1):  
            if bit>>i&1:
                see += 1
                if tmpAs[i+1] <= highest:
                    total += (highest-tmpAs[i+1])+1
                    tmpAs[i+1] = highest+1
            highest = max(highest, tmpAs[i+1])

        if see >= K:
            ans = min(ans, total)
    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**19
for i in range(2**n):
    colors = 0
    height = 0
    res = 0
    for j in range(n):
        if (i>>j)%2:
            colors += 1
            need = max(0,height - a[j] +1)
            res += need
            height += 1
            
        height = max(a[j] ,height)
    if colors >= k:ans = min(ans,res)
    
print(ans)

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

ans = 1 << 60
for i in range(1 << N):
    if i % 2 == 0:
        continue
    
    selected = [j for j in range(N) if i & (1 << j)]
    if len(selected) != K:
        continue
    
    h_max = a[0]
    cost = 0
    for j in range(1, N):
        if j in selected:
            if a[j] <= h_max:
                cost += h_max + 1 - a[j]
                h_max += 1
            else:
                h_max = a[j]
        else:
            h_max = max(h_max, a[j])
    
    ans = min(ans, cost)

print(ans)

Solution (Python):
from itertools import combinations

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

ans = 10**12
for cmb in combinations(range(1,n),k-1):    
  cost = 0
  h = A[0]
  
  for i in range(1,n):    
    if i in cmb: 
      if A[i] > h:        
        h = A[i]      
      else:
        cost += h - A[i] + 1
        h += 1    
    h = max(h,A[i])
        
  ans = min(ans,cost)
          
print(ans)

Solution (Python):
n, k = map(int, input().split())
li = list(map(int, input().split()))
min_ = 10**12
for i in range(1<<n):
    max_height = li[0]
    money = 0
    can_look = 0
    li_h = []
    for j in range(n):
        if j != 0:
            max_height = max(max_height, li_h[j-1])
        
        if j == 0:
            can_look += 1
            li_h.append(li[0])
            continue
        if (i>>j)&1:
            can_look += 1
            if li[j] <= max_height:
                li_h.append(max_height+1)
            else:
                li_h.append(li[j])
        else:
            li_h.append(li[j])
    if can_look >= k:
        money = sum(li_h) - sum(li)
        min_ = min(min_, money)

print(min_)

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

res = 1 << 60 
for i in range(1<<n): 
    if(i%2 == 0): continue 

    use_idx = [0 for _ in range(n)] 
    use_cnt = 0 
    for j in range(n):
        if(i & (1<<j)):
            use_idx[j] = 1 
            use_cnt += 1 

    if(use_cnt != k): continue 

    sm = 0 
    mx = a[0] 
    for j in range(1, n):

        if(use_idx[j]): 
            if(a[j] <= mx): 
                sm += mx+1 - a[j] 
                mx += 1 

        mx = max(mx, a[j]) 

    res = min(res, sm) 

print(res)

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

res = 1 << 60 
for i in range(1<<n): 
    if(i%2 == 0): continue 

    use_idx = [0 for _ in range(n)] 
    use_cnt = 0 
    for j in range(n):
        if(i & (1<<j)):
            use_idx[j] = 1 
            use_cnt += 1 

    if(use_cnt != k): continue 

    sm = 0 
    mx = a[0] 
    for j in range(1, n):

        if(use_idx[j]): 
            if(a[j] <= mx): 
                sm += mx+1 - a[j] 
                mx += 1 

        mx = max(mx, a[j]) 

    res = min(res, sm) 

print(res)

Solution (Python):
N, K = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

ans = 10 ** 12
for i in range(1, 2 ** N):
    if bin(i)[2:].count('1') != K: continue
    tmp = 0
    hmax = a[0]
    for j in range(1, N):
        if (i >> j) & 1:
            h = max(hmax + 1, a[j])
            tmp += h - a[j]
            hmax = h
        else:
            hmax = max(hmax, a[j])
    ans = min(ans, tmp)

print(ans)

Solution (Python):
from itertools import combinations as cmb
n, k = map(int, input().split())
A = list(map(int, input().split()))
highest = [A[0]] * n
for i in range(1, n):
  highest[i] = max(A[i], highest[i-1])

def cost_calc(pattern):
  cost = 0
  max_height_re = 0
  for num in pattern:
    cost += max(max_height_re, highest[num]) - A[num]
    max_height_re = max(max_height_re, highest[num]) + 1
  return cost

max_val = float("inf")
for pattern in cmb(range(n), k):
  max_val = min(max_val, cost_calc(pattern))
print(max_val)

Solution (Python):
from itertools import combinations as cmb
import copy
n, k = map(int, input().split())
A = list(map(int, input().split()))
highest = [A[0]] * n
for i in range(1, n):
  highest[i] = max(A[i], highest[i-1])

def cost_calc(pattern):
  cost = 0
  max_height_re = 0
  A_copy = copy.copy(A)
  for num in pattern:
    cost += max(max_height_re, highest[num]) - A[num]
    max_height_re = max(max_height_re, highest[num]) + 1
  return cost

max_val = float("inf")
for pattern in cmb(range(n), k):
  max_val = min(max_val, cost_calc(pattern))
print(max_val)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

    ans = float('inf')
    for i in range(2**(N-1)):
        if bin(i).count("1") != K-1:
            continue
        height = A[0]
        tmp = 0
        for j in range(N-1):
            if (i >> j) & 1:
                height += 1
                if A[j+1] >= height:
                    height = A[j+1]
                    continue
                tmp += height - A[j+1]
            height = max(height, A[j+1])
        ans = min(ans, tmp)
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

    ans = float('inf')
    for pattern in combinations(range(1,N), K-1):
        height = A[0]
        tmp = 0
        for i in range(1,N):
            if i in pattern:
                height += 1
                if A[i] >= height:
                    height = A[i]
                    continue
                tmp += height - A[i]
            height = max(height, A[i])
        ans = min(ans, tmp)
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

    ans = float('inf')
    for pattern in combinations(range(1,N), K-1):
        height = A[0]
        tmp = 0
        p_s = set(pattern)
        for i in range(1,N):
            if i in p_s:
                height += 1
                if A[i] >= height:
                    height = A[i]
                    continue
                tmp += height - A[i]
            height = max(height, A[i])
        ans = min(ans, tmp)
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations 
INF = int(1e9)*15
def main():
    n, k = map(int, input().split()) 
    a = [int(i) for i in input().split()]
    c = [int(i) for i in range(1, n)]
    ans = INF
    for comb in combinations(c, k-1):
        s = set(comb)
        mx = a[0]
        cost = 0
        for i in range(n):
            if i in s:
                if a[i] > mx:
                    mx = a[i]
                    continue
                else:
                    mx += 1
                    cost += mx-a[i] 
                    continue
            mx = max(mx, a[i])
        ans = min(cost, ans)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from itertools import combinations 
INF = int(1e9)*15
def main():
    n, k = map(int, input().split()) 
    a = np.array(input().split(), np.int32)
    c = np.array([int(i) for i in range(1, n)])
    ans = INF
    for comb in combinations(c, k-1):
        s = set(comb)
        mx = a[0]
        cost = 0
        for i in range(n):
            if i in s:
                if a[i] > mx:
                    mx = a[i]
                    continue
                else:
                    mx += 1
                    cost += mx-a[i] 
                    continue
            mx = max(mx, a[i])
        ans = min(cost, ans)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from itertools import combinations 
INF = int(1e9)*15
def main():
    n, k = map(int, readline().split()) 
    a = np.array(readline().split(), np.int32)
    c = np.array([int(i) for i in range(1, n)])
    ans = INF
    for comb in combinations(c, k-1):
        s = set(comb)
        mx = a[0]
        cost = 0
        for i in range(n):
            if i in s:
                if a[i] > mx:
                    mx = a[i]
                    continue
                else:
                    mx += 1
                    cost += mx-a[i] 
                    continue
            mx = max(mx, a[i])
        ans = min(cost, ans)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from itertools import combinations 
INF = int(1e9)*15
def main():
    n, k = map(int, readline().split()) 
    a = np.array(readline().split(), np.int64)
    c = np.array([int(i) for i in range(1, n)])
    ans = INF
    for comb in combinations(c, k-1):
        mx = a[0]
        cost = 0
        for i in range(n):
            if i in comb:
                if a[i] > mx:
                    mx = a[i]
                    continue
                else:
                    mx += 1
                    cost += mx-a[i] 
                    continue
            mx = max(mx, a[i])
        ans = min(cost, ans)
    print(ans)
if __name__ == '__main__':
    main()

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

ans = 10**15
for i in range(2**N):
    if bin(i).count('1')<K:
        continue
    cost = 0
    now = 0
    for j in range(N):
        if i>>j&1:
            if now>=a[j]:
                cost += now-a[j]+1
                now += 1
            else:
                now = a[j]
        else:
            now = max(now,a[j])
    ans = min(ans,cost)
print(ans)

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

ans = 10**15
for i in range(2**N):
    if bin(i).count('1')!=K:
        continue
    cost = 0
    now = 0
    for j in range(N):
        if i>>j&1:
            if now>=a[j]:
                cost += now-a[j]+1
                now += 1
            else:
                now = a[j]
        else:
            now = max(now,a[j])
    ans = min(ans,cost)
print(ans)

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

ans = 10**12
for i in range(2**N):
    if bin(i).count('1')!=K:
        continue
    cost = 0
    now = 0
    for j in range(N):
        if i>>j&1:
            if now>=a[j]:
                cost += now-a[j]+1
                now += 1
            else:
                now = a[j]
        else:
            now = max(now,a[j])
    ans = min(ans,cost)
print(ans)

Solution (Python):
from itertools import combinations as comb
N,K = map(int,input().split())
a = [int(i) for i in input().split()]
ans = float("INF")

for c in comb(range(1,N),K-1):
    cnt = 0
    color = 0
    mh = a[0]
    for i in range(1,N):
        if i == c[color]:
            cnt += max(mh-a[i]+1,0)
            color += 1
            if color == K-1: break
            mh = max(mh+1,a[i])
        else:
            mh = max(mh,a[i])
    ans = min(cnt ,ans)
print(ans)

Solution (Python):
N,K = map(int,input().split())
a = [int(i) for i in input().split()]
ans = float("INF")
for i in range(1<<N):
    cnt = 0
    tmp = a[:]
    m = tmp[0]
    for j in range(1,N):
        if i >> j & 1 and m >= tmp[j]:
            cnt += m - tmp[j] + 1
            tmp[j] = m + 1
        m = max(m,tmp[j])
    color = 1
    m = tmp[0]
    for j in range(1,N):
        if tmp[j] > m:
            color += 1
            m = tmp[j]
    if color >= K: ans = min(ans,cnt)
print(ans)

Solution (Python):
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
if k == 1:
  print(0)
  exit()
  
b = [int(i)+1 for i in range(n-1)]
ans = float('inf')
import itertools
for j in itertools.combinations(b, k-1):
  s = list(j)
  now_high = a[0]
  cost = 0
  for l in range(1,n):
    if l in s:
      if a[l] > now_high:
        now_high = a[l]
        continue
      else:
        cost += (now_high-a[l]+1)
        now_high += 1
    now_high = max(now_high, a[l])
  ans =  min(ans,cost)
print(ans)

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


ans = 10 ** 11
for  i in range(2 ** N):
    if bin(i).count("1") != K:
        continue
    max_height = 0
    height_num = 0
    for j in range(N):
        if i >> j & 1:
            if a[j] <= max_height:
                height_num += (max_height + 1 - a[j])
                max_height += 1
            else:
                max_height = a[j]
        else:
            max_height = max(max_height, a[j])
    ans = min(ans, height_num)

print(ans)