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>
using namespace std;

int m,n;
int a[100];

bool check(int x){
  int b[20];
  int i,j=0;
  for(i=0;i<m;i++)b[i] = x;
  for(i=0;i<n;i++){
    if(b[j]>=a[i])b[j] -= a[i];
    else {
      j++;
      i--;
      if(j==m)break;
    }
  }
  if(i==n)return true;
  return false;
}

int main(){
  int l,r,mid;

  while(1){
    cin >> m >> n;
    if(!m && !n)break;

    for(int i=0;i<n;i++)cin >> a[i];

    l = 0;r = 1500000;

    while(l+1<r){
      mid = (l+r)/2;
      if(check(mid))r = mid;
      else l = mid;
    }

    cout << r << endl;
  }
}

C++: #include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>
#include <stack>
#include <set>
#include <vector>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INF = 1 << 29;
const double EPS = 1e-10;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
    return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
    os<<'[';
    rep(i,a.size()) os<<(i?" ":"")<<a[i];
    return os<<']';
}



int main() {
    for (int m, n; cin >> m >> n, (m | n) != 0;) {
        int bs[100];
        rep(i, n) cin >> bs[i];

        int lb = 0, ub = 1500000;
        while (ub - lb > 1) {
            int mid = (ub + lb) / 2;
            int c = 1;
            int l = 0;
            bool suc = true;
            rep(i, n) {
                if (l + bs[i] > mid) {
                    if (c == m || l == 0) {
                        suc = false;
                        break;
                    }
                    c++;
                    l = bs[i];
                }
                else {
                    l += bs[i];
                }
            }
            if (suc) ub = mid;
            else lb = mid;
        }
        cout << ub << endl;
    }
    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  while(1){
    int n,m;
    cin >> m >> n;
    if(n==0 && m==0){
      return 0;
    }
    int w[110],i;
    for(i=0;i<n;i++){
      cin >> w[i];
    }
    int min=0,max=1500001;
    while(abs(min-max)>1){
      int sum=0,sum1=0,mid=(min+max)/2;
      for(i=0;i<n;i++){
        if(w[i]>mid){
          sum1=100;
          break;
        }
        else if(sum+w[i]<=mid){
          sum+=w[i];
        }
        else{
          sum=w[i],sum1++;
        }
      }
      sum1++;
      if(sum1<=m){
        max=mid;
      }
      else{
        min=mid;
      }
    }
    cout << max << endl;
  }
}

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 = 30;
		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++: #include<iostream>
#include<algorithm>
#include<vector>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
vector<int> G;
int m;

bool check(int v)
{
  int cnt = 0;
  int sum = 0;
  rep(i,G.size())
    {
      if(G[i] > v)return false;
      sum += G[i];
      if(sum > v)
	{
	  sum = G[i];
	  cnt++;
	}
    }
  return cnt < m;
}

int main()
{
  int n;
  while(cin >> m >> n,m|n)
    {
      G.resize(n);
      rep(i,n)cin >> G[i];
      int L = 0;
      int R = 1500000;
      int M;
      rep(j,100)
	{
	  M = (L+R)/2;
	  if(!check(M))
	    L = M;
	  else
	    R = M;	      
	}
      cout << R << endl; 
    }
  return 0;
}

C++: #include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i,j;
  int w[100],b[21],e[21],s[21],m,n,y,wmn,bmn;
  for(;;){
    cin>>m>>n;
    if(m+n==0)
      break;
    y=0;
    for(i=0;i<n;i++){
      cin>>w[i];
      y=max(y,w[i]);
    }
    i=0;
    j=0;
    s[i]=w[j];
    b[i]=j;
    e[i]=j;
    for(j++;j<n;j++){
      if(s[i]+w[j]<=y){
	s[i]+=w[j];
	e[i]=j;
      }else{
	i++;
	s[i]=w[j];
	b[i]=j;
	e[i]=j;
	if(i==m)
	  break;	
      }
    }
    if(j!=n){
      for(;;){
	wmn=y;
	for(i=0;i<m;i++){
	  if(s[i]+w[b[i+1]]-y<wmn){
	    wmn=s[i]+w[b[i+1]]-y;
	    bmn=i;
	  }
	}
	y+=wmn;
	i=bmn;
	j=e[bmn];
	for(j++;j<n;j++){
	  if(s[i]+w[j]<=y){
	    s[i]+=w[j];
	    e[i]=j;
	  }else{
	    i++;
	    s[i]=w[j];
	    b[i]=j;
	    e[i]=j;
	    if(i==m)
	      break;	  
	  }
	}
	if(j==n)
	  break;
      }
    }
    cout<<y<<endl;
  }
  return 0;
}

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

const int WMAX = 1500000;
const int NMAX = 100;

int n, m, a[NMAX];

bool check(int w) {
  int p, q, r;
  p = q = r = 0;
  while (p < m) {
    if (q + a[r] > w) {
      ++p;
      q = a[r];
    } else {
      q += a[r];
    }
    ++r;
    if (r >= n) {
      break;
    }
  }
  return (p<m);
}

int main() {
  int l, r, c, minw;
  bool b;
  while (1) {
    cin >> m >> n;
    if (!m && !n) break;
    minw = 0;
    for (int i=0; i<n; i++) {
      cin >> a[i];
      if (minw < a[i]) {
        minw = a[i];
      }
    }
    l = minw;
    r = WMAX;
    c = (l+r)/2;
    while (l != r) {
      b = check(c);
      if (b) {
        r = c;
      } else {
        l = c+1;
      }
      c = (l+r)/2;
    }
    cout << l << endl;
  }
  return 0;
}