Saturday 24 July 2021

Codeforces Round #734 (Div. 3) - A & B

 Một contest mà mình feed nhiều thời gian ngu nhất, cuối cùng rating tụt thê thảm.

Nguồn ảnh

Tạm thời mình không code contest nữa, đồ án cuối kỳ tới rồi :(

---

A - Polycarp and Coins

Tóm tắt: Cho số nguyên dương $n$. Tìm $2$ số nguyên $c_1, c_2\  (c_1, c_2 \geq 0)$ sao cho $c_1 + 2c_2 = n$ và $|c_1 - c_2|$ đạt giá trị nhỏ nhất. 

Giải: Toán

  • Nếu $n \equiv{0} \pmod{3}$ thì $\displaystyle c_1 = c_2 = \frac{n}{3}$. Khi đó $|c_1 - c_2| = 0$.

  • Nếu $n \equiv{1} \pmod{3}$ thì $\displaystyle c_1 = \frac{n}{3} + 1,\ c_2 = \frac{n}{3}$. Khi đó $|c_1 - c_2| = 1$.

  • Nếu $n \equiv{2} \pmod{3}$ thì $\displaystyle c_1 = \frac{n}{3},\ c_2 = \frac{n}{3} + 1$. Khi đó $|c_1 - c_2| = 1$.

Code mẫu (C++).

Nhận xét: Chủ yếu bài này phải quan sát và tìm ra pattern chung. Tuy nhiên mình quan sát ngu nên mất $2$ sub!

---

B - Wonderful Coloring -  1

Tóm tắt: Tô một xâu bằng $2$ màu xanh, đỏ sao cho

  • Các chữ cái giống nhau phải có màu khác nhau
  • Số lượng chữ cái màu xanh bằng số lượng chữ cái màu đỏ
  • Có thể không tô một chữ cái.
  • Số lượng chữ cái được tô màu là nhiều nhất.
Xác định số lượng chữ cái tô màu xanh (hoặc đỏ - sao cũng được vì $2$ số này bằng nhau).

Giải: Algoritham.

  • Nếu xâu chỉ có $1$ loại chữ cái duy nhất thì đây là trường hợp duy nhất không thể tô. Output $0$ cho lẹ.
  • Còn lại thì ta xài algoritham thôi: 

    • nếu một chữ cái xuất hiện $\geq 2$ lần thì chỉ lấy $2$ chữ tô $2$ mầu, số còn lại không tô.
    • một chữ cái xuất hiện $1$ lần thì đếm vào biến $\text{spare}$, cuối cùng tô một nửa số $\text{spare}$ mầu xanh và nửa còn lại mầu đỏ.

Code mẫu (C++).

Nhận xét: Bài toán không khó, chủ yếu là đừng ngu như mình!

---

Happy coding!

No comments:

Post a Comment

Popular posts