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;

typedef unsigned long long ull;

int m, n;
float avg;
ull books[100];

bool judge(int i, ull width)
{
	ull w = 0;
	int h = 2;
	for(int k=i+1; k<n; k++)
	{
		w += books[k];
		if(w > width)
		{
			w = books[k];
			h++;
		}

		if(h > m) return false;
	}

	return true;
}

ull solve()
{
	ull width = 0;
	for(int i=0; i<n; i++)
	{
		width += books[i];
		if(width >= avg)
		{
			if(judge(i, width)) return width;
		}
	}

	return -1;
}

int main()
{
	while( 1 )
	{
		cin >> m >> n;
		if(m==0 && n==0) break;
		
		avg = 0.0f;
		for(int i=0; i<n; i++)
		{
			scanf("%llu", &books[i]);
			avg += books[i];
		}
		avg /= (float)n;

		ull ans = solve();
		printf("%llu\n", ans);
	}
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,n) FOR(i,0,n)

int main() {
	int n, m;
	while (cin >> m >> n, n || m) {
		int v[100];
		REP(i, n) scanf("%d", &v[i]);
		
		int ans = 1;
		REP(i, n) ans = max(ans, v[i]);
		
		while (true) {
			int cnt = 0, pos = 0;
			while (pos < n) {
				cnt++;
				int now = v[pos++];
				while (pos < n && now + v[pos] <= ans) now += v[pos++];
			}
			
			if (cnt <= m) {
				cout << ans << endl;
				break;
			}
			
			ans++;
		}
	}
	
	return 0;
}

C++: #include<cstdio>

#define	rep(i,n)	for(int i=0;i<(n);i++)

using namespace std;

int m,n,book[100];

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

int main(){
	while(scanf("%d%d",&m,&n),m){
		rep(i,n)	scanf("%d",book+i);

		int lo=0,hi=1500000;
		while(lo<hi){
			int mi=(lo+hi)/2;
			if(check(mi))	hi=mi;
			else			lo=mi+1;
		}

		printf("%d\n",lo);
	}

	return 0;
}

C++: #include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  int m,n,w[101],l,r,mid,cnt,dan,ans;
  while(scanf("%d %d",&m,&n),m!=0||n!=0){
    l = 0;
    r = 0;
    for(int i=0;i<n;i++){
      scanf("%d",&w[i]);
      l = max(l,w[i]);
      r += w[i];
    }
    ans = r;
    while(l <= r){
      mid = (l+r)/2;
      cnt = 0;
      dan = 1;
      for(int i=0;i<n;i++){
	if(cnt+w[i] > mid){
	  cnt = 0;
	  dan++;
	}
	cnt += w[i];
      }
      
      if(dan <= m){
	ans = mid;
	r = mid-1;
      }
      else{
	l = mid+1;
      }
      
    }
    printf("%d\n",ans);
  }
  return(0);
}

C++: #include<iostream>
using namespace std;
int n, m;
int a[101];
bool search(int v);
int main()
{	
	cin >> m >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	int l, r;
	l = 0; r = 1 << 15;
	for (int i = 0; i < 100; i++){
		int mi = (l + r) / 2;
		if (search(mi))r = mi;
		else l = mi;
	}
	cout << r << endl;
}
bool search(int v){
	int n2=0, m2=0,b=0;
	while (n2 < n&&m2 < m){
		if (b + a[n2] <= v){
			b += a[n2];
			n2++;
		}
		else{
			b = 0;
			m2++;
		}
	}
	if (n2 == n&&m2 < m)return true;
	return false;
}

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

int n, m, max_a;
int a[100];

bool check(int k) {
	int num = 1, sum = 0;
	for(int i = 0; i < n; i++) {
		sum += a[i];
		if(sum > k) {
			num++;
			sum = a[i];
		}
	}
	return num <= m;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	while(cin >> m >> n, m) {
		for(int i = 0; i < n; i++) {
			cin >> a[i];
		}
		max_a = *max_element(a, a + n);

		int ng = max_a - 1, ok = max_a * n;
		while(abs(ng - ok) > 1) {
			int mid = (ng + ok) / 2;
			if(check(mid)) ok = mid;
			else ng = mid;
		}

		cout << ok << endl;
	}
}

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

using namespace std;

int calc_m (vector <int> w, int curr_w )
{
	int n = w.size();
	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;
	int m, n;	// {IÌi 1  m  20, {Ìª 1  n  100

	while (cin >> m >> n && m && n ){
		vector <int> w (n, 0 );	// {Ì 1  w[i]  1000000
		int res = 0;				// {IÌ ans  1500000
		for (int i = 0; i < n; i++ ){
			cin >> 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 (w, mid );
			if (curr_m > m ){
				l = mid+1;
			}else{
				r = mid-1;		
			} // end if
		} // end while
		cout << mid << endl;
	} // end loop
		
	return 0;
}