768D - Jon and Orbs - CodeForces Solution

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

typedef long long       ll;
typedef pair<int, int>  pii;

#define bugatti         cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define fi              first
#define se              second
#define max_heap(T)     priority_queue<T>
#define min_heap(T)     priority_queue<T, vector<T>, greater<T>>
#define fr(i, a, b)     for(int i=a;i<b;i++)
#define frr(i, a, b)    for(int i=a;i>b;i--)
#define frin(i, A)      for(auto &i : A)
#define sz(x)           (int)x.size()
#define all(A)          A.begin(), A.end()
#define md(a, b)        (a%b + b)%b

const ll  INF  = 2e9;
const ll  MOD  = 1e9 + 7;
const int MAXN = 1003;
const double eps = 1e-7;

int k, q, ans[MAXN];
double dp[MAXN];

void solve() {
    cin >> k >> q;
    dp[0] = 1;
    int p = 1;
    for(int i = 1; p < MAXN; i++) {
        frr(j, k, 0)
            dp[j] = j*1.0/k*dp[j] + (k-j+1)*1.0/k*dp[j-1];
        while(p < MAXN && 2000*dp[k] >= (p))
            ans[p++] = i;
        dp[0] = 0;
    }
    while(q--) {
        cin >> p;
        cout << ans[p] << '\n';
    }
}

int32_t main() {
    bugatti
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int T;
    // cin >> T;
    T = 1;
    while(T--)
        solve();
    return 0;
}