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)
	}
}

C++: #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int height(const vint& v, int w)
{
	int res = 0, pl = 0;
	
	rep(i, v.size())
	{
		if(w < pl + v[i])
		{
			res++;
			
			if(w < v[i]) return INT_MAX;
			
			pl = 0;
		}
		
		pl += v[i];
	}
	
	return res + (pl != 0);
}

int main()
{
	int m, n;
	while(cin >> m >> n && n)
	{		
		vint v(n);
		rep(i, n) cin >> v[i];
		
		double lb = 1, ub = 1500000;
		
		rep(i, 10000)
		{
			double mid = (ub + lb) / 2;
			
			if(height(v, ceil(mid)) <= m) ub = mid;
			else lb = mid;
		}
		
		cout << ceil(ub) << endl;
	}
}

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

int main(){
    while(1){
        int m, n;
        cin >> m >> n;

        if(m + n == 0)  break;

        int w[n], minp = 1000001;
        for(int i = 0; i < n; i++){
            cin >> w[i];
            minp = min(minp, w[i]); 
        }

        int l = minp, r = 1500000;

        while(r-l > 0){
            int mid = (r+l) / 2;

            int tmpm = 1, nowp = 0;
            for(int i = 0; i < n; i++){
                if(nowp + w[i] <= mid){
                    nowp += w[i];
                }else{
                    nowp = w[i];
                    tmpm++;
                }
            }

            if(tmpm <= m)   r = mid;
            else            l = mid+1;
        }

        cout << r << endl;
    }

    return 0;
}

C++: #include<iostream>
#include<vector>
using namespace std;
int n,m;
vector<int> v;
bool f(int sz){
	int temp=sz;
	int ret=1;
	for(int i=0;i<m;i++){
		if(sz-v[i]>=0){
			sz-=v[i];
		}else{
			ret++;
			sz=temp-v[i];
		}
	}
	return ret<=n;
}
int main(){
	while(cin>>n>>m,n||m){
		v=vector<int>(m);
		int l=0,r=0;
		for(int i=0;i<m;i++){
			cin>>v[i];
			r+=v[i];
			l=max(l,v[i]);
		}
		
		while(r>l){
			int mid=(l+r)/2;
			if(f(mid)){
				r=mid;
			}else{
				l=mid+1;
			}
			
		}
		cout<<r<<endl;
	}
	return 0;
}

C++: #include <stdio.h>

int book[100];

class list{
public:
	int listwide,stert,end;
	
	//本棚の大きさの更新
	void totalwide(){
		int i,j;
		listwide = 0;
		for(i = stert; i <= end; i++){
			listwide += book[i];
		}
	}
	void print(){
		printf("w:%d s:%d e:%d\n",listwide,stert,end);
	}
};

list ct[20];
int n,m;

int main()
{
	int i,j,maxNO,max;
	int totalmin;

	scanf("%d%d",&m,&n);
	while(m != 0 && n != 0){
		//初期化
		for(i = 0; i < m; i++){
			ct[i].stert = i;
			ct[i].end = i;
		}
		for(; i < n; i++){
			ct[m-1].end++;
		}
		totalmin = 100000;

		//入力
		for(i = 0; i < n; i++){
			scanf("%d",&book[i]);
		}
		
		//処理開始
		//一番幅の大きい棚から1冊、上の棚へ移動する
		//同じ幅の棚が複数ある場合、一番下の棚からとる
		//最大の棚が一番上の棚になったら終了
		for(i = 0; i < m; i++){
			ct[i].totalwide();
		}
		while(1){
			//一番大きい棚のナンバー
			max = 0;
			for(i = 0; i < m; i++){
				if(max < ct[i].listwide){
					max = ct[i].listwide;
					maxNO = i;
				}
			}
			if(max < totalmin){
				totalmin = max;
			}
			/*printf("最大NO:%d サイズ:%d\n",maxNO,max);
			for(i = 0; i < m; i++){
			printf("NO:%d サイズ:%d\n",i,ct[i].listwide);
			}*/
			//一番上なら終了
			if(maxNO == 0){
				break;
			}
			ct[maxNO].stert++;
			ct[maxNO-1].end++;
			ct[maxNO].totalwide();
			ct[maxNO-1].totalwide();
		}
		printf("%d\n",totalmin);

		scanf("%d%d",&m,&n);
	}

	return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<int>V;
int main(){
    int m,n;
    while(cin>>m>>n,m||n){
        V.clear();
        V.resize(n);
        int Max=0;
        for(int i=0;i<n;i++){
            cin>>V[i];
            Max=max(Max,V[i]);
        }
        int l=Max,r=100000000;
        while(r-l>=1){
            int mid=(l+r)/2;
            int cnt=1,leftW=mid;
            for(int i=0;i<n;i++){
                if(leftW>=V[i])leftW-=V[i];
                else{
                    cnt++;
                    leftW=mid-V[i];
                }
            }
            if(m<cnt)l=mid+1;
            else r=mid;
        }
        cout<<r<<endl;
    }
    return 0;
}

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

int main()
{
	int i,n,m,hon[100],max,dan,temp;
	while(cin >> m >> n, n || m){
		max = 0;
		for(i = 0;i < n;i++){
			cin >> hon[i];
			if(max < hon[i])
				max = hon[i];
		}
		dan = m + 1;
		for(i = max;dan > m;i++){
			dan = 1;
			temp = 0;
			for(int j = 0;j < n;j++){
				if(temp + hon[j] <= i){
					temp += hon[j];
				} else {
					temp = hon[j];
					dan++;
				}
			}
		}
		cout << i - 1 << endl;
	}
	return 0;
}

C++: #include<cstdio>
#include<algorithm>
using namespace std;
int psum[128];
int m,n;
bool check(int mid){
	int now = 0;
	int D = 0;
	int cnt = 0;
	bool f = false;
	int x = 1000;
	while(x--){
		if(psum[now] < mid && !f)now++;
		else if(psum[now] == mid && !f){
			f = true;
			cnt++;
			D = now-1;
		}
		else if(f && psum[now]-psum[D] < mid)now++;
		else if(f && psum[now]-psum[D] == mid){
			cnt++;
			D = now-1;
		}
		else{
			f = true;
			cnt++;
			D = now-1;
		}
		if(now == n)break;
	}
	
	if(cnt > m-1)return false;
	else return true;
}
int main(){
	while(scanf("%d%d",&m,&n),(m|n)){
		int books[128];
		int sum = 0;
		int ma = -1000;
		for(int i = 0; i < n; i++){
			scanf("%d",&books[i]);
			sum += books[i];
			ma = max(ma,books[i]);
			if(i==0)psum[i] = sum;
			else psum[i] = psum[i-1]+books[i];
		}
		
		int l = ma,r = sum;
		int mid=0;
		for(int i = 0;i < 100; i++){
			mid = (l+r)/2;
			if( check(mid) ){
				r = mid;
			}
			else l = mid;
		}
		printf("%d\n",mid);
	}
	return 0;
}