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 a,b,ans;
  while(cin>>a>>b){
    if(a==0&&b==0) break;
    int book[b],hei=0;
    for(int i=0;i<b;i++) cin >> book[i];
    if(a>=b){
      sort(book,book+b,greater<int>());
      cout << book[0] << endl;
    }
    else{
      for(int i=0;i<b;i++) hei += book[i];
      hei /= a;
      //cout << hei << endl;
      for(int i=hei;i<1500000;i++){
	int h[a],count=0;
	for(int j=0;j<a;j++) h[j] = 0;
	for(int j=0;j<b;j++){
	  if(h[count]+book[j]>i){
	    count++;
	    if(count>=a) break;
	    h[count] += book[j]; 
	  }
	  else if(j==b-1){
	    ans = i;
	    goto END;
	  }
	  else h[count] += book[j];
	}
      }
    END:
      cout << ans << endl;
    }
  }
  return 0;
}

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

int m,n;
int books[110];
int solves();
int search(int a);

int main(){
	while(1){
		cin >> m >> n;
		if(m == 0 && n == 0) break;
		for(int i=0;i<n;i++){
			cin >> books[i];
		}
		int ans = solves();
		cout << ans << endl;
	}
}

int solves(){
	int ub = 0,lb = 2000000, mid;
	for(int i=0;i<100;i++){
		mid = (ub + lb) / 2;
		if(search(mid)) lb = mid;
		else ub = mid;
		cout << ub << " " << lb << endl;
	}
	return lb;
}

int search(int a){
	int len = a;
	int cou = 0;
	for(int i=0;i<n;i++){
		while(1){
			if(0 > len-books[i]){
				cou++;
				len = a;
			}
			else break;
			if(cou == m) return 0;
		}
		len -= books[i];
	}
	return 1;
}

C++: // AOJ 0181
#include <iostream>

const int kMaxWidth = 1500000;
const int kMaxBooks = 100;

int thickness[kMaxBooks];
int m, n;

bool canPlace(int width) {
	int k = 0;
	int filled = 0;
	for (int i = 0; i < n; i++) {
		if (thickness[i] > width) return false;
		if (filled + thickness[i] > width) {
			if (++k >= m) return false;
			filled = 0;
		}
		filled += thickness[i];
	}
	return true;
}

int solve() {
	int left = 0, right = kMaxWidth;
	while (right - left > 1) {
		int mid = (left + right) / 2;
		if (canPlace(mid)) right = mid;
		else left = mid;
	}
	return right;
}

int main() {
	while (1) {
		std::cin >> m >> n;
		if (m == 0) break;
		for (int i = 0; i < n; i++)
			std::cin >> thickness[i];
		std::cout << solve() << std::endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <climits>
#include <queue>
#include <cstring>
using namespace std;
#define INF (1<<21)
#define rep(i,n) for(int i=0;i<n;i++)	
int solve(int &m,int &n,vector<int> &book){
	int ret = INF;
	int dp[n][n];	
	memset(dp,0,n*n*4);
	rep(i,n){
		for(int j=i;j<n;j++){
			if(i == j)dp[i][j] = book[j];
			else dp[i][j] = dp[i][j-1] + book[j];
		}
	}
	rep(x,n)rep(y,n){
		rep(i,n){
			int width = dp[x][y];
			int cur = i,p,sum = 0;
			
			if(dp[0][i] > width)continue;
			
			bool flag;
			//cout << "[" << width << "]" << endl;
			int count = 0;
			do{
				flag = true;
				p = cur+1;
				while( cur+1 < book.size() && dp[p][cur+1] <= width){
					cur++; flag = false;
				}
				count++;
			}while(!flag);

			if(cur == book.size()-1 && count <= m)
				ret = min(ret,width);
		}
	}
	return ret;
}
int main(){
	int n,m;
	while(cin >> m >> n,n){
		vector<int> book(n);
		rep(i,n)cin >> book[i];
		cout << solve(m,n,book) << endl;
	}
}

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

int main() {
  int M, N;
  while(cin >> M >> N && M) {
    vector<int> books(N);
    for(int i=0; i<N; i++) {
      cin >> books[i];
    }
    
    int l = 0, r = 1500001;
    while(r - l > 1) {
      int m = (l+r)/2;
      int bpos = 0;
      for(int i=0; i<M; i++) {
	int size = m;
	for(;;) {
	  if(bpos == N) break;
	  if(size - books[bpos] < 0) break;
	  size -= books[bpos++];
	}
	if(bpos == N) break;
      }
      if(bpos == N) {
	r = m;
      } else l = m+1;
    }
    
    cout << l << endl;
  }
  
  return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

const int INF=1e9;
int n, m;
vi d(110);

bool ok(int mid) {
	int cnt = 1, now = 0;
	rep(i, 0, n) {
		if (now + d[i] <= mid) {
			now += d[i];
		}
		else if (d[i] <= mid) {
			now = d[i];
			cnt++;
		}
		else {
			return false;
		}
	}
	//cout << mid << " " << (cnt <= m ? "ok" : "ng") << cnt << m << endl;
	return cnt <= m;
}

signed main() {
	while (1) {
		cin >> m >> n;
		if (n + m == 0) break;
		d.clear();
		rep(i, 0, n) {
			cin >> d[i];
		}
		int l = 1, r = 1500000;
		rep(i, 0, 100) {
			int mid = (l + r) / 2;
			if (ok(mid)) r = mid;
			else l = mid;
		}
		cout << r << endl;
	}
}

C++: #include <iostream>
#include<cstdio>
#include <cstring>	// require memset
#include <fstream>	// require freopen

using namespace std;

const int MaxW = 1500000;
int m, n;	// {IÌi 1  m  20, {Ìª 1  n  100
int w[100];

bool calc_m (int curr_w )
{
	int l[20];
	memset (l, 0, sizeof (l ) );

	int j = 0;
	for (int i = 0; i < n; i++ ){
		if (l[j] + w[i] > curr_w )
			j++;
		if (j == m )
			return false;
		l[j] += w[i];
	} // end for

	return true;
}

int main()
{
//	cut here before submit 
//	freopen ("testcase.persistence", "r", stdin );

	for (;; ){// {IÌ ans  1500000
		scanf ("%d%d", &m, &n ); if (!m ) break;
		memset (w, 0, sizeof (w ) );

		for (int i = 0; i < n; i++ ){
			scanf ("%d", w+i );
		} // end for
		int l = w[0];
		int r = MaxW;
		int mid = 0;
		int res = MaxW;
		while (l <= r ){
			mid = (l+r)/2;
			if (calc_m (mid ) ){
				res = min (res, mid );
				r = mid-1;		
			}else{
				l = mid+1;
			} // end if
		} // end while
		cout << res << endl;
	} // end loop
		
	return 0;
}

C++: #include<iostream>
#include<stdio.h>

using namespace std;
int m, n, t[101];

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

int main(){

    while(1){
        cin>> m>> n;
        if(m==0&&n==0) break;
        for(int i=0; i<n; i++){
            scanf("%d", &t[i]);
        }

        int l=1, r=1500000;
        while(r-l>1){
            int md=(l+r)/2;
            if(cnt(md)>m){// exceeded
                l=md;
            }else{
                r=md;
            }
        }
        cout<< r<< endl;
    }

    return 0;
}