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 <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main(void)
{
	int M,N;

	while(cin >> M >> N){
		priority_queue<int, vector<int>, greater<int> > pq;

		for(int i = 0; i < M; i++)
			pq.push(0);		//本棚初期

		int book;
		while(N > 0){
			cin >> book;

			int pqt = pq.top();	pq.pop();

			pqt += book;
			pq.push(pqt);
			N--;
		}
		while(pq.size()-1 > 0)
			pq.pop();

		cout << pq.top() << endl;
		pq.pop();
	}

	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,i=0;
  while(i<n){
    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;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int a[110],n,m;
bool Cando(int lim){
  int cnt=0,cls=0;
  for(int i=0;i<n;i++){
    if(a[i]>lim)return false;
    if(cls+a[i]>lim){
      cls=a[i];
      cnt++;
    }
    else cls+=a[i];
  }
  if(cnt<m)return true;
  return false;
}
int main(){
 while(cin>>m>>n&&n+m){
   for(int i=0;i<n;i++)cin>>a[i];
   int left=0,right=100000000,mid;
   while(left<right-1){
     mid=(left+right)/2;
     if(Cando(mid)==false)left=mid;
     else right=mid;
   }
   cout<<right<<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<1000;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++: //21
#include<iostream>
#include<algorithm>
#include<numeric>

using namespace std;

int m,n;
int w[100];
int memo[21][100];

int mw(int rm,int f){
  if(rm==1){
    return accumulate(w+f,w+n,0);
  }else if(memo[rm][f]!=-1){
    return memo[rm][f];
  }else{
    int mnw=1<<30;
    for(int i=f;i<n;i++){
      mnw=min(mnw,max(accumulate(w+f,w+i,0),mw(rm-1,i)));
    }
    memo[rm][f]=mnw;
    return mnw;
  }
}

int main(){
  while(cin>>m>>n,m|n){
    fill(memo[0],memo[21],-1);
    for(int i=0;i<n;i++){
      cin>>w[i];
    }
    cout<<mw(m,0)<<endl;
  }
  return 0;
}

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

#define NMAX 100
#define KMAX 100
static const int INFTY = (1<<21);

// n >= k
int compute( int n, int k, int S[NMAX+1] ){
    
    int M[NMAX+1][KMAX+1], D[NMAX+1][KMAX+1];
    int P[NMAX+1];
    
    P[0] = 0;
    for ( int i = 1; i <= n; i++ ) P[i] = P[i-1] + S[i];
    
    for ( int i = 1; i <= n; i++ ) M[i][1] = P[i];
    for ( int j = 1; j <= k; j++ ) M[1][j] = S[1];
    
    for ( int i = 2; i <= n; i++ ){
	for ( int j = 2; j <= k; j++ ){
	    M[i][j] = INFTY;
	    for ( int x = 1; x <= i-1; x++ ){
		int maximum = max( M[x][j-1], P[i] - P[x] );
		if ( M[i][j] > maximum ){
		    M[i][j] = maximum;
		    D[i][j] = x;
		}
	    }
	}
    }

    return M[n][k];
}

int main(){
    int n, k, S[NMAX+1];
    while(1){
	cin >> k >> n;
	if ( k == 0 && n == 0 ) break;
	for ( int i = 1; i <= n; i++ ) cin >> S[i];
	cout << compute(n, k, S) << endl;
    }
    return 0;
}

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

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

using namespace std;

int main(){
	
	while(1){
		int n,m;
		int hon[100];
		sintt(n,m);
		if(n==0)break;
		rep(i,m){
			sint(hon[i]);
		}
		
		
		int left=0;
		int right=0;
		
		rep(i,m){
			right+=hon[i];
		}
		
		while(1){
			double harf= (double)(right+left)/2;
			//printf("%d %lf %d\n",left,harf,right);
			
			if(right==left){
				break;
			}
			
			int flg=0;
			int sum=0;
			int dan=0;
			for(int i=0;i<m;i++){
				
				if(dan>n){
					break;
				}
				
				if(sum+hon[i]>harf){
					sum=0;
					i--;
					dan++;
					continue;
				}else{
					sum+=hon[i];
				}
			}
			
			if(dan<n){
				flg=1;
			}
			
			if(flg==1){
				right=harf;
			}else{
				left=(int)((double)harf+0.5);
			}
		}
		printf("%d\n",right);
	}
}
/*
3 9
500
300
800
200
100
600
900
700
401

*/