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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import combinations, accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
A=LIST()

acc=list(accumulate(A, max))

ans=INF
for comb in combinations(range(N), K):
    sm=0
    for i, n in enumerate(comb):
        if i==0:
            cost=max(acc[comb[i]]-A[comb[i]], 0)
            if comb[i]!=0 and A[comb[i]-1]==A[comb[i]]:
                cost+=1
        else:
            cost=max(prev-A[comb[i]]+1, 0)
        sm+=cost
        prev=A[comb[i]]+cost
    ans=min(ans, sm)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import combinations, accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
A=LIST()

acc=list(accumulate(A, max))

ans=INF
for comb in combinations(range(N), K):
    sm=0
    for i, n in enumerate(comb):
        if i==0:
            cost=max(acc[comb[i]]-A[comb[i]], 0)
        else:
            cost=max(prev-A[comb[i]]+1, 0)
        sm+=cost
        prev=A[comb[i]]+cost
    ans=min(ans, sm)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import combinations, accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
A=LIST()

acc=list(accumulate(A, max))

ans=INF
for comb in combinations(range(N), K):
    sm=0
    for i, n in enumerate(comb):
        if i==0:
            cost=max(acc[i]-A[comb[i]], 0)
        else:
            cost=max(prev-A[comb[i]]+1, 0)
        sm+=cost
        prev=A[comb[i]]+cost
    ans=min(ans, sm)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = (int(i+1) for i in range(n-1))
a2,ans = [0],float("inf")
for i in range(n): a2.append(max(a[i],a[-1]))
def f(q):
	m,c = a[0],0
	for i in q:
		m2 = max(m,a2[i-1])
		if a[i]>m2: m = a[i]
		else: m,c = m2+1,c+(m2+1-a[i])
	return c
for i in combinations(b,k-1): ans = min(ans,f(i))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = (int(i+1) for i in range(n-1))
def f(q):
	m,c = a[0],0
	for i in q:
		if a[i]>m: m = a[i]
		else: m,c = m+1,c+(m+1-a[i])
	return c
ans = float("inf")
for i in combinations(b,k-1): ans = min(ans,f(i))
print(ans)

Submission status: Wrong Answer

Solution code:
def b_buildings_are_colorful(N, K, A):
    import itertools
    combination = itertools.combinations(range(1, N), K - 1)
    ans = float('inf')
    for comb in combination:
        tmp = [A[0]]
        for c in comb:
            tmp.append(A[c])
        l = len(tmp)
        tmp1 = tmp[:]
        for k in range(1, l):
            if tmp1[k] <= tmp1[k - 1]:
                tmp1[k] += tmp1[k - 1] - tmp1[k] + 1
        delta = 0
        for k in range(l):
            delta += tmp1[k] - tmp[k]
        ans = min(ans, delta)
    return ans

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

Submission status: Wrong Answer

Solution code:
import itertools
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
S=list(itertools.permutations(range(1,N),K))
M=10**11
for sg in S:
  l=sorted(list(sg))
  m=0
  m+=max([a[l[0]]-a[0],0])
  for i in range(1,K):
    m+=max([a[l[i]]-a[l[i-1]],0])
  if m<M:
    M=m
print(M)

Submission status: Wrong Answer

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

ans = 10**18
for P in product(range(2), repeat=N-1):
    if sum(P) < K-1:
        continue
    res = 0
    base = A[0]
    for i in range(N-1):
        if P[i]:
            if A[i+1] < base:
                res += (base+1 - A[i+1])
                base += 1
            else:
                base = A[i+1]
        else:
            if base < A[i+1]:
                res += (A[i+1] - base)
                base = A[i+1]
    ans = min(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=float("inf")
for i in xrange(1<<n):
    cnt=1
    li=[0]
    for j in xrange(1,n):
        if i>>j&1:
            cnt+=1
            li.append(j)
    if cnt<k:continue
    tmp=0
    h=a[0]
    for j in xrange(1,len(li)):
        tmp+=max(h+1-a[li[j]],0)
        h=max(h+1,a[li[j]])
    ans=min(ans,tmp)
print ans

Submission status: Wrong Answer

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=float("inf")
for i in xrange(1<<n):
    cnt=1
    li=[0]
    for j in xrange(1,n):
        if i>>j&1:
            cnt+=1
            li.append(j)
    if cnt!=k:continue
    tmp=0
    h=a[0]
    for j in xrange(1,k):
        tmp+=max(h+1-a[li[j]],0)
        h=max(h+1,a[li[j]])
    ans=min(ans,tmp)
print ans

Submission status: Wrong Answer

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=10**12
for i in xrange(1<<n):
    cnt=1
    li=[0]
    for j in xrange(1,n):
        if i>>j&1:
            cnt+=1
            li.append(j)
    if cnt!=k:continue
    tmp=0
    h=a[0]
    for j in xrange(1,k):
        tmp+=max(h+1-a[li[j]],0)
        h=max(h+1,a[li[j]])
    ans=min(ans,tmp)
print ans

Submission status: Wrong Answer

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=10**12
for i in xrange(1<<n):
    cnt=1
    li=[0]
    for j in xrange(1,n):
        if i>>j&1:
            cnt+=1
            li.append(j)
    if cnt!=k:continue
    tmp=0
    h=a[0]
    for j in xrange(1,k):
        tmp+=max(h+1-a[li[j]],0)
        h=max(h+1,a[j])
    ans=min(ans,tmp)
print ans

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding=utf-8
# __author__ = '小美'

n,k = map(int,raw_input().split())
a = [i for i in raw_input().split()]

#按照从左到右找出最大的K的序列
lis = []
i = 0
while i < k:
    max = a[0]
    for q in a:
        if q>max:
            max = q
    lis.append(max)
    a.remove(max)
    i+=1
sum = 0
for i in range(1,len(lis)):
    if lis[i]<=lis[i-1]:
        sum += int(lis[i-1])+1-int(lis[i])
        lis[i] = str(int(lis[i-1])+1)
print sum

Submission status: Wrong Answer

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

    i = 0
    cost = 0
    while i < K - 1:
        if a[i] > a[i+1]:
            cost += a[i] - a[i+1] + 1
            a[i+1] = a[i] + 1
        i += 1

    print(cost)

main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
bills = list(map(int,input().split()))
ans = 0
k = 0
while k < K:
	k = 0
	cost =[]
	cosd = {}
	tatekae = {}
	maxh = 0
	for bi,b in enumerate(bills):
		if b > maxh:
			cost.append(0)
			maxh = b
			k = k + 1
		else:
			c = maxh - b + 1
			cost.append(c)
			maxh2 = maxh + 1
			tatekae[bi] = []
			for b2i,b2 in enumerate(bills[bi:]):
				if maxh2 < b2:
					break
				elif maxh2 == b2:
					c = c + 1
					maxh2 = maxh2 + 1
					tatekae[bi].append(b2i + bi)
			cosd[bi] = c
	if k > K:
		break
	a = min(cosd.items(),key =lambda x: x[1])[0]
	ans = ans + cosd[a]
	bills[a] = bills[a] + cost[a]
	for t in tatekae[a]:
		bills[t] = bills[t] + 1
	k = k + 1
print(ans)

Submission status: Wrong Answer

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

n = int(n)
k = int(k)

a_list = [int(a) for a in a_list]

money = 0
left = a_list[0]
for i,a in enumerate(a_list[1:]):
    if a_list[i] >= a:
        money += a_list[i]-a+1
        a_list[i+1] = a_list[i]+1
print(money)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = map(int,stdin.readline().split())
def solve(b):
    req = 0
    ans = 0
    pr = b[0]-1
    for ii in b:
        i = ii
        if i <= pr:
            ans += pr+1-i
            i = pr+1
        pr = i
    return ans


ma = 1<<n
res = 10**38
for mask in xrange(ma):
    b = [a[0]]
    ma = a[0]
    pr = a[0]
    for i in xrange(1,n):
        if mask & (1<<i):
            b.append(a[i])
        elif a[i] > pr:
            b.append(a[i])
        pr = a[i]
    if len(b)>=k:
        res = min(res, solve(b[:k]))
print res

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = map(int,stdin.readline().split())
def solve(b):
    ans = 0
    pr = b[0]-1
    for ii in b:
        i = ii
        if i <= pr:
            ans += pr+1-i
            i = pr+1
        pr = i
    return ans


ma = 1<<n
res = 10**38
for mask in xrange(ma):
    b = [a[0]]
    ma = a[0]
    for i in xrange(1,n):
        if a[i] > ma:
            ma = a[i]
        if mask & (1<<i):
            if ma > a[i]:
                b.append(ma)
                ma = 0
            b.append(a[i])
    if len(b)>=k:
        res = min(res, solve(b))
print res

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = map(int,stdin.readline().split())
def solve(b):
    ans = 0
    pr = b[0]-1
    for ii in b:
        i = ii
        if i <= pr:
            ans += pr+1-i
            i = pr+1
        pr = i
    return ans


ma = 1<<n
res = 10**38
for mask in xrange(ma):
    b = [a[0]]
    for i in xrange(1,n):
        if mask & (1<<i):
            b.append(a[i])
    if len(b)>=k:
        res = min(res, solve(b))
print res

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = map(int,stdin.readline().split())
def solve(b):
    ans = 0
    pr = b[0]-1
    for ii in b:
        i = ii
        if i <= pr:
            ans += pr+1-i
            i = pr+1
        pr = i
    return ans


ma = 1<<n
res = 10**18
for mask in xrange(ma):
    b = [a[0]]
    for i in xrange(1,n):
        if mask & (1<<i):
            b.append(a[i])
    if len(b)>=k:
        res = min(res, solve(b))
print res

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = map(int,stdin.readline().split())
def solve(b):
    ans = 0
    pr = b[0]-1
    for i in b:
        if i < pr:
            ans += pr+1-i
            i = pr+1
        pr = i
    return ans


ma = 1<<n
res = 10**18
for mask in xrange(ma):
    b = [a[0]]
    for i in xrange(1,n):
        if mask & (1<<i):
            b.append(a[i])
    if len(b)>=k:
        res = min(res, solve(b))
print res

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = map(int,stdin.readline().split())
def solve(b):
    ans = 0
    pr = b[0]-1
    for i in b:
        if i < pr:
            ans += pr+1-i
            i = pr+1
        pr = i
    return ans


ma = 1<<n
res = 10**18
for mask in xrange(ma):
    b = [a[0]]
    for i in xrange(1,n):
        if mask & (1<<i):
            b.append(a[i])
    if len(b)==k:
        res = min(res, solve(b))
print res

Submission status: Time Limit Exceeded

Solution code:
import copy
from itertools import combinations
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 10**9*15
for i in list(combinations(range(2,N+1),K-1)):#2番~N番からK-1個選ぶ
    B = copy.copy(A)
    count = 0
    C = sorted(i)#組み合わせをソート
    
    for j in C:
        while max(B[0:j-1]) >= B[j-1]:#シフト量+2番のビルが1番:B[0]~シフト量+1番:B[k]のビルより高く
            B[j-1] += 1#シフト量+2番目のビルを伸ばす
            count += 1#コストをプラス
    ans = min(ans,count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)):#2番~N番からK-1個選ぶ
    B = copy.copy(A)
    count = 0
    bit = 0
    for j in range(N-1):#A[1]~A[N-1]の内、選ばれるものの数
        bit = bit + (1&(i>>j))
    if(bit == K-1):#K-1個選ぶ
        for k in range(N-1):
            if(i>>k&1):
                while max(B[0:k+1]) >= B[k+1]:#シフト量+2番のビルが1番:B[0]~シフト量+1番:B[k]のビルより高く
                    B[k+1] += 1#シフト量+2番目のビルを伸ばす
                    count += 1#コストをプラス
        ans = min(ans,count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
li=[i for i in range(1,n)]
ans=[]

for i in itertools.permutations(li, k-1):
  cost,height=0,A[0]
  for j in i:
    if height < A[j]:
      height=A[j]
      continue
    cost += (height-A[j]+1)
    height += 1 
  ans.append(cost)
  
print(min(ans))

Submission status: Time Limit Exceeded

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

# 建物iをミられる高さにするかいなかのbit探索

ans = pow(10,100000000000)

for byte in range(pow(2,N-1)):
    height = a_list[0]
    cost = 0
    if bin(byte).count("1")>=K-1:
        for i in range(N-1):
            if not (byte & 1<<i)==0: # i番目を見る場合
                cost += max(0, height + 1 - a_list[i+1])
                height = max(height + 1, a_list[i+1])
        if cost < ans:
            ans = cost
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
S=list(itertools.permutations(range(N),K))
M=10**11
for sg in S:
  l=sorted(list(sg))
  b=[a[i] for i in range(N)]
  m=0
  for i in range(1,K):
    x=max(b[:l[i]])
    m+=max([x-b[l[i]]+1,0])
    b[l[i]]=x+1
  if m<M:
    M=m
print(M)

Submission status: Accepted

Solution code:
import sys

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

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

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

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

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

    print(ans)
    return

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

    return ans

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

ans=float('inf')
for i in result:
    cost = 0
    for j in range(N):
        if heights[j] < i[j]:
            cost += i[j] - heights[j]
    ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

ans = 10 ** 12

for n in combinations(range(N), K):
    m = A[0]
    c = 0
    for i in range(1, N):
        if i in n:
            c += max(m + 1 - A[i], 0)
            m = max(m+1, A[i])
        else:
            m = max(m, A[i])
    ans = min(ans, c)

print(ans)

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=float('inf')
for i in range(1<<(N-1)):
  cost,cnt,h=0,1,a[0]+1
  for j in range(N-1):
    x=a[j+1]
    if i>>j&1:
      cnt+=1
      if x>h:
        h=x+1
      else:
        cost+=h-x
        h+=1
    h=max(h,x+1)
  if cnt>=K:
    ans=min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=10**15
for i in range(1<<(N-1)):
  cnt,s,t=0,0,a[0]+1
  for j in range(N-1):
    if i>>j&1:
      x=a[j+1]
      cnt+=1
      if x>=t:
        t=x+1
      else:
        s+=(t-x)
        t+=1
    else:
      t=max(t,a[j+1]+1)
  if cnt>=K-1:
    ans=min(s,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

        maxi = max(maxi, A[j])

    res = min(res, cnt)

print(res)
# print(A)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

ans = max(a) * N

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

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

    ans = min(ans, cost)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

        if cnt < k:
            continue

        ans = min(ans, cost)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

        if len(lst) < k:
            continue

        highest = a_list[0]
        cost = 0

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

        ans = min(ans, cost)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

inf=float('inf')

ans=inf

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

Submission status: Accepted

Solution code:
from itertools import combinations

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

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
# 小課題１
# cost = 0
# for i in range(1,n):
#    if a[i] < a[i-1] + 1 :
#        cost += a[i-1] + 1 - a[i]
#        a[i] = a[i-1] + 1
# print(cost)

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#
# s8pc4 b
#
import sys
from io import StringIO
import unittest


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

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

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

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


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

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

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


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

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

print(ans)

Submission status: Accepted

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

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

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