2013
12-25

Gallup

Often, we see results of gallups, like this:
Prefer red: 3.5%
Prefer green: 4.5%
Prefer yellow: 22.0%
Prefer blue: 70.0%

and you begin to wonder: how many people did they really ask? If the numbers are simple, like 20%, 40%, and 40%, you know that they asked 5 people (or 10, or 15, or more, but we are interested in the minimum number of people).

Your task is to write a program that reads sets of percentages and calculates the smallest number of people that could produce the given percentages. We know that this number is always less than 10 000.

The input is a set of percentages. Each set is on a line of its own. Every line starts with an integer n (0 <= n <= 20) giving the number of percentages in the set. If n > 0, the percentages follow as n numbers; these numbers may have 0�5 decimals, and all percentages in a set have the same number of decimals. (If there are no decimals, there is no decimal point.) The percentages always add up to about 100% as there may be small rounding errors. Numbers are rounded when digits are removed; they are rounded upwards if the first removed digit is 5 or more. Thus, 4.472 is rounded to 4.47, 4.5, or 4, depending on how many digits you want.

The input is a set of percentages. Each set is on a line of its own. Every line starts with an integer n (0 <= n <= 20) giving the number of percentages in the set. If n > 0, the percentages follow as n numbers; these numbers may have 0�5 decimals, and all percentages in a set have the same number of decimals. (If there are no decimals, there is no decimal point.) The percentages always add up to about 100% as there may be small rounding errors. Numbers are rounded when digits are removed; they are rounded upwards if the first removed digit is 5 or more. Thus, 4.472 is rounded to 4.47, 4.5, or 4, depending on how many digits you want.

3 20 40 40
3 33.3 33.3 33.3
2 33 67
1 100.0000
4 3.75 4.25 22.00 70.00
2 49 51
2 50 51
2 49 50
0

Case 1: 5
Case 2: 3
Case 3: 3
Case 4: 1
Case 5: 400
Case 6: 35
Case 7: 200
Case 8: error

int n;
char in[20][20];

int main()
{
int cs=0;
while(scanf("%d",&n),n){
int a[20];
rep(i,n)scanf("%s",in[i]);
int ten=1, i;
for(i=strlen(in[0])-1;i>=0;i--){
if(in[0][i]=='.')break;
ten*=10;
}
if(i<0)ten=1;

rep(i,n){
double t;
sscanf(in[i],"%lf",&t);
a[i]=int(t*ten+0.5);
}
int total=100*ten, m=1;
for(;m<=9999;m++){
int MX=0,MN=0;
bool ok=1;
rep(i,n){
int mn=(int)ceil(m*(a[i]-0.5)/100/ten-EPS);
int mx=(int)(m*(a[i]+0.5)/100/ten-EPS);
if(mn>mx)ok=0;
MX+=mx; MN+=mn;
}
if(ok&&MN<=m&&m<=MX)break;
}
printf("Case %d: ",++cs);
if(m>9999)puts("error");
else printf("%d\n",m);
}
return 0;
}


1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

2. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确