2014
03-13

# Lottery

Your living city is holding a big lottery game now! There are M people in this city who want to play this lottery. Everyone of them must pay C dollars to get a lottery ticket. Taking this ticket, he can get a chance to win a prize by randomly selecting one from N indistinguishable boxes and getting the prize if there is a ball in the selected box. The ball in the selected box is also taken by this winner, so if a box with a ball happens to be selected by a player, it will never contain balls from then on, but it will be closed and can be selected by the future players. Every box contains exactly one ball at the beginning, and two or more players cannot select the boxes and the same time.

Of course, the latter you join this game, the less the chance you win a prize will be. So the lottery holder make such a rule: If you are the n-th player who wins a prize, you will get A*(n-1)+B dollars. That is to say, the first winner will get B dollars, the second winner will get A+B dollars, the income of the third winner is 2*A+B, and so on.

Being curious about the expected profit, the lottery holder is too lazy to calculate it himself. So he finds you and give you a lot of money to do this work. If you can solve it quickly, you will be a millionaire!

The first line of input is a integer T, the number of test cases. Each case contains exactly 5 integers M, N, C, A, B in this order, where 1 <= M, N <= 10^6 and 0 <= C, A, B <= 100.

The first line of input is a integer T, the number of test cases. Each case contains exactly 5 integers M, N, C, A, B in this order, where 1 <= M, N <= 10^6 and 0 <= C, A, B <= 100.

3
1 2 10 5 7
2 2 10 5 7
7 5 0 0 1

3
7
-3.95142

*二分的上限下限是：MAX（最大的数字），SUM （总和）；

*其中一定有一个数字满足，将N分成M份；

*求最小的；只要当它达到M份时，依然减小上届值；

/*
*problem ID: POJ 3273
* Author ID: fuqiang
*      TIME: 2013-07-17
* Algorithm: 二分
*    Status: (Accept)
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#define maxn 100010
int a[maxn],N,M;
using namespace std;
inline bool check(int mid)
{
int num = 1, sum = 0;
for(int i = 0; i <= N; i++)
{
if(sum + a[i] <= mid)
sum += a[i];
else
{
sum = a[i];
num++;
}
}
return num>M;
}
int main(int argc, char *argv[])
{
while(scanf("%d%d",&N,&M)!=EOF)
{
int MAX = 0, sum = 0;
for(int i = 1; i <= N; i++)
{
scanf("%d",&a[i]);
sum += a[i];
MAX = max(MAX,a[i]);
}
int left = MAX, right = sum, mid;
while(left < right)
{
mid = (left + right) / 2;
if(check(mid))
left = mid + 1;
else
right = mid - 1;
}
printf("%d\n",left);
}
return 0;
}