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

Solution (Python):
N, K = list(map(int, input().split()))
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)

Solution (Python):

import sys
from collections import Counter
from itertools import permutations, combinations
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10 ** 6)

def input():
    return sys.stdin.readline()[:-1]

def main():
    n, k = map(int, input().split())
    a = tuple(map(int, input().split()))
    
    select = []
    for i in range(1 << n):
        comb = [None] * n
        cnt = 0
        for j in range(n):
            if (i >> j) & 1:
                comb[j] = 1
                cnt += 1
            else:
                comb[j] = 0
        if cnt == k:
            select.append(comb)

    ans = float('inf')
    for s in select:
        tmp_a = list(a)
        tmp_ans = 0
        for i in range(1, n):
            max_height = max(tmp_a[:i])
            if s[i] and max_height >= tmp_a[i]:
                tmp_ans += max_height - tmp_a[i] +1
                tmp_a[i] = max_height + 1
        ans = min(ans, tmp_ans)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = float('inf')
def search(x):
    if len(x)==n:
        if x.count(1)>=k:
            global ans
            m = a[0]
            c = 0
            for i in range(1,n):
                if x[i]==1:
                    c += max(0,m-a[i]+1)
                    m = max(m+1,a[i])
                m = max(m,a[i])
            ans = min(ans,c)
    else:
        search(x+[1])
        search(x+[0])
search([])
print(ans)

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

ans=float("inf")
for i in range(1,2**n):
    num=format(i,"b").zfill(n)
    point=0
    if num.count("1")!=k:continue
    highest=A[0]
    for j in range(1,n):
        if highest>=A[j] and  num[j]=="1":
            point +=highest-A[j]+1
            highest +=1
        highest=max(highest,A[j])
    ans=min(ans,point)

print(ans)

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

ans=float("inf")
for i in range(1,2**n):
    num=format(i,"b").zfill(n)
    point=0
    if num.count("1")!=k:continue
    highest=A[0]
    for j in range(1,n):
        if num[j]=="1":
            point +=max(0,highest-A[j]+1)
            highest=max(highest+1,A[j])
        highest=max(highest,A[j])
    ans=min(ans,point)

print(ans)

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 = 10 ** 15

for bit in range(2 ** N):
    cnt = 0
    for i in range(N):
        if (bit >> i) & 1:
            cnt += 1

    if cnt < K:
        continue

    cost = 0
    height = A[0]
    if (bit >> 0) & 1:
        for i in range(1, N):
            if (bit >> i) & 1 and height >= A[i]:
                cost += height - A[i] + 1
                height += 1
            elif height < A[i]:
                height = A[i]

        res = min(res, cost)

print(res)

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

res = 10 ** 15

for bit in range(2 ** N):
    cnt = 0
    for i in range(N):
        if (bit >> i) & 1:
            cnt += 1

    if cnt < K:
        continue

    cost = 0
    height = 0
    for i in range(0, N):
        if (bit >> i) & 1 and height >= A[i]:
            cost += height - A[i] + 1
            height += 1
        elif height < A[i]:
            height = A[i]

    res = min(res, cost)

print(res)

Solution (Python):
import itertools

N,K = map(int,input().split())
a = list(map(int,input().split()))
lis = [x for x in range(1,N)]
m = 10**15

for con in itertools.combinations(lis, K-1):
  mm = 0
  f = a[0]
  for i in range(K-1):
    if f+1 <= a[con[i]]:
      f = a[con[i]]
    else:
      mm += (f+1) - a[con[i]]
      f += 1
    for j in range(con[i]-1):
      if a[j] >= f:
        mm = 10**15
        break
    else:
      continue
    break
  m = min(m,mm)
  
print(m)

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

ans = 10**18
for bit in product(range(2), repeat=n):
    ma = 0
    cost = 0
    see = 0
    for i in range(n):
        ai = a[i]
        if ai>ma:
            see += 1
            ma = ai
        elif bit[i]:
            ma = ma + 1
            see += 1
            co = ma - ai
            cost += co
    if see>=k:
        ans = min(ans, cost)
            
print(ans)

Solution (Python):
from itertools import combinations
INF = int(1e18)
def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    p = [i for i in range(1,n)]
    
    
    ans = INF
    for i in combinations(p, k-1):
        s = set(i)
        cost = 0
        mx = a[0]
        for j in range(1, n):
            if j in s:
                if a[j] > mx:
                    mx = a[j]
                    continue
                mx += 1
                cost += mx-a[j]
            mx = max(mx, a[j])
        ans = min(cost, ans)                
    print(ans)
main()

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
money = float('inf')
for bit in range(1 << N):
    S = [0]*N
    for i in range(N):
        if bit & (1 << i):
            S[i] = 1
    if S.count(1) >= K:
        sumnum = 0
        maxh = A[0]
        for i in range(1, N):
            if S[i] == 1:
                if A[i] > maxh:
                    maxh = A[i]
                else:
                    maxh += 1
                    sumnum += (maxh - A[i])
            else:
                maxh = max(maxh, A[i])

        money = min(money, sumnum)
print(money)

Solution (Python):
import copy

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

ans = []
for i in range(2**N):
    s = a.copy()
    cnt = 0
    tmp = 1
    henkou = [False for _ in range(N)]
    for j in range(N):
        if((i >> j)&1):
            henkou[j] = True
    bill = s[0]
    for k in range(1, N):
        if(henkou[k]):
            if(bill >= s[k]):
                cnt += bill-s[k]+1
                s[k] = bill+1
                bill = s[k]
                tmp += 1
            else:
                bill = s[k]
                tmp += 1
        else:
            if(bill < s[k]):
                bill = s[k]
                tmp += 1
    if(tmp >= K):
        ans.append(cnt)
print(min(ans), end='\n')

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

ans = 10**15
for i in range(2**n):
    
    maxheight = a[0]
    money = 0
    see = 1
    for j in range(1,n):
        if see >= k:
            break 
        if a[j]>maxheight:
            see += 1
            maxheight = a[j]
        elif a[j]<=maxheight and (i>>j)&1 ==1:
            
            money += maxheight-a[j]+1
            
            maxheight += 1
            see +=1
    
    if see >= k and money <= ans:
        ans = money
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):
    height = a[0]
    count = 1
    cost = 0
    for j in range(1,n):
        if (i>>j)&1:
            cost += max(0,(height-a[j]+1))
            height = max(height+1, a[j])
            count +=1
        else:
            if a[j] > height:
                count +=1
                height = a[j]
    if count >= k:
        ans = min(ans, cost)
print(ans)

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10**7)

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

LEN = 1 << N
H = np.zeros(LEN,dtype = np.int64)
cost = np.zeros(LEN,dtype = np.int64)


for i,a in enumerate(A):
    bit = 1 << i
    H[bit:2*bit] = np.maximum(H[:bit]+1,a)
    H[:bit] = np.maximum(H[:bit],a)
    cost[bit:2*bit] = (H[bit:2*bit] - a) + cost[:bit]

pop_count = np.zeros(LEN,dtype=np.int32)
for i in range(LEN):
    pop_count[i] = bin(i).count('1')


print(cost[pop_count >= K].min())

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

import numpy as np

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

L = 1 << N
right = np.zeros(L,dtype=np.int64)
total = np.zeros(L,dtype=np.int64)

for i, v in enumerate(A):
    bit = 1 << i
    
    right[bit:2*bit] = np.maximum(right[:bit]+1,v)
    np.maximum(right[:bit], v, out=right[:bit])
    total[bit:2*bit] = (right[bit:2*bit] - v) + total[:bit]
    
    



popcount = np.zeros(L,dtype=np.int32)
rng = np.arange(L)

for _ in range(15):
    popcount += rng&1
    rng >>= 1



answer = total[popcount >= K].min()
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

import numpy as np

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

L = 1 << N
right = np.zeros(L,dtype=np.int64)
total = np.zeros(L,dtype=np.int64)

for i, v in enumerate(A):
    bit = 1 << i
    
    right[bit:2*bit] = np.maximum(right[:bit]+1,v)
    np.maximum(right[:bit], v, out=right[:bit])
    total[bit:2*bit] = (right[bit:2*bit] - v) + total[:bit]
    
    



popcount = np.zeros(L,dtype=np.int32)
rng = np.arange(L)

for _ in range(15):
    popcount += rng&1
    rng >>= 1



answer = total[popcount >= K].min()
print(answer)

Solution (Python):





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



def calc(i, heights):
    cost = 0
    for shift in range(1, N):
        if i & (1 << shift):
            max_h = max(heights[:shift])
            if max_h >= heights[shift]:
                cost += (max_h + 1) - heights[shift]
                heights[shift] = max_h + 1
    return cost


str_bin = ""
for _ in range(K):
    str_bin += "1"
min_i = int(str_bin, 2)
min_cost = float("inf")


def is_valid(i, K):
    count = 0
    for bit in range(N):
        if i & (1 << bit):
            count += 1
    if count == K:
        return True
    return False


for i in range(min_i, 2 ** N):
    if is_valid(i, K):
        heights_copy = heights[:]
        
        cost = calc(i, heights_copy)
        
        min_cost = min(min_cost, cost)

print(min_cost)

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):
import sys
import copy

readline = sys.stdin.readline

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

    h = [max(a[:i]) for i in range(1, N+1)]
    

    mincost = float('inf')
    for i in range(2**N):
        cost = 0
        htmp = copy.copy(h)
        tmp = []
        tmpappend = tmp.append
        for j in range(N):
            if (i>>j) & 1:
                tmpappend(j)
        if len(tmp) != K:
            continue
        
        for k in tmp:
            if k >= 1 and htmp[k] <= htmp[k-1]:
                maxh = max(htmp[:k])
                cost += maxh - a[k] + 1
                htmp[k] = maxh + 1
        
        mincost = min(mincost, cost)

    print(mincost)

if __name__ == "__main__":
    main()

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    N, K = iip()
    A = iip()


    ans = 10**30
    for i in range(2**N):
        cn = 0
        mh = 0
        cost = 0
        m = 1
        for j in range(N):
            if (i % (m*2)) // m == 1:
                
                cn += 1
                mh = max(mh+1, A[j])
                cost += mh-A[j]
            else:
                mh = max(mh, A[j])
            m *= 2
        if cn >= K:
            ans = min(cost, ans)

    print(ans)




def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=True):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m

def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): 
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    N, K = iip()
    A = iip()


    ans = 10**30
    for i in range(2**N):
        cn = 0
        mh = 0
        cost = 0
        for j in range(N):
            if (i % 2**(j+1)) // 2**j == 1:
                
                cn += 1
                mh = max(mh+1, A[j])
                cost += mh-A[j]
            else:
                mh = max(mh, A[j])
        if cn >= K:
            ans = min(cost, ans)

    print(ans)




def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=True):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m

def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): 
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import product

def main():
    n, k = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    res = 10e10
    for t in product([0,1], repeat=n):
        if sum(t) < k:
            continue
        a_tmp = list(a)
        score = 0
        t_height = 0
        cnt = 0
        for i, h in enumerate(a_tmp):
            if t_height < h:
                t_height = h
                cnt += 1
            elif t[i]:
                t_height += 1
                score += t_height - h
            if cnt >= k:
                break
        res = min(res, score)
    print(res)
if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))
result = 1000000001*15
def j_cost(cost):
    c = 1
    for i in range(1,len(A)):
        if(max(cost[:i]) < cost[i]):
            c += 1
    
    if c >= k:
        return True
    else:
        return False

for i in range(2**n):
    cost = [0]*len(A)
    for j in range(1,n):
        if((i>>j)&1):
            total = [x + y for (x,y) in zip(A[:j],cost[:j])]
            if(max(total)>=A[j]):
                cost[j] = max(total)+1-A[j]
            else:
                cost[j] = 0
    
    if(sum(cost) < result and j_cost([x + y for (x,y) in zip(A,cost)])):
        result = sum(cost)
print(result)

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))
result = 1000000001*15
def j_cost(cost):
    c = 1
    for i in range(1,len(A)):
        if(max(cost[:i]) < cost[i]):
            c += 1
    
    if c >= k:
        return True
    else:
        return False

for i in range(2**n):
    cost = [0]*len(A)
    for j in range(1,n):
        if((i>>j)&1):
            total = [x + y for (x,y) in zip(A[:j],cost[:j])]
            if(max(total)>=A[j]):
                cost[j] = max(total)+1-A[j]
            else:
                cost[j] = 0
    
    if(sum(cost) < result and j_cost([x + y for (x,y) in zip(A,cost)])):
        result = sum(cost)
print(result)

Solution (Python):



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

ans = float('inf')
for bit in range(2**N):
    cnt = 0
    for i in range(N):
        if bit >> i & 1:
            cnt += 1
    if cnt < K:
        continue

    cost = 0
    maxh = 0
    for i, a in enumerate(A):
        if bit >> i & 1 and maxh >= a:
            cost += maxh - a + 1
            maxh += 1
        elif maxh < a:
            maxh = a


    if cost < ans:
        ans = cost


print(ans)

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

inf = 10 ** 9 * 15
ans = inf
for bits in range(2 ** n):
    selected = set()
    for shift in range(n):
        if bits & (1 << shift) > 0:
            selected.add(shift)

    if len(selected) < k:
        continue
    highest = aa[0]
    cost = 0

    for i in range(1, n):
        if highest < aa[i]:
            highest = aa[i]
        else:
            if i in selected:
                highest += 1
                cost += highest - aa[i]
    ans = min(ans, cost)
print(ans)

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

ans=10**12

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

    if cnt>=K:
        ans=min(ans,cost)

print(ans)

Solution (Python):
from itertools import combinations as comb

N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = 10**17

for i in comb([n for n in range(1, N)], K-1):
    tmpa = a[:]
    tmp = 0
    for j in range(K-1):
        pre = max(tmpa[:i[j]])
        if tmpa[i[j]] <= pre:
            tmp += pre+1-tmpa[i[j]]
            tmpa[i[j]] = pre+1
    
    if tmp < ans:
        ans = tmp

print(ans)

Solution (Python):
import math
import copy
import sys
import fractions


import decimal
import heapq
import collections
import itertools












def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




n, k = map(int, input().split())
data = getInputIntList()

items = [n for n in range(1,n)]
comb = []
for v in itertools.combinations(items,k-1):
    comb.append(v)

ans = sys.maxsize
for com in comb:
    tmpans = 0
    highest = data[0]
    for i in range(1, n):
        if i in com:
            if highest < data[i]:
                highest = data[i]
                continue
            else:
                highest += 1
                tmpans += highest - data[i]
        else:
            if highest < data[i]:
                highest = data[i]
                continue
  

    ans = min(ans, tmpans)

if k == 1:
    print(0)
else:
    print(ans)

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


def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))





from itertools import combinations

def main():
	n,k=MI()
	ans=10**18

	A=LI()
	A=[A[0]-1]+A

	for t in combinations(range(n),k):
		B=A.copy()
		tmp=0
		for i in t:
			i+=1
			B[i]=max(max(B[:i])+1,A[i])
			tmp+=B[i]-A[i]
		ans=min(ans,tmp)
	print(ans)

if __name__ == "__main__":
	main()