Một thầy trong trường mình từng bảo, "chỉ khi nào các em vứt bỏ được sự thông minh, khi đó các em mới làm Toán được". Tối hôm qua mấy cái problem này là Toán, nhưng thực ra chỉ cần suy nghĩ đơn giản tí là xong.
Dù là làm việc gì cũng phải suy nghĩ cẩn thận nhưng mình lại là một giống loài đặc biệt gì đấy luôn làm hỏng những gì đơn giản nhất bằng cách phức tạp hóa vấn đề đến một mức độ mà bản thân mình cũng ngạc nhiên là làm sao lại suy nghĩ làm gì cho cực. Đến khổ/
Tóm tắt: Một mảng được gọi là tốt nếu tổng các phần tử của mảng đó bằng 0. Cho mảng A có N phần tử; trong mỗi phép biến đổi bạn chọn một vị trí i và giảm phần tử thứ A[i] một khoảng i (i.e i = 5 thì bạn có thể giảm A[5] mỗi lần 5 đơn vị). Xác định xem với một mảng A[i] cho trước, sau một số phép biến đổi (tùy ý) bạn có thể đưa mảng A trở thành một mảng tốt hay không?
Hướng giải: Chỉ cần xác định tổng các phần tử ban đầu trong mảng lớn hơn hoặc bằng (≥) 0 thì mảng A có thể đưa về mảng tốt. (Giải thích xem ở link bên dưới).
---
Tóm tắt: Xét mảng A gồm N phần tử, A[i] = i. Với mỗi phép biến đổi, bạn được chọn 2 chỉ số i và j, tính ước chung lớn nhất (GCD) của A[i] và A[j] sau đó gán A[i] = A[j] = GCD(A[i], A[j]). Cho mảng B cũng có N phần tử, có thể biến đổi mảng A thành mảng B sau một số phép biến đổi (tùy ý) hay không?
Hướng giải: bài này duyệt trâu cũng AC. Tuy nhiên nếu chúng ta quan sát thì dễ dàng nhận ra mảng A chỉ có thể biến đổi thành mảng B khi và chỉ khi A[i] mod B[i] = 0 (i.e B[i] là ước của A[i]), với mọi i từ 1 đến N. (Giải thích xem ở link bên dưới)
Link đến file giải thích cho các công thức trong bài. Happy coding!
No comments:
Post a Comment