include <bits></bits>

using namespace std; int n,a[1000006],i; int main() { cin>>n; for(i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); for(i=1;i<=n;i++) if(a[i]!=a[i-1]) cout<

Trong các bài tập chia căn, đôi lúc chúng ta sử dụng tới CTDL DSU hỗ trợ Rollback, trong CTDL này, chúng ta không nén đường đi tới các nút cha do rollback khiến việc nén này không hiệu quả

Tuy nhiên, với các bài tập chia căn này, chúng ta không quan tâm tới tất cả các thao tác merge, mà chỉ có một số thao tác merge quan trọng cần rollback, vì vậy ta có thể chỉnh CTDL DSU Rollback như sau để cải thiện thời gian chạy

• Với các thao tác merge bình thường (như mở rộng chiều R trong chia căn Mo), ta có thể merge và nén đường đi như cũ
• Ta sẽ có O(căn) thao tác thêm cần rollback, mỗi thao tác sẽ tác động vào tối đa 2 nút (tạm gọi là nút DSU), và chỉ có các nút này bị thay đổi trong quá trình thêm, từ đó ta có ý tưởng đơn giản như sau:
• • Duyệt qua O(căn) thao tác thêm, tìm nút DSU đang chứa các nút cần ghép lại
• • Lưu danh sách thông tin O(căn) nút DSU này
• • Lưu lại thông tin nút DSU của (các) truy vấn
• • Thực hiện merge và vẫn nén đường đi như thường với các nút DSU vừa duyệt
• • Trả lời truy vấn thông qua các nút DSU
• • Với danh sách thông tin đã lưu trên, ta rollback thông tin của O(căn) nút DSU

Phần không-hẳn-là-chứng-minh:

• Với các thao tác merge bình thường, tổng độ phức tạp của chúng sẽ về O(alpha(n))
• Với mỗi O(căn) thao tác merge cần rollback, ta biết các nút DSU luôn là đỉnh cao nhất của các DSU (do ta định nghĩa vậy), việc tìm ra chúng tốn O(alpha(n)) tổng cộng, và mỗi thao tác merge tốn O(1)
• Mỗi thao tác rollback chỉ là gán lại giá trị, vì vậy cũng là O(1), các thao tác rollback này không ảnh hưởng tới việc các nút con tìm tới nút DSU, vì vậy không khiến ta chạy chậm hơn

include <bits></bits>

using namespace std;

int main() { cout<< 863215479 << endl; cout<< 742639185 << endl; cout<< 519487326 << endl; cout<< 486351792 << endl; cout<< 237894651 << endl; cout<< 195762843 << endl; cout<< 328576914 << endl; cout<< 651948237 << endl; cout<< 974123568 << endl; }

1. 👋 Giới Thiệu

Tìm kiếm nhị phân (Binary Search) là một thuật toán tìm kiếm hiệu quả 💪 được sử dụng để tìm kiếm một giá trị mục tiêu 🎯 trong một tập hợp dữ liệu đã được sắp xếp 📚. Thay vì tìm kiếm tuần tự, tìm kiếm nhị phân liên tục chia đôi không gian tìm kiếm ✂️, giúp giảm đáng kể thời gian tìm kiếm ⏱️.

1.1. 💡 Ý Tưởng Cơ Bản

1. 🔍 Kiểm tra phần tử ở giữa khoảng tìm kiếm.
2. ✅ Nếu phần tử giữa là giá trị mục tiêu: Tìm kiếm thành công! 🎉
3. ⬆️ Nếu phần tử giữa lớn hơn giá trị mục tiêu: Thu hẹp không gian tìm kiếm xuống nửa bên trái. ⬅️
4. ⬇️ Nếu phần tử giữa nhỏ hơn giá trị mục tiêu: Thu hẹp không gian tìm kiếm xuống nửa bên phải. ➡️
5. 🔄 Lặp lại các bước 1-4 cho đến khi tìm thấy giá trị mục tiêu hoặc không gian tìm kiếm rỗng.

1.2. 📌 Ví Dụ Minh Họa: Bài Toán "Cây Thứ K"

Bạn có một khu vườn với nhiều cây được trồng thẳng hàng. Bạn cần đặt một máy tưới tự động sao cho:

• Máy tưới bắt đầu tưới từ cây gần nó nhất, tiếp tục tưới cây gần thứ hai, thứ ba, ..., cho đến khi tưới đủ k cây.
• Công suất máy tưới được đo bằng khoảng cách từ vị trí đặt máy đến cây xa nhất trong số k cây đã tưới.
• Nhiệm vụ: Xác định công suất tối thiểu cần thiết để tưới đủ k cây. (Đã chỉnh sửa yêu cầu bài toán cho rõ ràng hơn)

(Bài toán tham khảo từ anh YugiHacker.)

2. 🤔 Khi Nào Sử Dụng Tìm Kiếm Nhị Phân?

Tìm kiếm nhị phân không phải lúc nào cũng "vạn năng". Cần đáp ứng các điều kiện tiên quyết sau:

2.1. 🗂️ Không Gian Tìm Kiếm Có Thứ Tự

Dữ liệu cần tìm kiếm phải được sắp xếp (tăng dần hoặc giảm dần). Hoặc, không gian các giá trị mà bạn đang tìm kiếm phải có tính chất đơn điệu.

2.2. 📈 Tính Đơn Điệu

Phải tồn tại một tính chất đơn điệu liên quan đến điều kiện kiểm tra và không gian tìm kiếm:

• ⬆️ Tăng đơn điệu: Nếu một giá trị x thỏa mãn điều kiện, thì mọi giá trị y lớn hơn hoặc bằng x cũng phải thỏa mãn điều kiện. (Ví dụ: bài "Cây thứ k")
• ⬇️ Giảm đơn điệu: Nếu một giá trị x thỏa mãn điều kiện, thì mọi giá trị y nhỏ hơn hoặc bằng x cũng phải thỏa mãn điều kiện.

2.3. ✅ Hàm Kiểm Tra Hiệu Quả

Cần có một hàm check(value) có thể kiểm tra nhanh chóng ⚡ (thường là O(log N) hoặc tốt hơn) xem một giá trị value có thỏa mãn điều kiện hay không.

3. 🚀 Các Ứng Dụng Phổ Biến

Tìm kiếm nhị phân có rất nhiều ứng dụng 🌍 trong lập trình thi đấu và thực tế:

3.1. 🔍 Tìm Kiếm Giá Trị Trong Mảng Đã Sắp Xếp

Đây là ứng dụng cơ bản nhất 🦴. Các ngôn ngữ lập trình thường cung cấp các hàm thư viện (ví dụ: binary_search, lower_bound, upper_bound trong C++, bisect trong Python).

💻 Ví dụ: Kiểm tra xem số x có tồn tại trong mảng a đã sắp xếp hay không.

3.2. 🎯 Bài Toán Tối Ưu Hóa (Ví Dụ "Cây Thứ K")

Tìm giá trị tối ưu (ví dụ: công suất tối thiểu, chi phí nhỏ nhất) thỏa mãn một điều kiện, nếu có tính đơn điệu.

💻 Ví dụ: (Bài toán "Cây thứ k")

3.3. 📐 Tìm Kiếm Cận Trên/Cận Dưới

Tìm căn bậc hai, căn bậc n, hoặc cận trên/cận dưới của một giá trị thỏa mãn bất phương trình/phương trình.

💻 Ví dụ: Tìm căn bậc hai của một số dương x. Tìm kiếm nhị phân trong khoảng [0, max(1, x)] giá trị mid sao cho mid * mid xấp xỉ x.

3.4. 🧩 Tìm Kiếm Trong Không Gian Nghiệm Rời Rạc

Áp dụng khi không gian nghiệm là các giá trị rời rạc và có tính đơn điệu.

💻 Ví dụ: Phân bổ M máy chủ cho N dịch vụ (xem chi tiết trong bản nháp của bạn - ví dụ rất tốt).

3.5. 🌳 Tìm Kiếm Trên Đồ Thị/Cây (Trường Hợp Đặc Biệt)

• 🛣️ Tìm đường đi ngắn nhất có trọng số cạnh thỏa mãn điều kiện: Tìm kiếm nhị phân trên giá trị trọng số.
• 🌲 Tìm kiếm trên cây nhị phân tìm kiếm (BST): BST được xây dựng dựa trên ý tưởng của tìm kiếm nhị phân.

4. 🔑 Mẹo và Lưu Ý

4.1. 📏 Chọn Khoảng Tìm Kiếm Ban Đầu [l, r]

• Đảm bảo khoảng tìm kiếm đủ lớn để chứa nghiệm. 🎯
• Tránh chọn khoảng tìm kiếm quá lớn không cần thiết. 🐌
• Xác định rõ l và r có thể là giá trị nghiệm hay không.

4.2. ⚙️ Thiết Kế Hàm check(value)

• Hàm check là trái tim ❤️. Đảm bảo nó chính xác và hiệu quả ⚡.
• Chú ý đến tính đơn điệu 📈⬇️.

4.3. 🚧 Xử Lý Trường Hợp Biên

• Đảm bảo vòng lặp có điểm dừng 🛑.
• Xử lý trường hợp không tìm thấy nghiệm ❌ (nếu có thể).

4.4. 🔢 Chú Ý Kiểu Dữ Liệu

• Sử dụng kiểu dữ liệu phù hợp (ví dụ: long long) để tránh tràn số. 🧐

5. 🎉 Kết Luận

Tìm kiếm nhị phân là một kỹ thuật mạnh mẽ 💪 và linh hoạt ✨. Nắm vững 🧠 nguyên tắc, điều kiện áp dụng và các biến thể là quan trọng 🌟. Luyện tập thường xuyên 🏋️‍♀️!

6. 🔗 Tham Khảo

• Binary Search - GeeksforGeeks
• Binary Search - Wikipedia
• Bài toán "Cây thứ k" - Tham khảo từ anh YugiHacker.

🚀 Happy Coding! 🎯

Không gian metric

Định nghĩa, sự hội tụ

Định nghĩa : Cho tập hợp ~X~, ánh xạ ~\rho :X \times X \rightarrow \mathbb{R}~ được gọi là metric (khoảng cách) khi và chỉ khi thỏa mãn các điều kiện sau:

• ~\rho(x, y) \ge 0~ ~\forall x, y \in X;\ \rho(x,y) = 0 \Leftrightarrow x = y~
• ~\rho(x, y) = \rho(y, x) \Leftrightarrow x = y \ \forall \ x, y \in X~
• ~\rho(x, z) \le \rho(x, y) + \rho(y, z) \ \forall \ x, y, z \in X~

Khi đó ~(X, \rho)~ được gọi là không gian metric

Sự hội tụ : Cho ~\{x_n\} \subset X, x_0 \in X~, ta bảo $$\lim_{n \rightarrow \infty} x_n = x_0 \Leftrightarrow \lim_{x \rightarrow \infty} \rho(x_n, x_0) = 0$$

Tập mở, tập đóng

Cho ~(X, \rho)~ là không gian metric :

• ~B\left(x_0, r\right) = \{ x \in X : \rho(x, x_0) < r \}~ là hình cầu mở tâm ~x_0~ bán kính ~r~

• ~B\left[x_0, r \right] =\{x \in X : \rho(x, x_0) \le r \}~ là hình cầu đóng tâm ~x_0~ bán kính ~r~

• ~A \subset X~ được gọi là tập mở ~\Leftrightarrow~ ~\forall x \in X, \exists \ r > 0: B\left(x, r\right) \subset A~

• ~A \subset X~ được gọi là tập đóng nếu ~X \backslash A~ là mở

Định lí 1 : Cho ~(X, \rho)~ là không gian metric, thì có :

1. ~\varnothing, X~ là các tập mở.
2. Hợp của họ bất kì các tập mở là tập hợp mở.
3. Giao của họ hữu hạn các tập mở là tập hợp mở.

Định lí 2 : Cho ~(X, \rho)~ là không gian metric, thì có :

1. ~\varnothing, X~ là các tập đóng.
2. Hợp của họ hữu hạn các tập đóng là tập hợp đóng.
3. Giao của họ bất kì các tập đóng là tập hợp đóng.

Định lí 3 : Cho ~(X, \rho)~ là không gian metric, khi đó ~A~ đóng ~\Leftrightarrow \ \forall \ \{x_n\} \subset X, x_n \rightarrow x_0~ khi ~n \rightarrow \infty \ \Rightarrow x_0 \in A~

Mệnh đề :

• Trong không gian metric, hình cầu đóng là tập đóng
• Cho ~x \in X~, tập mở bất kì chứa điểm ~x~ được gọi là lân cận của ~x~.
• Cho ~x \in X~, ~x~ được gọi là điểm trong của tập ~A \subset X~ khi và chỉ khi tồn tại một lân cận của ~x~ nằm trong ~A~
• Cho ~x \in X~, ~x~ được gọi là điểm biên của ~A~ khi và chỉ khi mọi lân cận ~U~ của ~x~ đều có ~U \cap A \neq \varnothing, \ U \cap (X \backslash A) \neq \varnothing~

Định lí 4 : điểm ~x_0 \in X~ được gọi là điểm tụ của tập ~A \subset X~ khi và chỉ khi tồn tại dãy ~\{x_n\}~ đôi một khác nhau của ~A~ sao cho ~x_n \rightarrow x_0~ khi ~n \rightarrow \infty~

Hệ quả : ~A \subset X~, ~A~ đóng ~\Leftrightarrow~ A chứa các điểm tụ của nó

Định nghĩa : Cho ~A \subset X~, ta gọi ~\overline{A} = A \cup \partial A~ là bao đóng của ~A~, ở đó ~\partial A~ là tập các điểm biên của ~A~.

Định lí 5 : ~\overline{A}~ là tập đóng và là tập đóng nhỏ nhất chứa ~A~.

Định lí 6 : Cho ~A \subset X~, khi đó ~x_0 \in \overline{A} \ \Leftrightarrow \exists \ \{x_n\} \subset A : x_n \rightarrow x_0~ khi ~n \rightarrow \infty~

Định nghĩa : Phần trong của ~A~ là tập hợp các điểm trong của ~A~ và được kí hiệu là ~A^0~ hoặc ~\text{Int} A~

Định lí 7 : Ta có

• ~A^0~ là tập mở và là tập mở lớn nhất trong ~A~
• ~A^0 = A \backslash \partial A~

Định nghĩa : Cho ~A \subset X~, ta nói ~A~ trù mật trong ~X~ ~\Leftrightarrow \ \overline{A} = X~

Hệ quả : Ta nói ~A~ mở ~\Leftrightarrow \ A = A^0~ và ~A~ đóng ~\Leftrightarrow \ A = \overline{A}~

Không gian metric đủ (đầy)

Cho ~(X, \rho)~ là không gian metric.

Định nghĩa : Mọi dãy ~\{x_n\} \subset X~ là dãy cơ bản ~\Leftrightarrow \ \rho(x_n, x_m) \rightarrow 0~ khi ~n, m \rightarrow \infty~

Chú ý : Mọi dãy hội tụ đều là dãy cơ bản.

Định nghĩa : ~(X, \rho)~ được gọi là không gian metric đủ khi và chỉ khi mọi dãy cơ bản trong ~X~ đều hội tụ.

Nguyên lí Cantor : Trong không gian metric đủ, mỗi dãy hình cầu đóng thắt dần đều có một điểm chung duy nhất.

Định nghĩa. : Ánh xạ ~f~ từ không gian metric ~X~ vào chính nó được gọi là ánh xạ co ~\Leftrightarrow \ \exists \ \theta \in (0; 1) : \rho(f(x_1), f(x_2)) \le \theta \rho(x_1, x_2)~

Định nghĩa : Điểm ~x \in X~ được gọi là điểm bất động của ánh xạ ~f~ khi và chỉ khi ~f(x) = x~

Định lí 8 (Banach) : Mỗi ánh xạ co ~f~ từ không gian metric đủ ~X~ vào chính nó đều có một điểm bất động duy nhất.

Không gian định chuẩn

Định nghĩa : Ánh xạ ~\Vert \ \Vert : X \rightarrow \mathbb{R} \ (x \rightarrow \Vert x \Vert)~ thỏa mãn các điều kiện sau :

• ~\Vert x \Vert \ge 0, \ \Vert x \Vert = 0 \Leftrightarrow x = 0 \ \forall x \in X~
• ~\Vert \lambda x \Vert = \vert \lambda \vert \Vert x \Vert \ \forall x \in X, \lambda \in \mathbb{R}~
• ~\Vert x + y \Vert \le \Vert x \Vert + \Vert y \Vert \ \forall x, y \in X~

thì được gọi là chuẩn trên ~X~

Định nghĩa : ~X~ là không gian tuyến tính thực, khi đó ~(X, \Vert \ \Vert)~ được gọi là không gian tuyến tính định chuẩn.

Mệnh đề : ~(X, \Vert \ \Vert)~ là không gian định chuẩn, khi đó ~(X, \rho)~ là không gian metric, ở đó ~\rho(x, y) = \Vert x - y \Vert~

Định nghĩa : Cho ~(X, \Vert \ \Vert_1), (X, \Vert \ \Vert_2)~ Ta bảo các chuẩn ~\Vert \ \Vert_1, \Vert \ \Vert_2~ tương đương ~\Leftrightarrow \exists \ M > 0, m > 0 : m\Vert x \Vert_1 \le \Vert x \Vert_2 \le M\Vert x \Vert_1 \ \forall x \in X~

Nhận xét : Các chuẩn trên không gian tuyến tính hữu hạn chiều đều tương đương với nhau.

import time

my_time = int(input("Enter the time in seconds: "))

for x in range(my_time, 0, -1): seconds = x % 60 minutes = int(x / 60) % 60 hours = int(x / 3600) print(f"{hours:02}:{minutes:02}:{seconds:02}") time.sleep(1)

print("TIME'S UP!")