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

Solution code:
while True:
    m, n = map(int, raw_input().split())
    if m+n==0:
        break
    book = []
    for i in xrange(n):
        book.append(input())
    left = max(book)-1; right = 10**8+1;
    mid = -1
    while True:
        mid = (left + right) / 2
        print mid, left, right
        sz = 0
        cnt = 1
        for i in xrange(n):
            if book[i]>mid:
                cnt = 10**9
                break
            if sz+book[i] > mid:
                sz = 0
                cnt += 1
            sz += book[i]
        print m, cnt
        if m < cnt:
            if left == mid:
                break
            left = mid
        else:
            if right == mid:
                break
            right = mid
    print mid+1

Submission status: Wrong Answer

Solution code:
while True:
    m, n = map(int, raw_input().split())
    if m+n==0:
        break
    book = []
    for i in xrange(n):
        book.append(input())
    left = max(book)-1; right = 10**8+1;
    mid = -1
    while True:
        mid = (left + right) / 2
        print mid, left, right
        sz = 0
        cnt = 1
        for i in xrange(n):
            if book[i]>mid:
                cnt = 10**9
                break
            if sz+book[i] > mid:
                sz = 0
                cnt += 1
            sz += book[i]
        print m, cnt
        if m < cnt:
            if left == mid:
                break
            left = mid
        else:
            if right == mid:
                break
            right = mid
    print left+1

Submission status: Wrong Answer

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 c != m:
            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: Wrong Answer

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 c != m:
                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: Wrong Answer

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 c != m:
                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 int(pe)

Submission status: Wrong Answer

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 c != m:
                if len(book[i:]) == 1:
                    pe = book[i]
                elif ll <= float(sum(book[i:]))/(m-c):
                    pe = ll
                else:
                    pe = float(sum(book[i:]))/(m-c)
                ll = 0
                c += 1
            else:
                pe = ll
                print 1
    else:
        print int(pe)

Submission status: Wrong Answer

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 c != m:
                if len(book[i:]) == 1:
                    pe = book[i]
                elif 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 int(pe)

Submission status: Wrong Answer

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 len(book[i:]) == 1:
                pe = book[i]
            elif 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: Wrong Answer

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 len(book[i:]) == 1:
                pe = ll
            elif 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: Wrong Answer

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 c != m:
                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:
                pe = sum(ll)
    else:
        print int(pe)

Submission status: Wrong Answer

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 = []
    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
    bid = 0
    n_si = 0
    for i in range(m):
        bid = nibutan(bid,n - 1,n_si + best_num,i)
        si = w_lis[bid]
        dan_num.append(si)
    print(max(dan_num))

Submission status: Wrong Answer

Solution code:
import bisect
def main():
    m,n  = list(map(int,input().split()))
    if n==0:
        exit()
    W = [int(input()) for _ in range(n)]

    w_total = 0
    w_sum =[]
    for w in W:
        w_total+=w
        w_sum.append(w_total)

    def judge(shelf_length):
        last_val = 0
        for i in range(m):
            _index= bisect.bisect_right(w_sum,last_val+shelf_length)
            #print(_index)
            if _index == n:
                return True
            if _index == 0:
                return False
            last_val =w_sum[ _index-1]
        return False


    def nibun(func ,min_ ,max_ ):
        left = min_
        right= max_
        while not(left==right):
            mid = (left+right) //2
            tmp = func(mid)
            if tmp:
                right = mid
            else:
                left = mid+1
        return left

    print(nibun(judge,0,1000000))

while True:
    main()

Submission status: Wrong Answer

Solution code:
def is_include(mid, m, book):
    cnt = 1
    length = 0
    for sz in book:
        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)]
    sum_of_length = sum(book)
    l = sum_of_length / n
    r = sum_of_length
    while l <= r:
        mid = (l + r) / 2
        if is_include(mid, m, book):
            r = mid - 1
            ans = mid
        else:
            l = mid + 1
    print ans

Submission status: Wrong Answer

Solution code:
def is_include(mid, m, book):
    cnt = 1
    length = 0
    for sz in book:
        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)]
    sum_of_length = sum(book)
    l = sum_of_length / n
    r = sum_of_length
    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: Wrong Answer

Solution code:
def is_include(mid, m, book):
    cnt = 1
    length = 0
    for sz in book:
        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)]
    sum_of_length = sum(book)
    l = sum_of_length / n
    r = sum_of_length
    if m > n:
        print max(book)
        continue
    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: Wrong Answer

Solution code:
while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	for i in range(n):
		max_shelf = sum(book[:i+1])
		cur_shelf,num = 0,2
		j = i+1
		while j < n:
			if num > m: break
			if cur_shelf + book[j] > max_shelf:
				num += 1
				cur_shelf = 0
			else:
				cur_shelf += book[j]
				j += 1
		else:
			break
	print max_shelf

Submission status: Wrong Answer

Solution code:
while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	
	for i in range(n):
		max_shelf = sum(book[:i+1])
		cur_shelf,num = 0,2
		j = i+1
		while j < n:
			if num > m: break
			if cur_shelf + book[j] > max_shelf:
				num += 1
				cur_shelf = 0
			else:
				cur_shelf += book[j]
				j += 1
		else:
			break
	
	flag = 0
	unit = min(book)
	for i in range(n):
		max_shelf -= unit
		cur_shelf,num = 0,2
		j = i+1
		while j < n:
			if num > m:
				flag = 1
				break
			if cur_shelf + book[j] > max_shelf:
				num += 1
				cur_shelf = 0
			else:
				cur_shelf += book[j]
				j += 1
		if flag == 1: break
	print max_shelf+unit

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
	else:
		if isStorage(max_shelf+1): max_shelf += 1
		if isStorage(max_shelf-1): max_shelf -= 1
		if isStorage(max_shelf-1): max_shelf -= 1
	print max_shelf

Submission status: Wrong Answer

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 += 2
	while isStorage(max_shelf-1):
		max_shelf -= 1
	print max_shelf

Submission status: Time Limit Exceeded

Solution code:
while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	
	for i in range(n):
		max_shelf = sum(book[:i+1])
		cur_shelf,num = 0,2
		j = i+1
		while j < n:
			if num > m: break
			if cur_shelf + book[j] > max_shelf:
				num += 1
				cur_shelf = 0
			else:
				cur_shelf += book[j]
				j += 1
		else:
			break
	
	flag = 0
	unit = min(book)
	while 1:
		max_shelf -= unit
		cur_shelf,num = 0,2
		j = i+1
		while j < n:
			if num > m:
				flag = 1
				break
			if cur_shelf + book[j] > max_shelf:
				num += 1
				cur_shelf = 0
			else:
				cur_shelf += book[j]
				j += 1
		if flag == 1: break
	print max_shelf+unit

Submission status: Time Limit Exceeded

Solution code:
while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	unit = min(book)
	max_shelf = max(sum(book)/m,max(book))
	while 1:
		i = 0
		cur_shelf,num = 0,1
		while i < n:
			if num > m: break
			if cur_shelf + book[i] > max_shelf:
				num += 1
				cur_shelf = 0
			else:
				cur_shelf += book[i]
				i += 1
		else:
			break
		max_shelf += unit
	print max_shelf

Submission status: Accepted

Solution code:

def check(book, width, m):
    d = 1
    sumv = 0
    for i in range(len(book)):
        if (book[i] > width):
            return False
        if (sumv + book[i] <= width):
            sumv += book[i]
        else:
            sumv = book[i]
            d += 1
    if (d > m):
        return False
    else:
        return True

            
        


if __name__ == "__main__":
    while True:
        m,n = map(int, raw_input().split())
        if (m == 0 and n == 0):
            break
        book = [0 for i in range(n)]
        for i in range(n):
            book[i] = input()
        left,right = 0,1500000
        while (right - left > 1):
            med = (right + left) / 2
            if (check(book, med, m) == True):
                right = med
            else:
                left = med
        print right

Submission status: Accepted

Solution code:
import sys
_allinput = []
for inp in sys.stdin:
	_allinput += inp.strip().split(" ")
def _input():
	for put in _allinput:
		yield put
_obj = _input();
def __input():
	return _obj.__next__()
def nextInt():
	return int(__input())
def check(lst,L):
	tot = 1
	curSum = 0
	for i in lst:
		if curSum + i <= L:
			curSum += i
		else:
			curSum = i
			tot += 1
	return tot

def solve(lst,m):
	l = max(lst)
	r = 1000000 * m;
	while l != r:
		mid = int((l+r)/2);
		if check(lst,mid) <= m: r = mid
		else: l = mid + 1
	return l
try:
	while True:
		m,n = nextInt(),nextInt()
		if m > 0 or n > 0:
			lst = [nextInt() for i in range(0,n)]
			print(solve(lst,m))
		else:
			break
except:
	'''
	'''

Submission status: Accepted

Solution code:
#!/usr/bin/python

import os
import sys
import itertools

def solve(f):
    ans = []

    while True:
        m, n = f.read_int_list()
        if m == 0: break
        books = [f.read_int() for _ in xrange(n)]

        lo = 0
        hi = 1500000

        while hi - lo > 1:
            mid = (lo + hi) / 2
            if check(books, mid, m):
                hi = mid
            else:
                lo = mid

        ans.append(hi)

    return "\n".join(map(str, ans))

def check(books, width, height):
    w = 0
    h = 1

    for i in books:
        if i > width:
            return False
        elif (width-w) >= i:
            w += i
        else:
            h += 1
            w = i
        if h > height: return False

    return True

class Reader(object):
    def __init__(self, filename=None):
        self.test_mode = filename is not None
        self.cases = 1
        self.buffer = []
        if self.test_mode:
            with open(filename) as f:
                blank_flg = False
                for line in f:
                    line = line.strip()
                    if line:
                        self.buffer.append(line)
                        blank_flg = False
                    else:
                        if not blank_flg: self.cases += 1
                        blank_flg = True

    def __readline(self):
        return self.buffer.pop(0) if self.test_mode else raw_input()

    def read_int(self):
        return int(self.__readline())
    def read_float(self):
        return float(self.__readline())
    def read_long(self):
        return long(self.__readline())
    def read_str(self):
        return self.__readline()

    def read_int_list(self):
        return [int(item) for item in self.__readline().split()]
    def read_float_list(self):
        return [float(item) for item in self.__readline().split()]
    def read_long_list(self):
        return [long(item) for item in self.__readline().split()]
    def read_str_list(self):
        return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv)>1 else None
    f = Reader(filename)
    if f.test_mode:
        for c in xrange(f.cases):
            print "Case #%d"%(c+1)
            print solve(f)
    else:
        print solve(f)

Submission status: Accepted

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:
    s = Solve()
    if s.M == 0 and s.N == 0:
        break
    print(s.solve())

Submission status: Accepted

Solution code:
import bisect
def main():
    m,n  = list(map(int,input().split()))
    if n==0:
        exit()
    W = [int(input()) for _ in range(n)]

    w_total = 0
    w_sum =[]
    for w in W:
        w_total+=w
        w_sum.append(w_total)

    def judge(shelf_length):
        last_val = 0
        for i in range(m):
            _index= bisect.bisect_right(w_sum,last_val+shelf_length)
            #print(_index)
            if _index == n:
                return True
            if _index == 0:
                return False
            last_val =w_sum[ _index-1]
        return False


    def nibun(func ,min_ ,max_ ):
        left = min_
        right= max_
        while not(left==right):
            mid = (left+right) //2
            tmp = func(mid)
            if tmp:
                right = mid
            else:
                left = mid+1
        return left

    print(nibun(judge,0,1500009))

while True:
    main()

Submission status: Accepted

Solution code:
def hondan(w,m):
    m_sum = b_lis[0]
    num = 0
    if w < max(b_lis):
        return False
    else:
        for i in range(len(b_lis) - 1):
            m_sum += b_lis[i + 1]
            if m_sum > w:

                m_sum = b_lis[i + 1]
                num += 1

        if num < m:
            return True
        else:
            return False
        
def nibutan(f_id,e_id,m):
    
    
    m_id = int((f_id + e_id) / 2)
    m_bo = hondan(m_id,m)


    if (f_id > e_id):
        return m_id + 1
    else:
        if m_bo:
            return(nibutan(f_id,m_id -1,m))
        elif not m_bo:
            return(nibutan(m_id + 1,e_id,m))
        else:
            return m_id + 1



while True:
    global w_lis
    b_lis = []
    w_lis = []
    dan_num = [0]

    m,n = map(int,input().split())
    if m == n == 0:
        break
    for i in range(n):
        num = int(input())
        b_lis.append(num)
    s_num = int(sum(b_lis) /m)

    print(nibutan(s_num,1500000,m) )

Submission status: Accepted

Solution code:
import bisect
def main():
    m,n  = list(map(int,input().split()))
    if n==0:
        exit()
    W = [int(input()) for _ in range(n)]

    w_total = 0
    w_sum =[0]
    for w in W:
        w_total+=w
        w_sum.append(w_total)

    def judge(shelf_length):
        last_val = 0
        for i in range(m):
            _index= bisect.bisect_right(w_sum,last_val+shelf_length)
            #print(_index)
            if _index == n+1:
                return True
            assert _index > 0
            last_val =w_sum[_index-1]
        return False


    def nibun(func ,min_ ,max_ ):
        left = min_
        right= max_
        while not(left==right):
            mid = (left+right) //2
            tmp = func(mid)
            if tmp:
                right = mid
            else:
                left = mid+1
        return left

    print(nibun(judge,0,1500009))

while True:
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181

"""
import sys
from sys import stdin
input = stdin.readline


def Cond(m, n, mid, books):
    if max(books) > mid:
        return False

    rem = mid
    while books:
        while rem >= books[0]:
            rem -= books[0]
            books = books[1:]
            if len(books) == 0:
                break
        rem = mid
        m -= 1

    if m >= 0:
        return True
    else:
        return False


def solve(m, n, books):
    ub = 1500000
    lb = 0
    min_width = float('inf')

    for i in range(100):
        mid = (ub + lb) // 2
        if Cond(m, n, mid, books):
            min_width = min(min_width, mid)
            ub = mid
        else:
            lb = mid

    return min_width



def main(args):
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break
        books = [int(input()) for _ in range(n)]
        result = solve(m, n, books)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181

"""
import sys
from sys import stdin
input = stdin.readline


def Cond(m, n, mid, books):
    if max(books) > mid:
        return False

    rem = mid
    while books:
        while rem >= books[0]:
            rem -= books[0]
            books = books[1:]
            if len(books) == 0:
                break
        rem = mid
        m -= 1

    if m >= 0:
        return True
    else:
        return False


def solve(m, n, books):
    ub = 1500000
    lb = 0
    min_width = float('inf')

    for i in range(50):
        mid = (ub + lb) // 2
        if Cond(m, n, mid, books):
            min_width = min(min_width, mid)
            ub = mid
        else:
            lb = mid

    return min_width



def main(args):
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break
        books = [int(input()) for _ in range(n)]
        result = solve(m, n, books)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181

"""
import sys
from sys import stdin
input = stdin.readline


def Cond(m, n, mid, books):
    if max(books) > mid:
        return False

    rem = mid
    while books:
        while rem >= books[0]:
            rem -= books[0]
            books = books[1:]
            if len(books) == 0:
                break
        rem = mid
        m -= 1

    if m >= 0:
        return True
    else:
        return False


def solve(m, n, books):
    ub = 1500000
    lb = min(books)
    min_width = float('inf')

    for i in range(30):
        mid = (ub + lb) // 2
        if Cond(m, n, mid, books):
            min_width = min(min_width, mid)
            ub = mid
        else:
            lb = mid

    return min_width



def main(args):
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break
        books = [int(input()) for _ in range(n)]
        result = solve(m, n, books)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181

"""
import sys
from sys import stdin
input = stdin.readline


def Cond(m, n, mid, books):
    if max(books) > mid:
        return False

    rem = mid
    while books:
        while rem >= books[0]:
            rem -= books[0]
            books = books[1:]
            if len(books) == 0:
                break
        rem = mid
        m -= 1
        if m < 0:
            return False
        
    return True


def solve(m, n, books):
    ub = 1500000
    lb = max(books)
    min_width = float('inf')

    for i in range(30):
        mid = (ub + lb) // 2
        if Cond(m, n, mid, books):
            min_width = min(min_width, mid)
            ub = mid
        else:
            lb = mid
    return min_width


def main(args):
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break
        books = [int(input()) for _ in range(n)]
        result = solve(m, n, books)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181


"""
import sys
from sys import stdin
input = stdin.readline


def Cond(m, n, mid, books):
    rem = mid
    i = 0
    while True:
        while rem >= books[i]:
            rem -= books[i]
            i += 1
            if i == n:
                break
        rem = mid
        m -= 1
        if i == n:
            break

    if m < 0:
        return False
    else:
        return True


def solve(m, n, books):
    ub = 1500000
    lb = max(books)

    min_width = float('inf')
    for i in range(30):
        mid = (ub + lb) // 2
        if Cond(m, n, mid, books):
            min_width = min(min_width, mid)
            ub = mid
        else:
            lb = mid
    return min_width


def main(args):
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break
        books = [int(input()) for _ in range(n)]
        result = solve(m, n, books)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
while(True):
    # n:#ofShelf, m:#ofBook
    n, m = map(int, input().split(' '))
    if n == 0:
        break
    widths = [int(input()) for i in range(m)]
    minwid = max(widths)
    maxwid = sum(widths)

    def packable():
        bookQ = widths.copy()
        nShelf = 1
        sumBook = 0
        while len(bookQ) != 0 and nShelf <= n:
            if sumBook + bookQ[0] <= guess:
                sumBook += bookQ.pop(0)
            else:
                nShelf += 1
                sumBook = bookQ.pop(0)
        return len(bookQ) == 0 and nShelf <= n

    # Try packing
    while minwid != maxwid:
        guess = (maxwid+minwid)//2
        if packable():
            maxwid = guess
        else:
            minwid = guess + 1
    print(minwid)