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;
#define rep(i,n) for(int i = 0 ; i < n ; i++ )
#define INF ( 1 << 30 )
int book[100],dp[20][100],m,n;
int solve(int index,int dan,int maxsize,int nowsize){
  if(index == n) return maxsize;
  if(dp[dan][index] < maxsize) return dp[dan][index];
  int res = INF;
  res = min( res, solve( index+1, dan, max(maxsize, nowsize + book[index]),nowsize+book[index]));
  if(dan+1 != m)
    res = min( res, solve( index+1, dan+1, max(maxsize,nowsize + book[index]), 0));
  return dp[dan][index] = res;
}
int main(){
  while(cin >> m >> n , m){
    fill_n(dp[0],20*100,INF);
    rep(i,n) cin >> book[i];
    cout << solve(0,0,0,0) << endl;
  }
}

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 = 1500000, 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<iostream>
using namespace std;
int t[100];
int m,n,L,R,M;


bool check(int x){
  int cnt=0,cnt2=0,sum=0;
  
  while(cnt<n&&cnt2<m){
    if(sum+t[cnt]>x){
      sum=0;
      cnt2++;
    }else{
      sum+=t[cnt];
      cnt++;
    }
  }
  
  if(cnt==n)return true;
  else return false;
}

int main(){
  while(cin>>m>>n){
    if(m==0&&n==0)break;
    R=0;
    for(int i=0;i<n;i++){
      cin>>t[i];
      R+=t[i];
    }

    L=0;
    M=(L+R)/2;

    while(L<R){
      if(check(M)){
	R=M-1;
	M=(L+R)/2;
      }else{
	L=M+1;
	M=(L+R)/2;
      }
    }
    cout<<R+1<<endl;
  }
  return 0;
}

C++: #include <iostream>

using namespace std;

int main(){
	while(true){
		int n, m;
		cin >> m >> n;
		if(n == 0 && m == 0){ break; }
		int iw[100];
		cin >> iw[0];
		for(int i = 1; i < n; i++){
			cin >> iw[i];
			iw[i] += iw[i - 1];
		}
		int left = 0, right = 1500000, answer = 0;
		while(left < right){
			int center = (left + right) / 2;
			bool flag = false;
			for(int i = 0, f = 0, p = 0; i < m; i++){
				for(; f < n; f++){
					if(iw[f] - p > center){ break; }
				}
				if(f == n){ flag = true; break; }
				if(f == 0 || iw[f] == p){ break; }
				p = iw[f - 1];
			}
			if(flag){
				answer = center;
				right = center;
			}else{
				left = center + 1;
			}
		}
		cout << answer << 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,max_length;

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

		max_length = 0;

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

		min_size = MAX_SIZE;
		left = max_length,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>
#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=100000000,a;
    for(int i=0;i<n;i++){
      cin >> a;
      v.push_back(a);
    }
    
    int mid=(l+r)/2;
    while(r-l>1){
      if(C(mid))r=mid;
      else l=mid;
      mid=(l+r)/2;
    }
    cout << r << endl;
  }

  return 0;
}

C++: #include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;

int w[100];
int main() {
	int m, n;
	while (scanf("%d%d", &m, &n), m) {
		int ans = 0;
		rep(i, n) {
			scanf("%d", &w[i]);
			ans = max(ans, w[i]);
		}
		for (;; ans++) {
			int j = 0, k = 0;
			bool flag = true;
			rep(i, n) {
				j += w[i];
				if (j > ans) {
					k++; j = w[i];
					if (k >= m) {
						flag = false;
						break;
					}
				}
			}
			if (flag) {
				printf("%d\n", ans);
				break;
			}
		}
	}
}

C++: #include<cstdio>

using namespace std;

int simulate(int row,int turn,int weight);

int book[101];

int main(void)
{
   int row,turn;
   while(scanf("%d%d",&row,&turn),row+turn)
   {
      for(int i = 0;i < turn;i++)
         scanf("%d",&book[i]);

      int flag = 0;
      int left = 0,right = 1500000;
      while(left <= right)
      {
         int mid = (left+right)/2;
         int check = simulate(row,turn,mid);

         if(check == -1) left = mid + 1;
         else right = mid - 1;
      }
      printf("%d\n",left);
   }
   return 0;
}

int simulate(int row,int turn,int weight)
{
   int book_id = 0;
   int current_row = 1;
   int remaining_weight = weight;
   while(row >= current_row)
   {
      if(book_id == turn) return 1;
      if(book[book_id] <= remaining_weight)
      {
         remaining_weight -= book[book_id];
         book_id++;
      }
      else
      {
         current_row++;
         remaining_weight = weight;
      }
   }
   return -1;
}