PKU 3001 Gallup
http://poj.org/problem?id=3001
アンケートで、どの選択肢を何%の人が選択したかという情報を、同一の桁で四捨五入した結果が与えられる。
このような結果が与えられる最小の回答者数を答えろというような問題。
人数を小さい方から試していき、与えられた%になるような最小の人数と最大の人数を求めて計算する。
サンプルが親切だと思った。
int in[20]; PI near(ll all,ll ch,ll pa){ PI ret; int l=0,r=all+1; while(l+1<r){ ll mid=(l+r)/2; if(2*mid*pa<all*(2*ch+1))l=mid; else r=mid; } ret.S=l; l=0,r=all+1; while(l+1<r){ ll mid=(l+r)/2; if(all*(2*ch-1)<=2*mid*pa)r=mid; else l=mid; } ret.F=r; return ret; } main(){ int n; int ca=0; while(cin>>n,n){ printf("Case %d: ",++ca); int sum=100; string ss; rep(i,n){ cin>>ss; int t=0; rep(j,SZ(ss)) if(ss[j]!='.')t=t*10+ss[j]-'0'; in[i]=t; } if(ss.find('.')!=-1){ int p=ss.find('.')+1; rep(j,SZ(ss)-p)sum*=10; } int ans=-1; //cout<<sum<<endl; for(int i=1;i<10000;++i){ bool ok=true; PI mix(0,0); rep(j,n){ PI x=near(i,in[j],sum); //cout<<'('<<x.F<<','<<x.S<<") "; mix.F+=x.F; mix.S+=x.S; if(x.F>x.S){ ok=false; break; } } if(ok && mix.F<=i && i<=mix.S){ ans=i; break; } } if(ans==-1)cout<<"error"<<endl; else cout<<ans<<endl; } }