Problem:


本棚

太郎君はとある小説にはまっています。その小説は全部で n 巻あり、各巻で本の厚さが異なります。太郎君はこの小説が大変気に入ったので、その小説専用の本棚を買おうと思っています。しかし、部屋に大きな本棚を置くとかなり狭くなってしまうので、出来るだけ本棚の幅が小さくなるように工夫しなければなりません。床から天井の高さを測ったところ、どうやら m 段の本棚なら置けることが分かりました。そこで、小説 n 巻をどのように分ければ m 段の本棚の幅を最小に出来るでしょうか?
 太郎君にはこだわりがあり、各段に納める小説は巻の番号順に並んでいなければなりません。
 

 本棚の段数、小説の巻数、各本の厚さを入力として、全巻を 1巻から順に収めることができる本棚の中で幅が最小となるものの幅を求めるプログラムを作成してください。ただし、本棚の枠の大きさは幅に含めないこととします。
 

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。

m n
w1
w2
:
wn

１行目に部屋に置くことができる本棚の段数 m (1 ≤ m ≤ 20)、 小説の巻数 n (1 ≤ n ≤ 100) が与えられます。続く n 行に第 i 巻の本の厚さを表す整数 wi (1 ≤ wi ≤ 1000000) が与えられます。

ただし、本棚の幅は 1500000 を超えないものとします。

データセットの数は 50  を超えません。

Output

データセット毎に最小となる本棚の幅を１行に出力します。

Sample Input

3 9
500
300
800
200
100
600
900
700
400
4 3
1000
1000
1000
0 0

Output for the Sample Input

1800
1000



Sample input:
3 9
500
300
800
200
100
600
900
700
400
4 3
1000
1000
1000
0 0


Sample output:
1800
1000

Submission status: Accepted

Solution code:
# AOJ 0181 Bookshelf
# Python3 2018.6.23 bal4u

INF = 0x7fffffff
while 1:
	m, n = map(int, input().split())
	if m == 0: break
	dp = [[[INF for k in range(n+1)] for j in range(n+1)] for i in range(m+1)]
	w, k = [0]*(n+1), 0
	for i in range(1, n+1):
		l = int(input())
		w[i] = w[i-1]+l
		if l > k: k = l
	if n <= m:
		print(k)
		continue
	for i in range(1, n+1): dp[1][1][i] = w[i]
	for k in range(2, m+1):
		for i in range(1, n+1):
			for j in range(i, n):
				for l in range(j, n):
					if dp[k-1][i][j] < INF:
						dp[k][j+1][l+1] = min(dp[k][j+1][l+1], max(w[l+1]-w[j], dp[k-1][i][j]))
	ans = INF
	for i in range(1, n+1):
		if dp[m][i][n] < ans: ans = dp[m][i][n]
	print(ans)

Submission status: Accepted

Solution code:
def search(width, books, m):
  acc = 0
  cnt = 1
  for book in books:
    if book > width:
      return False
    if acc + book > width:
      cnt += 1
      acc = book
    else:
      acc += book
  return cnt <= m
while True:
  m, n = map(int, input().split())
  if m == 0:
    break
  books = [int(input()) for _ in range(n)]
  left = 0
  right = 1500000
  while right - left > 1:
    mid = (left + right) // 2
    #print(mid)
    if search(mid, books, m):
      right = mid
    else:
      left = mid
  print(right)

Submission status: Accepted

Solution code:
def check(L,m,n,d):
    i = 0
    for _ in xrange(m):
        s = 0
        while i < n:
            if s+L[i] > d:
                break
            s += L[i]
            i += 1
    return i == n

def bs(L,m,n):
    left,right = 0,sum(L)
    while left != right:
        mid = (left+right)/2
        if check(L,m,n,mid):
            right = mid
        else:
            left = mid+1
    return left

while True:
    m,n = map(int,raw_input().split())
    if m|n == 0:
        break
    L = [input() for _ in xrange(n)]
    print bs(L,m,n)

Submission status: Accepted

Solution code:
def is_include(mid, m, book):
    cnt = 1
    length = 0
    for sz in book:
        if sz > mid:
            return False
        if length + sz <= mid:
            length += sz
        else:
            cnt += 1
            length = sz
    return cnt <= m

while True:
    m, n = map(int, raw_input().split())
    if m == n == 0:
        break
    book = [input() for i in range(n)]
    l = 1
    r = 1500000
    ans = 10000000
    while l <= r:
        mid = (l + r) / 2
        if is_include(mid, m, book):
            r = mid - 1
            ans = min(ans, mid)
        else:
            l = mid + 1
    print ans

Submission status: Accepted

Solution code:
def isStorage(max_shelf):
	i,cur_shelf,num = 0,0,1
	while i < n:
		if num > m:
			return False
		if cur_shelf + book[i] > max_shelf:
			num += 1
			cur_shelf = 0
		else:
			cur_shelf += book[i]
			i += 1
	else:
		return True
			
while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	max_shelf = len = sum(book)
	while len:
		len /= 2
		max_shelf -= len if isStorage(max_shelf) else -len
	max_shelf += 10
	while isStorage(max_shelf-1):
		max_shelf -= 1
	print max_shelf

Submission status: Accepted

Solution code:
def isStorage(max_shelf):
	i,cur_shelf,num = 0,0,1
	while i < n:
		if num > m:
			return False
		if cur_shelf + book[i] > max_shelf:
			num += 1
			cur_shelf = 0
		else:
			cur_shelf += book[i]
			i += 1
	else:
		return True
			
while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	max_shelf = len = sum(book)
	while len:
		len /= 2
		max_shelf -= len if isStorage(max_shelf) else -len
	max_shelf += 6
	while isStorage(max_shelf-1):
		max_shelf -= 1
	print max_shelf

Submission status: Accepted

Solution code:
def isStorage(max_shelf):
	i,cur_shelf,num = 0,0,1
	while i < n:
		if num > m:
			return False
		if cur_shelf + book[i] > max_shelf:
			num += 1
			cur_shelf = 0
		else:
			cur_shelf += book[i]
			i += 1
	else:
		return True
			
while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	max_shelf = len = sum(book)/2
	while len:
		len /= 2
		max_shelf -= len if isStorage(max_shelf) else -len
	max_shelf += 6
	while isStorage(max_shelf-1):
		max_shelf -= 1
	print max_shelf

Submission status: Accepted

Solution code:
while 1:
    M, N = map(int, input().split())
    if M == N == 0:
        break
    W = [int(input()) for i in range(N)]
    left = max(W)-1; right = sum(W)
    while left+1 < right:
        mid = (left + right) >> 1
        k = 1; cur = 0
        for w in W:
            if mid < cur+w:
                cur = w
                k += 1
            else:
                cur += w
        if k <= M:
            right = mid
        else:
            left = mid
    print(right)

Submission status: Accepted

Solution code:
while True:
    m, n = map(int, input().split())
    if n+m == 0:
        break
    else:
        book_list = [int(input()) for _ in range(n)]
        left = min(book_list)
        right = 10**7
        while left < right:
            w = (left+right)//2
            cnt_m = 1
            tmp_w = 0
            for book in book_list:
                if book > w:
                    cnt_m = m + 1
                else:
                    tmp_w += book
                    if tmp_w > w:
                        tmp_w = book
                        cnt_m += 1
            if cnt_m > m:
                left = w + 1
            else:
                right = w
        print(left)

Submission status: Accepted

Solution code:
def IsStorable( m, n, w, width ):
    row = 1
    c = 0
    i = 0
    while i < n :
        if c + w[i] <= width :
            c += w[i]
            i += 1
        elif row < m :
            c = 0
            row += 1
        else : return False
    return True

while ( True ):
    m,n = map(int, input().split())
    if m == 0 and n == 0 : break
    w = []
    for i in range(n) : w.append(int(input()))

    minw = 1
    maxw = 1500000
    if not IsStorable( m, n, w, maxw ) : print("NA")
    
    while maxw > minw :
        mid = int((maxw + minw)/2)
        if IsStorable( m, n, w, mid ) : maxw = mid
        else : minw = mid + 1
    print(minw)

Submission status: Accepted

Solution code:
def func(q,m,W):
    s = 0
    c = 1
    for w in W:
        s += w
        if s > q:
            c += 1
            s = w
            if s > q:
                return 1
    return (c > m)

while(1):
    m,n=[int(x) for x in input().split()]
    if m==0:
        break
    W=[]
    A=[0]
    for i in range(n):
        W.append(int(input()))
        A.append(A[-1]+W[-1])
    A.pop(0)
    qsmall = sum(W)/m
    qbig   = 1500000
    while(1):
        if qbig - qsmall < 1e-3:
            break
        q = (qbig+qsmall)/2 
        issmall = func(q,m,W)
        if issmall:
            qsmall = q
        else:
            qbig = q
    q = int(qsmall)
    if func(q,m,W):
        print(q + 1)
    else:
        print(q)

Submission status: Runtime Error

Solution code:
while True:
    m, n = map(int, raw_input().split())
    if m == n == 0: break
    tl = 0
    book = []
    for i in range(n):
        l = input()
        tl += l
        book.append(l)
    else:
        pe = float(tl)/m
    ll = 0
    c = 1
    for i, length in enumerate(book):
        ll += length
        if pe <= ll:
            if ll <= float(sum(book[i:]))/(m-c):
                pe = ll
            else:
                pe = float(sum(book[i:]))/(m-c)
            ll = 0
            c += 1
    else:
        print pe

Submission status: Runtime Error

Solution code:
while True:
    m, n = map(int, raw_input().split())
    if m == n == 0: break
    tl = 0
    book = []
    for i in range(n):
        l = input()
        tl += l
        book.append(l)
    else:
        pe = float(tl)/m
    ll = 0
    c = 1
    for i, length in enumerate(book):
        ll += length
        if pe <= ll and m != 0:
            if ll <= float(sum(book[i:]))/(m-c):
                pe = ll
            else:
                pe = float(sum(book[i:]))/(m-c)
            ll = 0
            c += 1
        else:
            pe = ll
    else:
        print pe

Submission status: Runtime Error

Solution code:
while True:
    m, n = map(int, raw_input().split())
    if m == n == 0: break
    tl = 0
    book = []
    for i in range(n):
        l = input()
        tl += l
        book.append(l)
    else:
        pe = float(tl)/m
    if m == 1:
        print int(pe)
        continue
    ll = 0
    c = 1
    for i, length in enumerate(book):
        ll += length
        if pe <= ll:
            if ll <= float(sum(book[i:]))/(m-c):
                pe = ll
            else:
                pe = float(sum(book[i:]))/(m-c)
            ll = 0
            c += 1
    else:
        print int(pe)

Submission status: Runtime Error

Solution code:
while True:
    m, n = map(int, raw_input().split())
    if m == n == 0: break
    tl = 0
    book = []
    for i in range(n):
        l = input()
        tl += l
        book.append(l)
    else:
        pe = float(tl)/m
    ll = []
    c = 1
    for i, length in enumerate(book):
        ll.append(length)
        if pe <= sum(ll):
            if len(ll) == 1:
                pe = sum(ll)
            elif ll <= float(sum(book[i:]))/(m-c):
                pe = sum(ll)
            else:
                pe = float(sum(book[i:]))/(m-c)
            ll = []
            c += 1
    else:
        print int(pe)

Submission status: Runtime Error

Solution code:

class Solve:
    def __init__(self):
        self.M, self.N = map(int, input().split())
        self.bs = [int(input()) for i in range(self.N)]

        self.S = min(sum(self.bs), 1500000)
        self.l, self.r = 0, self.S

    def check(self, W):
        w = W
        i = 1
        for b in self.bs:
            if(W < b):
                return False
            if(w >= b):
                w -= b
            else:
                if(i >= self.M):
                    return False
                else:
                    i += 1
                    w = W - b
        return True

    def solve(self):
        while self.r - self.l > 1:
            m = (self.l + self.r) // 2
            if self.check(m):
                self.r = m
            else:
                self.l = m
        return self.r

while True:
    print(Solve().solve())

Submission status: Runtime Error

Solution code:

class Solve:
    def __init__(self):
        self.M, self.N = map(int, input().split())
        self.bs = [int(input()) for i in range(self.N)]

        self.S = min(sum(self.bs), 1500000)
        self.l, self.r = 0, self.S

    def check(self, W):
        w = W
        i = 1
        for b in self.bs:
            if(w >= b):
                w -= b
            elif(W >= b):
                if(i >= self.M):
                    return False
                i += 1
                w = W - b
            else:
                return False
        return True

    def solve(self):
        while self.r - self.l > 1:
            m = (self.l + self.r) // 2
            if self.check(m):
                self.r = m
            else:
                self.l = m
        return self.r

while True:
    print(Solve().solve())

Submission status: Runtime Error

Solution code:
def nibutan(f_id,e_id,f_num,yn):
    
    
    m_id = int((f_id + e_id) / 2)
    m_num = w_lis[m_id]


    if e_id - f_id <= 1:
        if yn == 0:

            return e_id
        else:
            return f_id
    else:
        if m_num > f_num:
            return(nibutan(f_id,m_id -1,f_num,yn))
        elif m_num < f_num:
            return(nibutan(m_id + 1,e_id,f_num,yn))
        else:
            return  m_num




while True:
    global w_lis
    b_lis = []
    w_lis = []
    dan_num = [0]
    atu_num = [0]
    wa = 0
    m,n = map(int,input().split())
    if m == n == 0:
        break
    for i in range(n):
        num = int(input())
        wa += num
        b_lis.append(num)
        w_lis.append(wa)
    best_num = wa / m
    if best_num < max(b_lis):
        print(max(b_lis))
    else:
        bid = 0
        n_si = 0
        for i in range(m):
            bid = nibutan(bid,n - 1,n_si + best_num,i)
            n_si = w_lis[bid]
            dan_num.append(n_si)
            atu_num.append(n_si - dan_num[i])
            
        print(max(atu_num))