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
readline = sys.stdin.readline



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

ans = 10 ** 13
for i in range(2 ** N):
  case = bin(i)[2:].zfill(N)
  if case.count("1") < K:
    continue
  
  
  
  cost = 0
  high = 0
  for j in range(N):
    
    if (i >> j) & 1:
      if high >= A[j]:
        high += 1
        cost += (high - A[j])
    high = max(A[j], high)
  if ans > cost:
    ans = cost
print(ans)

Solution (Python):

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


def get_bits_pattern(n):
    bits_pattern = []
    for i in range(2**n):
        bits = [False]*n

        for j in range(n):
            if i >> j & 1:
                bits[j] = True
        bits_pattern.append(bits)
    return bits_pattern


bits_pattern = get_bits_pattern(n)
new_bits_pattern = []
for bits in bits_pattern:
    counter = 0
    for bit in bits:
        if bit:
            counter += 1
    if counter == k:
        new_bits_pattern.append(bits)

yens = []
for bits in new_bits_pattern:
    max_height = 0
    yen = 0
    for i, bit in enumerate(bits):
        if bit:
            if max_height >= a[i]:
                yen += max_height - a[i] + 1
                max_height = max(max_height, a[i]) + 1
            else:
                max_height = max(max_height, a[i])
        else:
            max_height = max(max_height, a[i])
            
    yens.append(yen)

import numpy as np
print(np.min(yens))

Solution (Python):
from itertools import combinations

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














    










best_score = float("inf")
for sel in combinations(range(N), K):
    sel = sorted(sel)
    cost = 0
    m = -1

    for i in range(N):
        if i not in sel:
            
            m = max(m, A[i])
        else:
            if m >= A[i]:
                cost += 1 + m - A[i]
                m += 1
            else:
                m = A[i]
    best_score = min(best_score, cost)
print(best_score)

Solution (Python):
import copy

n,m = map(int, input().split())
li = list(map(int, input().split()))

ans = 10**18
for i in range(2**n):
    check = [0]*n
    
    for j in range(n):
        if ((i >> j) & 1):
            check[n - j - 1] = 1

    if sum(check) < m:
        continue
    
    li_copy = copy.copy(li)
    tmp_ans = 0
    
    for x in range(n):
        if x == 0:
            continue
        if check[x] == 0:
            continue
        
        s = max(li_copy[0:x])
        t = li_copy[x]

        if s >= t:
            tmp_ans += s - t + 1
            li_copy[x] = s + 1
    ans = min(ans, tmp_ans)
    
print(ans)

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

from itertools import combinations as com

folds = com(range(N), K)
ans = float('inf')
for fold in folds:
    B = A[:]
    tmp = 0
    for i in range(1, K):
        if B[fold[i]] <= B[fold[i-1]]:
            diff = B[fold[i-1]] - B[fold[i]] + 1
            tmp += diff
            B[fold[i]] += diff

    k = 1
    border = B[0]
    for i in range(1, N):
        if border < B[i]:
            k += 1
            border = B[i]

    if k >= K:
        ans = min(ans, tmp)

print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    n, k = map(int, input().split())
    buildings = list(map(int, input().split()))

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

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

    print(ans)       

if __name__ == '__main__':
    main()

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 = 1
    prev_build = buildings[0]
    
    for j in range(1, n):
        if (i >> j) & 1:
            cnt += 1
            if prev_build >= buildings[j]:
                res += prev_build - buildings[j] + 1
                prev_build += 1
            else:
                prev_build = buildings[j]
        else:
            if prev_build < buildings[j]:
                cnt += 1
                prev_build = buildings[j]

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

print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
a=list(map(int,input().split()))
ans=10**30
if m==0:
  print(0)
  exit()
for i in itertools.combinations(range(1,n),m-1):
  s=list(i)
  mx=a[0]
  cost=0
  for j in range(1,n):
    if j in s:
      if a[j]>mx:
        mx=a[j]
        continue
      else:
        cost+=mx+1-a[j]
        mx+=1
    mx=max(mx,a[j])
  ans=min(cost,ans)
print(ans)

Solution (Python):
import sys
from itertools import product


def main():
    input = sys.stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 10 ** 12
    for p in product((0, 1), repeat=n - 1):
        max_h = a[0]
        visible = 1
        cost = 0
        for i in range(1, n):
            if a[i] > max_h:
                max_h = a[i]
                visible += 1
            elif p[i - 1]:
                cost += max_h + 1 - a[i]
                max_h += 1
                visible += 1
        if visible < k:
            continue
        ans = min(ans, cost)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
from itertools import combinations
ans = float("inf")
for c in combinations(range(n), k):
    c = sorted(c)
    val = 0
    m = -1
    for i in range(n):
        if i in c:
            if m>=a[i]:
                val += (m+1)-a[i]
                m = m + 1
            else:
                m = a[i]
        else:
            m = max(m, a[i])

    ans = min(ans, val)
print(ans)

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

money = 10**20

for i in range(2**n):
    cnt = 0
    b = a[:]
    max_b = b[0]
    for j in range(1, n):
        max_b = max(max_b, b[j])
        if i >> j & 1:
            cnt += max_b - b[j] + 1
            b[j] = max_b + 1
            max_b = b[j]
    col = 1
    m = b[0]
    for j in range(1, n):
        if b[j] > m:
            col += 1
            m = b[j]
    if col >= k:
        money = min(money, cnt)

print(money)

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


ans = float("inf")
for b in range(2 ** (N - 1)):
    cnt = 0
    cost = 0
    height = A[0]
    for i in range(N - 1):
        if height - A[i + 1] < 0:
            cnt += 1
            height = A[i + 1]
        elif (b >> i) & 1:
            cnt += 1
            cost += height - A[i + 1] + 1
            height += 1
    if cnt + 1 >= K:
        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):
    h = 0
    cost = 0
    count = 0
    for j in range(n):
        if j != 0:
            h = max(h, a[j - 1])
        if i >> j & 1:
            if h < a[j]:
                h = a[j]
                count += 1
            else:
                h += 1
                cost += h - a[j]
                count += 1
    if count >= k:
        ans = min(ans, cost)

print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 10**18
for i in range(1<<N):
    cnt = 0
    tot = 0
    now = 0
    for j in range(N):
        if A[j] > now:
            cnt += 1
            now = A[j]
        elif i&(1<<j):
            cnt += 1
            tot += now-A[j]+1
            now += 1
    if cnt >= K:
        ans = min(ans, tot)
print(ans)

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

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



ans=10**12
for i in Arr:
    cost=0
    hight=L[0]
    for j in range(1,N):
        if j in i:
            if hight<L[j]:
                hight=L[j]
            else:
                cost+=(hight-L[j]+1)
                hight+=1
        else:
            hight=max(hight,L[j])
    if ans>cost:
        ans=cost
print(ans)

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

ans = float('inf')
for key in range(1 << N):
    if bin(key).count('1') < K:
        continue
    cost = 0
    height = 0
    for i in range(N):
        if not (key & (1 << i)):
            height = max(A[i], height)
            continue
        height = max(A[i], height+1)
        cost += height - A[i]
    ans = min(ans, cost)
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, K = getNM()
A = getList()

N_a = K - 1
root = N - 1

def judge(array):
    A_alta = copy.deepcopy(A)
    highest = A_alta[0]
    cnt = 0
    for i in range(1, N):
        if i in array and A_alta[i] <= highest:
            cnt += highest - A_alta[i] + 1
            A_alta[i] = highest + 1
            highest = A_alta[i]
        if A[i] > highest:
            highest = A[i]
    return cnt

ans = float('inf')
def comb_pow_2(i, array):
    global ans
    if i == N_a:
        ans = min(ans, judge(array))
        return
    
    last = 0
    if len(array) > 0:
        last = array[-1]

    for j in range(last + 1, root + 1):
        new_array = array + [j]
        comb_pow_2(i + 1, new_array)
comb_pow_2(0, [])
print(ans)

Solution (Python):

n, k, *a = map(int, open(0).read().split())
ans = 10**18
for i in range(2 << n):
    h = 0
    c = 0
    b = 0
    for j in range(n):
        if a[j] > h:
            b += 1
            h = a[j]
        elif i >> j & 1:
            c += h - a[j] + 1
            h += 1
            b += 1
    if b >= k:
        ans = min(ans, c)
print(ans)

Solution (Python):
n,k=map(int,input().split())
INF=10**18
a=list(map(int,input().split()))
ans=INF
for i in range(2**(n-1)):
  cst=0
  cnt=0
  b=a[0]
  for j in range(n-1):
    if (i>>j) & 1:
      cst+=max(b+1-a[j+1],0)
      b=max(a[j+1],b+1)
      cnt+=1
    elif a[j+1]>b:
      cst+=a[j+1]-b
      b=a[j+1]
  if cnt==k-1:
    ans=min(ans,cst)
print(ans)

Solution (Python):
from itertools import combinations

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

work=lst[0]
ini=[x-work for x in lst]
ini_seen=[0]
work=0
for i in range(1,n):
    if ini[i]>work:
        work=ini[i]
        ini_seen.append(i)

mn=None
for x in combinations(range(n-len(ini_seen)),k-len(ini_seen)):
    sm=0
    work=0
    xtoken=0
    count=1
    for i in range(1,n):
        if i in ini_seen:
            count+=1
            if work<ini[i] : work=ini[i]
            else:
                work+=1
                sm+=work-ini[i]
        elif xtoken<len(x) and i==x[xtoken]+count:
            work+=1
            sm+=work-ini[i]
            xtoken+=1
    if not mn : mn=sm
    if mn>sm : mn=sm
print(mn)

Solution (Python):
import sys
from itertools import product
from copy import deepcopy

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A_init = list(map(int, input().split()))

    res = f_inf
    for pattern in product([0, 1], repeat=n - 1):
        A = deepcopy(A_init)
        cost = 0
        for idx, p in enumerate(pattern):
            if p == 1:
                prev = max([A[i] for i in range(idx + 1)])
                if A[idx + 1] > prev:
                    continue
                cost += prev + 1 - A[idx + 1]
                A[idx + 1] = prev + 1
        cnt = mi = 0
        for a in A:
            if mi < a:
                mi = a
                cnt += 1
        if cnt >= k:
            res = min(res, cost)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
from itertools import combinations as comb
n, k = map(int, input().split())
ns = list(map(int, input().split()))
res = float('inf')
perms = list(range(1,n))
for p in comb(perms, k-1):
    res_tmp = 0
    tmp_max = 0
    p = [0] + list(p)
    for i in range(n):
        if i in p and ns[i] <= tmp_max:
            res_tmp += tmp_max - ns[i] + 1
            tmp_max = tmp_max + 1
        else:
            tmp_max = max(tmp_max, ns[i])
    res = min(res, res_tmp)
print(res)

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

res = float('inf')

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

  if paint == K:
    res = min(res, add)

print(res)

Solution (Python):
from itertools import combinations
import numpy as np

n, k = map(int, input().split())
arr = np.array(list(map(int, input().split())))

ans = 1 << 60
for x in list(combinations(range(1, n), k - 1)):
    h = 0
    tmp_arr = arr.copy()
    for i in x:
        big = tmp_arr[:i].max() + 1
        if big > tmp_arr[i]:
            h += big - tmp_arr[i]
            tmp_arr[i] = big
    ans = min(ans, h)

print(ans)

Solution (Python):
def num_cleared(N, A):
    cleared = 0
    highest_h = 0
    for i in range(N):
        h = A[i]
        if h > highest_h:
            cleared += 1
            highest_h = h
    return cleared

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

    cleared = num_cleared(N, A)
    if cleared >= K:
        print(0)
        return

    ans = N * 10**9
    for i in range(1 << N):
        highest_h = A[0]
        cost = 0
        B = [A[0]]
        for j in range(1, N):
            h = A[j]
            if ((i >> j) & 1) == 0:
                highest_h = max(h, highest_h)
                B.append(h)
                continue
            if highest_h >= h:
                cost += (highest_h - h) + 1
                highest_h += 1
                B.append(highest_h)
            else:
                B.append(h)
        cleared = num_cleared(N, B)
        if cleared >= K:
            ans = min(ans, cost)
    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(2**n):
    num=format(i,"b").zfill(n)
    if num.count("1")!=k:continue
    height,money=0,0
    for j in range(n):
        if num[j]=="1":
            if A[j]<=height:
                money +=height-A[j]+1
                height +=1
            else:height=A[j]
        else:
            if A[j]>height:height=A[j]
    ans=min(ans,money)
print(ans)

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

for i in range(2**(N-1)):
    L=[0]*(N-1)
    total=0
    count=0
    for j in range(N-1):
        if ((i>>j)&1):
            L[j]=1
            count+=1
    if count>=K-1:
        A=copy.copy(B)
        for m in range(N-1):
            
            if L[m]==1:
                height=max(max(A[:m+1])+1,A[m+1])
                total+=height-A[m+1]
                A[m+1]=height
                
        ans.append(total)
        

print(min(ans))

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

ans = float('inf')
for bit in range(2**(N-1)):
    pre_num = a_list[0]
    ans_pre = 0
    count = 1
    index = []
    for i in  range(N-1):
        if bit & (1<<i):
            count+=1
            index.append(i+1)
            if pre_num >= a_list[i+1]:
                ans_pre += pre_num-a_list[i+1]+1
            
                pre_num += 1
                
            else:
                pre_num = a_list[i+1]
                
        else:
            pre_num = max(pre_num, a_list[i+1]+1)
    if count >= K:
        ans = min(ans, ans_pre)
            
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=15*10**10
for i in range(2**(n-1)):
    cnt,s,mh=0,0,a[0]+1
    for j in range(n-1):
        if i>>j&1:
            cnt+=1
            x=a[j+1]
            if x>=mh:
                mh=x+1
            else:
                s+=mh-x
                mh+=1
        else:
            mh=max(mh,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()))
if n==k:
    suma=sum(a)
    m=a[0]+1
    for i in range(1,n):
        x=a[i]
        if x>=m:
            m=x+1
        else:
            a[i]=m
            m+=1
    print(sum(a)-suma)
    exit()
ans=15*10**10
for i in range(2**(n-1)):
    cnt,s,mh=0,0,a[0]+1
    for j in range(n-1):
        if i>>j&1:
            cnt+=1
            x=a[j+1]
            if x>=mh:
                mh=x+1
            else:
                s+=mh-x
                mh+=1
        else:
            mh=max(mh,a[j+1]+1)
    if cnt>=k-1:
        ans=min(ans,s)
print(ans)

Solution (Python):

import copy
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 10**9*15
for i in range(2**(N-1)):
    B = copy.copy(A)
    count = 0
    bit = 0
    for j in range(N-1):
        bit = bit + (1&(i>>j))
    if(bit == K-1):
        for k in range(N-1):
            if(i>>k&1):
                if max(B[0:k+1]) >= B[k+1]:
                    dif =max(B[0:k+1])-B[k+1]+1
                    B[k+1] += dif
                    count += dif
        ans = min(ans,count)
print(ans)

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 j in range(1, n):
        if j in b:
            if a[j] <= mx : 
                mx += 1
                score += (mx - a[j])
            else: 
                mx = a[j]
        else:
            mx = max(mx, a[j])
    mn = min(mn, score)
print(mn)

Solution (Python):

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

ans = 10 ** 18
for bit in range(1 << N):
    
    count = 0
    for i in range(N):
        if bit & 1 << i > 0:
            count += 1
    if count < K:
        continue

    cost = 0
    h = -1
    for i in range(N):
        if bit & 1 << i > 0:
            if A[i] <= h:
                cost += h - A[i] + 1
                h += 1
        h = max(h, A[i])
    ans = min(ans, cost)
print(ans)

Solution (Python):
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
MIN = float('inf')
for bit in range(1<<N):
    tmpA = A[:]
    L = []
    for i in range(N):
        if bit & (1<<i):
            L.append(i)
    SUM = 0
    for l in L:
        MAX = max(tmpA[:l]+[0])
        if MAX >= tmpA[l]:
            SUM += MAX+1-tmpA[l]
            tmpA[l] = MAX+1
    count = 0
    MAX = 0
    for i in range(N):
        if tmpA[i] > MAX:
            count += 1
            MAX = tmpA[i]
    if count >= K:
        MIN = min(MIN,SUM)
print(MIN)

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

for i in range(1<<n-1):
  if bin(i).count("1")!=k-1:
    continue
  cnt=0
  cost=0
  
  prevh=a[0]
  for j in range(n-1):
    if 1<<j & i:
      if prevh>=a[j+1]:
        cost+=prevh+1-a[j+1]
        prevh+=1
        
      else:
        prevh=a[j+1]
    else:
      prevh=max(prevh,a[j+1])
  ans=min(ans,cost)
  
print(ans)

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

ans = 1e+18
for i in range(1<<N):
  if bin(i).count('1') != K:
    continue
  cost = 0
  cur_height = 0
  for j in range(N):
    if i & (1<<j):
      cost += max(0, cur_height-a[j]+1)
      cur_height = max(a[j], cur_height+1)
    else:
      cur_height = max(a[j], cur_height)
  ans = min(ans, cost)
print(ans)

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


for i in range(1 << n):
    li = []
    for j in range(n):
        if (i >> j)&1:
            li.append(j)
    if len(li) < k:
        continue
    point = 0
    now = a[0]
    for l in range(1,n):
        if l in li and a[l] <= now:
            point += now+1-a[l]
            now += 1
        now = max(now,a[l])
    ans = min(ans,point)
    
print(ans)

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

ans = float('inf')
for status in range(1<<N):
    cnt = 0
    tmp = 0
    std = 0
    for mask in range(N):
        if (1<<mask)&status:
            cnt += 1
            if std >= A[mask]:
                tmp += std - A[mask] + 1
                std += 1
        
        std = max(std,A[mask])
    if cnt >= K:
        ans = min(ans,tmp)
    
print(ans)

Solution (Python):
import copy

def bit_all(n,k,nn):
    ans = float("inf")
    for i in range(2 ** n):
        m = 0
        cnt = 0
        num = copy.deepcopy(nn)
        kind = 0
        for j in range(n):
            
            if ((i >> j) & 1):
                
                if m >= num[j]:
                    cnt += 1 + m - num[j]
                    num[j] = m+1
                m = max(m,num[j])
                kind += 1
            else:
                
                if num[j] > m:
                    m = num[j]
                    kind += 1
        if kind >= k:
            ans = min(ans,cnt)
            
    return ans
n,k = map(int,input().split())
num = list(map(int,input().split()))
print(bit_all(n,k,num))

Solution (Python):
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq

n, k = map(int, sys.stdin.readline().split())

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

l = list(itertools.combinations(range(n), k))

ans = 10 ** 18
for i in range(len(l)):
    cost = 0
    m1 = 0
    p = 20
    for j in range(l[i][0]+1):
        if a[j] > m1:
            m1 = a[j]
            p = j

        if j == l[i][0]:
            if m1 == a[j]:
                if p != j:
                    cost += 1
            else:
                cost += (m1 - a[j] + 1)

    
    r = 1
    if len(l[0]) >= 2:
        q = l[i][r]
    else:
        q = 20

    m2 = a[l[i][0]] + cost

    for j in range(l[i][0]+1, n):
        if j == q:
            if a[j] > m2:
                m2 = a[j]
            else:
                m2 += 1
                cost += (m2 - a[j])

            if r != len(l[0])-1:
                r += 1
                q = l[i][r]
            
        else:
            if a[j] > m2:
                cost += a[j] - m2
                m2 = a[j]
                

    if cost < ans:
        ans = cost


print(ans)

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

def slove():
    n, k = map(int,input().split())
    building = list(map(int,input().split()))
    
    
    ans = 10 ** 15
    for i in range(1 << n):
        if i & 1 == 1 or bin(i >> 1).count("1") != k-1:
            continue

        
        
        """ 
        p_b = [building[0],]
        for j in range(1,n):
            if i >> j & 1 == 1:
                p_b.append(building[j])
        
        tmp_ans = 0
        max_h = p_b[0]
        for j in range(1,n):
            if max_h < p_b[j]:
                max_h = p_b[j]
                continue
            else:
                tmp_ans += 1 + max_h - p_b[j]
                max_h += 1
        
        else:
            ans = min(ans,tmp_ans)
        """
        tmp_ans = 0
        highest = 0
        for j in range(n):
            if i >> j & 1 and highest < building[j]:
                highest = building[j]
            elif i >> j & 1 and highest >= building[j]:
                highest += 1
                tmp_ans += highest - building[j]
            else:
                if highest < building[j]:
                    highest = building[j]
        ans = min(ans,tmp_ans)
    print(ans)

if __name__ == "__main__":
    slove()

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

cost = 10 ** 18
for i in range(2 ** (n - 1)):
    num = 0
    c = 0
    prev = a[0]
    for j in range(n - 1):
        if i >> j & 1:
            num += 1
            if a[j + 1] <= prev:
                c += prev - a[j + 1] + 1
                prev += 1
        prev = max(prev, a[j + 1])
    if num >= k - 1:
        cost = min(c, cost)
print(cost)

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

ans = pow(10, 18)

for i in range(2 ** N):
    cost = 0
    cnt = 0
    highest = 0
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
            if highest >= a[j]:
                cost += highest - a[j] + 1
                highest += 1

        highest = max(highest, a[j])
    if cnt >= K:
        ans = min(cost, ans)

print(ans)

Solution (Python):
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K,*A= map(int, read().split())
l = [i for i in range(1,N)]
cost = float('inf')
for B in itertools.combinations(l,K-1):
  ans = 0
  pre = A[0]
  j = 0
  for i in range(1,N):
    if j == K-1:
      break
    if B[j]== i:
      j+=1
      if pre < A[i]:
        pre = A[i]
      else:
        ans += pre-A[i]+1
        pre +=1
    else:
      if pre < A[i]:
        pre = A[i]
  cost = min(ans,cost)
print(cost)

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

ans = pow(10, 18)

for i in range(2 ** N):
    cost = 0
    cnt = 0
    highest = 0
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
            if highest >= a[j]:
                cost += highest - a[j] + 1
                highest += 1

        highest = max(highest, a[j])
    if cnt >= K:
        ans = min(cost, ans)

print(ans)

Solution (Python):
import itertools


N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = float('inf') 

for pattern in itertools.combinations(range(1,N),K-1):
    temp_cost = 0
    temp_pattern = [0] + list(pattern)
    max_high = a[0]

    for i in range(1,N):
        if i in temp_pattern:
            diff = a[i]- max_high
            if diff ==  0:
                temp_cost += 1
                max_high = max_high + 1
            elif diff < 0 :
                temp_cost += ( max_high - a[i] ) + 1
                max_high = max_high +1
            else:
                temp_cost += 0
                max_high = a[i]
        else:
            max_high = max (a[i] ,max_high)

    ans = min(ans, temp_cost)

print(ans)

Solution (Python):
import copy
import sys

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

def dfs(bitstring):
  if len(bitstring) == N:
    if sum(bitstring) == K:
      cost = 0
      B = copy.deepcopy(A)
      for i in range(1, N):
        if bitstring[i]:
          previousMax = max(B[0:i])
          if previousMax < B[i]:
            continue
          else:
            cost += previousMax - B[i] + 1
            B[i] = previousMax + 1
      return cost
    else:
      return sys.maxsize
  else:
    return min(dfs(bitstring + [False]), dfs(bitstring + [True]))

print(dfs([1]))

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

ans = 10 ** 100
for item in itertools.combinations(range(n), r=k):
    tmp = 0
    b = copy.copy(a)
    for i in item:
        b[i] = a[i] if i==0 else max(max(b[:i]) + 1, a[i])
        tmp += b[i] - a[i]
    ans = min(ans, tmp)
print(ans)