UVA 11413 Fill the ...

d

6
82
1
21
6
20
21
72
2
1

i

5 3
1 2 3 4 5
3 2
4 78 9
1 1
1
6 1
1 2 3 4 5 6
6 6
1 2 3 4 5 6
10 5
10 10 10 10 10 10 10 10 10 10
10 5
10 10 10 10 10 10 10 10 10 11
10 5
10 10 72 10 10 10 10 10 10 10
2 1
1 1
2 3
1 

p11413.cpp

#include <bits/stdc++.h>
using namespace std;
#define maxN 1000
//DISCUSS!!! TOOK MY 5 hrs 
int n, m;
int vessels[maxN];

enum outcome {undershoot, done, overshoot};

outcome simulation(int conCap){
	//for each vessel
	int rem = conCap;
	int remM = m;
	
	for (int i = 0; i < n; ++i){
		if (vessels[i] <= rem) rem -= vessels[i];
		else {
			remM--;
			if (remM <= 0) return undershoot;
			rem = conCap; 
			if (rem < vessels[i]) return undershoot;
			rem -= vessels[i]; 
		}
	}
	//if (remM > 0 || rem > 0) return overshoot;
	return overshoot;
}

int main(){
	outcome res;
	while (scanf("%d %d", &n, &m) != EOF){
		long int sum = 0;
		for(int i = 0; i < n; ++i){
			scanf("%d", &vessels[i]);
			sum += vessels[i];
		}

		int lo = 0, hi = sum, mid;
		for (int i = 0; i < 100; ++i){
			// mid = (lo + hi) / 2;
			// cout << lo << " " << hi << " " << mid << endl;
			res = simulation(hi);
			if (res == undershoot) {
				lo = hi;
				hi = hi + hi / 2;
			}
			else if (res == overshoot) hi = lo + (hi - lo) / 2;
			// else if (lo >= hi) break;
		}
		printf("%d\n", hi + 1);
	}	
	return 0;
}

p11413_a.cpp

#include <bits/stdc++.h>
using namespace std;
#define maxN 1000
int n, m;
int vessels[maxN];

//checks whether cap is a valid sol or not
bool simulation(int cap){
	int tot = 1, cur = 0;
	//for each vessel
	for (int i = 0; i < n; ++i){
		if (vessels[i] > cap) return false;
		//when new container is required
		if (cur + vessels[i] > cap) {
			cur = 0;
			tot++; 	//wrong if tot is set to 0
		}
		// if (cur == 0) tot++;
		cur += vessels[i];
		if (tot > m) return false;
	}
	return true;
}


int main(){
	while (scanf("%d %d", &n, &m) != EOF){
		long int sum = 0;
		for(int i = 0; i < n; ++i){
			scanf("%d", &vessels[i]);
			sum += vessels[i];
		}

		int lo = 1, hi = sum, mid, best;
		// for (int i = 0; i < 50; ++i){
		while(lo <= hi){
			mid = lo + (hi - lo) / 2;	//takes care of large lo and hi
			if (simulation(mid)){		//mid is a valid ans; check smaller
				best = mid;
				hi = mid - 1;
			}
			else lo = mid + 1;
		}
		printf("%d\n", best);
	}
	return 0;
}

p11413_wrking.cpp

/*
 * Sai Cheemalapati
 * UVA 11413: Fill the containers
 *
 */
 
#include<cstdio>
 
using namespace std;
 
int n, m, c[1100];
 
bool simul(int cap) {
    int tot = 0, cur = 0;
    for(int i = 0; i < n; i++) {
        if(c[i] > cap) return false;
        if(cur + c[i] > cap) cur = 0;
        if(cur == 0) tot++;
        cur += c[i];
        if(tot > m) return false;
    }
    return true;
}
 
int main() {
 
    while(scanf("%d %d", &n, &m) == 2) {
        for(int i = 0; i < n; i++)
            scanf("%d", &c[i]);
 
        int high = 1000000000, low = 0;
        while(high - low > 0) {
            if(simul(high)) {
                high = low + (high - low) / 2;
            } else {
                low = high;
                high = high + high / 2;
            }
        }
        printf("%d\n", high + 1);
    }
    return 0;
}