#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; } const double *g_A; int g_N; double g_s_inv; long long g_res; #ifdef MY_LOCAL_RUN extern "C" void sum_trunc_mul(); __declspec(noinline) void sum_trunc_mul() { const double *A = g_A; int N = g_N; double s_inv = g_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); g_res = res; } #else extern "C" void sum_trunc_mul(); __asm( "\n" ".text\n" "sum_trunc_mul:\n" ".L_FB3893:\n" " pushq %rbp\n" " movq %rsp, %rbp\n" " subq $112, %rsp\n" " subq $352, %rsp\n" " movq %rsp, %rax\n" " addq $31, %rax\n" " shrq $5, %rax\n" " salq $5, %rax\n" " movq g_A(%rip), %rdx\n" " movq %rdx, -32(%rbp)\n" " movl g_N(%rip), %edx\n" " movl %edx, -36(%rbp)\n" " movq g_s_inv(%rip), %rdx\n" " movq %rdx, -48(%rbp)\n" " movq -48(%rbp), %rdx\n" " movq %rdx, -56(%rbp)\n" " vbroadcastsd -56(%rbp), %ymm0\n" " vmovapd %ymm0, 256(%rax)\n" " movl $0, -4(%rbp)\n" " vxorpd %xmm0, %xmm0, %xmm0\n" " vmovapd %ymm0, 288(%rax)\n" " jmp .L_6\n" ".L_10:\n" " movl -4(%rbp), %edx\n" " movslq %edx, %rdx\n" " leaq 0(,%rdx,8), %rcx\n" " movq -32(%rbp), %rdx\n" " addq %rcx, %rdx\n" " movq %rdx, -64(%rbp)\n" " movq -64(%rbp), %rdx\n" " vmovapd (%rdx), %ymm0\n" " vmovapd %ymm0, 224(%rax)\n" " vmovapd 224(%rax), %ymm0\n" " vmovapd %ymm0, 128(%rax)\n" " vmovapd 256(%rax), %ymm0\n" " vmovapd %ymm0, 96(%rax)\n" " vmovapd 128(%rax), %ymm0\n" " vmulpd 96(%rax), %ymm0, %ymm0\n" " vmovapd %ymm0, 192(%rax)\n" " vroundpd $11, 192(%rax), %ymm0\n" " vmovapd %ymm0, 160(%rax)\n" " vmovapd 288(%rax), %ymm0\n" " vmovapd %ymm0, 64(%rax)\n" " vmovapd 160(%rax), %ymm0\n" " vmovapd %ymm0, 32(%rax)\n" " vmovapd 64(%rax), %ymm0\n" " vaddpd 32(%rax), %ymm0, %ymm0\n" " vmovapd %ymm0, 288(%rax)\n" " addl $4, -4(%rbp)\n" ".L_6:\n" " movl -4(%rbp), %edx\n" " addl $3, %edx\n" " cmpl -36(%rbp), %edx\n" " jl .L_10\n" " leaq -112(%rbp), %rdx\n" " movq %rdx, -72(%rbp)\n" " vmovapd 288(%rax), %ymm0\n" " vmovapd %ymm0, (%rax)\n" " movq -72(%rbp), %rdx\n" " vmovapd (%rax), %ymm0\n" " vmovupd %ymm0, (%rdx)\n" " movq $0, -16(%rbp)\n" " movl $0, -20(%rbp)\n" " jmp .L_11\n" ".L_12:\n" " movl -20(%rbp), %eax\n" " cltq\n" " movq -112(%rbp,%rax,8), %rax\n" " vmovq %rax, %xmm1\n" " vcvttsd2siq %xmm1, %rax\n" " addq %rax, -16(%rbp)\n" " addl $1, -20(%rbp)\n" ".L_11:\n" " cmpl $3, -20(%rbp)\n" " jle .L_12\n" " jmp .L_13\n" ".L_14:\n" " movl -4(%rbp), %eax\n" " cltq\n" " leaq 0(,%rax,8), %rdx\n" " movq -32(%rbp), %rax\n" " addq %rdx, %rax\n" " movq (%rax), %rax\n" " vmovq %rax, %xmm2\n" " vmulsd -48(%rbp), %xmm2, %xmm0\n" " vcvttsd2siq %xmm0, %rax\n" " addq %rax, -16(%rbp)\n" " addl $1, -4(%rbp)\n" ".L_13:\n" " movl -4(%rbp), %eax\n" " cmpl -36(%rbp), %eax\n" " jl .L_14\n" " movq -16(%rbp), %rax\n" " movq %rax, g_res(%rip)\n" " movq %rbp, %rsp\n" " popq %rbp\n" " ret\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; g_A = &A_d[0], g_N = N, g_s_inv = inv; sum_trunc_mul(); long long sum = g_res; if(sum >= K) l = mid; else u = mid; } printf("%.10f\n", (l + u) / 2); } return 0; }