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 <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){

			shelf[0] = 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)shelf[dansu_index] = m;
				}
			}

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

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

	}

    return 0;
}

C++: ?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF 99999999
 
 
int m,n;
int b[110];
 
bool solve(int v){
    int l=0;
    int x=v;
    rep(i,n){
        while(x<b[i]&&l<m){
            x=v;
            l++;
        }
        if(l>=m)return false;
        if(x>=b[i]){
            x-=b[i];
        }
    }
    return true;
}
 
int main(){
    while(cin>>m>>n){
        if(m==0&&m==0)break;
        rep(i,n)cin>>b[i];
         
        int left=0;
        int right=1500000-1;
        while(right>left+1){
//            cout<<left<<" "<<right<<endl;
            int cent=(left+right)/2;
            bool res = solve(cent);
            if(res) right=cent;
            else left=cent;
        }
        cout<<right<<endl;
    }
}

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

int m,n,*b,*l,a,t,mp;
map<int,int> hk;

int max(){
	int tmp = l[0];
	for(int i=1; i<m; i++)
		if(tmp < l[i])
			tmp = l[i];
	return tmp;
}

void solve(){
	mp = 0;
	int k;
	l[0] = 0;
	for(int i=0; i<n; i++){
		k = i+1;
		l[0] += b[i];
		for(int j=1; j<m-1; j++){
			l[j] = 0;
			for(; k<n; k++){
				l[j] += b[k];
				if(k == n-1){
					k++;
					break;
				}
				if((l[j] - l[0] >= 0 && l[j] - l[0] < b[k+1])||(l[j] >= l[0])){
					k++;
					break;
				}
			}
		}
		l[m-1] = 0;
		for(; k<n; k++)
			l[m-1] += b[k];
		if(k == n){
			hk[mp] = max();
			mp++;
		}
	}
}

int min(){
	int tmp = hk[0];
	map<int, int>::iterator it = hk.begin();
	while(it!=hk.end()){
		if(tmp > (*it).second)
			tmp = (*it).second;
		it++;
	}
	return tmp;
}

int main(){
	while(true){
		cin >> m >> n;
		if(!m && !n)
			return 0;
		b = new int[n];
		l = new int[m];
		for(int i=0; i< n; i++)
			cin >> b[i];
		solve();
		cout << min() << endl;
		delete[] b;
		delete[] l;
		hk.clear();
	}
}

C++: //suhan lee, saitama university;
#include <iostream>
using namespace std;
int putbook(int *list,int bookwi,int stair,int width){

  int dara[100];
  int j=0;
  for(int i=0;i<100;i++)
    dara[i]=0;
  for(int i=0;i<bookwi;i++)
    if(dara[j]+list[i]<=width)
      dara[j]+=list[i];
    else  if(list[i]>width){
      //cout <<"too big book"<<endl;
      return 0;
    }
    else  dara[++j]+=list[i];     
  //  cout <<"hondara";
  for(int i=0;i<stair;i++)
    // cout <<dara[i]<<endl;
    // cout <<"kugiri";
  if(j<stair) return 1;// no problem
  else return 0;
}


int main(){

  int list[100];

  int bookwi,stair,temp;
  int max,min;
  while(1){
    cin >>stair>>bookwi;
    if(bookwi==0&&stair==0)
      return 0;
    for(int i=0;i<bookwi;i++)
      cin>>list[i];
    max=1000000;
    min=1;
    //cout << putbook( list,bookwi,stair,1800 )<<endl;
    while(1){
      if(min==max) break;
      if(putbook( list,bookwi,stair, ( max+min)/2  ) )
	max=(max+min)/2;
      else min= (max+min)/2+1;
      //   cout <<endl<<max<<" max&min   "<<min<<endl;   
    }
    cout <<max<<endl;
  }

}

C++: #include<iostream>
#include<vector>
using namespace std;
int main(){
  int n,m;
  while(cin >>n>>m,n||m){
    vector<int> book;
    int x,ans = 0;
    for(int i=0; i<m; i++){
      cin >>x;
      book.push_back(x);
      if(ans<x){ans = x;}
    }
    for(int i;;ans++){
      int last = ans,l = n;
      for(i=0; i<m; i++){
	if(last < book[i]){
	  last = ans;
	  l--;
	  if(l == 0){break;}
	  last-=book[i];
	}
	else{last-=book[i];}
      }
      if(i == m){cout <<ans<<endl;break;}
    }
  }
  return 0;
}

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

int m,n,*b,*l,mp;
map<int,int> hk;

int max(){
	int tmp = l[0];
	for(int i=1; i<m; i++)
		if(tmp < l[i])
			tmp = l[i];
	return tmp;
}

void solve(){
	mp = 0;
	int k;
	l[0] = 0;
	for(int i=0; i<n; i++){
		k = i+1;
		l[0] += b[i];
		for(int j=1; j<m-1; j++){
			l[j] = 0;
			for(; k<n; k++){
				l[j] += b[k];
				if(k == n-1){
					k++;
					break;
				}
				if((l[0] - l[j] >= 0 && l[0] - l[j] < l[j] + b[k+1] - l[0])||(l[j] >= l[0])){
					k++;
					break;
				}
			}
		}
		l[m-1] = 0;
		for(; k<n; k++)
			l[m-1] += b[k];
		hk[mp++] = max();
	}
}

int min(){
	int tmp = hk[0];
	map<int, int>::iterator it = hk.begin();
	while(it!=hk.end()){
		if(tmp > (*it).second)
			tmp = (*it).second;
		it++;
	}
	return tmp;
}

int main(){
	while(true){
		cin >> m >> n;
		if(!m && !n)
			return 0;
		b = new int[n];
		l = new int[m];
		for(int i=0; i< n; i++)
			cin >> b[i];
		solve();
		cout << min() << endl;
		delete[] b;
		delete[] l;
		hk.clear();
	}
}

C++: #include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	int w,n;
	cin >> w >> n;
	vector<int> b(n);
	vector<int> temp(n);
	if(w == 0 && n == 0) break;
	REP(i,n) cin >> b[i];
	temp = b;
	sort(ALL(temp));
	int l,m,h;
	int s,count;
	h = 1500000;
	l = 0;
	m = (h+l)/2;
	while(h-l>1){
	    s = 0;
	    count = 0;
	    if(temp.back() > m){
		l = m;
		m = (h+l)/2;
		continue;
	    }
	    REP(i,n){
		if((s+b[i]) > m){
		    s = 0;
		    count++;
		}
		s += b[i];
	    }

	    if(count < w){
		h = m;
	    }else{
		l = m;
	    }
	    m = (h+l)/2;
	}
	cout << h << endl;
    }
    return 0;
}