#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class CuttingStick2 { public: void solve(void) { // // クエリ数が多いので二分探索では O(N*Q*log(N)) では間に合わない // そこで以下のように考える // // 各 L から a[i] 本切り出すとする // L[0] L[1] ... L[N-1] // a[0] a[1] ... a[N-1] // // ∑ a[i] = K なる {a[i]} (K の分割数) と考えると // i // // D(K) = min{L[i]/a[i]} が K のこの分割 a(K) での最大長となる。 // i // // ある K にたいして D(K) を最大にする分割 A がもとまっているとき // D(K+1) を最大にする分割 A' は // // L[j]/(A[j]+1) が最大になる j を使って // // A' = {A[0],...,A[j]+1,...,A[N-1]} と表せる。 // (つまり K+1 の最適な分割は K の最適分割から導かれる) // // なぜなら 別の最適な K+1 の分割 B があるとすると L[ii]/B[ii] < min(L[i]/A[i], L[j]/(A[j]+1)) // となるので B から A よりも最適な K の分割がつくれてしまう。(不要な棒をすてればよい) // // よってこの逐次更新結果を保持しておけば各クエリに O(1) で答えられる。 // O(maxK*log(N)) int N; cin>>N; vector L(N); REP(i,N) cin>>L[i]; int maxK = (int)5*10E+5; vector ans(maxK+1,0); vector a(N,0); priority_queue> que; REP(i,N) que.emplace(L[i],i); double D = 1E+9; for (int k = 1; k <= maxK; ++k) { double l; int i; tie(l,i) = que.top(); // L[i]/(a[i]+1) が最大になる i を取得 que.pop(); D = min(D, l); ++a[i]; ans[k] = D; que.emplace(L[i]/(a[i]+1),i); } int Q; cin>>Q; REP(i,Q) { int K; cin>>K; cout<solve(); delete obj; return 0; } #endif