Mình vẫn nợ 1 bài code Lunchtime tháng 3 chưa viết editorial, cũng là bài duy nhất mình giải được trong contest này :(
Link đề bài trên Codechef - bản dịch tiếng Việt
Hướng dẫn giải:
Xét một số nguyên trong đoạn [1, 99]. Số đó có thể được biểu diễn dưới dạng 10*A + B, với A và B lần lượt là các số nguyên. VD: 28 = 10*2 + 8 (A = 2, B = 8), 56 = 10 * 5 + 6 (A = 5, B = 6).
Nếu lấy 28 + 56, ta có các khả năng swap vị trí như sau: 28 + 56, 68 + 52, 25 + 86. Chúng ta không xét tới các khả năng 58 + 26 hay 26 + 58, vì 2 khả năng này cho kết quả như nhau (và cùng bằng 28 + 56), lý do là vì tính chất giao hoán của phép cộng đều cho kết quả như nhau.
Đối với trường hợp phép cộng giữa một số có 2 chữ số với một số chỉ có 1 chữ số (VD: 12 + 9), ta vẫn swap vị trí như trên, nhưng lúc này chỉ còn 1 vị trí có thể swap (91 + 2). Trường hợp còn lại là phép cộng giữa 2 số có 1 chữ số thì tổng lớn nhất là tổng của 2 số đó, không cần swap.
Code mẫu (C++)
Happy coding!
No comments:
Post a Comment