UVa 714

From Algorithmist

Contents 1 714 - Copying Books 2 Summary 3 Explanation 4 Gotcha's 5 Input 6 Output

[edit] 714 - Copying Books

• http://acm.uva.es/p/v7/714.html

[edit] Summary

Use binary search, with some cleaning up for ties.

[edit] Explanation

Do a binary search on the maximum number of pages assigned to a scriber. You can easily test if a number is high enough by greedily assigning books to scribers. Once you have the optimal value, be sure to assign books to meet the tie-breaking rule (this is done greedily).

Another approach is dynamic programming, as long as you "fix" your solution to meet the tie-breaker requirement (or maybe assign books backwards?).

[edit] Gotcha's

• Overflow should be a consideration (500 * 10000000 > 2^32)

[edit] Input

8
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100
4 2
1 2 4 8
6 2
1 2 4 8 4 2
6 2
1 2 3 3 2 1
2 2
10000000 10000000
6 3
1000000 1 1 1 1 1
6 6
6 5 4 3 2 1

[edit] Output

100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100
1 2 4 / 8
1 2 4 / 8 4 2
1 2 3 / 3 2 1
10000000 / 10000000
1000000 / 1 / 1 1 1 1
6 / 5 / 4 / 3 / 2 / 1