#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; } extern "C" long long sum_trunc_mul(double *A, int N, double s_inv); #ifdef MY_LOCAL_RUN __attribute__((noinline)) long long sum_trunc_mul(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 __asm( " .text\n" " .p2align 4,,15\n" " .globl sum_trunc_mul\n" " .type sum_trunc_mul, @function\n" "sum_trunc_mul:\n" ".L_FB4609:\n" " .cfi_startproc\n" " pushq %rbp\n" " .cfi_def_cfa_offset 16\n" " .cfi_offset 6, -16\n" " vmovddup %xmm0, %xmm3\n" " vinsertf128 $1, %xmm3, %ymm3, %ymm3\n" " movq %rsp, %rbp\n" " .cfi_def_cfa_register 6\n" " andq $-32, %rsp\n" " addq $16, %rsp\n" " cmpl $3, %esi\n" " jle .L_9\n" " leal -4(%rsi), %ecx\n" " movq %rdi, %rax\n" " vxorpd %xmm1, %xmm1, %xmm1\n" " shrl $2, %ecx\n" " movl %ecx, %edx\n" " salq $5, %rdx\n" " leaq 32(%rdi,%rdx), %rdx\n" " .p2align 4,,10\n" " .p2align 3\n" ".L_4:\n" " vmulpd (%rax), %ymm3, %ymm2\n" " addq $32, %rax\n" " vroundpd $11, %ymm2, %ymm2\n" " cmpq %rdx, %rax\n" " vaddpd %ymm2, %ymm1, %ymm1\n" " jne .L_4\n" " leal 4(,%rcx,4), %r9d\n" ".L_2:\n" " vmovupd %ymm1, -48(%rsp)\n" " leaq -48(%rsp), %rdx\n" " xorl %eax, %eax\n" " leaq -16(%rsp), %r8\n" ".L_6:\n" " vmovsd (%rdx), %xmm1\n" " addq $8, %rdx\n" " vcvttsd2siq %xmm1, %rcx\n" " addq %rcx, %rax\n" " cmpq %r8, %rdx\n" " jne .L_6\n" " cmpl %r9d, %esi\n" " jle .L_10\n" " subl $1, %esi\n" " movslq %r9d, %rcx\n" " leaq (%rdi,%rcx,8), %rdx\n" " subl %r9d, %esi\n" " addq %rsi, %rcx\n" " leaq 8(%rdi,%rcx,8), %rsi\n" " .p2align 4,,10\n" " .p2align 3\n" ".L_8:\n" " vmulsd (%rdx), %xmm0, %xmm1\n" " addq $8, %rdx\n" " vcvttsd2siq %xmm1, %rcx\n" " addq %rcx, %rax\n" " cmpq %rsi, %rdx\n" " jne .L_8\n" ".L_10:\n" " vzeroupper\n" " leave\n" " .cfi_remember_state\n" " .cfi_def_cfa 7, 8\n" " ret\n" ".L_9:\n" " .cfi_restore_state\n" " vxorpd %xmm1, %xmm1, %xmm1\n" " xorl %r9d, %r9d\n" " jmp .L_2\n" " .cfi_endproc\n" "\n"); #endif int main() { int N; { scanf("%d", &N); char *A_d_buf = new char[N * 8 + 32]; double *A_d = reinterpret_cast((reinterpret_cast(A_d_buf) | 31) + 1); 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, N, inv); if(sum >= K) l = mid; else u = mid; } printf("%.10f\n", (l + u) / 2); delete[] A_d_buf; } return 0; }