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 <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int m, n;
        cin >> m >> n;
        if(m == 0)
            return 0;

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

        int a = 1;
        int b = 1500000;
        while(a != b){
            int c = (a + b) / 2;
            int k = 1;
            for(int i=0; i<m; ++i){
                k = upper_bound(book.begin()+k, book.end(), book[k-1] + c) - book.begin();
                if(k == n+1)
                    break;
            }

            if(k == n+1)
                b = c;
            else
                a = c+1;
        }

        cout << a << endl;
    }
}

C++: #include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<sstream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<cmath>
#include <fstream>	// require freopen
using namespace std;
#define REP(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) REP(i,0,n)
int b[100],m,n;
bool C(int d)
{
  int v[20]; rep(i,m)v[i]=0;
  int ii=0;
  rep(i,n){
    while(ii<m && v[ii]+b[i]>d)ii++;
    if(ii==m)return false;
    v[ii]+=b[i];
  }
  return true;
}
int main(void)
{
//	cut here before submit 
//	freopen ("testcase.persistence", "r", stdin );

  for(;;){
    scanf("%d%d",&m,&n); if(!m)break;
    rep(i,n) scanf("%d",b+i);
    int l,r,mid,res=9999999;
    l=0; r=1500000;
    while(l<=r){
      mid=(l+r)/2;
      //printf("%d %d %d\n",l,mid,r);
      if(C(mid)){
	res=min(res,mid);
	r=mid-1;
      }
      else l=mid+1;
    }
    printf("%d\n",res);
  }
}

C++: #include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <limits>
using namespace std;
typedef long long ll;

int n, m;
int book[110];

bool can(int W){
	int cnt = 1;
	int w = 0;

	for(int i=0;i<n;i++){
		if(w + book[i] <= W){
			w += book[i];
		} else {
			++cnt;
			w = book[i];
		}
	}

	return (cnt <= m);
}

int main(){
	while(cin >> m >> n){
		if(n == 0 && m == 0)break;
		for(int i=0;i<n;i++)cin >> book[i];

		int sum = accumulate(book, book + n, 0);
		int maxi = *max_element(book, book + n);

		int low = maxi - 1, high = sum;

		while(high - low > 1){
			int mid = (high - low) / 2 + low;
			if(can(mid))high = mid; else low = mid;
		}

		cout << high << endl;
	}
	return 0;
}

C++: #include<iostream>

using namespace std;
int m, n, w[100];

int calc(int t){
    int sum=0, ret=1;
    for(int i=0; i<n; i++){
        if(w[i]>t) return 1500001;
        if(sum+w[i]>t){
            sum=0;
            ret++;
        }
        sum+=w[i];
    }
    return ret;
}

int main(){

    while(1){
        cin>> m>> n;
        for(int i=0; i<n; i++){
            cin>> w[i];
        }

        int l=1, h=1500000;
        while(h-l>1){
            int md=(l+h)/2;
            if(calc(md)>m) l=md;
            else h=md;
        }

        cout<< h<< endl;

    }

    return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>

using namespace std;

#define rep(i,n) for(int i=0;i<int(n);i++)
#define reps(i,n) for(int i=1;i<=int(n);i++)
#define sint(i) scanf("%d",&i);
#define sintt(i,j) scanf("%d%d",&i,&j);
#define sinttt(i,j,k) scanf("%d%d%d",&i,&j,&k);

#define INF 1010000000
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int main(){
	while(1){
		int n,m;
		sintt(m,n);
		if(n==0)break;
		int hon[101];
		rep(i,n){
			sint(hon[i]);
		}
		
		int left=0;
		int right=1500000;
		
		while(1){
			double harf=(right+left)/2.0;
			
			int flg=0;
			
			int now=0;
			int cont=0;
			rep(i,n){
				if(now+hon[i]<=harf){
					now+=hon[i];
				}else{
					now=0;
					i--;
					cont++;
				}
				if(cont>=m){
					break;
				}
			}
			
			if(cont>=m){
				flg=1;
			}
			
			if(flg==1){
				left=harf+0.5;
			}else{
				right=harf;
			}
			
			if(left==right){
				printf("%d\n",left);
				break;
			}
		}
	}
}

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

bool comp(int i, int j){
	return i > j;
}

int main(){
	int n, m;
	while(cin >> m >> n){
		const int mmax = 100;
		int books[mmax];
		if(m == 0 && n == 0) break;
		for(int i = 0; i < n; i++){
			cin >> books[i];
		}
		while(n > m){
			sort(books, books+n, comp);
			books[n-2] += books[n-1];
			n--;
		}
		int size = -1;
		for(int i = 0; i < n; i++){
			size = max(size, books[i]);
		}
		cout << size << endl;
	}
	return 0;
}

C++: //b
#include <iostream>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <memory>
#include <functional>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define REPR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define EACH(i, c) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define BIT(n, b) ((n>>b) & 1)
#define PB push_back
#define MP make_pair

using namespace std;

static const double PI = acos(-1.0);
static const double EPS = 1e-9;
typedef long long ll;
typedef pair<int, int> pii;	

int m, n;
int book[10000];

bool chk(int width){
	
	int sum = 0, height = 0;
	
	for(int i=0; i<n; ++i){
		
		if(book[i] > width){
			return false;	//明らかに入らない本が出てきたら広げなくてはいけない
		}
		
		sum += book[i];		//本を詰める
		
		if(sum > width){
			sum = book[i];	//入らなくなったら下の段に移動
			height++;		//段の数を増やす
		}
	}
	
	return height < m;
}	

int main(){
	
	while(cin>>m>>n, (m||n)){
		
		for(int i=0; i<n; ++i){
			cin>>book[i];
		}
		
		int upper = INT_MAX/2, lower = 0, middle;
		
		while(upper - lower > 1){
			
			middle = (upper+lower)/2;
			
			if( chk(middle) ){ 
				upper = middle;
			}
			else{
				lower = middle;
			}
		}
		
		cout << upper << endl;
	}
	
	return 0;	
}