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 main(){
	while(true){
		int m,n,book[101]={},sum[101]={};
		cin >> m >> n;
		if(m==0) break;
		for(int i=1;i<=n;i++){
			cin >> book[i];
			sum[i]=sum[i-1]+book[i];
		}
		int d=0;
		int u=1500000;
		int md;
		while(d+1<u){
//			cout << u << " " << d << endl;
			bool ok=false;
			int j=0,until=0;
			md=(d+u)/2;
			for(int i=0;i<m;i++){
				while(sum[j]-sum[until]<=md){
					j++;
					if(j==n+1){
						ok=true;
						break;
					}
				}
				if(ok) break;
				until=j-1;
			}
			if(ok){
				u=md;
				if(d+1>=u){
					cout << u << endl;
					break;
				}
			}
			else{
				d=md;
				if(d+1>=u){
					cout << u << endl;
					break;
				}
			}
		}
	}
	return 0;
}

C++: #include<cstdio>
#include<algorithm>
#include<numeric>
using namespace std;

int m,n,a[110],lim;

int check(int b){
  int cnt = 1, rem = b;
  for(int i=0;i<n;i++){
    if(rem<a[i]){
      cnt++; rem = b - a[i];
    }else rem -= a[i];
  }
  return cnt;
}

int main(){
  while(scanf("%d%d",&m,&n),m){
    for(int i=0;i<n;i++)scanf("%d",a+i);
    
    int l = *max_element(a,a+n)-1, r = accumulate(a,a+n,0);
    while(r-l>1){
      int mid = (l+r)/2;
      if(check(mid)<=m)r = mid;
      else l = mid;
    }
    printf("%d\n",r);
  }
}

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

using namespace std;

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

int calc_m (int curr_w )
{
	int cm = 0;
	int j = 0;
	while (j < n ){
		int cw = 0;
		while (cw + w[j] <= curr_w && j < n ){
			cw += w[j];
			j++;
		} // end while
		cm++;
	} // end if

	return cm;
}

int main()
{
	const int MaxW = 1500000;

	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;
		while (l <= r ){
			mid = (l+r)/2;
			int curr_m = calc_m (mid );
			if (curr_m > m ){
				l = mid+1;
			}else{
				r = mid-1;		
			} // end if
		} // end while
		cout << mid << endl;
	} // end loop
		
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#define rep1(i,n) for(int i=1;i<=n;i++)
using namespace std;
int main(){
	int m,n;
	int M[101][21],S[101],P[101]={0};
	while(cin>>m>>n,m){
		rep1(i,n)cin>>S[i],P[i]=P[i-1]+S[i];
		rep1(i,n)rep1(j,m)if(i!=1&&j!=1){
			int t,mi,mn=1<<30;
			rep1(x,i-1){
				t=max(M[x][j-1],P[i]-P[x]);
				if(mn>t)mn=t,mi=x;
			}
			M[i][j]=mn;
		}else M[i][j]=(i-1?P[i]:S[1]);
		cout<<M[n][m]<<endl;
	}
	return 0;
}

C++: 
#include<iostream>
#include<vector>
using namespace std;
int main()
{
  int m,n;
  int low,high,medi;
  int column,breadth;
  int i;
  bool f;
  while(cin>>m>>n,m,n){
    vector<int>v(n);
    for(i=low=0;i<n;i++){cin>>v[i];low+=v[i];}
    low/=m;
    high=1500000;

    while(high-low>1){
      medi=(low+high)/2;
      breadth=column=f=0;
      for(i=0;i<n;i++){
	if(medi<v[i]){f=1;break;}
	if(breadth+v[i]<=medi){
	  breadth+=v[i];
	}else{
	  breadth=v[i];
	  column++;
	  if(column==m){f=1;break;}
	}
      }
      if(f)low=medi;
      else high=medi;
    }
    cout<<high<<endl;
  }
}

C++: #include<iostream>

using namespace std;
int m, n, w[100];

int calc(int t){
    int sum=0, ret=1;
    bool f=false;
    for(int i=0; i<n; i++){
        if(sum+w[i]>t){
            sum=0;
            ret++;
            f=true;
        }
        sum+=w[i];
    }
    if(f==false) return 1500001;
    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<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int m,n;
vector<int>v;

bool C(int x){

  int cnt=0,sum=0;
  for(int i=0;i<n;i++){
    if(sum+v[i]>x)cnt++,sum=v[i];
    else sum+=v[i];
  }
  return m==cnt+1;
}

int main(void){

  while(cin >> m >> n,m|n){
    v.clear();
    m=min(m,n);
    int l=0,r=0,a;
    for(int i=0;i<n;i++){
      cin >> a;
      r+=a;
      v.push_back(a);
    }
    
    int mid=(l+r)/2+1;
    while(r-l>1){
      if(C(mid))r=mid;
      else l=mid;
      mid=(l+r)/2;
    }
    cout << r << endl;
  }

  return 0;
}

C++: #include<iostream>

using namespace std;


int main(){
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0){
			break;
		}
		int hon[100];
		for(int i=0;i<m;i++){
			cin>>hon[i];
		}
		
		int reft=0;
		int right=0;
		for(int i=0;i<m;i++){
			right+=hon[i];
		}
		
		while(1){
			double h = (double)(reft+right)/2;
			
			int now=0;
			int cont=1;
			for(int i=0;i<m;i++){
				if(cont>n){
					break;
				}
				if(now+hon[i]>h){
					now=0;
					cont++;
					i--;
					continue;
				}
				now+=hon[i];
			}
			
			if(cont>n){
				reft=h;
			}else{
				right=h+0.5;
			}
			
			if(reft+1==right){
				break;
			}
		}
		printf("%d\n",right);
	}
}

C++: #include <cstdio>
#include <algorithm>
using namespace std;

#define INF (1<<28)
#define MAX_N 100

int m, n;
int book[MAX_N];

int len(int from, int to) { // [from, to)
    int l = 0;
    for (int i = from; i < to; i++) {
        l += book[i];
    }
    return l;
}

int solve(int index, int rem, int max_len) {
    if (rem == 1) return max(max_len, len(index, n));
    if (index == n) return max_len;
    int min_len = INF;
    for (int i = index+1; i <= n; i++) {
        min_len = min(min_len, solve(i, rem-1, max(max_len, len(index, i))));
    }
    return min_len;
}

int main() {
    while (scanf("%d %d", &m, &n), m || n) {
        for (int i = 0; i < n; i++) scanf("%d", &book[i]);
        printf("%d\n", solve(0, m, 0));
    }
    return 0;
}

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

using namespace std;

int main() {
	int m, n;
	while (cin >> m >> n) {
		if (m == 0 && n == 0) {
			break;
		}
		vector<int> d(n);
		for (int i = 0; i < n; i++) {
			cin >> d[i];
		}
		int lb = 0;
		int rb = 1500000;
		while (rb-lb > 1) {
			int mid = (lb+rb)/2;
			int mm = 1;
			int c = 0;
			bool h = true;
			for (int i = 0; i < n; i++) {
				if (d[i] > mid) {
					h = false;
					break;
				}
				c += d[i];
				if(c > mid) {
					mm++;
					c = 0;
					i--;
				}
			}
			if (mm > m) {
				h = false;
			}
			if (h) {
				rb = mid;
			} else {
				lb = mid;
			}
		}
		cout << rb << endl;
	}
	return 0;
}