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.
---
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.
---
Happy coding!
No comments:
Post a Comment