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<iostream>
#include<vector>
#include<climits>

using namespace std;

bool check(vector<int> vi,int m,int mid){
	int buf=0;
	int use=0;
	for(int i=0;i<vi.size();i++){
		if(buf+vi[i] > mid){
			if(buf == 0){
				return false;
			}
			use++;
			buf=0;
			i--;
			continue;
		}
		buf += vi[i];
	}
	if(buf != 0){
		use++;
	}
	if(use <= m){
		return true;
	}else{
		return false;
	}

}

int main(){
	while(true){
		int m,n;
		cin >> m >> n;
		if(m==0){
			break;
		}

		vector<int> vi;
		int l=INT_MAX,u=1500001;
		for(int i=0;i<n;i++){
			int buf;
			cin >> buf;
			l = min(l,buf);
			vi.push_back(buf);
		}

		for(int i=0;i<100;i++){
			int mid = (l+u)/2;
			if(check(vi,m,mid)){
				u = mid;
			}else{
				l = mid+1;
			}
		}
		cout << ((l+u)/2) << endl;
	}
}

C++: #define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <iterator>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
 
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())

typedef unsigned long long ull;
const int INF = (int)1e8;

int C(vector<int>& v,int md){
	int len = 0;
	int ret = 1;
	FOR(i,sz(v)){
		if(md < v[i]) return INF;
		if(len + v[i] <= md) len += v[i];
		else {ret++; len = v[i];}
	}

	return ret;
}

int main(){
	int n,m;
	while(cin>>n>>m,n||m){
		vector<int> v(m); FOR(i,m) cin>>v[i];
		int l = 1, r = INF;
		while(r-l!=1){
			int md = (r+l)/2;
			if(C(v,md) <= n) r = md;
			else l = md;
		}
		cout << r << endl;
	}
	return 0;
}

C++: //2?????¢?´¢????????£????§£????????????????????????????????§??????
#include<cstdio>
#include<iostream>

using namespace std;

int gcd(int m, int n)
{
	if ((0 == m) || (0 == n))
		return 1;
	while (m != n)
	{
		if (m > n) m = m - n;
		else         n = n - m;
	}
	return m;
}




int main(void) {

//	while (1) {

		int floor, n, book[101] = { 0 };
		cin >> floor >> n;

		if (floor == 0)return 0;

		for (int i = 0; i < n; i++) {
			cin >> book[i];
		}

		//?????§??¬?´???°????±???????
		int m = book[0];
		int w_avr = book[0];
		for (int i = 1; i < n; i++) {
			m = gcd(m, book[i]);
			w_avr += book[i];
		}
		//?????????????????§?????¬??????????????????????????°??§?????£?????°??????????????¬????????§?????????
		int ans = w_avr / floor;

		for (int i = 0; i < n; i++) {
			if (ans < book[i]) {
				ans = book[i];
			}
		}
		while (ans%m != 0) {
			ans=ans-1;
		}
		while (1) {
			int count = floor;
			int length = ans;
			int i = 0;
			while (count != 0 && i < n) {
				if (length >= book[i]) {
					length -= book[i];
					i++;
				}
				else {
					length = ans;
					count = count - 1;
				}
			}
			if (count != 0) {
				break;
			}
			ans += m;
		}
		cout << ans << endl;

//	}
}

C++: #include<cstdio>
#include<algorithm>
using namespace std;
int psum[128];
bool vis[1500001];
int m,n;
bool check(int mid){
	int now = 0;
	int D = 0;
	int cnt = 0;
	bool f = false;
	while(true){
		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;
}

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.5;
			}else{
				right=h;
			}
			
			if((int)left==(int)right+1){
				printf("%d\n",(int)h);
				break;
			}
		}
	}
}

C++: #include<bits/stdc++.h>
using namespace std;
int books[1005],m,c,ri,le,mid,ans,sum[205],n;
bool flag=false;

int main(){
    while(1){
        cin >> m >> n;
        if(n==0&&m==0)break;
        for(int i=0;i<n;i++){
                cin >> books[i];
                ri+=books[i];
        }
        mid=ri/2;
        le=0;

        for(int i=0;i<1000;i++){
            for(int j=0;j<m;j++){
                for(;;){
                    if(c==n){
                        flag=true;
                        break;
                    }
                    if(sum[j]+books[c]>mid)break;
                    else sum[j]+=books[c];
                    c++;
                    }
                }

                if(flag==true){
                    ri=mid;
                    mid=ri/2;
                }else{
                    le=mid;
                    mid=(le+ri)/2;
                }
                flag=false;
                c=0;
                for(int o=0;o<n+1;o++)sum[o]=0;
            }
            cout << ri << endl;
            ri=0,le=0,mid=0;
            for(int i=0;i<1000;i++)books[i]=0;
    }

 return 0;
}