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

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

    if N == K:
        mask = [1] * N

        print(calc(N, a, mask))
        return

    ans = sys.maxsize
    for i in range(1 << N):
        mask = [i >> j & 1 for j in range(N)]
        if sum(mask) < K: continue
        mask.reverse()

        ans = min(ans, calc(N, a, mask))

    print(ans)
    return

def calc(N, a, mask):
    ans = 0
    m = a[0]
    for i in range(1, N):
        m = max(m, a[i - 1])
        if mask[i] == 0:continue
        if m < a[i]:
            continue
        else:
            v = m - a[i] + 1
            ans += v
            m = a[i] + v

    return ans

if __name__ == '__main__':
    main()

Solution (Python):
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
height = [max(A[:i+1]) for i in range(N)]

ans = 10**11
for i in range(2**N):
    task = []
    for j in range(N):
        if (i >> j) & 1:
            task.append(j)
    if len(task) != K:
        continue
    c = 0
    h = -1
    for t in task:
        h = max(height[t], A[t], h+1)
        c += h-A[t]
    ans = min(ans, c)
print(ans)

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

temp = "0" + str(N) + "b"
case = []
for i in range(2 ** N):
    x = format(i, temp)
    if x[0] == "1" and x.count("1") >= K:
        case.append(x)

result = []
for x in case:
    test = heights.copy()
    now = test[0]
    for y in range(1, N):
        if x[y] == "1":
            if test[y] <= now:
                test[y] = now + 1
                now = test[y]
            else:
                now = test[y]
        else:
            now = max(now, test[y])
    result.append(test)

ans=float('inf')
for i in result:
    cost = 0
    for j in range(N):
        if heights[j] < i[j]:
            cost += i[j] - heights[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 n in combinations(range(N), K):
    m = A[0]
    c = 0
    for i in range(1, N):
        if i in n:
            c += max(m + 1 - A[i], 0)
            m = max(m+1, A[i])
        else:
            m = max(m, A[i])
    ans = min(ans, c)

print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import product
from copy import deepcopy
def main():
    n, k, *a = map(int, read().split())
    inf = float('inf')
    visible = [inf] * (n + 1)
    pat = tuple(product((0, 1) , repeat=(n - 1)))
    for pate in pat:
        a2 = deepcopy(a)
        cost = 0
        visible_cur = 1
        tall_max = a2[0]
        for i1 in range(1, n):
            tall_max = max(tall_max, a2[i1 - 1])
            visible_flag = tall_max < a2[i1]
            if pate[i1 - 1]:
                if tall_max >= a2[i1]:
                    cost += tall_max + 1 - a2[i1]
                    a2[i1] = tall_max + 1
                visible_flag = True
            visible_cur += visible_flag
        visible[visible_cur] = min(visible[visible_cur], cost)
    ans = min(visible[k:])
    print(ans)

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<<(N-1)):
  cost,cnt,h=0,1,a[0]+1
  for j in range(N-1):
    x=a[j+1]
    if i>>j&1:
      cnt+=1
      if x>h:
        h=x+1
      else:
        cost+=h-x
        h+=1
    h=max(h,x+1)
  if cnt>=K:
    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(1<<(N-1)):
  cnt,s,t=0,0,a[0]+1
  for j in range(N-1):
    if i>>j&1:
      x=a[j+1]
      cnt+=1
      if x>=t:
        t=x+1
      else:
        s+=(t-x)
        t+=1
    else:
      t=max(t,a[j+1]+1)
  if cnt>=K-1:
    ans=min(s,ans)
print(ans)

Solution (Python):
import sys

N, K = map(int, input().split())
B = list(map(int, sys.stdin.readline().rsplit()))

res = 10 ** 18
for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        
        if (i >> j) & 1:
            cnt += 1
    
    if cnt != K:
        continue
    
    A = B[::]
    cnt = 0
    maxi = A[0] - 1
    for j in range(N):
        if (i >> j) & 1:
            if A[j] <= maxi:
                cnt += (maxi + 1) - A[j]
                A[j] = maxi + 1

        maxi = max(maxi, A[j])

    res = min(res, cnt)

print(res)

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

ans = 10**9 * 15
for bit in range(1<<N):
    cnt = 0
    for i in range(N):
        
        if (bit>>i) & 1 == 1:
            cnt += 1
    
    if cnt == K:
        max_height = a[0]
        price = 0
        for i in range(1, N):
            if ((bit>>i) & 1 == 1
                    and a[i] <= max_height):
                price += max_height + 1 - a[i]
                max_height += 1
            max_height = max(max_height, a[i])
        ans = min(ans, price)
print(ans)

Solution (Python):
def MII(): return map(int,input().split())
def LMI(): return list(map(int,input().split()))
import copy

n,k=MII()
hights=LMI()
money_list=[]
for i in range(2**(n-1)):
    bit = [i>>j&1 for j in range(n-1)]
    hights_copy=copy.deepcopy(hights)
    money=0
    if sum(bit)==k-1:
        for a in range(n-1):
            if bit[a]==1:
                tmp=max(hights_copy[:a+1])+1
                if tmp>hights_copy[a+1]:
                    money+=(tmp-hights_copy[a+1])
                    hights_copy[a+1]=tmp
        money_list.append(money)
print(min(money_list))

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

ans = max(a) * N

for i in range(pow(2, N)):
    candidate = bin(i)[2:].zfill(N)
    if candidate.count("1") != K:
        continue

    cost = 0
    local_min = a[0] - 1
    for j, build in enumerate(a):
        if candidate[j] == "1":
            cost += max(0, local_min + 1 - build)
            local_min = max(build, local_min + 1)
        else:
            local_min = max(build, local_min)

    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
import copy
N, K = map(int, input().split())
A =list(map(int, input().split()))
ans=10**15
for c in itertools.product([0,1],repeat=N):
    a=copy.deepcopy(A)
    sm=0
    for i in range(1,N):
        if c[i]==1:
            if a[i]<=max(a[:i]):
                sm+=max(a[:i])-a[i]+1
                a[i]=max(a[:i])+1
    cnt=1
    for i in range(1,N):
        if max(a[:i])<a[i]:
            cnt+=1
    if cnt==K:
        ans=min(ans,sm)
print(ans)

Solution (Python):
from itertools import combinations

def getval():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    return n,k,a

def main(n,k,a):
    arr = []
    locmax = 0
    for i in a:
        arr.append(locmax)
        locmax = max(locmax,i)

    ans = 2**60
    for c in combinations(range(1,n),k-1):
        cost = 0
        prev = a[0]
        for i in c:
            if a[i]<=prev:
                cost += max(prev,arr[i])+1-a[i]
            prev = max(max(prev,arr[i])+1,a[i])
        ans = min(ans,cost)
    if k==1:
        ans = 0
    print(ans)

if __name__=="__main__":
    n,k,a = getval()
    main(n,k,a)

Solution (Python):
from itertools import product
n, k = list(map(int, input().split()))
al = list(map(int, input().split()))
INF = float("inf")
ans = INF
for bit in product([0, 1], repeat=(n-1)):
    if sum(bit)+1 >= k:
        t = 0
        pre = al[0]
        for i, a in enumerate(al):
            if i != 0:
                if bit[i-1] == 1:
                    t += max(0, (pre+1)-al[i])
                    pre = max(al[i], pre+1)
                    continue
                pre = max(pre, al[i])
        ans = min(ans, t)
print(ans)

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

ans = float('inf')
for bit in range(1<<(n-1)):
  cand = [0]*(n-1)
  for i in range(n-1):
    if bit & 1<<i: cand[i] = 1
  if cand.count(1) != k-1: continue
  cost = 0
  mx = a[0]
  for i in range(1, n):
    if cand[i-1]:
      if a[i] <= mx:
        cost += mx-a[i]+1
        mx += 1
    mx = max(mx, a[i])
  ans = min(ans, cost)
print(ans)

Solution (Python):
def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    ans = 10 ** 12

    for i in range(2 ** n):
        highest = 0
        cost = 0
        cnt = 0

        for j in range(n):
            if (i >> j) & 1:
                cnt += 1
                if highest < a_list[j]:
                    highest = a_list[j]
                else:
                    highest += 1
                    cost += highest - a_list[j]
            else:
                highest = max(highest, a_list[j])

        if cnt < k:
            continue

        ans = min(ans, cost)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    ans = 10 ** 12

    for i in range(2 ** n):
        lst = []

        for j in range(n):
            if (i >> j) & 1:
                lst.append(j)

        if len(lst) < k:
            continue

        highest = a_list[0]
        cost = 0

        for j in range(1, n):
            if highest < a_list[j]:
                highest = a_list[j]
            else:
                if j in lst:
                    highest += 1
                    cost += highest - a_list[j]

        ans = min(ans, cost)

    print(ans)


if __name__ == "__main__":
    main()

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

inf=float('inf')

ans=inf

for i in range(2**n):
  iro=0
  ch=0
  cost=0
  h_max=a[0]
  for j in range(n):
    if (i>>j)&1:
      iro+=1
      if j==0:
        ch+=1
  if iro==k and ch==1:
    for j in range(1,n):
      if (i>>j)&1:
        if h_max<a[j]:
          h_max=a[j]
        else:
          cost+=(h_max+1)-a[j]
          h_max+=1
      else:
        if h_max<a[j]:
          cost+=(a[j]+1)-h_max
          h_max=a[j]+1
    ans=min(ans,cost)
  
print(ans)

Solution (Python):
from itertools import combinations

n, k = map(int, input().split())
a = [int(i) for i in input().split()]  
bar = [0] * n
for i in range(1, n):
    bar[i] = max(a[i-1], bar[i-1])


ans = float('inf')
for idx in combinations(range(1, n), k-1):
    x0 = a[0] ;dif = 0
    
    for i in range(k-1):
        if x0 < bar[idx[i]]:
            x0 = bar[idx[i]] 
        if a[idx[i]] > x0:
            x0 = a[idx[i]]
        else:
            dif += x0 - a[idx[i]] + 1
            x0 = x0 + 1
    ans = min(ans, dif)
print(ans)

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








ans = 10**100
for i in range(1,2**n,2):
    if k != sum([ i>>j & 1 for j in range(n)]) :
        continue
    kijun = a[0]
    cost = 0
    for j in range(1,n):
        if ((i>>j) & 1) :
            if a[j] <= kijun :
                cost += (kijun + 1 - a[j])
                kijun = kijun + 1
            else :
                kijun = a[j]
        else :
            kijun = max(kijun,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(1, 2**n, 2):
    if k != sum([i >> j & 1 for j in range(n)]):
        continue
    pre = a[0]
    cost = 0
    for j in range(1, n):
        if i >> j & 1:
            tmp = max(pre - a[j] + 1, 0)
            pre = a[j] + tmp
            cost += tmp
        else:
            pre = max(pre, a[j])
    ans = min(ans, cost)
print(ans)

Solution (Python):



import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例1(self):
        input = """5 5
3949 3774 3598 3469 3424"""
        output = """1541"""
        self.assertIO(input, output)

    def test_入力例2(self):
        input = """5 3
7 4 2 6 4"""
        output = """7"""
        self.assertIO(input, output)

    def test_入力例3(self):
        input = """2 2
7 8"""
        output = """0"""
        self.assertIO(input, output)


def resolve():
    N, K = map(int, input().split())
    a0, *A = map(int, input().split())

    ans = float("inf")
    for bit in range(1 << (N-1)):
        if bin(bit).count("1") != K-1:
            continue
        cost = 0
        target = a0+1
        for i, a in enumerate(A):
            if (1 << i) & bit == (1 << i):
                cost += max(0, target-a)
                target = a + max(0, target-a) + 1
            else:
                if a > target:
                    target = a+1
        ans = min(ans, cost)

    print(ans)


if __name__ == "__main__":
    
    resolve()

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


N,K = MI()
A = LI()

ans = 10**18
for i in range(2**(N-1)):
    r = 0
    color = 1
    height = A[0]
    for j in range(N-1):
        if A[j+1] > height:
            color += 1
            height = A[j+1]
        else:
            if (i >> j) & 1:
                color += 1
                r += height-A[j+1]+1
                height += 1
    if color >= K:
        ans = min(ans,r)

print(ans)

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

a_list = [i for i in range(n)]

ans = 10**12
for A in combinations(a_list[1:], k-1):
    a_max = a[0]
    tmp = 0
    for i in range(1, n):
        if i in A:
            if a[i] <= a_max:
                tmp += a_max-a[i]+1
                a_max += 1
        if a[i] > a_max:
            a_max = a[i]
    ans = min(ans, tmp)
print(ans)

Solution (Python):
def nasu(n):
  L = [0] * N
  for i in range(N):
    if n >> i & 1:
      L[i] = 1
  ans = 0
  t = a[0]
  for i in range(1, N):
    if L[i] == 1:
      if t >= a[i]:
        ans += t - a[i] + 1
        t = t + 1
      else:
        t = a[i]
    else:
      t = max(t, a[i])
  return ans

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

ans = 15 * 10 ** 9 

n = (1 << K) - 1
while n < (1 << N):
  ans = min(ans, nasu(n))

  x = n & -n
  y = n + x
  n = ((n & ~y) // x >> 1) | y

print(ans)

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

ans=float('inf')
for i in range(2**N):
    b=copy.deepcopy(a)
    num=0
    for j in range(N):
        if i>>j&1:
            num+=max(b[:j+1])+1-b[j]
            b[j]=max(b[:j+1])+1
    o=1
    
    for y in range(1,N):
        if max(b[:y])<b[y]:
            o+=1
    if o>=K:
        
        ans=min(num,ans)
        
print(ans)

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

ans = 10**18
for bit in range(1<<N):
    highest, cost, cnt = 0, 0, 0
    for i in range(N):
        if bit>>i & 1:
            if A[i] <= highest:
                cost += highest-A[i]+1
                highest += 1
            else:
                highest = max(highest,A[i])
            cnt += 1
        else:
            highest = max(highest,A[i])
    if cnt >= K:
        ans = min(ans, cost)

print(ans)

Solution (Python):
import itertools
import copy

def main():
    N,K = map(int, input().split())
    a_list = [int(e) for e in input().split()]

    
    
    
    

    ans = 10**100

    l = [i for i in range(0,N)]

    for v in itertools.combinations(l,K): 
        copied_a_list = copy.copy(a_list)
        
        v = set(v)
        left_max = copied_a_list[0]-1
        temp_ans = 0
        
        for i in range(N): 
            if i in v:
                temp_ans += max(0,left_max+1 - copied_a_list[i])
                copied_a_list[i] = max(left_max+1,copied_a_list[i])
            
            if copied_a_list[i] > left_max:
                left_max = copied_a_list[i]
        
        
        
        if temp_ans < ans:
            ans = temp_ans
            
    print(ans)

main()

Solution (Python):

def main():
    N, K = map(int, input().split())
    a = [int(x) for x in input().split()]

    ans = 10 ** 11
    for bit in range(1 << N):
        can = set()
        for i in range(1, N):
            if bit & (1 << i):
                can.add(i)
        h_max = a[0]
        cost = 0
        cnt = 1
        for i in range(1, N):
            res = h_max - a[i] + 1 if i in can and a[i] <= h_max else 0
            cost += res
            cnt += 1 if a[i] + res > h_max else 0
            h_max = max(h_max, a[i] + res)
        if cnt >= K:
            ans = min(ans, cost)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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

min_cost = float('inf')
for target_indexes in itertools.combinations(N_index, K-1): 
    cost = 0
    copy_A = A.copy()
    for i in target_indexes:
        if copy_A[i] <= max(copy_A[:i]):
            diff = max(copy_A[:i]) - copy_A[i] 
            copy_A[i] += diff + 1
            cost += diff + 1

    min_cost = min(min_cost, cost)

print(min_cost)

Solution (Python):
import itertools

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

min_cost = float('inf')
for target_indexes in itertools.combinations(N_index, K-1): 
    cost = 0
    copy_A = A.copy()
    for i in range(1, N):
        if i in target_indexes:
            if copy_A[i] <= max(copy_A[:i]):
                diff = max(copy_A[:i]) - copy_A[i] 
                copy_A[i] += diff + 1
                cost += diff + 1

    min_cost = min(min_cost, cost)

print(min_cost)

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):
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = inpl()

ans = float('inf')
for bi in itertools.product([0,1],repeat=n-1):
    if bi.count(1) < k-1:
        continue

    pre = A[0]
    s = 0
    for i in range(1,n):
        if bi[i-1] == 1:
            pre = max(pre+1,A[i])   
            s += max(0,pre-A[i])
        else:
            pre = max(pre,A[i])
    ans = min(ans,s)

print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7

    n,k=MI()
    height=LI()
    ans=inf
    for x in product([0,1],repeat=n):
        if sum(list(x))<k:
            continue
        mx=0
        res=0
        for i in range(n):
            if x[i]==1:
                if height[i]<=mx:
                    res+=mx-height[i]+1
                    
                    mx+=1
                else:
                    res+=0
                    mx=max(mx,height[i])
            else:
                mx=max(mx,height[i])
        
        ans=min(ans,res)
    print(ans)            
                
                
    
        
        
        
        




if __name__=="__main__":
    main()

Solution (Python):


import sys
import itertools


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N, K = list(map(int, input().split()))
    a = list(map(int, input().split()))

    return N, K, a


def main(N: int, K: int, a: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 建物の個数(1 <= N <= 15)
        K (int): 色の数(1 <= K <= N)
        a (list): 高さ(1 <= a_i <= 10**9)
    """
    
    ans = sys.maxsize
    for buildings in itertools.combinations(range(N), K):
        cost = 0
        highest = a[0] - 1
        for n in range(N):
            a_n = a[n]
            built = 0
            if n in buildings:
                built = max(highest - a_n + 1, 0)
                cost += built
            highest = max(highest, a_n + built)
        ans = min(ans, cost)

    
    print(ans)


if __name__ == "__main__":
    
    N, K, a = get_input()

    
    main(N, K, a)

Solution (Python):


import sys
import itertools


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


ans = sys.maxsize
for buildings in itertools.combinations(range(N), K):
    cost = 0
    highest = a[0] - 1
    for n in range(N):
        a_n = a[n]
        built = 0
        if n in buildings:
            built = max(highest - a_n + 1, 0)
            cost += built
        highest = max(highest, a_n + built)
    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(1<<N):
    seen = 1
    pay = 0
    now = a[0]
    for j in range(1, N):
        if (i >> j) & 1:
            if a[j] <= now:
                pay += now - a[j] + 1
                now += 1
                seen += 1
            else:
                break
        else:
            if a[j] > now:
                seen += 1
                now = a[j]
        if seen >= K:
            ans = min(ans, pay)
            break


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):
    kar = a[:]
    b = format(i, 'b').rjust(n,"0")
    if b.count("1") != k:
        continue
    now = 0
    cou = 0
    for j in range(n):
        if b[j] == "1":
            cou += max(0,now - kar[j] + 1)
            kar[j] += max(0,now - kar[j] + 1)
        now = max(now,kar[j])
    ans = min(ans,cou)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = tuple(map(int, input().split()))
import itertools
import numpy as np
ans_cnt = np.Inf
for now in itertools.combinations(range(1,N), K-1):
    height = A[0]
    cnt = 0
    for i in range(1,len(A)):
        if i in now:
            if A[i] > height:
                height = A[i]
            else:
                height += 1
                cnt += height - A[i]
        else:
            height = max(height, A[i])
    ans_cnt = min(cnt, ans_cnt)
print(ans_cnt)

Solution (Python):
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=float('INF')
for i in range(1<<(N-1)):
  cnt,s,t=0,0,a[0]+1
  for j in range(N-1):
    if i>>j&1:
      cnt+=1
      x=a[j+1]
      if x>=t:
        t=x+1
      else:
        s+=t-x
        t+=1
    else:
      t=max(t,a[j+1]+1)
  if cnt>=K-1:
    ans=min(ans,s)
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):
    can_see_list = list(bin(i)[2:].zfill(n))
    cost = 0
    now_hieght = A[0]
    if can_see_list[0] == '1':
        if can_see_list.count('1') < k:
            continue
    else:
        if can_see_list.count('1') < k - 1:
            continue
    for num, can_see in enumerate(can_see_list):
        if can_see == "1":
            if now_hieght >= A[num]:
                cost += (now_hieght - A[num]) + 1
                now_hieght = now_hieght + 1
            else:
                now_hieght = A[num]
        else:
            now_hieght = max(now_hieght, A[num])
    ans = min(ans, cost)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
ans = 10**11

for i in range(2 ** N):
    B = ""
    lenB = 0
    for j in range(N):
        if (i >> j) & 1:
            B += "1"
            lenB += 1
        else:
            B += "0"
    if lenB == K:
        s = 0
        cur = A[0]
        for k in range(1, N):
            if B[k] == "1" and A[k] <= cur:
                s += cur - A[k] + 1
                cur += 1
            else:
                cur = max(cur, A[k])
        
        ans = min(ans, s)
print(ans)

Solution (Python):
import itertools
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=float('inf')
for bit in itertools.product([0,1],repeat=N):
    if bit[0]==1 and bit.count(1)>=K:
        cost=0
        cr=a[0]
        for i in range(1,N):
            if bit[i]==1:
                if cr+1>=a[i]:
                    cost+=(cr+1-a[i])
                    cr=cr+1
                else:
                    cr=a[i]
            else:
                cr=max(cr,a[i])
        ans=min(ans,cost)
print(ans)

Solution (Python):
import copy
import math
import time
import statistics
import math


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

def get_int_multi():
    return map(int, input().split())

def get_string_char_list():
    return list(str(input()))




'''
while (idx < n) and ():

    idx += 1
'''

def main():
    start = time.time()

    n, k = get_int_multi()
    a = get_int_list()
    ans = 10 ** 10 * 15

    for i in range(2 ** n):
        count = 0
        for ii in range(n):
            if (i >> ii) & 1:
                count += 1
        if count != k: 
            continue

        wk_high = 0
        money = 0
        for ii in range(n):
            if (i >> ii) & 1:
                add_money = max(0, wk_high + 1 - a[ii])
                money += add_money
                wk_high = a[ii] + add_money
            else:
                wk_high = max(wk_high, a[ii])
        ans = min(ans, money)
    print(ans)




if __name__ == '__main__':
    main()

Solution (Python):

import itertools

import numpy as np



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

min_cost = 15000000001
for i in itertools.product([True, False], repeat=n):
    key = np.array(i, dtype=bool)
    if np.count_nonzero(key) != k:
        continue
    
    
    cost = 0
    max_height = 0
    for is_look, ai in zip(key, a):
        if not is_look:
            max_height = max(max_height, ai)
        elif ai > max_height:
            max_height = ai
        else:
            max_height += 1
            cost += max_height - ai
    
    min_cost = min(min_cost, cost)

print(min_cost)

Solution (Python):
import itertools

N,K = map(int,input().split())
A = list(map(int,input().split()))
L = [_ for _ in range(1,N)]
ans = float("inf")
cand = list(itertools.combinations(L,K-1))

for C in cand:
  C = list(C)
  C.sort()
  temp = 0
  prev = A[0] 
  
  Flag = True
  for i in C:
    
    if prev < max(A[:i]):
      
      Flag = False
      break
    if A[i] <= prev:
      prev += 1
      temp += prev-A[i]
    else:
      prev = A[i]
  if Flag:
    ans = min(ans,temp)
print(ans)

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

min_cost = float('inf')
for Buildings in itertools.combinations(range(N),K):
    min_height = 0
    cost = 0
    for i in range(N):
        if i in Buildings:
            h = A[i]
            if h>min_height:
                min_height = h
                continue
            cost+=(min_height+1) - h
            min_height += 1
            continue
        min_height = max(min_height,A[i])

    min_cost=min(min_cost,cost)

print(min_cost)

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

for i in range(1<<N):
  a = A[::]
  cur,add = 0,0
  see = 0
  for j in range(N):
    if (i>>j)&1:
      see += 1
      if cur >= a[j]:
        add += (cur-a[j])+1
        a[j] = cur+1
      cur = max(cur,a[j])
    else:
      cur = max(cur,a[j])

  if see == K:
    ans = min(ans, add)

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):
    x=format(i,'015b')
    Max=0
    yen=0
    for j in range(1,n+1):
        if x[-j]=='1':
            if Max<a[j-1]:
                Max=a[j-1]
            else:
                Max+=1
                yen+=Max-a[j-1]
        else:
            Max=max(Max,a[j-1])
    
    temp=0
    for j in range(15):
        temp+=int(x[j])
    
    if temp>=k:
        ans=min(ans,yen)
print(ans)