#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef MY_LOCAL_RUN #include #endif #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } #ifdef MY_LOCAL_RUN __declspec(noinline) long long sum_trunc_mul(const double *A, int N, double s_inv) { __m256d inv = _mm256_set1_pd(s_inv); int i = 0; __m256d sum = _mm256_setzero_pd(); for(; i + 3 < N; i += 4) { __m256d a_d = _mm256_load_pd(A + i); __m256d prod = _mm256_mul_pd(a_d, inv); __m256d truncated = _mm256_round_pd(prod, (_MM_FROUND_TO_ZERO |_MM_FROUND_NO_EXC)); sum = _mm256_add_pd(sum, truncated); } double sum4[4]; _mm256_storeu_pd(sum4, sum); long long res = 0; rep(k, 4) res += (ll)sum4[k]; for(; i < N; ++ i) res += (ll)(A[i] * s_inv); return res; } #else long long sum_trunc_mul(const double *A, int N, double s_inv); __asm( ".intel_syntax noprefix\n" "_Z13sum_trunc_mulPKdid:\n" ".LMY_FB3893:\n" " push rbp\n" " mov rbp, rsp\n" " sub rsp, 80\n" " mov QWORD PTR 16[rbp], rcx\n" " mov DWORD PTR 24[rbp], edx\n" " vmovsd QWORD PTR 32[rbp], xmm2\n" " sub rsp, 352\n" " mov rax, rsp\n" " add rax, 31\n" " shr rax, 5\n" " sal rax, 5\n" " mov rdx, QWORD PTR 32[rbp]\n" " mov QWORD PTR -32[rbp], rdx\n" " vbroadcastsd ymm0, QWORD PTR -32[rbp]\n" " vmovapd YMMWORD PTR 256[rax], ymm0\n" " mov DWORD PTR -4[rbp], 0\n" " vxorpd xmm0, xmm0, xmm0\n" " vmovapd YMMWORD PTR 288[rax], ymm0\n" " jmp .LMY_8\n" ".LMY_12:\n" " mov edx, DWORD PTR -4[rbp]\n" " movsx rdx, edx\n" " lea rcx, 0[0+rdx*8]\n" " mov rdx, QWORD PTR 16[rbp]\n" " add rdx, rcx\n" " mov QWORD PTR -40[rbp], rdx\n" " mov rdx, QWORD PTR -40[rbp]\n" " vmovapd ymm0, YMMWORD PTR [rdx]\n" " vmovapd YMMWORD PTR 224[rax], ymm0\n" " vmovapd ymm0, YMMWORD PTR 224[rax]\n" " vmovapd YMMWORD PTR 128[rax], ymm0\n" " vmovapd ymm0, YMMWORD PTR 256[rax]\n" " vmovapd YMMWORD PTR 96[rax], ymm0\n" " vmovapd ymm0, YMMWORD PTR 128[rax]\n" " vmulpd ymm0, ymm0, YMMWORD PTR 96[rax]\n" " vmovapd YMMWORD PTR 192[rax], ymm0\n" " vroundpd ymm0, YMMWORD PTR 192[rax], 11\n" " vmovapd YMMWORD PTR 160[rax], ymm0\n" " vmovapd ymm0, YMMWORD PTR 288[rax]\n" " vmovapd YMMWORD PTR 64[rax], ymm0\n" " vmovapd ymm0, YMMWORD PTR 160[rax]\n" " vmovapd YMMWORD PTR 32[rax], ymm0\n" " vmovapd ymm0, YMMWORD PTR 64[rax]\n" " vaddpd ymm0, ymm0, YMMWORD PTR 32[rax]\n" " vmovapd YMMWORD PTR 288[rax], ymm0\n" " add DWORD PTR -4[rbp], 4\n" ".LMY_8:\n" " mov edx, DWORD PTR -4[rbp]\n" " add edx, 3\n" " cmp edx, DWORD PTR 24[rbp]\n" " jl .LMY_12\n" " lea rdx, -80[rbp]\n" " mov QWORD PTR -48[rbp], rdx\n" " vmovapd ymm0, YMMWORD PTR 288[rax]\n" " vmovapd YMMWORD PTR [rax], ymm0\n" " mov rdx, QWORD PTR -48[rbp]\n" " vmovapd ymm0, YMMWORD PTR [rax]\n" " vmovupd YMMWORD PTR [rdx], ymm0\n" " mov QWORD PTR -16[rbp], 0\n" " mov DWORD PTR -20[rbp], 0\n" " jmp .LMY_13\n" ".LMY_14:\n" " mov eax, DWORD PTR -20[rbp]\n" " cdqe\n" " mov rax, QWORD PTR -80[rbp+rax*8]\n" " vmovq xmm1, rax\n" " vcvttsd2si rax, xmm1\n" " add QWORD PTR -16[rbp], rax\n" " add DWORD PTR -20[rbp], 1\n" ".LMY_13:\n" " cmp DWORD PTR -20[rbp], 3\n" " jle .LMY_14\n" " jmp .LMY_15\n" ".LMY_16:\n" " mov eax, DWORD PTR -4[rbp]\n" " cdqe\n" " lea rdx, 0[0+rax*8]\n" " mov rax, QWORD PTR 16[rbp]\n" " add rax, rdx\n" " mov rax, QWORD PTR [rax]\n" " vmovq xmm3, rax\n" " vmulsd xmm0, xmm3, QWORD PTR 32[rbp]\n" " vcvttsd2si rax, xmm0\n" " add QWORD PTR -16[rbp], rax\n" " add DWORD PTR -4[rbp], 1\n" ".LMY_15:\n" " mov eax, DWORD PTR -4[rbp]\n" " cmp eax, DWORD PTR 24[rbp]\n" " jl .LMY_16\n" " mov rax, QWORD PTR -16[rbp]\n" " mov rsp, rbp\n" " pop rbp\n" " ret\n" ".att_syntax\n" "\n"); #endif int main() { int N; while(~scanf("%d", &N)) { vector A_d(N); rep(i, N) { int A; scanf("%d", &A); A_d[i] = A; } long long K; scanf("%lld", &K); const double EPS = 1e-9; double l = 0, u = 1e9; while(l + EPS < u && l * (1 + EPS) < u) { double mid = (l + u) / 2; double inv = 1. / mid; long long sum = sum_trunc_mul(&A_d[0], N, inv); if(sum >= K) l = mid; else u = mid; } printf("%.10f\n", (l + u) / 2); } return 0; }