Đây là Div.3 với đề dễ nên giải được nhiều. Quan trọng là nhiều bao nhiêu cũng không đủ, vẫn ngu.
Dạo này mình mới tập viết template, trông cũng xàm nhưng được cái nó dài. Có điều là tới hồi viết blog lại phải copy ra file non-template cho đỡ rối mắt.
Bài thơ trong template là mình vô tình đọc được trên vOz, sau đó mất một khoảng thời gian mình Google mãi vẫn không tìm thấy. Mãi sau này nhớ mang máng cái câu "mùa thu vàng còn vàng nữa người ơi" nên thử tra exact keyword và ra được kết quả ở diễn đàn Lưu học sinh Việt Nam. Tính ra là mình Google sai vì nhớ nhầm câu sau, tốn mẹ mất mấy năm.
Tips: vừa code vừa mở SGO48 nghe cuốn cực, với điều kiện đề dễ hoặc trình bạn cao. Đối với mình là do đề dễ.
---
A. Boring Apartments.
Tóm tắt: dãy số được sinh từ 1 đến 9 và có từ 1 ký tự đến 4 ký tự sao cho mỗi số trong dãy chỉ được viết từ 1 số tự nhiên duy nhất. Nhập vào số nguyên $x$, cho biết tổng cộng từ đầu dãy đến $x$ có bao nhiêu ký tự đã được nhập.
Hướng dẫn: sinh rồi duyệt, độ phức tạp $\mathcal{O}(n)$. Bài này còn có cách làm $\mathcal{O}(1)$, mời bạn tham khảo editorial chính thức.
---
B. Yet another bookshelf.
Tóm tắt: Bạn phải dồn hết sách về một phía và mỗi lần chỉ dời được 1 block (i.e nhiều quyển sách nằm kề nhau) sang bên phải 1 vị trí, tìm xem cần bao nhiêu lần dời thì hoàn thành.
Hướng dẫn: Kết quả là tổng số lượng số $0$ nằm giữa 2 số $1$ liên tiếp. Code mẫu dùng 2 con trỏ để đếm, độ phức tạp $\mathcal{O}(n)$.
---
C. Dominant Piranha.
Tóm tắt: Trong một bầy cá Piranha có một con cá đầu đàn; con đó sẽ ăn những con Piranha nhỏ hơn xung quanh nó và nó cũng phình ra thêm một lượng bằng với tổng kích thước những con cá nó vừa mới ăn. Tìm con cá đó và in ra vị trí của nó, nếu không có con cá nào thì in ra $-1$. Chú ý index bài này bắt đầu từ $1$.
Hướng dẫn: Algoritham.
- Nếu tất cả các con cá đều có kích thước bằng nhau thì không con cá nào có thể ăn con bên cạnh mình, do đó trường hợp này in ra $-1$.
- Trường hợp còn lại, ta chỉ cần tìm con cá có kích thước lớn nhất trong toàn dãy và lớn hơn ít nhất 1 trong 2 con cạnh bên. Mục đích của điều kiện lớn hơn con bên cạnh là để loại trừ trường hợp con cá cần tìm nằm trong dãy các con cá liên tiếp có kích thước bằng nhau và đều lớn nhất.
Code mẫu dùng std::set để đếm số lượng kích thước khác nhau, thêm 1 vòng lặp để tìm con Piranha phù hợp; tổng độ phức tạp là $O(n)$.
---
E. Two Round Dances.
Tóm tắt: Có $n$ ($n$ chẵn) người chia làm 2 nhóm nhảy, mỗi nhóm gồm chính xác $\displaystyle \frac{n}{2}$ người. Tìm tổng số cách chia nhóm $n$ người thành 2 nhóm nhảy sao cho mỗi nhóm gồm đúng $\displaystyle \frac{n}{2}$ người và mỗi người chỉ tham gia 1 trong 2 nhóm. Bài toán này không tính đến hoán vị, nên mỗi nhóm được chia chỉ nên xuất hiện 1 lần.
i.e: (ví dụ đề bài) với $n = 4$ có 3 cách chia nhóm: $\{1, 2\}$ và $\{3, 4\}; \{2, 4\}$ và $\{3, 1\}; \{4, 1\}$ và $\{3, 2\}$. Trong ví dụ này, $\{1, 2\}$ và $\{2, 1\}$ được tính là 1 nhóm.
Hướng dẫn: một chút kiến thức về tổ hợp.
- Ta xếp $\displaystyle \frac{n}{2}$ người từ $n$ người vào nhóm đầu, nửa còn lại sẽ vào nhóm thứ 2. Vậy tổng cộng có $\displaystyle {n \choose \frac{n}{2}}$ cách. (Note: $\displaystyle {n \choose k}$ là tổ hợp chập $k$ của $n$ phần tử).
- $\displaystyle \frac{n}{2}$ người trong mỗi nhóm phải xếp theo một thứ tự nhất định nhưng bỏ qua các phép hoán vị. Vậy tổng cộng có $\displaystyle \left(\frac{n}{2} - 1\right)!$ cách xếp, mà mỗi lần xếp cần 2 nhóm nên có $\displaystyle \left[\left(\frac{n}{2} - 1\right)!\right]^2$ cách.
- Cuối cùng, ta cần chia 2 kết quả do trong lần đếm bên trên có đếm trùng các nhóm.
Tóm lại, đáp án là $\displaystyle \frac{\displaystyle {n \choose \frac{n}{2}} \times \left[\left(\displaystyle \frac{n}{2} - 1\right)!\right]^2}{2}$, rút gọn còn $\displaystyle \frac{(n - 1)!\times 2}{n}$. Do $n \leq 20$ nên hoàn toàn có thể tính $(n - 1)!$ trong phạm vi số nguyên 64-bit, độ phức tạp chung là $\mathcal{O}(n)$.
---
Happy coding!
No comments:
Post a Comment