### haribhatt34's blog

By haribhatt34, history, 8 months ago, ,

My Solution -

#include <bits/stdc++.h>
using namespace std;

map<int, int> mp;

int findPower(int i, int k)
{
int t = i, cnt = 0;
while (t <= k)
{
if (mp.find(t) != mp.end())
{
cnt += mp[t];
break;
}
t *= 2;
++cnt;
}
return mp[i] = cnt;
}

int main()
{
int n, k;
cin >> n >> k;
// power of 2
vector<int> p2(31);
p2[0] = 1;
for (int i=1; i<p2.size(); ++i)	p2[i] = p2[i-1] * 2;

long double b = 0.0;
for (int i=n; i>=1; --i)
{
int p = findPower(i, k);
p = p2[p];
b += (long double)1/p;
}
cout << ((long double)1/n) * b << '\n';
return 0;
}


I know my solution is unnecessarily long, I was trying to catch value, so to use them later. I don't know what I am doing wrong, moreover I am not getting correct decimal precision. For sample — 100000 5, the output should be — 0.999973749998, but my program is returning 0.9999687500, why could it be?

• 0

 » 8 months ago, # |   0 Auto comment: topic has been updated by haribhatt34 (previous revision, new revision, compare).
 » 8 months ago, # |   0 Auto comment: topic has been updated by haribhatt34 (previous revision, new revision, compare).
 » 8 months ago, # |   +3 u can use cout << fixed ; cout << setprecision(15) i did same and get ac
 » 8 months ago, # |   +5 Change while (t <= k) to while (t < k).
 » 8 months ago, # |   0 Your code is giving the wrong output for 100000 5 because in findPower() function you have written while(t<=k) it should be while(t using namespace std; typedef long long lld; int main() { std::ios::sync_with_stdio(false); lld t = 1; // cin >> t; while(t--) { lld n, k; cin >> n >> k; lld ans = -1; vector deno; for(lld i = 1; i <= n; i++) { lld sc = i; lld turn = 0; while(sc < k) { sc = 2 * sc; turn++; } lld val = (1 << turn) * 1LL; deno.push_back(val); ans = max(ans, val); } lld num = 0; for(lld i = 0; i < deno.size(); i++) { num += (ans / deno[i]); } cout << fixed << setprecision(10) << (num * 1.0 / (ans * n)) << "\n"; } } `
 » 8 months ago, # |   0 Thanks guys. :)