Fraction
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 239 Accepted Submission(s): 55
Problem Description Given a number n, and a geometric progression a
i = b * q
i, i ≥ 0, what is the fraction of the elements of that progression with decimal notation that has the decimal notation of n as prefix ?
More formally, if c
i out of the first i elements of the progression start with n in decimal notation, you need to find the limit
. It is guaranteed that the limit always exists.
For example, n = 7, b = 1, q = 2. About 5.799% of all powers of two start with 7. (the smallest one is 2
46 = 70368744177664)
Input The first line of the input is T (1 ≤ T ≤ 100), which stands fZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vciB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgeW91IG5lZWQgdG8gc29sdmUuPGJyPgo8YnI+CkVhY2ggY2FzZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBuLGIgYW5kIHEuICgxIKHcIG4sIGIsIHEgodwgMTAwMCkKCiAKPGJyPgoKT3V0cHV0CgpGb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IGEgbGluZSChsENhc2UgI3Q6IKGxKHdpdGhvdXQgcXVvdGVzLCB0IG1lYW5zIHRoZSBpbmRleCBvZiB0aGUgdGVzdCBjYXNlKSBhdCB0aGUgYmVnaW5uaW5nLiBUaGVuIG91dHB1dCBvbmUgZmxvYXRpbmcgbnVtYmVyIKhDIHRoZSBzb3VnaHQgZnJhY3Rpb24uIFJvdW5kIHlvdXIgYW5zd2VyIHRvIHRoZSA1dGggZGVjaW1hbCBwbGFjZS4KCiAKPGJyPgoKU2FtcGxlIElucHV0Cgo8cHJlIGNsYXNzPQ=="brush:java;">2 7 1 2 1 1 1
Sample Output
Case #1: 0.05799
Case #2: 1.00000
Source 2014 ACM/ICPC Asia Regional Shanghai Online
题目大意 给定n,b,q 设a
i = b * q^i 求当m趋近于无穷时，a1~am之中前缀为n的概率
解题思路 因为保证一定收敛，试着打表找一下规律 后来发现n取定后 不论b,q为何值都会基本收敛到一个数值，模拟100000项误差也不是很大 最后发现关于取定的n ans=(lg(n+1)/n) 特判一下q=1,10,100,1000的情况（相当于只向后面添加0，或者保持b不变）
想到了代码就水了，比赛的时候卡了多次边界= =
#include
#include
using namespace std; int main() { int T,ca=0; scanf("%d",&T); while (T--) { int n,b,q; scanf("%d%d%d",&n,&b,&q); double nn=n,bb=b,qq=q;/* 以下为打表 bb=log10(bb); printf("Case #%d: ",++ca); int ans=0; for (int i=1;i<=1000000;i++) { bb+=log10(q); if ((int) (pow(10.0,(bb-((int)(bb))))+(int)(log10(double (n)))==n) if (bb>bb-((int)(bb))+(int)(log10(n))) ans++; } printf("%.5f\n",((double)ans)/1000000); 打表结束 */ double r; if (q==10||q==100||q==1000) if (b==n||b/10==n||b/100==n||b/1000==n||b*10==n||b*100==n||b*1000==n) r=1; else r=0; else if (q==1) if (b==n||b/10==n||b/100==n||b/1000==n) r=1; else r=0; else r=log10((double)(n+1)/double(n)); printf("%.5f\n",r); } return 0; }