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 <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int m, n;
int w[111];

bool f(ll x) {
    ll step = 1, len = 0;
    for (int i = 0; i < n; i++) {
        if (len + w[i] <= x) len += w[i];
        else {
            step++;
            if (w[i] <= x) len = w[i];
            else return false;
        }
        if (step > m) return false;
    }
    return true;
}

int main() {
    while (cin >> m >> n && (m != 0 || n != 0)) {
        for (int i = 0; i < n; i++) cin >> w[i];
        ll ng = 0, ok = 1515151;
        while (ok - ng > 1) {
            ll md = (ok + ng) / 2;
            if (f(md)) ok = md;
            else ng = md;
        }
        cout << ok << endl;
    }
}

C++: #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> books;
int m,n;

bool check(int r){
	int rank=0;
	int place=0;
	for(int i = 0; i < books.size(); i++){
		if(books[i]>r)
			return false;
		// àµTCYª éå«³æè¬³¯êÎ
		if(place+books[i]<=r){
			place+=books[i];
		}
		else{
			rank++;
			if(rank>=m)
				return false;
			place=0;
			place+=books[i];
		}
	}
	return true;
}

int main(){

	while(cin>>m>>n&&!(n==0&&m==0)){
		for(int i = 0; i < n; i++){
			int t;
			cin>>t;
			books.push_back(t);
		}

		int ub=1000000;
		int lb=-1;
		while(ub-lb>1){
			int med=ub+lb;
			med/=2;
			// ¨¯éÈç
			if(check(med)){
				ub=med;
			}
			else{
				lb=med;
			}
		}
		cout<<ub<<endl;
		books.clear();
	}
	
	return 0;
}

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

//3 9 5 3 8 2 1 6 9 7 4

using namespace std;

int main(){
	int DP[101][21];
	int dansu,kansu;
	while(1){
		scanf("%d%d",&dansu,&kansu);
		if(dansu==0){
			break;
		}
		int hon[101];
		for(int i=1;i<=kansu;i++){
			scanf("%d",&hon[i]);
		}
		int atu[101];
		atu[0]=0;
		for(int i=1;i<=kansu;i++){
			atu[i]=atu[i-1]+hon[i];
		}
		for(int i=1;i<=kansu;i++){
			for(int j=1;j<=dansu;j++){
				DP[i][j]=99999;
			}
		}
		for(int i=1;i<=kansu;i++){
			DP[i][1]=atu[i];
		}
		for(int i=1;i<=dansu;i++){
			DP[1][i]=atu[1];
		}
		
		for(int i=2;i<=kansu;i++){
			for(int j=2;j<=dansu;j++){
				for(int k=1;k<i;k++){
					DP[i][j]=min(max(DP[k][j-1],atu[i]-atu[k]),DP[i][j]);
				}
			}
		}
		
		/*
		for(int i=1;i<=kansu;i++){
			for(int j=1;j<=dansu;j++){
				printf("%6d",DP[i][j]);
			}
			puts("");
		}
		for(int i=1;i<=kansu;i++){
			printf("%d ",atu[i]);
		}
		puts("");
		*/
		
		printf("%d\n",DP[kansu][dansu]);
	}
}

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

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,n) for(int i=1;i<=n;i++)

int main(){
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0)break;
		
		int hon[1000];
		rep(i,m){
			cin>>hon[i];
		}
		
		int right,left;
		right=0;
		left=1000000000;
		
		int ans;
		while(1){
			double harf = double(right+left)/2;
			
			int cont=0;
			int sum=0;
			
			int flg=1;
			rep(i,m){
				if(sum+hon[i]<=harf){
					sum+=hon[i];
				}else{
					i--;
					cont++;
					sum=0;
				}
				
				if(cont>=n){
					flg=0;
					break;
				}
			}
			
			if(flg==0){
				right=harf;
			}else{
				left = harf+0.5;
			}
			
			ans=left;
			if(right+1 == left)break;
		}
		
		printf("%d\n",ans);
	}
}

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

int m,c,maxim,minim,k;
int bc[100];

int search(int w){
    int empty = 0;
    int d = 1;
    for(int i = 0; i < c; i++){
        if(empty + bc[i] >= w){
            if(d == m){
                return 0;
            }else{
                d++;
                empty = bc[i];
            }
        }else{
            empty += bc[i];
        }
    }
    //cout << "ばーか" << w <<endl;
    return 1;
}

int saiki(int n,int s){
    //cout << n << " " << s << endl;
    if(s <= 2){
        if(search(n + 1)==1){
            return n;
        }else{
            return n + 1;
        }
    }else{
        if(s % 2 == 1){
            if(search(n + (s + 1) / 2)==1){
                return saiki(n, (s + 1) / 2);
            }else{
                return saiki(n + (s + 1) / 2, (s + 1) / 2);
            }
        }else{
            if(search(n + s / 2)==1){
                return saiki(n, s / 2);
            }else{
                return saiki(n + s / 2, s / 2);
            }
        }
    }
}

int main(){
    for(;;){
        maxim = 0;
        minim = 0;
        if(cin >> m >> c){
            if(m == 0 && c == 0){
                break;
            }else{
                for(int i = 0; i < c; i++){
                    cin >> bc[i];
                    maxim += bc[i];
                    if(minim <= bc[i]){
                        minim = bc[i];
                    }
                    //cout << bc[i] << endl;
                }
                cout << saiki(minim, maxim-minim) << endl;
            }
        }else{
            break;
        }
    }
    return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10
#define MAX_N 20000
#define MAX_M 16

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

ll  n, m, b[1000];

int main(){
	while (cin >> m >> n&&n + m){
		ll MAX = -1;
		REP(i, n){
			cin >> b[i];
			MAX = max(MAX, b[i]);
		}
		ll lb = MAX - 1, ub = 1500001;
		while (ub - lb > 1){
			cout << lb << " " << ub << endl;
			int co = 1;
			ll mid = (lb + ub) / 2;
			ll sum = 0;
			REP(i, n){
				sum += b[i];
				if (sum > mid){
					sum = b[i];
					co++;
				}
			}
			if (co <= m)ub = mid;
			else lb = mid;
		}
		cout << ub << endl;
	}
}