Codechef January Lunchtime 2021 - Division C

 Vẫn là một contest bị unrate do server lỗi.

---

SUMPOS - Pair Me

Tóm tắt: Cho 3 số nguyên $x, y, z$. Tìm xem 3 số nguyên trên có thỏa

• $x + y = z$ hoặc
• $x + z = y$ hoặc
• $y + z = x$

Hướng dẫn giải: cakewalk, 1 câu lệnh điều kiện là xong. 

Code mẫu (C++).

---

EVENDIFF - Even Differences

Tóm tắt: Mảng a gồm n phần tử nguyên. Trong mỗi thao tác, bạn được chọn một vị trí i và gán $a_i := a_i + 1$ Xác định xem bạn phải thực hiện thao tác trên ít nhất bao nhiêu lần để với mỗi vị trí $i, j (1 \leq i, j \leq n), a_i - a_j$ chẵn.

Hướng dẫn giải: Toán.

Hai số nguyên $x$ và $y$ có $x - y$ chẵn khi và chỉ khi

• $x$ và $y$ đều chẵn hoặc
• $x$ và $y$ đều lẻ.

Vậy, ta chỉ cần đếm tổng số chẵn và tổng số lẻ trong mảng, sau đó output ra số lượng số nhỏ hơn. Giả sử ta có 3 số chẵn và 5 số lẻ $(n = 8)$, khi đó với mỗi số chẵn ta sẽ cộng 1 để được 8 số lẻ và thỏa yêu cầu đề bài. Ta cũng có thể lấy 5 số lẻ và cộng 1 vào mỗi số để được 8 số chẵn, nhưng khi đó tổng số thao tác thực hiện không thỏa điều kiện ít thao tác nhất.

Code mẫu (C++).

---

EVENGAME - Even Sum

Tóm tắt: Có 2 người đang chơi một trò chơi trên mảng $a$ gồm $n$ số nguyên. Trong mỗi lượt chơi, người chơi có thể đặt dấu cho một phần tử $a_i$ là $+a_i$ ($a_i$ dương) hoặc $-a_i$ ($a_i$ âm). Đến cuối cùng, tất cả các phần tử trong mảng được cộng hết lại. Nếu tổng mảng chẵn, người chơi 1 thắng và ngược lại, người chơi 2 thắng. Giả sử số lượng lượt chơi bằng với số lượng phần tử của mảng và người chơi chỉ có thể đặt dấu cho những phần tử chưa có dấu. Tìm xem ai sẽ là người thắng, nếu mỗi người đều chơi tối ưu nhất?

Hướng dẫn giải: Algoritham.

Nếu tổng của mảng $a$ từ ban đầu đã chẵn thì người 2 chắc chắn sẽ thắng, ngược lại người 1 chắc chắn thắng.

Code mẫu (C++).

---

INTRVS - Ashishgup and Interviews

Tóm tắt: Ashishgup muốn tổ chức một buổi phỏng vấn tuyển thêm nhân viên. Những người được phỏng vấn phải giải $n$ bài toán trên hệ thống chấm online. Dữ liệu bài làm của ứng viên được lưu trong một mảng $a$, với phần tử $a_i$ là thời gian giải bài toán thứ $i$. Nếu $a_i = -1$, ứng viên đó không giải được bài toán $a_i$. Kết quả trúng tuyển của người đó được chấm như sau:

• Nếu ứng viên giải được $< \left \lceil{\frac{n}{2}}\right \rceil$ (i.e làm tròn lên) bài, Rejected.
• Nếu ứng viên không nhận được verdict Rejected nhưng tốn nhiều hơn $k$ giây để giải một bài toán $a_i$ bất kỳ, Too Slow.
• Nếu ứng viên không nhận được 1 trong 2 verdict bên trên, nhưng có thời gian thực hiện bất kỳ bài toán $a_i$ nào $\leq 1$ giây, khi đó người này là Bot.
• Còn lại, người này được nhận, Accepted.

Hướng dẫn giải: Cứ theo mô tả mà làm.

Code mẫu (C++).

---

BINSUBS - Binary Subsequence

Tóm tắt: Cho xâu nhị phân $s$ gồm $n$ ký tự $0$ hoặc $1$. Tìm độ dài xâu con nhỏ nhất cần xóa đi để xâu $s$ không giảm dần $(s_i \geq s_{i - 1}\ \forall i \in [1, n - 1])$.

Hướng dẫn giải: Algoritham.

Để thu được một xâu con không giảm dần thì ta chỉ cần loại bỏ các yếu tố giảm - $10$. Ở đây không cần dùng 2 con trỏ mà chỉ cần dùng một stack là được: nếu phần tử trên cùng của stack là $1$ và phần tử đang xét là $0$ thì pop stack, còn lại thì cứ thêm vào stack. Đếm tổng số lần pop stack, ta thu được kết quả.

Code mẫu (C++).

---

Ngoài lề: Bài cuối mình làm được 30 điểm, nhưng cay cái là tạch duy nhất 1 test trong tổng số 15 test 70 điểm.

Tuy nhiên mình vẫn không thể đoán được testcase đó là gì, nên vẫn chỉ có 30/100.

Happy coding.