{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\u003cp\u003e\n Cây tìm kiếm nhị phân tối ưu là một cây tìm kiếm nhị phân được xây dựng từ $n$ khóa và $n+1$ khóa giả để giảm thiểu giá trị kỳ vọng của chi phí cho một phép tìm kiếm.\n\u003c/p\u003e\n\n\u003cp\u003e\n Chúng ta được cung cấp một chuỗi $K \u003d {k_1, k_2, ..., k_n}$ các khóa $n$ phân biệt theo thứ tự sắp xếp $(k_1 \u0026lt; k_2 \u0026lt; ... \u0026lt; k_n)$, và chúng ta muốn xây dựng một cây tìm kiếm nhị phân. Đối với mỗi khóa $k_i$, chúng ta có xác suất $p_i$ mà một tìm kiếm sẽ là cho $k_i$. Một số tìm kiếm có thể là cho các giá trị không có trong $K$, và vì vậy chúng ta cũng có $n+1$ khóa giả $d_0, d_1, d_2, ..., d_n$ đại diện cho các giá trị không có trong $K$. Các khóa giả $d_i (0 \\le i \\le n)$ được xác định như sau:\n\u003c/p\u003e\n\n\u003cul\u003e\n \u003cli\u003enếu $i\u003d0$, thì $d_i$ đại diện cho tất cả các giá trị nhỏ hơn $k_1$\u003c/li\u003e\n \u003cli\u003enếu $i\u003dn$, thì $d_i$ đại diện cho tất cả các giá trị lớn hơn $k_n$\u003c/li\u003e\n \u003cli\u003enếu $1 \\le i \\le n-1$, thì $d_i$ đại diện cho tất cả các giá trị nằm giữa $k_i$ và $k_{i+1}$\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\n Đối với mỗi khóa giả $d_i$, chúng ta có xác suất $q_i$ mà một tìm kiếm sẽ tương ứng với $d_i$.\nĐối với $p_i (1 \\le i \\le n)$ và $q_i (0 \\le i \\le n)$, chúng ta có \n\n \\[\n \\sum_{i\u003d1}^n p_i + \\sum_{i\u003d0}^n q_i \u003d 1\n \\]\n\n Sau đó, chi phí kỳ vọng của một tìm kiếm trong cây tìm kiếm nhị phân $T$ là\n\n \\[\n E_T \u003d \\sum_{i\u003d1}^n (depth_T(k_i) + 1) \\cdot p_i + \\sum_{i\u003d0}^n (depth_T(d_i) + 1) \\cdot q_i\n \\]\n\n trong đó $depth_T(v)$ là độ sâu của nút $v$ trong $T$.\n\n Đối với một tập hợp xác suất cho trước, mục tiêu của chúng ta là xây dựng một cây tìm kiếm nhị phân mà chi phí tìm kiếm kỳ vọng là nhỏ nhất. Chúng ta gọi một cây như vậy là một \u003cb\u003ecây tìm kiếm nhị phân tối ưu\u003c/b\u003e.\n\n\u003c/p\u003e\n\u003cp\u003e\n Mỗi khóa $k_i$ là một nút nội bộ và mỗi khóa giả $d_i$ là một lá. Ví dụ, hình sau đây cho thấy cây tìm kiếm nhị phân tối ưu được thu được từ Đầu vào Mẫu 1.\n\u003c/p\u003e\n\u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/f30b5eb975fa153ef1e30ac9b9cf57e8?v\u003d1711023847\"\u003e\n\u003c/center\u003e\n\n\u003ch2\u003eNhiệm vụ\u003c/h2\u003e\n\n\u003cp\u003e\n Viết một chương trình tính giá trị kỳ vọng của một phép tìm kiếm trên cây tìm kiếm nhị phân tối ưu được thu được bằng cách cho $p_i$ rằng một tìm kiếm sẽ là cho $k_i$ và $q_i$ rằng một tìm kiếm sẽ tương ứng với $d_i$.\n\u003c/p\u003e\n\n\u003ch2\u003eNhập\u003c/h2\u003e\n\n\u003cpre\u003e$n$\n$p_1$ $p_2$ ... $p_n$\n$q_0$ $q_1$ $q_2$ ... $q_n$\n\u003c/pre\u003e\n\n\u003cp\u003e\n Trong dòng đầu tiên, một số nguyên $n$ đại diện cho số lượng khóa được cung cấp.\u003cbr\u003e\nTrong dòng thứ hai, $p_i (1 \\le i \\le n)$ được cung cấp dưới dạng số thực với bốn chữ số thập phân.\u003cbr\u003e\nTrong dòng thứ ba, $q_i (0 \\le i \\le n)$ được cung cấp dưới dạng số thực với bốn chữ số thập phân.\u003cbr\u003e\n\u003c/p\u003e\n\n\u003ch2\u003eĐầu ra\u003c/h2\u003e\n\n\u003cp\u003e\n In giá trị kỳ vọng cho một phép tìm kiếm trên cây tìm kiếm nhị phân tối ưu trong một dòng.\nKết quả không được chứa lỗi lớn hơn $10^{−4}$.\n\u003c/p\u003e\n\n\u003ch2\u003eGiới hạn\u003c/h2\u003e\n\n\u003cul\u003e\n \u003cli\u003e$1 \\le n \\le 500$\u003c/li\u003e\n \u003cli\u003e$0 \\lt p_i, q_i \\lt 1$\u003c/li\u003e\n \u003cli\u003e$\\displaystyle \\sum_{i\u003d1}^n p_i + \\sum_{i\u003d0}^n q_i \u003d 1$\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch2\u003eĐầu vào Mẫu 1\u003c/h2\u003e\n\u003cpre\u003e5\n0.1500 0.1000 0.0500 0.1000 0.2000\n0.0500 0.1000 0.0500 0.0500 0.0500 0.1000\n\u003c/pre\u003e\n\n\u003ch2\u003eĐầu ra Mẫu 1\u003c/h2\u003e\n\u003cpre\u003e2.75000000\n\u003c/pre\u003e\n\n\u003ch2\u003eĐầu vào Mẫu 2\u003c/h2\u003e\n\u003cpre\u003e7\n0.0400 0.0600 0.0800 0.0200 0.1000 0.1200 0.1400\n0.0600 0.0600 0.0600 0.0600 0.0500 0.0500 0.0500 0.0500\n\u003c/pre\u003e\n\n\u003ch2\u003eĐầu ra Mẫu 2\u003c/h2\u003e\n\u003cpre\u003e3.12000000\n\u003c/pre\u003e"}}]}