Còn 3 tuần nữa thi cuối kỳ, 2 tuần nữa deadline CS104, Chủ nhật là nộp deadline CS108. Vậy mà mình vẫn dành thời gian ngồi code contest và viết blog. Contest này là Div.3 nên nó dễ và mình làm được nhiều không phải vì giỏi mà là vì mình may.
---
A - Cards for Friends
Tóm tắt: Bạn cần chia một tấm bìa kích thước $w \times h$ cho $n$ người bạn.
- Nếu $w$ chẵn, bạn có thể cắt tấm bìa thành 2 tấm kích thước $\displaystyle \frac{w}{2} \times {h}$.
- Nếu $h$ chẵn, bạn có thể cắt tấm bìa thành 2 tấm kích thước $\displaystyle w \times \frac{h}{2}$.
Xác định xem có thể chia tấm bìa $w \times h$ ban đầu thành ít nhất $n$ miếng bìa nhỏ để chia cho $n$ bạn hay không?
Hướng dẫn giải: Algoritham.
Mỗi lần cắt tấm bìa theo chiều $w$ hay chiều $h$, ta lại thu được 2 tấm bìa. Vậy ta cắt đến khi nào không cắt được nữa thì thôi, rồi so sánh tổng số miếng bìa cắt được với $n$.
---
B - Fair Division
Tóm tắt: Có $n$ viên kẹo $A_1, A_2, .., A_n$ được chia cho Alice và Bob, mỗi viên có trọng lượng là 1 hoặc 2 grams. Một phép chia kẹo là công bằng khi Alice và Bob nhận được số kẹo có trọng lượng bằng nhau. Biết là không thể cắt 1 viên kẹo ra thành nhiều phần, hãy xác định xem $n$ viên kẹo đó có thể chia công bằng cho 2 đứa Alice và Bob không?
Hướng dẫn giải: Toán, nhưng cách mình làm hơi dị xíu:
- Nếu tổng trọng lượng kẹo lẻ, tất nhiên ta không thể chia cho 2 đứa được.
- Nếu tổng trọng lượng kẹo chẵn, nếu ta chỉ có 2 viên kẹo thì chỉ cần 2 viên đó cùng loại là được.
- Còn lại, gọi tổng trọng lượng kẹo là $K$, ta xét xem có tồn tại một bộ $\displaystyle A_{x_1} + A_{x_2} + .. + A_{x_n} = \frac{K}{2}$ hay không.
Ở ý cuối mình dùng 2 con trỏ để check.
Ngoài lề: mất 1 sub vì đọc đề ngu.
---
C - Long Jumps
Tóm tắt: Cho mảng $A$ có $n$ phần tử. Ban đầu, điểm số $p$ của bạn bằng 0. Bạn được chọn một vị trí $i$ làm vị trí bắt đầu. Khi $i \leq n, p := p + A_i$ và $i := i + A_i$. Trò chơi kết thúc khi $i > n$. Tìm $\max(p)$ mà bạn có thể đạt được.
Hướng dẫn giải: DP.
Gọi $B_i$ là điểm số ghi được khi đến vị trí $i$. Với mỗi thao tác duyệt qua một vị trí $i$, nếu $i + A_i \leq n$ thì $B_{i + A_i} = \max(B_i + A_{i + A_i}, B_{i + A_i})$. Kết quả sẽ là $\max(B)$.
Ngoài lề: mất 1 sub vì làm naive method.
---
D - Even-Odd Game
Tóm tắt: Cho mảng A gồm n phần tử, có thể có nhiều phần tử giống nhau. Alice và Bob đang chơi một trò chơi trên mảng này:
- Alice đi trước.
- Mỗi người chơi chọn 1 phần tử trong mảng và bỏ nó ra khỏi mảng.
- Nếu Alice chọn phần tử chẵn thì cộng phần tử đó vào điểm của Alice và ngược lại, chọn phần tử lẻ thì không cộng phần tử đó vào điểm.
- Nếu Bob chọn phần tử lẻ thì cộng phần tử đó vào điểm của Bob và ngược lại, chọn phần tử chẵn thì không cộng phần tử đó vào điểm.
Trò chơi dừng lại khi mảng không còn phần tử. Tìm xem ai thắng nếu cả 2 đều chơi tối ưu nhất có thể?
Hướng dẫn giải: Algoritham.
Cách chơi tối ưu là mỗi người chơi sẽ chọn phần tử lớn nhất của mảng và bỏ đi, nếu chọn sai phần tử chẵn lẻ cũng là bỏ đi cơ hội cho người chơi kia.
Bài toán này dùng một std::vector sort thường xuyên là ổn, nhưng mình dùng cấu trúc dữ liệu std::multiset. Cấu trúc này có thứ tự và quan trọng là có cho phép các phần tử trùng nhau tồn tại trong cùng 1 multiset.
Ngoài lề: problem này mất 1 sub vì đặt datatype là int thay vì longint.
---
Happy coding!
No comments:
Post a Comment