Educational Codeforces Round 102 (Rated for Div. 2) - A & B

 Một may mắn cho mình, join contest trễ 1 tiếng. May làm sao, mình AC 2 bài trong 2 đấm và may mắn lắm mới không bị trừ điểm mà được +5.

AC 2 bài là do may, không phải mình giỏi.

---

A - Replacing Elements

Tóm tắt đề bài: Cho mảng a gồm n phần tử. Trong một thao tác, bạn có thể chọn một bộ i, j, k khác nhau từng đôi một, sau đó gán a[i] = a[j] + a[k]. Xác định xem sau một số lượng thao tác nhất định, liệu ta có thể biến đổi mảng sao cho mỗi phần tử của mảng ≤ d hay không?

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

Ta có thể biến đổi mảng a khi và chỉ khi một trong hai trường hợp sau xảy ra:

• a[i] ≤ d, ∀ i ϵ [1, N].
• Tồn tại một bộ j, k (j ≠ k) sao cho a[j] + a[k] ≤ d.

Code mẫu (C++).

---

B - String LCM

Tóm tắt đề bài: xâu a là ước của xâu b nếu tồn tại một số nguyên x sao cho viết xâu a lặp đi lặp lại x lần sẽ thu được xâu b. Cho hai xâu s, t, tìm một xâu mà cả s và t đều là ước của xâu đó.

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

Độ dài xâu kết quả = LCM(độ dài xâu s, độ dài xâu t). Từ đó, ta có thể tạo ra một xâu kết quả từ xâu có độ dài nhỏ hơn trong hai xâu s và t. Cuối cùng, kiểm tra xem s và t có phải là ước của xâu đó hay không.

Code mẫu (C++).

---

Happy coding!