【字节跳动笔试题汇总】 2024-03-31-字节跳动春招笔试题-三语言题解(CPP/Python/Java)

🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新字节跳动近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试｜编程一对一辅导

👏 感谢大家的订阅➕ 和喜欢💗

文章目录

- 01.K小姐的基环树游戏
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 02.魔法糖果屋
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 03.K小姐的树形公园设计
- - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 样例说明
  - 数据范围
  - 题解
  - 参考代码
- 04.LYA的光纤网络设计
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 样例说明
  - 数据范围
  - 题解
  - 参考代码
- 写在最后
- 📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取～

01.K小姐的基环树游戏

问题描述

K小姐最近迷上了一款基环树游戏。这个游戏的游戏地图是一个无向图,图中有 $n$ 个节点和 $m$ 条边,且不包含重边和自环。在这个游戏中,玩家需要在图上再选择连接一条边,使得整个无向图变成一棵基环树。

所谓基环树,是一种包含 $n$ 个节点, $n$ 条边,且不包含重边和自环的无向连通图。形象地说,基环树可以由一棵普通的树再添加一条之前不存在的边构成。

现在,K小姐想知道,对于当前的游戏地图,一共有多少种不同的连边方案可以使其变成一棵基环树呢?

输入格式

第一行输入两个正整数 $n, m$ ,代表无向图的节点数和边数。

接下来的 $m$ 行,每行输入两个正整数 $u, v$ ,代表节点 $u$ 和节点 $v$ 之间有一条边相连。保证给定的无向图中不存在重边和自环。

输出格式

输出一个整数,代表添加一条新边使其变成基环树的方案数。

样例输入

样例输出

在这个样例中,原图已经是一棵基环树了,因此不需要再添加新边,方案数为0。

数据范围

$\le n, m \le 10^5$
$\le u, v \le n$

题解

这道题可以用并查集和计数的方法来解决。基本思路如下:

首先判断原图是否已经是一棵树了,如果边数 $m$ 不等于节点数 $n - 1$ ,则原图一定不是树,方案数为0。
如果原图是树,则用并查集将所有边合并。合并完成后,统计并查集中连通分量的个数 $c n t$ 。
如果 $c n t > 2$ ,说明图不连通,无法通过添加一条边使其变成基环树,方案数为0。
如果 $c n t = 1$ ,说明原图已经是基环树,方案数为 $\frac{n*(n-1)}{2}-(n-1)$ ,即在完全图中选择一条之前不存在的边。
如果 $c n t = 2$ ,说明原图由两个连通分量组成,方案数为两个连通分量的大小的乘积。

参考代码

Python

def find(x):
    if pre[x] != x:
        pre[x] = find(pre[x])
    return pre[x]

n, m = map(int, input().split())
if m != n - 1:
    print(0)
    exit()

pre = list(range(n))
for _ in range(n - 1):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    pu, pv = find(u), find(v)
    if pu != pv:
        pre[pu] = pv

cnt = sum(pre[i] == i for i in range(n)) 
print(0 if cnt > 2 else n * (n - 1) // 2 - (n - 1) if cnt == 1 else next(a * b for a in map(pre.count, set(pre)) for b in map(pre.count, set(pre)) if a != n and b != n))

Java

import java.io.*;
import java.util.*;

public class Main {
    static int[] pre;
    
    static int find(int x) {
        if (pre[x] != x) 
            pre[x] = find(pre[x]);
        return pre[x];
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int m = Integer.parseInt(params[1]);
        
        if (m != n - 1) {
            System.out.println(0);
            return;
        }
        
        pre = new int[n];
        for (int i = 0; i < n; i++) 
            pre[i] = i;
        
        for (int i = 0; i < n - 1; i++) {
            params = br.readLine().split(" ");
            int u = Integer.parseInt(params[0]) - 1;
            int v = Integer.parseInt(params[1]) - 1;
            int pu = find(u), pv = find(v);
            if (pu != pv) 
                pre[pu] = pv;
        }
        
        int cnt = 0;
        int[] size = new int[n];
        for (int i = 0; i < n; i++) {
            if (pre[i] == i) 
                cnt++;
            size[find(i)]++;
        }
        
        if (cnt > 2) {
            System.out.println(0);
        } else if (cnt == 1) {
            System.out.println(n * (n - 1L) / 2 - (n - 1));
        } else {
            int a = -1, b = -1;
            for (int s : size) {
                if (s > 0) {
                    if (a == -1) 
                        a = s;
                    else
                        b = s;
                }
            }
            System.out.println((long) a * b);
        }
    }
}

#include <iostream>
#include <vector>
using namespace std;

vector<int> pre;

int find(int x) {
    if (pre[x] != x)
        pre[x] = find(pre[x]); 
    return pre[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    
    if (m != n - 1) {
        cout << 0 << endl;
        return 0;
    }
    
    pre.resize(n);
    for (int i = 0; i < n; i++)
        pre[i] = i;
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        int pu = find(u), pv = find(v);
        if (pu != pv)
            pre[pu] = pv;
    }
    
    int cnt = 0;
    vector<int> size(n);
    for (int i = 0; i < n; i++) {
        if (pre[i] == i)
            cnt++;
        size[find(i)]++;
    }
    
    if (cnt > 2) {
        cout << 0 << endl;
    } else if (cnt == 1) {
        cout << n * (n - 1L) / 2 - (n - 1) << endl;
    } else {
        int a = -1, b = -1;
        for (int s : size) {
            if (s > 0) {
                if (a == -1)
                    a = s;
                else 
                    b = s;
            }
        }
        cout << (long long)a * b << endl;
    }
    return 0;
}

02.魔法糖果屋

问题描述

小美是一个贪吃的小朋友,有一天她发现了一个装满魔法糖果的糖果屋。糖果屋里一共有 $n$ 颗糖果,第 $i$ 颗糖果上写着数字 $a_i$ 。

小美每天都必须吃一颗糖果,而且第 $x$ 天必须吃一颗写着数字 $x$ 的糖果。小美有一个魔法棒,可以用来改变一颗糖果上的数字,将其变成原来的两倍。但魔法棒只能使用一次。

小美想知道使用魔法棒一次之后,自己最多能连续吃到糖果的天数是多少呢?你能帮帮她吗?

输入格式

第一行包含一个正整数 $n$ ,表示糖果的数量。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ ,表示每颗糖果上写的数字。

输出格式

输出一个整数,表示小美最多能连续吃到糖果的天数。

样例输入

4
1 1 3 5

样例输出

数据范围

$\le n \le 10^5$
$\le a_i \le 10^9$

题解

这道题可以用贪心的思想来解决。我们可以先将所有糖果按照数字从小到大排序,然后统计出每个数字出现的次数。

接下来,我们从左到右扫描排序后的糖果数组。如果当前数字 $x$ 和前一个数字 $y$ 满足 $x = y + 1$ ,那么我们可以直接跳过,因为这两个数字之间没有断层。

如果 $x > y + 1$ ,那么我们就找到了一个断层 $[y + 1, x - 1]$ 。我们可以计算出这个断层的长度 $x - y - 1$ ,更新答案。

最后,我们再考虑使用魔法棒的情况。对于每个数字 $x$ ,我们都可以将其变成 $2 x$ ,然后看看能否跟左右两侧的数字连成更长的序列。

具体来说,如果 $2 x + 1$ 存在,那么我们可以将 $2 x$ 和右侧的数字连成一段;如果 $2 x - 1$ 存在,那么我们可以将 $2 x$ 和左侧的数字连成一段。选择其中更长的一段更新答案即可。

注意,如果 $x$ 本身在原序列中出现了两次及以上,那么将其变成 $2 x$ 之后,断层的长度还需要额外加 $1$ 。

时间复杂度 $\log n)$ ,空间复杂度 $O (n)$ 。

参考代码

Python

from typing import List
from collections import defaultdict

def maxConsecutiveDays(candies: List[int]) -> int:
    candies.sort()
    n = len(candies)
    cnt = defaultdict(int)
    for candy in candies:
        cnt[candy] += 1

    last = candies[0]
    left_range = {candies[0]: candies[0]}
    right_range = {}
    res = 0

    for i in range(n - 1):
        if candies[i + 1] != candies[i] + 1:
            left_range[last] = candies[i]
            right_range[candies[i]] = last
            res = max(res, candies[i] - last + 1)
            last = candies[i + 1]
            left_range[last] = candies[i + 1]

    if last != candies[-1]:
        left_range[last] = candies[-1]
        right_range[candies[-1]] = last
        res = max(res, candies[-1] - last + 1)

    for candy in candies:
        double_candy = candy * 2
        r = -1
        if candy in left_range and cnt[candy] < 2:
            r = left_range[candy]
            if r == candy:
                right_range.pop(r, None)
            else:
                right_range[r] = candy + 1

        ans = 1
        if double_candy + 1 in left_range:
            ans += left_range[double_candy + 1] - double_candy
        if double_candy - 1 in right_range:
            if cnt[candy] >= 2:
                ans += double_candy - right_range[double_candy - 1]
            else:
                ans += double_candy - max(right_range[double_candy - 1], candy + 1)
        res = max(res, ans)

        if r != -1:
            right_range[r] = candy

    return res

Java

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        int[] candies = new int[n];
        for (int i = 0; i < n; i++) {
            candies[i] = Integer.parseInt(str[i]);
        }
        System.out.println(maxConsecutiveDays(candies));
    }

    private static int maxConsecutiveDays(int[] candies) {
        Arrays.sort(candies);
        int n = candies.length;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int candy : candies) {
            cnt.put(candy, cnt.getOrDefault(candy, 0) + 1);
        }

        int last = candies[0];
        Map<Integer, Integer> leftRange = new HashMap<>();
        Map<Integer, Integer> rightRange = new HashMap<>();
        leftRange.put(candies[0], candies[0]);
        int res = 0;

        for (int i = 0; i < n - 1; i++) {
            if (candies[i + 1] != candies[i] + 1) {
                leftRange.put(last, candies[i]);
                rightRange.put(candies[i], last);
                res = Math.max(res, candies[i] - last + 1);
                last = candies[i + 1];
                leftRange.put(last, candies[i + 1]);
            }
        }

        if (last != candies[n - 1]) {
            leftRange.put(last, candies[n - 1]);
            rightRange.put(candies[n - 1], last);
            res = Math.max(res, candies[n - 1] - last + 1);
        }

        for (int candy : candies) {
            int doubleCandy = candy * 2;
            int r = -1;
            if (leftRange.containsKey(candy) && cnt.get(candy) < 2) {
                r = leftRange.get(candy);
                if (r == candy) {
                    rightRange.remove(r);
                } else {
                    rightRange.put(r, candy + 1);
                }
            }

            int ans = 1;
            if (leftRange.containsKey(doubleCandy + 1)) {
                ans += leftRange.get(doubleCandy + 1) - doubleCandy;
            }
            if (rightRange.containsKey(doubleCandy - 1)) {
                if (cnt.get(candy) >= 2) {
                    ans += doubleCandy - rightRange.get(doubleCandy - 1);
                } else {
                    ans += doubleCandy - Math.max(rightRange.get(doubleCandy - 1), candy + 1);
                }
            }
            res = Math.max(res, ans);

            if (r != -1) {
                rightRange.put(r, candy);
            }
        }

        return res;
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int maxDays(vector<int>& candies) {
    sort(candies.begin(), candies.end());
    int n = candies.size();
    unordered_map<int, int> cnt;
    for (int candy : candies) {
        cnt[candy]++;
    }

    int last = candies[0];
    unordered_map<int, int> leftRange, rightRange;
    leftRange[candies[0]] = candies[0];
    int res = 0;

    for (int i = 0; i < n - 1; i++) {
        if (candies[i + 1] != candies[i] + 1) {
            leftRange[last] = candies[i];
            rightRange[candies[i]] = last;
            res = max(res, candies[i] - last + 1);
            last = candies[i + 1];
            leftRange[last] = candies[i + 1];
        }
    }

    if (last != candies.back()) {
        leftRange[last] = candies.back();
        rightRange[candies.back()] = last;
        res = max(res, candies.back() - last + 1);
    }

    for (int candy : candies) {
        int doubleCandy = candy * 2;
        int r = -1;
        if (leftRange.count(candy) && cnt[candy] < 2) {
            r = leftRange[candy];
            if (r == candy) {
                rightRange.erase(r);
            } else {
                rightRange[r] = candy + 1;
            }
        }

        int ans = 1;
        if (leftRange.count(doubleCandy + 1)) {
            ans += leftRange[doubleCandy + 1] - doubleCandy;
        }
        if (rightRange.count(doubleCandy - 1)) {
            if (cnt[candy] >= 2) {
                ans += doubleCandy - rightRange[doubleCandy - 1];
            } else {
                ans += doubleCandy - max(rightRange[doubleCandy - 1], candy + 1);
            }
        }
        res = max(res, ans);

        if (r != -1) {
            rightRange[r] = candy;
        }
    }

    return res;
}

03.K小姐的树形公园设计

题目描述

K小姐是一名园林设计师,最近她接到了一个新的任务。任务是设计一个树形公园,公园由 $n$ 个节点组成,节点之间由 $n - 1$ 条无向边连接。公园建成后,为了方便游客游览,K小姐需要在公园中选择一个节点建立一个游客中心。

建立游客中心后,公园会被分割成若干个连通块。为了避免某些连通块游客过于拥挤,K小姐希望最大的连通块的节点数量尽可能小。但是她发现要找到最优的游客中心位置并不容易。因此,她决定随机选择一个节点作为游客中心的位置。

现在,K小姐想知道,如果随机选择一个节点作为游客中心,最大连通块节点数量的期望值是多少呢?

输入格式

第一行包含一个正整数 $n$ ,表示树形公园的节点数量。

接下来 $n - 1$ 行,每行包含两个正整数 $u$ 和 $v$ ,表示节点 $u$ 和节点 $v$ 之间有一条无向边相连。

输出格式

输出一个实数,表示最大连通块节点数量的期望值,与标准答案误差不超过 $10^{-6}$ 即视为正确。

样例输入

2
1 2

样例输出

1.000000000

样例说明

无论选择节点 1 还是节点 2 作为游客中心,最大连通块的节点数量均为 1。

数据范围

$\le n \le 10^5$
$\le u, v \le n$

题解

本题可以使用树形 DP 的思想求解。我们可以对树进行一次 DFS 遍历,在遍历的过程中维护以每个节点为根的子树的大小。

对于每个节点 $u$ ,我们可以计算出以 $u$ 为游客中心时,最大连通块的节点数量。具体地,设 $f_u$ 表示以 $u$ 为根的子树的节点数量,则最大连通块的节点数量为 $\max(n-f_u, \max\limits_{v \in son(u)} f_v)$ ,其中 $so n (u)$ 表示 $u$ 的所有子节点。

这样,我们可以在 DFS 的过程中,计算出每个节点作为游客中心时最大连通块的节点数量,然后将它们加和并除以 $n$ ,即可得到最大连通块节点数量的期望值。

时间复杂度 $O (n)$ ,空间复杂度 $O (n)$ 。

参考代码

Python

import sys
sys.setrecursionlimit(int(1e5 + 5))

n = int(input())
g = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

r = 1 / n
res = 0
f = [0] * (n+1)

def dfs(u, pre):
    global res
    f[u] = 1
    max_sz = 0
    for i in g[u]:
        if i != pre:
            dfs(i, u)
            f[u] += f[i]
            max_sz = max(max_sz, f[i])
    max_sz = max(max_sz, n - f[u])
    res += max_sz * r

dfs(1, 0)
print(f"{res:.10f}")

Java

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static List<Integer>[] g;
    static double r, res;
    static int[] f;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        g = new List[n+1];
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < n-1; i++) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            g[a].add(b);
            g[b].add(a);
        }
        r = 1.0 / n;
        res = 0;
        f = new int[n+1];
        dfs(1, 0);
        System.out.printf("%.10f\n", res);
    }

    static void dfs(int u, int pre) {
        f[u] = 1;
        int maxSz = 0;
        for (int i : g[u]) {
            if (i != pre) {
                dfs(i, u);
                f[u] += f[i];
                maxSz = Math.max(maxSz, f[i]);
            }
        }
        maxSz = Math.max(maxSz, n - f[u]);
        res += maxSz * r;
    }
}

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

const int N = 1e5 + 5;
int n;
vector<int> g[N];
double r, res;
int f[N];

void dfs(int u, int pre) {
    f[u] = 1;
    int maxSz = 0;
    for (int i : g[u]) {
        if (i != pre) {
            dfs(i, u);
            f[u] += f[i];
            maxSz = max(maxSz, f[i]);
        }
    }
    maxSz = max(maxSz, n - f[u]);
    res += maxSz * r;
}

int main() {
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    r = 1.0 / n;
    res = 0;
    dfs(1, 0);
    printf("%.10lf\n", res);
    return 0;
}

04.LYA的光纤网络设计

问题描述

LYA是一家通信公司的工程师,她正在设计一个新的光纤网络。这个网络需要在一条直线上建设 $5$ 个信号塔,用于传输信号。

直线上有 $n$ 个可以建设信号塔的位置,其中第 $1$ 个位置和第 $n$ 个位置必须建设信号塔。每个位置都有一个建设强度 $a_i$ ,代表在该位置建设信号塔的设备质量。

信号在两个信号塔之间传输时,信号强度会发生变化。信号强度的变化值与两个信号塔的建设强度之和成正比,与两个信号塔之间的距离成反比。具体来说,如果两个信号塔的建设强度分别为 $a$ 和 $b$ ,它们之间的距离为 $d$ ,则一个强度为 $x$ 的信号经过这两个信号塔传输后,强度将变为 $\times \frac{a+b}{d}$ 。

LYA需要在剩余的 $n - 2$ 个位置中选择 $3$ 个建设信号塔,使得从最左侧的信号塔传输到最右侧信号塔时,信号的强度尽可能大。假设最左侧信号塔发出的初始信号强度为 $1$ 。请你帮助LYA设计出这个光纤网络,计算出信号强度的最大值。

输入格式

第一行包含一个正整数 $n$ ,表示可以建设信号塔的位置数量。

第二行包含 $n$ 个正整数 $x_1, x_2, \ldots, x_n$ ,其中 $x_i$ 表示第 $i$ 个位置的坐标。

第三行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ ,其中 $a_i$ 表示在第 $i$ 个位置建设信号塔的建设强度。

输出格式

输出一个实数,表示信号强度的最大值。与标准答案误差不超过 $10^{-6}$ 即视为正确。

样例输入

6
1 3 5 7 8 10
7 6 9 5 1 3

样例输出

910.0000000000

样例说明

在第 $1$ 、 $2$ 、 $3$ 、 $4$ 、 $6$ 这五个位置建设信号塔是最优方案。第 $1$ 个信号塔发出强度为 $1$ 的信号:

传输到第 $2$ 个信号塔后,信号强度变为 $6.5$ 。
传输到第 $3$ 个信号塔后,信号强度变为 $48.75$ 。
传输到第 $4$ 个信号塔后,信号强度变为 $341.25$ 。
传输到第 $6$ 个信号塔后,信号强度变为 $910$ 。

可以证明这是最优的建设方案。

数据范围

$\le n \le 2000$
$\le x_i, a_i \le 10^4$
$x_1 < x_2 < \ldots < x_n$

题解

本题可以使用动态规划求解。我们可以定义两个数组 $f$ 和 $g$ ,其中:

$f [i]$ 表示从第 $1$ 个信号塔传输到第 $i$ 个信号塔的最大信号强度。
$g [i]$ 表示从第 $i$ 个信号塔传输到第 $n$ 个信号塔的最大信号强度。

我们可以先计算出 $f$ 数组的值。对于每个位置 $i$ ,枚举 $\le j < i$ ,更新 $f [i]$ 的值:

$\max\limits_{1 \le j < i} \left\{\frac{a_1 + a_j}{x_j - x_1} \times \frac{a_i + a_j}{x_i - x_j}\right\}$

类似地,我们可以计算出 $g$ 数组的值。对于每个位置 $i$ ,枚举 $\le n$ ,更新 $g [i]$ 的值:

$\max\limits_{i < j \le n} \left\{\frac{a_n + a_j}{x_n - x_j} \times \frac{a_j + a_i}{x_j - x_i}\right\}$

最后,我们枚举中间的信号塔位置 $i$ ,计算 $\times g[i]$ 的最大值即为答案。

时间复杂度为 $O(n^2)$ ,空间复杂度为 $O (n)$ 。

参考代码

Python

def solve():
    tower_count = int(input())
    positions = list(map(int, input().split()))
    strengths = list(map(int, input().split()))

    left_dp = [0] * tower_count
    right_dp = [0] * tower_count

    for i in range(1, tower_count):
        for j in range(1, i):
            left_dp[i] = max(left_dp[i], (strengths[0] + strengths[j]) / (positions[j] - positions[0]) * (strengths[i] + strengths[j]) / (positions[i] - positions[j]))

    for i in range(tower_count - 2, -1, -1):
        for j in range(i + 1, tower_count - 1):
            right_dp[i] = max(right_dp[i], (strengths[-1] + strengths[j]) / (positions[-1] - positions[j]) * (strengths[j] + strengths[i]) / (positions[j] - positions[i]))

    max_strength = 0
    for i in range(2, tower_count - 2):
        max_strength = max(max_strength, left_dp[i] * right_dp[i])

    print(f"{max_strength:.6f}")

solve()

Java

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int towerCount = scanner.nextInt();
        int[] positions = new int[towerCount];
        int[] strengths = new int[towerCount];
        
        for (int i = 0; i < towerCount; i++) {
            positions[i] = scanner.nextInt();
        }
        for (int i = 0; i < towerCount; i++) {
            strengths[i] = scanner.nextInt();
        }
        
        double[] leftDP = new double[towerCount];
        double[] rightDP = new double[towerCount];
        
        for (int i = 1; i < towerCount; i++) {
            for (int j = 1; j < i; j++) {
                leftDP[i] = Math.max(leftDP[i], (strengths[0] + strengths[j]) * 1.0 / (positions[j] - positions[0]) * (strengths[i] + strengths[j]) / (positions[i] - positions[j]));
            }
        }
        
        for (int i = towerCount - 2; i >= 0; i--) {
            for (int j = i + 1; j < towerCount - 1; j++) {
                rightDP[i] = Math.max(rightDP[i], (strengths[towerCount - 1] + strengths[j]) * 1.0 / (positions[towerCount - 1] - positions[j]) * (strengths[j] + strengths[i]) / (positions[j] - positions[i]));
            }
        }
        
        double maxStrength = 0;
        for (int i = 2; i < towerCount - 2; i++) {
            maxStrength = Math.max(maxStrength, leftDP[i] * rightDP[i]);
        }
        
        System.out.printf("%.6f\n", maxStrength);
    }
}

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int towerCount;
    cin >> towerCount;
    vector<int> positions(towerCount);
    vector<int> strengths(towerCount);

    for (int i = 0; i < towerCount; i++) {
        cin >> positions[i];
    }
    for (int i = 0; i < towerCount; i++) {
        cin >> strengths[i];
    }

    vector<double> leftDP(towerCount, 0);
    vector<double> rightDP(towerCount, 0);

    for (int i = 1; i < towerCount; i++) {
        for (int j = 1; j < i; j++) {
            leftDP[i] = max(leftDP[i], 1.0 * (strengths[0] + strengths[j]) / (positions[j] - positions[0]) * (strengths[i] + strengths[j]) / (positions[i] - positions[j]));
        }
    }

    for (int i = towerCount - 2; i >= 0; i--) {
        for (int j = i + 1; j < towerCount - 1; j++) {
            rightDP[i] = max(rightDP[i], 1.0 * (strengths[towerCount - 1] + strengths[j]) / (positions[towerCount - 1] - positions[j]) * (strengths[j] + strengths[i]) / (positions[j] - positions[i]));
        }
    }

    double maxStrength = 0;
    for (int i = 2; i < towerCount - 2; i++) {
        maxStrength = max(maxStrength, leftDP[i] * rightDP[i]);
    }

    cout << fixed << setprecision(6) << maxStrength << endl;

    return 0;
}