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].



Sample input:
5 5
3949 3774 3598 3469 3424


Sample output:
1541

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())

ans = 10 ** 9 * 20
for bit in range(2 ** N):
    if bin(bit).count("1") < K or not (bit >> 0 & 1):
        continue

    res = 0
    tmp = A[0]
    for i in range(1, N):
        if bit >> i & 1:
            res += max(0, tmp - A[i] + 1)
            tmp = max(A[i], tmp + 1)
        else:
            tmp = max(A[i], tmp)
    ans = min(ans, res)

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**11#INF

# 先頭を除いたn-1個からk-1個を選んで全探索 n,kが小さいのでbit全探索する
for i in range(2**(n-1)):
  select = [0]#先頭は必ずk　の中に入る
  len_select = 1
  for j in range(n-1):
    if i >> j & 1 and len_select < k:
      select.append(j+1)#先頭を除いてj 個目を選ぶ
      len_select += 1
  # 選び終わったら、selectないの各要素に対してそれより前にselectの要素外に自身より大きいものがないか確かめる
  # 前から操作してmaxを保持すればO(n),めんどくさいのでO(n**3)でやる
  ok = 1
  #print(select,i)
  for m in select:
    for l in range(n):
      if l in select: continue
      if l < m and a[l] >= a[m]:
        #print(i,m)
        ok = 0
  if ok == 0 or len_select < k: continue
  else:
    ans_i = 0
    pre_val = a[0]#1つ前の要素の値
    for j in range(1,k):
      #print(i,a[select[j]])
      if pre_val >= a[select[j]]:
        ans_i += pre_val+1 - a[select[j]]
        pre_val += 1
      else:#元々大きい
        pre_val = a[select[j]]
  ans = min(ans,ans_i)
print(ans)

Submission status: Accepted

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

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

ans = 10**18

for p in range(1<<N):
    P=p
    if popcount(p) < K: continue
    cost = 0
    mx = 0
    for a in A:
        flag = p&1
        p >>= 1
        if flag:
            if mx >= a:
                cost += mx + 1 - a
                mx += 1
            else: mx = a
        else: mx = max(mx, a)
    ans = min(ans, cost)

print(ans)

Submission status: Accepted

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

ans = 10 ** 18
for build in product(range(2), repeat=N - 1):
    if sum(build) != K - 1:
        continue

    # 左のやつは絶対見る
    cost = 0
    h = A[0]
    for i, p in enumerate(build, start=1):
        if p == 0:
            h = max(h, A[i])
            continue
        if A[i] > h:
            h = A[i]
            continue
        else:
            h += 1
            cost += (h - A[i])
    ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
if K==1:
    print(0)
    exit()

ans = 10**12
for b in range(1<<(N-1)):
    h = A[0]
    k = 1
    cost = 0
    for i in range(N-1):
        a = A[i+1]
        if a > h:
            k += 1
            h = a
        elif b&(1<<i):
            k += 1
            cost += h+1 - a
            h += 1
    if k >= K:
        ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
def examA():
    N, L = LI()
    V, D = LI()
    X = [LI()for _ in range(N)]

    ans = 0
    print(ans)
    return

def examB():
    N, K = LI()
    H = 11; W = 7
    S = [[0]*(W+1) for _ in range(H+3)]
    for h in range(H+2):
        for w in range(W):
            S[h+1][w+1] = (S[h][w+1] + S[h+1][w] - S[h][w] + (7*h+w+1))
    #print(S)
    base = 0
    for h in range(H):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                base += 1
                #print(h,w)
    ans = base * ((N-2)//11)
    #print(ans)
    rest = (N-2)%11
    for h in range(rest):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                ans += 1
                #print(h,w)
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    loop = 2**N
    ans = inf
    for i in range(loop):
        cnt = 0
        need = 0
        highest = 0
        for j in range(N):
            if i&(1<<j)==0:
                if highest<A[j]:
                    need = inf
                    break
                continue
            cnt += 1
            if highest>=A[j]:
                need += (highest+1-A[j])
                highest = highest + 1
            else:
                highest = A[j]
        if cnt>=K and need<ans:
            ans = need
        #print(need)
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Accepted

Solution code:

import itertools

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

mn = 1e12

for v in itertools.product([0,1], repeat=N-1):
    h = A[0]
    p = 0
    if sum(v) < K - 1:
        continue
    for i, vv in enumerate(v):
        if vv == 1:
            p += max(h - A[i+1] + 1, 0)
            h = max(A[i+1], h + 1)
        else:
            h = max(A[i+1], h)
    mn = min(mn, p)

print(mn)

Submission status: Accepted

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

ans = 1145141919810364364334
for i in range(1,2**n):
    ls = [0] * n
    qq = []
    
    for j in range(n):
        if (i >> j) & 1:
            ls[j] = 1
            qq.append(j)
            
    if sum(ls) < k:
        continue
        
    else:
        mt = a[0]
        cost = 0
        for j in range(1,n) :
            if mt < a[j]:
                mt = a[j]
            else:
                if ls[j] == 1:
                    cost += mt + 1 - a[j]
                    mt += 1
    ans = min(ans,cost)
    
print(ans)

Submission status: Accepted

Solution code:
def inpl():
    return list(map(int, input().split()))


def count(i):
    cost, k = 0, 1
    h = A[0]
    for j in range(1, N):
        if A[j] > h:
            k += 1
            h = A[j]
        elif (i >> j) & 1:
            k += 1
            cost += max(h - A[j] + 1, 0)
            h += 1
    return cost, k


N, K = inpl()
A = inpl()

ans = float('inf')
for i in range(1 << N):
    cost, k = count(i)
    if k >= K:
        ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    ans = 1 << 60
    for bit in range(1 << N):
        bills = A[:]
        # K個の建物が必要
        if bin(bit).count("1") != K:
            continue
        sum_H = 0
        cmb = []  # 建物の組み合わせ
        for i in range(N):
            if bit >> i & 1:
                cmb.append(i)
        for b in cmb:
            if b == 0:
                continue
            m = max(bills[:b])
            if m < bills[b]: # 後ろの建物が高かい場合、伸ばす必要なし
                pass
            else:
                sum_H += m + 1 - bills[b] # 伸ばすコスト
                bills[b] = m + 1 # 伸ばした高さに修正
        ans = min(ans, sum_H)

    return print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

res = len(A_orig) * max(A_orig)
for pattern in itertools.combinations(range(N), K):
    cnt = 0
    A = A_orig[:]
    for p in pattern:
        if p == 0:
            continue
        extension = max(0, max(A[:p]) - A[p] + 1)
        A[p] += extension
        cnt += extension
    res = min(res, cnt)
    
print(res)

Submission status: Accepted

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

#ビット全探索
ans=1000000000*N
for i in range(1<<N):
    bitlist=[]
    for j in range(N):
        bitlist.append((i >> j) & 1)
    if sum(bitlist) < K:
        continue

    tmp_max=0
    nedan=0
    for j in range(N):
        if bitlist[j]==1:
            if tmp_max >= A[j]:
                nedan+=(tmp_max-A[j]+1)
                tmp_max=tmp_max+1
            elif tmp_max < A[j]:
                tmp_max=A[j]
        elif bitlist[j]==0:
            if tmp_max < A[j]:
                tmp_max=A[j]
    ans=min(ans,nedan)
print(ans)

Submission status: Accepted

Solution code:
def bitcount(x):
  x = x - ((x >> 1) & 0x5555555555555555)
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
  x = x + (x >> 8)
  x = x + (x >> 16)
  x = x + (x >> 32)
  return x & 0x0000007f
N, K = map(int, input().split())
A = list(map(int, input().split()))
r = float('INF')
for i in range(1<<N):
  if bitcount(i) != K:
    continue
  cost, hights, idx = 0, [], 0
  for j in range(N):
    if j > 0 and i>>j & 1:
      c = max(0, max(hights[idx:j]) - A[j] + 1)
      cost += c
      hights.append(A[j] + c)
      idx = j
    else:
      hights.append(A[j])
  # print(bin(i), cost, hights)
  r = min(r, cost)
print(r)

Submission status: Accepted

Solution code:
import itertools

n, k = [int(i) for i in input().split()]
top, *a = [int(i) for i in input().split()]

ans = float("inf")
for pp in itertools.product((0, 1), repeat=n-1):
    now = top
    v = 1
    cost = 0
    for i, p in enumerate(pp):
        if p == 0:
            if a[i] > now:
                now = a[i]
                v += 1
            continue
        now = max(now+1, a[i])
        cost += max(now-a[i], 0)
        v += 1
    if v >= k:
        ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
nl = lambda: list(map(int, stdin.readline().split()))

n, K = na()
a = na()
ans = float('inf')
for i in range(2**(n-1)):
    colors = 1
    cost = 0
    tmp = a[0]
    for k in range(n-1):
        if tmp < a[k+1]:
            colors += 1
            tmp = a[k+1]
            continue
        if (i >> k) & 1:
            cost += tmp - a[k+1] + 1
            colors += 1
            tmp += 1
    if colors >= K:
        ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    ans=INF
    for i in range(2**N):
        c=0
        tmp=0
        l=a[0]
        for j in range(N):
            if j==0:
                if (i>>j)&1:
                    c+=1
                else:
                    break
            else:
                if (i>>j)&1:
                    c+=1
                    tmp+=max(0,l+1-a[j])
                    l=max(l+1,a[j])
                else:
                    l=max(l,a[j])
        if c>=K:
            ans=min(ans,tmp)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
array = list(map(int, input().split()))
if k == 1:
  print(0)
  quit()
  
import itertools
cost = float('inf')
for cand in itertools.combinations(range(1, n), k-1):
  dp = array[:]
  curr_cost = 0
  for index in cand:
    max_val = max(dp[:index])
    if array[index] > max_val:
      continue
    curr_cost += max_val - array[index] + 1
    dp[index] = max_val + 1
  cost = min(cost, curr_cost)
  
print(cost)

Submission status: Accepted

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

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

min_money = 10**18
for i in range(2**n):
    builds = []
    num_builds = 0
    for j in range(n):
        if ((i>>j)&1):
            builds += [j]
            num_builds += 1
    
    if num_builds==k:
        current_h = 0
        money = 0
        for b in builds:
            if b>0:
                current_h = max(max(H[:b]), current_h)
            if H[b]>current_h:
                current_h = H[b]
            elif H[b]<=current_h:
                d_h = current_h - H[b] + 1
                current_h += 1
                money += d_h
            #print(current_h, H[b], d_h)
        if money<min_money:
            min_money = money
            
print(min_money)

Submission status: Accepted

Solution code:
n,k= map(int, input().split())
a=list(map(int, input().split()))
b=[0]*n
y=a[0]
# 少なくともどこまで伸ばすべきか
for i in range(n):
    y=max(y,a[i])
    b[i]=y

ans=pow(10,12)
for i in range(2**(n-1)):
    H=[]
    for j in range(1,n):
        if (i>>(j-1))&1:
            H.append(j)

    if len(H)==k-1:
        cnt = 0
        x = b[0]+1
        for l in range(len(H)):
            if x>=b[H[l]]:
                cnt+=x-a[H[l]]
                x+=1
            else:
                if b[H[l]]==a[H[l]]:
                    x=b[H[l]]+1
                else:
                    cnt+=x-a[H[l]]
                    x=b[H[l]]+1

        ans=min(cnt,ans)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N, K = map(int, input().split())
l_height = list(map(int, input().split()))
# print(N, K)
# print(l_height)

costs = []
if N == K:
    cost = 0
    max_height = l_height[0]
    for i in range(1, N):
        if max_height >= l_height[i]:
            cost += (max_height + 1) - l_height[i]
            l_height[i] = max_height + 1
        max_height = l_height[i]
    costs.append(cost)
else:
    for bits in range(2 ** N):
        buildings = []
        # bit立っている建物の番号のリストを求める
        for i in range(N):
            if bits & (1 << i):
                buildings.append(i)

        l_height_copy = l_height[:]
        cost = 0
        # K色の色を見えるようにしたときのcostを求める
        if len(buildings) == K:
            # print(f"\nbits: {bin(bits)}")
            # print(f"buildings: {buildings}")
            max_height = l_height_copy[0]
            for i in range(1, N):
                if i in buildings:
                    # print(f"i: {i} is in buildings")
                    # print(f"buildings: {buildings}")
                    # print(f"l_height_copy: {l_height_copy}")
                    # print(f"max_height: {max_height}")
                    # print(f"l_height_copy[i]: {l_height_copy[i]}")
                    # 建物iの高さを増やす必要があるとき
                    if max_height >= l_height_copy[i]:
                        # print("max_height >= l_height[i]")
                        # print(f"diff: {(max_height + 1) - l_height_copy[i]}")
                        cost += (max_height + 1) - l_height_copy[i]
                        # print(f"cost: {cost}")
                        l_height_copy[i] = max_height + 1
                        max_height = l_height_copy[i]
                        # print(f"updated max_height: {max_height}")
                    else:
                        max_height = l_height_copy[i]
                else:
                    if l_height_copy[i] > max_height:
                        # print(f"updated max_height: {max_height}")
                        max_height = l_height_copy[i]
            costs.append(cost)

# print(costs)
print(min(costs))

# ----- 方針 -----
# N > Kとする。
# i個目の建物高さを変更するとき1が立つN個のbitsを考える。
# bitが立っている建物の番号のリストを以下で求める。
# buildings = []
# for i in range(N):
#     if bits & (1 << i):
#         buildings.append(i)
# bitsのうち、K個bitが立っているものを考える。
# bitが立っている番号の建物が必ず見えるように高さを増やしたときのcostを求める。

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,k = mi()

a = li()
min_cost = float('inf')

for i in range(2**n):
    select = []
    a2 = a.copy()
    for j in range(n):
        if (i >> j)&1:
            select.append(j)

    if(len(select) != k):
        continue

    cost = 0
    b_max = a2[0]
    for j in range(1,n):
        if j in select:
            if(a2[j] <= b_max):
                cost += b_max+1 - a2[j]
                a2[j] = b_max+1
        b_max = max(b_max, a2[j])
    min_cost = min(min_cost, cost)

print(min_cost)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,k = mi()

a = li()
min_cost = 10**9 * 16

for i in range(2**n):
    select = []
    a2 = a.copy()
    for j in range(n):
        if (i >> j)&1:
            select.append(j)

    if(len(select) != k):
        continue

    cost = 0
    b_max = a2[0]
    for j in range(1,n):
        if j in select:
            if(a2[j] <= b_max):
                cost += b_max+1 - a2[j]
                a2[j] = b_max+1
        b_max = max(b_max, a2[j])
    min_cost = min(min_cost, cost)

print(min_cost)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    ans = float("inf")
    for b in range(1<<(n-1)):
        b <<= 1
        if bin(b).count("1") != k-1:
            continue
        m = a[0]
        s = 0
        for i in range(1,n):
            if not b&(1<<i):
                if m < a[i]:
                    m = a[i]
            else:
                if a[i] <= m:
                    m += 1
                    s += m-a[i]
                else:
                    m = a[i]
        if s < ans:
            ans = s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    ans = float("inf")
    for b in range(1<<n):
        if bin(b).count("1") < k:
            continue
        m = 0
        s = 0
        for i in range(n):
            if not b&(1<<i):
                if m < a[i]:
                    m = a[i]
            else:
                if a[i] <= m:
                    m += 1
                    s += m-a[i]
                else:
                    m = a[i]
        if s < ans:
            ans = s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def dfs(index):
    global ans
    if index == N:
        if blst.count(1) >= K - 1:
            tmp = a[0]
            anstmp = 0
            for i in range(1, N):
                if blst[i - 1] == 0:
                    if tmp < a[i]:
                        tmp = a[i]
                    continue
                if tmp >= a[i]:
                    anstmp += tmp - a[i] + 1
                    tmp += 1
                else:
                    tmp = a[i]
            ans = min(ans, anstmp)
        return
    for i in range(2):
        blst[index - 1] = i
        dfs(index + 1)
    return

N, K = map(int, input().split())
a = list(map(int, input().split()))
blst = [0] * (N - 1)
ans = float('inf')
dfs(1)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import functools 
import sys
import bisect
import string
import math
import time
import random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

N=10**6+2
m=[0]*(N)

n,k=LI()
a=LI()
N=1<<n
ans=inf
for i in range(N):
    c=0
    t=[]
    for j in range(n):
        if (i>>j)&1:
            c+=1
            t+=[j]
    if c!=k:
        continue
    
    alt=0
    ti=0
    M=-1
    for j in range(n):
        
        if j==t[ti]:
            alt+=max(0,M+1-a[j])
            M=max(a[j],M+1)
            ti+=1
        #show(j,M,alt,ti)
        if ti==k:
            break
        M=max(M,a[j])
        
    #show(alt,t,a)
    if alt<ans:
        ans=alt
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
pbls = list(map(int, input().split()))
ans = 1e18
for i in range(pow(2, n)):
    bls = pbls[::]
    if (bin(i).count("1") != k):
        continue
    temp = 0
    l = []
    for b in range(n):
        if (i & (1 << b)):
            l.append(b)
    for c in l:
        if (c == 0):
            continue
        else:
            m = max(bls[:c])
            if (m < bls[c]):
                pass
            else:
                temp += m + 1 - bls[c]
                bls[c] = m + 1
    ans = min(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
ans = float('inf')

for i in range(2**N):
    cnt = 0
    last = 0
    cost = 0
    for j in range(N):
        if(A[j] > last):
            cnt += 1
            last = A[j]
        elif(i>>j & 1):
            cnt += 1
            cost += last-A[j]+1
            last += 1
    if(cnt>=K):
        ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=10**18
for i in range(2**n):
  build=set()
  maxi=a[0]
  for j in range(n):
    if (i>>j)&1:
      build.add(j)
  cnt=len(build)
  if 0 not in build:
    cnt+=1
  s=0
  for j in range(n):
    if j==0:
      continue
    elif j in build:
      if a[j]<=maxi:
        s+=maxi-a[j]+1
        maxi+=1
      else:
        maxi=a[j]
    else:
      if a[j]>maxi:
        cnt+=1
        maxi=a[j]
  if cnt>=k:
    ans=min(ans,s)
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

n, k = map(int, input().split())
buildings = list(map(int, input().split()))
# 一番目は必ず見えるとして、それ以外のどれが見えるかを考える。
# どれが見えるかは、全部やればいい。
most_left = buildings[0]
buildings = buildings[1:]
ans = float('inf')
for i in range(2 ** len(buildings)):
    if bin(i).count('1') < k - 1:
        continue
    t = most_left # 初期化
    cost = 0
    for j in range(len(buildings)):
        if (i >> j) & 1:
            if t >= buildings[j]:
                cost += t - buildings[j] + 1 # 差分より、1高い必要がある。
                t += 1 #新しく増築したモノが、前のモノより高くなる。
            else:
                # より高い建物があった場合、costは増加しないが視界を塞ぐ建物は高くなる。
                t = buildings[j]
        else: # より高い建物があった場合、costは増加しないが視界を塞ぐ建物は高くなる。
              # そして、これは建物を高くしようとしていなくても、発生する。
            if t < buildings[j]:
                t = buildings[j]
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = float('inf')
for i in range(2 ** (N-1)):
    l = [0] * (N-1)
    for j in range(N-1):
        if (i >> j) & 1:
            l[j] = 1
    cost = 0
    AA = A.copy()
    for k in range(N-1):
        if l[k] == 1:
            maxA = max(AA[:k+1])
            if maxA >= AA[k+1]:
                diff = maxA - AA[k+1] + 1
                AA[k+1] = maxA + 1
                cost += diff
    cnt = 1
    for num in range(1, N):
        if AA[num] > max(AA[:num]):
            cnt += 1
    if cnt >= K:
        ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
#square869120Contest#4_B
n,k=map(int,input().split())
a=list(map(int,input().split()))

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

Submission status: Accepted

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

a = [int(i) for i in input().split()]

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

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

b = list(range(1, n))
c = combinations(b, k-1)

min_sum = 10**30
for i in c:
    sum = 0
    target = a[0] + 1
    for j in range(1, n):
        if j in i:
            if target >= a[j]:
                sum += (target - a[j])
                target += 1
            else:
                target = a[j] + 1
        elif j not in i and a[j] > target:
            target = a[j] + 1
    if sum < min_sum:
        min_sum = sum

print(min_sum)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, K = MAP()
A = LIST()
INF = 10**20


def calc_cost(A, bit):
    cost = 0
    observed = 1
    prev_height = A[0]
    bit = bit | 1

    for n in range(1, N):
        if prev_height < A[n]:
            prev_height = A[n]
            observed += 1
        elif bit >> n & 1:
            costi = prev_height - A[n] + 1
            prev_height = A[n] + costi
            observed += 1
            cost += costi
    return observed, cost


ans = INF
for i in range(1 << N):
    observed, cost = calc_cost(A, i)
    if observed >= K:
        ans = min(ans, cost)

print(ans)


# for i in range(1 << N):
#     use = [i>>j & 1 for j in range(N)]
#     if sum(use) < K:
#         continue

#     res = 0
#     now =

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 10**12

for i in range(2**N):
  #print(i,bin(i).count('1'))
  # 左から見える数がK未満ならスキップ
  if bin(i).count('1') < K:
    pass
  # 1番左が見えない(0)は無理なのでpass
  elif (i >> 0) & 0:
    pass
  else:
    tmp = [None]*N
    tmp[0] = A[0]
    tmpAns = 0
    for j in range(1,N):
      maxLeft = max(tmp[:j],default=0)
      if (i >> j) & 1:#左から見える
        if maxLeft < A[j]:# 左側のどれよりも高い
          tmp[j] = A[j]
        else:
          tmp[j] = maxLeft+1
          tmpAns += maxLeft+1-A[j]            
      else:#左から見えない
        if maxLeft >= A[j]:# 元から見えてない
          tmp[j] = A[j]
        else:# 左から見えているので一番高いところをもっと高くして隠す
          tmp[j] = A[j]
          tmpIndex = tmp[:j].index(maxLeft)
          tmp[tmpIndex] = tmp[j]
          tmpAns += tmp[j] - maxLeft
    if tmpAns < ans:
      ans = tmpAns
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
import itertools
ans=float("inf")
for c in itertools.combinations(range(n),k):
  c=set(c)
  cur=0
  prev=0
  for i in range(n):
    if i not in c:
      prev=max(prev,A[i])
      continue
    else:
      if A[i]>prev:
        prev=A[i]
        continue
      else:
        cur+=prev-A[i]+1
        prev+=1
  ans=min(cur,ans)
print(ans)