Codeforces Round #719 (Div. 3) - A, B & D

 Code nhiều vẫn ngu

Nay blog đã hỗ trợ LaTeX!

---

A. Do Not Be Distracted!

Tóm tắt: Cho xâu $s$, xác định xem mỗi chữ cái giống nhau trong $s$ có xuất hiện liên tiếp nhau hay không?

Hướng dẫn: Duyệt + đánh dấu cơ bản. Bài này mình kết hợp std::map để đánh dấu ký tự đã xuất hiện trước đó hay chưa.

Code mẫu (C++)

---

B. Ordinary Numbers

Tóm tắt: Một số nguyên $n$ được gọi là tầm thường khi nó được tạo nên từ các chữ số giống nhau (xem ví dụ trong đề). Cho $n$, tìm số lượng số tầm thường trong đoạn $[1, n]$. 

Hướng dẫn: Phương pháp sinh.

Ta nhận xét: 

• trong phạm vi 1 chữ số có 9 số tầm thường: $1, 2, .., 9$.
• trong phạm vi 2 chữ số cũng có 9 số tầm thường: $11, 22, .., 99$
• ...
• trong phạm vi $k$ chữ số ($k \leq$ số chữ số của $n$) cũng có 9 số tầm thường: $ s, 2s, .., 9s $ với $\displaystyle s = \sum_{i = 0}^{k - 1} 10^{i}$.

Vậy ta có thể sinh ra một số $ s_1 $ gồm $k$ chữ số 1 ($ \displaystyle s_1 = \sum_{i = 0}^{k - 1} 10^{i}, 1 \leq k \leq 9$), sau đó duyệt qua $s_1 \times j$ với $1 \leq j \leq 9$. Khi nào $s_1 \times j > n$ thì dừng lại.

Đến đây nhiều bạn sẽ suy luận, vậy sẽ tốn ít nhất $O(n^2)$ cho bài toán này và dễ TLE!

Thật ra nếu ta để ý kỹ, ràng buộc cho $n$ trong bài là $1 \leq n \leq 10^9$, nghĩa là tối đa $n$ chỉ có 9 chữ số. Do đó, trong trường hợp xấu nhất ta phải sinh ra $s_1$ có độ dài từ 1 đến 9, rồi so sánh lần lượt từ $ s_1 .. 9s_1 $. Tổng cộng tối đa số lần sinh + so sánh chỉ có 81 lần, dư sức AC.

Code mẫu trong bài mình có áp dụng std::stringstream mà mình học được từ môn OOP. Cơ bản là mình sinh 1 xâu toàn ký tự '1', sau đó dùng stoi convert lại longint.

Code mẫu (C++)

---

D. Same Differences

Tóm tắt: Cho mảng số nguyên $a$ gồm $n$ phần tử. Đếm số cặp $(i, j)$ sao cho $ i < j $ và $ a_j - a_i = j - i$.

Hướng dẫn: Tổ hợp.

$a_j - a_i = j - i \iff a_j - j = a_i - i$. Để 2 vế bằng nhau thì cả $a_j - j$ và $a_i - i$ phải cùng bằng một hằng số $c$. Khi đó từ mảng ban đầu ta tính toán, thu được một mảng các hằng số $c_1, c_2, .., c_k$ mà trong đó kết quả ta cần thu được là số lượng cặp có thể tạo ra từ các hằng số $c_k$ giống nhau. (*)

Giả sử ta có $x$ phần tử. Số cặp có thứ tự có thể chọn từ $x$ phần tử là $\displaystyle \frac{x(x - 1)}{2}$. Khi đó, đáp án là $\displaystyle \sum_{i = 1}^{k} \frac{c_i(c_i - 1)}{2}$ .

Code mẫu (C++)

---

Happy coding!