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<algorithm>
using namespace std;
int main() {
	int m, n;
	while (cin >> m >> n, m, n) {
		int w[110];
		int f = 0;
		for (int i = 0; i < n; i++) { cin >> w[i]; f = max(w[i], f); }
		while (1) {
			int p = 1, q = f;
			for (int i = 0; i < n; i++) {
				if (w[i] <= q)q -= w[i];
				else {
					p++;
					q = f - w[i];
				}
			}
			if (p <= m)break;
			f += 100;
		}
		cout << f << endl;
	}
}

C++: #define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;

int C(int* book,int n,int m,int w){
	int j=0;
	for(int i=0;i<m;i++){
		int tmp = w;
		for(;j<n;){
			tmp-= book[j];
			if(tmp >= 0) j++;
			else {
				break;
			}
		}
	}

	if(j<n) return false;
	else return true;

}

int main(){
	int m,n;
	while(~scanf("%d %d",&m,&n)){
		if(m==n && n==0) break;

		int *book = new int[n]();
		for(int i=0;i<n;i++){
			scanf("%d",book+i);
		}

		int lb = 1;
		int ub = 1500000;
		int md;

		for(int i=0;i<100;i++){
			md = (lb+ub)/2;
			if(C(book,n,m,md)) ub = md;
			else lb = md;
		}

		printf("%d\n",ub);
		delete[] book;
	}
}

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

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 f first
#define s second

int main(){
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0)break;
		
		int hon[111];
		rep(i,m){
			cin>>hon[i];
		}
		
		double left=0;
		double right=15000001;
		
		while(1){
			double h=(left+right)/2;
			
			int dan=1;
			int now=0;
			rep(i,m){
				if(now+hon[i]>h){
					now=0;
					i--;
					dan++;
				}else{
					now+=hon[i];
				}
				if(dan>n)break;
			}
			
			if(dan>n){
				left=h;
			}else{
				right=h;
			}
			
			if(right-left<0.0001){
				printf("%d\n",(int)(right+0.001));
				break;
			}
		}
	}
}

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;
        if(m==0&&n==0) break;
        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<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>

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 f first
#define s second

int main(){
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0)break;
		
		int hon[111];
		rep(i,m){
			cin>>hon[i];
		}
		
		double left=0;
		double right=15000001;
		
		while(1){
			double h=(left+right)/2;
			
			int dan=0;
			int now=0;
			rep(i,m){
				if(now+hon[i]>h){
					now=0;
					i--;
					dan++;
				}else{
					now+=hon[i];
				}
				if(dan>n)break;
			}
			
			if(dan>n){
				left=h;
			}else{
				right=h;
			}
			
			if(right-left<0.0001){
				printf("%d\n",(int)(right+0.001));
				break;
			}
		}
	}
}

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

using namespace std;

int w[200];

bool judge(int num, int length, int height){
	int count = 0;
	int sum = 0;
	for(int i = 0; i < length; i++){
		if(w[i] > num){
			return false;
		}
		if(sum + w[i] > num){
			count++;
			sum = w[i];
		}else{
			sum += w[i];
		}
	}
	count++;
	if(count <= height){
		return true;
	}
	return false;
}

int binary_search(int lef, int rig, int m, int n){
	int middle = (lef + rig) / 2;
	if(rig - lef <= 1){
		if(judge(lef, n, m)){
			return lef;
		}else{
			return rig;
		}
	}
	if(judge(middle, n, m)){
		rig = middle;
		return binary_search(lef, rig, m, n);
	}else{
		lef = middle;
		return binary_search(lef, rig, m, n);
	}
}

int main(){
	
	int m, n;
	
	while(true){
		
		cin >> m >> n;
		
		if(m == 0 && n == 0){
			break;
		}
		
		for(int i = 0; i < n; i++){
			cin >> w[i];
		}
		
		cout << binary_search(0, 1600000, m, n) << endl;
		
	}
	return 0;
}

C++: #include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt" > "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\b.answer"
int main() {
	while (1) {
		int M, N; cin >> M >> N;
		if (!M)break;
		vector<int>as;
		for (int i = 0; i < N; ++i) {
			int a; cin >> a;
			as.emplace_back(a);
		}

		int amin = *max_element(as.begin(),as.end())-1; int amax = 1500001;
		while (amin + 1 != amax) {
			int amid = (amin + amax) / 2;
			{
				int h = 0;
				int num = 0;
				for (int b = 0; b < N; ++b) {
					if (as[b] + num > amid) {
						h++;
						num = as[b];
					}
					else {
						num += asa[b];
					}
				}
				if (h >= M) {
					amin = amid;
				}
				else {
					amax = amid;
				}
			}
		}
		cout << amax << endl;
	}
	return 0;
}

C++: #include<iostream>

int n,m;
int DP[100][20];
int book[100];

int solve(){
	for(int i=1; i<n; i++){
		for(int j=1; j<m; j++){
			if(DP[i-1][j-1] <= book[i])
				DP[i][j] = book[i];
			else{
				int tmp = book[i];
				DP[i][j] = DP[i-1][j-1];
				for(int k=1; k<i; k++){
					tmp += book[i-k];
					if(DP[i-k-1][j-1]<=tmp){
						if(tmp < DP[i][j])
							DP[i][j] = tmp;
						break;
					}else{
						if(DP[i-k-1][j-1] < DP[i][j])
							DP[i][j] = DP[i-k-1][j-1];
					}
				}
			}
		}
	}
	return DP[n-1][m-1];
}

int main(){
	while(true){
		std::cin >> m >> n;
		if(!m && !n)
			return 0;
		for(int i=0; i<n; i++){
			std::cin >> book[i];
			if(i>0){
				DP[i][0] = book[i];
				DP[i][0] += DP[i-1][0];
			}else{
				for(int k=0; k<m; k++)
					DP[i][k] = book[i];
			}
		}

		std::cout << solve() << std::endl;
	}
}