Go: package main

import (
	"bufio"
	"os"
	"strings"
	"strconv"
	"fmt"
	)

var scanner = bufio.NewScanner(os.Stdin)
const MAX_WIDTH = 1500000

func main() {
	// 二分探索で探す
	// 二分探索はソート済みの配列に対して、特定の条件を満たす値を
	// 効率よく選択するアルゴリズム
	for scanner.Scan() {
		buf := strings.Split(scanner.Text(), " ")
		m, _ := strconv.Atoi(buf[0])
		n, _ := strconv.Atoi(buf[1])
		if n == 0 && m == 0 {
			break
		}
		books := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			books[i], _ = strconv.Atoi(scanner.Text())
		}
		check := func(width int) bool {
			// widthの幅の本棚に順番にbooksを詰めて行ったら
			// 何段になるのかを確認し、それがmを以下であることを確認する
			shelf_index := 1
			position_in_stage := 0
			for i := 0; i < n; i++ {
				// 入れることができない本がある時点でこのwidthは不採用
				if books[i] > width {
					return false
				}
				// 新たに本を追加することができるかをチェックする
				if position_in_stage + books[i] <= width {
					// 新たに本を入れることができたので、そのステージにおける
					// 現在の本の位置を記録
					position_in_stage += books[i]
				} else {
					// 新たな本を入れることができなかったので、一段下のステージに
					// 入れれば良い
					position_in_stage = books[i]
					shelf_index++ // 本棚のステージ数が増えた
				}
			}
			return shelf_index <= m // 条件を満たすかの確認
		}
		low, high := 0, MAX_WIDTH
		for low < high {
			mid := (low+high)/2
			if check(mid) {
				high = mid
			} else {
				low = mid+1
			}
			// log.Printf("low: %d, high: %d\n", low, high)
		}
		fmt.Println(low)
	}
}

Python: # 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)

C++: #include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using int64 = int64_t;

constexpr int64 MOD = 1000000007;

int M, N;
int arr[100];

int main() {
    while (true) {
        cin >> M >> N;
        if (M+N == 0) break;
        for (int j = 0; j < N; ++j) {
            cin >> arr[j];
        }

        int l = 0, r = 1500000;
        while (l < r) {
            int m = (l+r) / 2;
            int row = 0, acc = 0;
            bool ok = true;
            for (int j = 0; j < N; ++j) {
                if (m-acc < arr[j]) {
                    ++row;
                    acc = 0;
                }
                if (row == M || m < arr[j]) {
                    ok = false;
                    break;
                } 
                if (m-acc >= arr[j]) {
                    acc += arr[j];
                }
            }
            if (ok) {
                r = m;
            } else {
                l = m+1;
            }
        }
        cout << r << endl;
    }
    return 0;
}

C++: #include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <complex>
using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define EPS 1e-8
#define DEB 0

int n,m;
int data[128];

int f(int mid){
	int cnt = 0;
	int sum = 0;
	rep(i,n){
		if( mid<data[i] ) return INT_MAX;
		sum += data[i];
		if( sum>mid ){
			cnt++;
			sum = data[i];
		}
	}
	return cnt+1;
}

int main(){
	while(scanf("%d%d",&m,&n),m|n){
		int sum = 0;
		rep(i,n){
			scanf("%d",data+i);
			sum += data[i];
		}
		int l = 0;
		int r = sum;
		while( l<r ){
			int mid = (l+r)/2;
			int k = f(mid);
#if DEB
			printf("mid:%d   k:%d\n",mid,k);
#endif			
			if( k<=m ){
				r = mid;
			}else{
				l = mid + 1;
			}
#if DEB
			printf("(l,r) = (%d,%d)\n",l,r);
#endif 			
		}
		printf("%d\n",r);
	}
	return 0;
}

C++: #include<iostream>
using namespace std;
int s[1001];
int b[1001];
int m, n;
int nb;
int w;
//find max x s[x]<=w+s[nb-1];
int se() {
	int be = 1;
	int en = n;
	int bb=-1;
	for (; en - be>0;) {
		int mid = (be + en) / 2;
		if (w + s[nb-1] >= s[mid]) {
			be = mid;
			if (bb == be)
				en--;
			else
				bb = be;

		}
		else {
			en = mid;
		}
		

	}
	
	if (be + 1 <= n)
		if (s[be+1] <= w + s[nb - 1])
			return be + 1;
	if (s[be] <= w + s[nb - 1])
		return be;
	else
		return -1000;
}

int main() {
	s[0] = 0;
	while (cin >> m >> n, m) {
		int i;
		int nm;
		for (i = 0; i < n; i++)
			cin >> b[i];
		for (i = 1; i <= n; i++)
			s[i] = s[i - 1] + b[i-1];
		for (w = 1; w <= 1500000; w++) {
			nb = 1;
			for (nm = 1; nm <= m&&nb<=n; nm++) {
				nb = se();
				if (nb < 0)
					break;
				nb++;
				
			}
			if (nb > n)
				break;

		}
		cout << w << endl;




	}
	return 0;
}

C++: #include<iostream>

using namespace std;

int main(){
	int n,m;
	while(1){
		cin>>n>>m;
		if(n==0 && m==0){
			break;
		}
		int hon[150];
		for(int i=0;i<m;i++){
			cin>>hon[i];
		}
		
		int right,left;
		right=left=0;
		
		for(int i=0;i<m;i++){
			left+=hon[i];
		}
		
		while(1){
			double h=(double)(left+right)/2;
			//printf("%d %d %lf\n",right,left,h);
			
			int ans=0;
			
			int now=0;
			int dan=1;
			for(int i=0;i<m;i++){
				if(now+hon[i]>h){
					if(now==0){
						dan=100000;
						break;
					}
					now=0;
					dan++;
					i--;
					continue;
				}
				now+=hon[i];
			}
			
			//printf("%lf zi dan = %d\n",h,dan);
			
			if(dan<=n){
				ans=1;
			}
			
			if(ans==1){
				left=h+0.499;
			}else{
				right=h;
			}
			
			if((int)left==(int)right+1){
				printf("%d\n",(int)h);
				break;
			}
		}
	}
}

C++: #include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF 99999999
 
 
int m,n;
int b[110];
 
bool solve(int v){
    int l=0;
    int x=v;
    rep(i,n){
        while(x<b[i]&&l<m){
            x=v;
            l++;
        }
        if(l>=m)return false;
        if(x>=b[i]){
            x-=b[i];
        }
    }
    return true;
}
 
int main(){
    while(cin>>m>>n){
        if(m==0&&m==0)break;
        rep(i,n)cin>>b[i];
         
        int left=0;
        int right=1500000-1;
        while(right>left+1){
//            cout<<left<<" "<<right<<endl;
            int cent=(left+right)/2;
            bool res = solve(cent);
            if(res) right=cent;
            else left=cent;
        }
        cout<<right<<endl;
    }
}

C++: #include <cstdio>
using namespace std;

int main()
{
	int M,N;
	while(scanf("%d%d", &M,&N), (M||N))
	{
		int wid[100]={0}, swid=0;
		for(int i=0; i<N; i++)
		{
			scanf("%d", &wid[i]);
			swid+=wid[i];
		}
		
		int hi=swid, lo=0,mi;
		
		while(hi>lo)
		{
			mi=(hi+lo)/2;
			int cap=0, d=1;
			bool g=true;
			for(int i=0; i<N; i++)
			{
				if(mi < wid[i])
				{
					g=false;
					break;
				}
				if(cap+wid[i] > mi)
				{
					cap=wid[i];
					d++;
				}
				else
				{
					cap+=wid[i];
				}
			}
			
			if(!g||d>M) lo=mi+1;
			else hi=mi;
		}
		
		printf("%d\n", hi);
	}
}