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 <set>
using namespace std;

const int WIDTH_LIMIT = 1500000;

int main()
{
	int m, n;
	while( cin >> m >> n && ( m || n ) ){
		int memo[ 100 ][ 100 ] = {0};
		set< int > width;
		for( int i = 0; i < n; ++i ){
			cin >> memo[ i ][ i ];
			width.insert( memo[ i ][ i ] );
		}
		for( int i = 0; i < n - 1; ++i ){
			for( int j = i + 1; j < n; ++j ){
				memo[ i ][ j ] = memo[ i ][ j - 1 ] + memo[ j ][ j ];
				width.insert( memo[ i ][ j ] );
			}
		}
		set< int >::iterator itr = width.begin();
		while( itr != width.end() ){
			int w = *itr;
			int b = 0;
			int s = 0;
			while( b < n && s < m ){
				int p = b;
				while( p < n && memo[ b ][ p ] <= w ){
					++p;
				}
				--p;
				if( b > p ){
					break;
				}
				++s;
				b = p + 1;
			}
			if( b == n ){
				cout << w << endl;
				break;
			}
			++itr;
		}
	}

	return 0;
}

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 n, m;
int v[100];

bool check(int x) {
	int cnt = 0, pos = 0;
	while (pos < n) {
		cnt++;
		int now = v[pos++];
		while (pos < n && now + v[pos] <= x) now += v[pos++];
	}
	
	return cnt <= m;
}

int main() {
	while (cin >> m >> n, n || m) {
		REP(i, n) scanf("%d", &v[i]);
		
		int r = 15000000, l = -1;
		
		while (r - l > 1) {
			int mid = (r + l) / 2;
			if (check(mid)) r = mid;
			else l = mid;
		}
		
		cout << r << 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;
		int i;

		while(left < right){

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

			if(i < kansu){
				left = m + 1;
				m = (left + right)/2;
			}else{
				right = right - 1;
				m = (left + right)/2;
			}
		}

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

	}

    return 0;
}

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

using namespace std;

#define rep(i,n) for(int i=0;i<int(n);i++)
#define reps(i,n) for(int i=1;i<=int(n);i++)
#define sint(i) scanf("%d",&i);
#define sintt(i,j) scanf("%d%d",&i,&j);
#define sinttt(i,j,k) scanf("%d%d%d",&i,&j,&k);

#define INF 1010000000
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int main(){
	while(1){
		int n,m;
		sintt(m,n);
		if(n==0)break;
		int hon[101];
		rep(i,n){
			sint(hon[i]);
		}
		
		int left=0;
		int right=1000000;
		
		while(1){
			double harf=(right+left)/2.0;
			
			int flg=0;
			
			int now=0;
			int cont=0;
			rep(i,n){
				if(now+hon[i]<=harf){
					now+=hon[i];
				}else{
					now=0;
					i--;
					cont++;
				}
				if(cont>=m){
					break;
				}
			}
			
			if(cont>=m){
				flg=1;
			}
			
			if(flg==1){
				left=harf+0.5;
			}else{
				right=harf;
			}
			
			if(left==right){
				printf("%d\n",left);
				break;
			}
		}
	}
}

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

long long int a[150];
int n, m;

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

int nibun(int s, int e, int m){
	if(!(i_can((s+e)/2,m))){
		return nibun((s + e) / 2 + 1, e, m);
	}
	else if (s >= e) return s;
	else return nibun(s, (s + e) / 2, m);
}

int main(){
	while(cin >> m >> n){
		if (!n && !m) break;
		a[0] = 0;
		for(int i = 1;i<=n;i++){
			cin >> a[i];
		}
		cout << nibun(0, 1500001, m) << endl;
	}
	return 0;
}

C++: #include<iostream>
using namespace std;
#include<iostream>
#include<cstdlib>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define fir first
#define sec second

const int M = 21;
const int inf = 1500000*2;
const int N = 101;
int dp[N][M];
int cost[N][N];
void pre(int n,int *in){
  rep(i,n){
    cost[i][i]=in[i];
    REP(j,i+1,n)cost[i][j]=cost[i][j-1]+in[j];
  }
}

int solve(int n,int m){
  rep(i,n+1)rep(j,m+1)dp[i][j]=inf;
  //dp[0][0]=0;
  REP(i,1,n+1){
    REP(j,1,m+1){
      rep(k,i){
	if (k==0)dp[i][j]=min(dp[i][j],cost[k][i-1]              );
	else     dp[i][j]=min(dp[i][j],max(dp[k][j-1],cost[k][i-1]));
      }
    }
  }
  return dp[n][m];
}

main(){
  int n,m;
  int in[N];
  while(cin>>m>>n && n){
    rep(i,n)cin>>in[i];
    pre(n,in);
    cout << solve(n,m) << 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[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){
				printf("%d\n",R);
				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;
			}
			
		}
	}
}

C++: #include <iostream>

using namespace std;

int m, n;

int books[100];

bool Check(int breadth){
  int stage = 0;
  int remaining = breadth;
  for(int i=0; i<n; i++){
	if(remaining - books[i] < 0){
	  stage++;
	  remaining = breadth;
	  if(stage >= m){
		return false;
	  }
	}
	remaining -= books[i];
  }
  return true;
}

void Solve(int max_book){
  int ng = max_book;
  int ok = 1500000;
  while(ok - ng > 1){
	int mid = (ng + ok)/2;
	if(Check(mid)){
	  ok = mid;
	}else{
	  ng = mid;
	}
  }
  cout << ok << endl;
}

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

  while(1){
	cin >> m >> n;
	if(m == 0){
	  return 0;
	}
	int max_book = -1;
	for(int i=0; i<n; i++){
	  cin >> books[i];
	  if(books[i] > max_book){
		max_book = books[i];
	  }
	}
	Solve(max_book);
  }
  
  
  return 0;
}