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 w[100];

bool check(int mid){
    int tmpm = 1, nowp = 0;
    for(int i = 0; i < n; i++){
        if(mid < w[i])  return false;

        if(nowp + w[i] <= mid){
            nowp += w[i];
        }else{
            nowp = w[i];
            tmpm++;
        }
    }
    return tmpm <= m;
}

int main(){
    while(1){
        cin >> m >> n;

        if(m + n == 0)  break;

        int minp = 1000001;
        for(int i = 0; i < n; i++){
            cin >> w[i];
            minp = min(minp, w[i]); 
        }

        int l = minp, r = 1500000;

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

        cout << (check(l) ? l : r) << endl;
    }

    return 0;
}

C++: #include<iostream>
using namespace std;
int m, n;
int a[1000];
bool check(int v) {
	int cnt = 0, s = 1000000000;
	for (int i = 0; i < n; i++) {
		if (a[i] > v)return false;
	}
	for (int i = 0; i < n; i++) {
		if (s + a[i] > v) {
			cnt++;
			s = a[i];
		}
		else {
			s += a[i];
		}
	}
	if (cnt > m)return false;
	return true;
}
int main() {
	while (true) {
		cin >> m >> n;
		if (m == 0 && n == 0) { break; }
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		int L = 0, R = 100000000, M;
		for (int i = 0; i < 50; i++) {
			M = (L + R) / 2;
			bool r1 = check(M - 1);
			bool r2 = check(M);
			if (r1 == true)R = M;
			if (r2 == false) { L = M; }
		}
		cout << M << endl;
	}
	return 0;
}

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

const int WIDTH_LIMIT = 1500000;

int main()
{
	int m, n;
	while( cin >> m >> n && ( m || n ) ){
		int book[ 100 ] = {0};
		int acum = 0;
		int sum[ 100 ] = {0};
		for( int i = 0; i < n; ++i ){
			int t;
			cin >> t;
			book[ i ] = t;
			acum += t;
			if( acum > WIDTH_LIMIT ){
				acum = WIDTH_LIMIT + 1;
			}
			sum[ i ] = acum;
		}
		int ans = 0x7fffffff;
		for( int i = 0; i < n; ++ i ){
			if( sum[ i ] > WIDTH_LIMIT ) continue;
			int shelf[ 20 ] = {0};
			int ib = i + 1;
			int is = 1;
			while( ib < n && is < m ){
				int w = shelf[ is ] + book[ ib ];
				if( w <= sum[ i ] ){
					++ib;
					shelf[ is ] = w;
				}else{
					++is;
				}
			}
			if( ib == n && ans > sum[ i ] ){
				ans = sum[ i ];
			}
		}
		cout << ans << endl;
	}

	return 0;
}

C++: #include <stdio.h>
#include <vector>
#include <algorithm>

#define MAX_SIZE 1500000

using namespace std;

int main(){
	int dansu,kansu,shelf[20],book[100],min_size,left,right,m,dansu_index;

	while(true){
		scanf("%d %d",&dansu,&kansu);
		if(dansu == 0 && kansu == 0)break;

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

		min_size = MAX_SIZE;
		left = 0,right = MAX_SIZE;
		m = (left+right)/2;

		while(left < right){

			for(int i = 0; i < dansu; i++)shelf[i] = m;
			dansu_index = 0;
			for(int i = 0; i < kansu && dansu_index < dansu;){
				if(shelf[dansu_index] >= book[i]){
					shelf[dansu_index] -= book[i];
					i++;
				}else{
					dansu_index++;
				}
			}

			if(dansu_index == dansu){
				left = m + 1;
				m = (left + right)/2;
			}else{
				min_size = min(min_size,m);
				right = right - 1;
				m = (left + right)/2;
			}
		}

		printf("%d\n",min_size);

	}

    return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
int m,n,book[100];
bool ok(int x){
  int h=0,d=1;
  for(int i=0;i<n;i++){
    h += book[i];
    if(h>x){
      d++;
      if(d>m) return false;
      h = 0;
      h += book[i];
    }
  }
  return true;
}
int main(){
  while(cin>>m>>n){
    int max=1500000,min=0,s;
    if(m==0&&n==0) break;
    for(int i=0;i<n;i++) cin >> book[i];
    if(m>=n){
      sort(book,book+n,greater<int>());
      cout << book[0] << endl;
      }
    else{
      while(1){
	s = (max + min) / 2;
	if(ok(s)) max = s;
	else if(!ok(s)) min = s;
	if(min+1==max){
	  cout << max << endl;
	  break;
	}
      }
    }
  }
  return 0;
}

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

template<typename T>
T in(){T tmp; cin >> tmp; return tmp;}

int n, m;
int book[100];

int search(int low, int high);

int main()
{

    while (scanf("%d %d", &m, &n), m){
        int sum = 0;
        int maxi = 0;

        for (int i = 0; i < n; i++){
            scanf("%d", book + i);
            sum += book[i];
            maxi = max(maxi, book[i]);
        }
        printf("%d\n", search(maxi, min(1500000, sum)));
    }

    return 0;
}

int search(int low, int high)
{
    int mini, maxi;

    mini = low, maxi = high;
    while (mini < maxi){
        int sum;
        int now = 1;
        int middle = (mini + maxi) / 2;
        bool flag = true;

        sum = 0;
        for (int i = 0; i < n; i++){
            if (sum + book[i] > middle){
                now++;
                if (now > m){
                    mini = middle + 1;
                    flag = false;
                    break;
                }
                sum = book[i];
            }
            else {
                sum += book[i];
            }
        }
        if (flag){
            maxi = middle;
        }
    }

    return mini;
}

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,i=0;
  while(i<n && cnt<m){
    if(sum+v[i]<=x)sum+=v[i],i++;
    else sum=0,cnt++;
  }
  return m>cnt;
}

int main(void){

  while(cin >> m >> n,m|n){
    v.clear();

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

  return 0;
}