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++: //2分探索したよ!!
#include<iostream>
#include<algorithm>
using namespace std;
#define INF ( 1 << 30 )
int n, m, book[100];
bool basic(double x){
  int index = 0, dan = 0, c = 0;
  while(index < n && dan < m){
    if(c + book[index] <= x) c += book[index++];
    else c = 0, dan++;
  }
  return index == n && dan < m;
}
int main(){
  while(cin >> m >> n , m){
    for(int i = 0 ; i < n ; i++ ) cin >> book[i];
    int light = 0, left = INF;
    for(int i=0 ; i < 100 ; i++){
      int java = (light + left ) / 2;
      basic(java) ? left = java : light = java;
    }
    cout << max(light,left) << endl;
  }
}

C++: #include<iostream>
using namespace std;
int n,m,w[100];
main()
{
	while(cin>>m>>n,n)
	{
		for(int i=0;i<n;i++)cin>>w[i];
		int l=0,r=1500001;
		while(r-l>1)
		{
			int W=(r+l)/2;
			int i=0;
			for(int j=0;j<m;j++)
			{
				int sum=0;
				while(i<n&&sum+w[i]<=W)sum+=w[i++];
			}
			if(i<n)l=W;
			else r=W;
		}
		cout<<r<<endl;
	}
}

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

using namespace std;

int main(){
	int R,L;
	int n,m;
	int hon[30];
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0&&m==0){
			break;
		}
		R=L=0;
		for(int i=0;i<m;i++){
			scanf("%d",&hon[i]);
			L+=hon[i];
		}
		if(n>=m){
			printf("%d\n",*max_element(hon,hon+n));
			continue;
		}
		//3 9 5 3 8 2 1 6 9 7 4
		while(1){
			if(R==L){
				break;
			}
			double H=(double)(R+L)/2;
			
			int dan=0;
			int at=0;
			for(int i=0;i<m;i++){
				if(at+hon[i] <= H){
					at+=hon[i];
				}else{
					at=0;
					dan++;
					at+=hon[i];
				}
			}
			
			if(dan<n){
				L=H;
			}else{
				R=H+0.5;
			}
			
				printf("%d %d\n",R,L);
		}
	}
}

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

typedef long long ll;

int main() {
	int n, m;
	while(cin >> m >> n, n || m) {
		vector<int> v;
		v.resize(n);
		for(int i = 0; i < n; i++)
			cin >> v[i];

		ll l, r, res;
		l = 0; r = 1600000;
		res = -1;
		while(l <= r) {
			int mid = (l + r) / 2;
			int d = 0;
			int cnt = 0;
			for(int i = 0; i < v.size(); i++) {
				if(d + v[i] > mid) {
					if(d == 0) {
						cnt = 1e9;
						break;
					}
					d = 0;
					i--;
					cnt++;
				}
				else
					d += v[i];
			}

			if(cnt < m) {
				res = mid;
				r = mid-1;
			}
			else {
				l = mid+1;
			}
		}
		cout << res << endl;
	}
}

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

int m,n;

vector<int> item;
int test(int W){
	int w = 0,r=0;
	for(int i = 0 ; i < item.size() ; i++){
		if( w - item[i] < 0 ){
			r++;
			w = W;
		}
		w -= item[i];
	}
	return r <= n;
}
int main(){

	while(cin >> n >> m && n){
		item.clear();
		int l = 0 , r = 1000000;
		for(int i = 0 ; i < m ; i++){
			int a;
			cin >> a;
			l = max(l,a);
			item.push_back(a);
		}
		while(l!=r){
			int M = (l+r) / 2;
			if( test(M) ){
				r = M;
			}else{
				l = M+1;
			}
		}
		cout << r << endl;
	}
}

C++: #include <bits/stdc++.h>
using namespace std ;

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int m, n;
bool check(vector<int> v,int mid){
  int h = 1;
  int w = 0;
  rep(i,n){
    if(v[i] > mid){
      return false;
    }
    if(w + v[i] <= mid){
      w += v[i];
    }
    else{
      w = v[i];
      ++h;
    }
  }
  if(h > m){
    return false;
  }
  return true;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  while(cin >> m >> n&&m&&n){
    vary(int,v,n,0);
    rep(i,n){
      cin >> v[i];
    }
    int lb = 0,ub = 1500000;
    while(1){
      int mid = (lb+ub)/2;
      if(mid == lb) break;
      if(check(v,mid)){
        ub = mid;
      }
      else{
        lb = mid;
      }
    }
    cout << ub << endl;
  }
  return 0;
}

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

using namespace std;

int main(){
	int R,L;
	int n,m;
	int hon[100];
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0&&m==0){
			break;
		}
		R=L=0;
		for(int i=0;i<m;i++){
			scanf("%d",&hon[i]);
			L+=hon[i];
		}
		if(n>=m){
			printf("%d\n",*max_element(hon,hon+n));
			continue;
		}
		//3 9 5 3 8 2 1 6 9 7 4
		while(1){
			if(R==L){
				break;
			}
			double H=(double)(R+L)/2;
			
			int dan=0;
			int at=0;
			for(int i=0;i<m;i++){
				if(at+hon[i] <= H){
					at+=hon[i];
				}else{
					at=0;
					dan++;
					at+=hon[i];
				}
			}
			
			if(dan<n){
				L=H;
			}else{
				R=H+0.5;
			}
			
				printf("%d %d\n",R,L);
		}
	}
}

C++: #include <iostream>

using namespace std;

typedef unsigned long long ull;
int n, m;
ull books[100];

bool solve(int width)
{
	ull w = 0;
	int h = 1;

	for(int i=0; i<n; i++)
	{
		if(w > width) return false;
		if(w + books[i] > width)
		{
			h++;
			w = 0;
		}
		w += books[i];
	}

	return h <= m;
}

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

		for(int i=0; i<n; i++)
		{
			scanf("%llu", &books[i]);
		}

		ull upper = 1500000;
		ull lower = 0;
		
		while(upper - lower > 1)
		{
			ull mid = (upper + lower) / 2;
			if(solve(mid)) upper = mid;
			else  lower = mid;
		}

		printf("%llu\n", solve(lower) ? lower : upper);
	}
}