Codechef January Challenge 2020 - Division C

January Challenge này có rất nhiều chuyện để nói.

Đầu tiên, January Challenge này toàn là cheater. Đến nỗi có ông còn post hẳn một video tutorial lên YouTube trong khi contest mới mở được có 3 ngày. Kết quả là nhiều ông dính plagiarsm ngay, cá biệt ông up video ra đảo chả biết ngày nào về.

Tiếp theo, mình lại dành thời gian kéo rating trong khi đáng lẽ thời gian này mình nên chuẩn bị ôn thi cuối kỳ.

Và cuối cùng, đây là Division C và mình làm được 4 bài là do đề dễ, không phải mình giỏi.

---

DIVTHREE - Chef and Division 3

Tóm tắt đề bài: Có N người ra đề, người thứ i soạn được A[i] đề bài. Mỗi contest cần đúng K đề bài và một bài không được cho trùng trong các contest khác nhau. Biết rằng mỗi contest kéo dài D ngày và mỗi ngày chỉ được tổ chức một contest. Tìm xem có thể tổ chức contest trong nhiều nhất là bao nhiêu ngày liên tục?

Hướng dẫn: Toán. Nếu tổng số bài / K bài mỗi ngày > D ngày thì output D, ngược lại ta output tổng số bài / K.

(Tổng số bài = A[1] + A[2] + ... + A[N]).

Code mẫu (C++).

---

DECODEIT - Encoded String

Tóm tắt đề bài: Đây là bài toán mã hóa đơn giản và việc của bạn là giải mã. Quy tắc mã hóa đề bài đã nêu chi tiết nên mình sẽ không dịch lại trong đây.

Hướng dẫn: Tìm kiếm nhị phân. Nếu S[i] = '0' thì right = mid, ngược lại left = mid. Chú ý là mảng có độ dài chẵn nên thao tác tính mid phải cẩn thận.

Code mẫu (C++).

---

FAIRELCT - Fair Election

Tóm tắt đề bài: Cho 2 mảng A có độ dài N và B có độ dài M. Trong mỗi thao tác, bạn được hoán đổi A[i] và B[i]. Tìm số lần hoán đổi ít nhất để tổng mảng A lớn hơn tổng mảng B. Nếu không thể biến đổi, in -1.

Hướng dẫn: Algoritham. Hoán đổi các phần tử nhỏ nhất của A với các phần tử lớn nhất của B và đếm, dừng lại khi A > B.

Code mẫu (C++).

---

BILLRD - Point of Impact

Tóm tắt đề bài: Trên bàn billard kích thước N × N, một viên bi đang đứng ở vị trí (x, y). Viên bi được tác động một lực khiến nó di chuyển một góc 45º hướng lên trên (xem hình trong đề bài). Giả sử viên bi không chịu tác động của ma sát hay một ngoại lực khiến nó di chuyển không ngừng, khi đó viên bi sẽ đập vào cạnh đối diện của nó và dội lại với một góc 45º. Nếu viên bi đập vào một góc của bàn billard, nó sẽ không di chuyển nữa. Tìm tọa độ điểm va chạm lần thứ K của viên bi với cạnh bàn billard?

Hướng dẫn: Toán.

Ta chia giả thuyết làm 2 trường hợp:

• Trường hợp điểm xuất phát nằm trên đường chéo chính (y = x), khi đó đáp án luôn là góc trên bên phải của hình vuông. Do đó, đáp án là tọa độ (N, N).
• Với các trường hợp còn lại, ta nhận thấy hai điểm va chạm với cạnh bên phải và cạnh đáy đều nằm trên một đường thẳng có phương trình y = ax + b. Ta đã có góc xuất phát là 45º, tương đương với a = tan(45º) = 1. Với b = y - x, ta có hai điểm va chạm với cạnh bên phải và cạnh đáy nằm trên đường thẳng y = x - b. Với hai điểm va chạm với cạnh trên và cạnh bên trái, ta quan sát thấy hai điểm này đối xứng với hai nghiệm của phương trình y = x - b qua đường thẳng y = x. Nói cách khác, hai điểm còn lại cần tìm nằm trên đường thẳng y = x + b.

Tiếp theo, ta cần xét thứ tự va chạm:

• Nếu b > 0, nghĩa là ta xuất phát ở miền bên trên đường thẳng y = x. Khi đó thứ tự va chạm là cạnh trên > cạnh phải > cạnh đáy > cạnh trái. Khi đó C[0] = (n - b, n), C[1] = (n, n - b), C[2] = (b, 0), C[3] = (0, b).
• Nếu b < 0, ta xuất phát ở miền bên dưới đường thẳng y = x. Khi đó thứ tự va chạm là cạnh phải > cạnh trên > cạnh trái > cạnh đáy. Khi đó C[0] = (n, n + b), C[1] = (n + b, n), C[2] = (0, -b), C[3] = (-b, 0).

Để tìm được tọa độ va chạm lần thứ K, ta xét b và đáp án sẽ là C[(K - 1) mod 4] với từng trường hợp b tương ứng.

Code mẫu (C++).

---

Happy coding!