Unlock premium benefits with premium membership. No ads, VIP access to private groups, special discounts on Bitcoin products and exciting contests with big prizes. Go Premium now and take charge of your Bitcoin journey. Don’t miss out, Download App Now: https://www.linkedin.com/posts/the-bitcoin-app_thebitcoinapp-premiummembership-gopremium-activity-7294699368736002048-PSmX?utm_source=share&utm_medium=member_desktop #thebitcoinapp #premiummembership #gopremium #bitcoincommunity #bitcoinrewards #digitalcurrency #gettheapp #bitcoin #bitcoinlife #bitcoinbenefits #bitcoinjourney

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Chúc các bạn học tốt và gặt hái nhiều thành công 🥰 Trước khi đi vào vấn đề chính của bài thì mình muốn các bạn phải đảm bảo biết qua điều này để về sau các bạn xem mới hiểu: Với các hệ thống web chấm bài giới hạn thời gian chạy của bài tối đa chỉ được 1 giây thì các bạn sẽ rất dễ bị rơi vào lỗi Time Limit Exceeded (TLE: Chạy quá giới hạn thời gian cho phép). Thì như mình đã nói rất nhiều lần là với các hệ thống web chấm bài hiện nay nếu không muốn bị TLE thì tối đa số phép toán trên toàn bài của các bạn chỉ nên ở ngưỡng (3 đến 5)*10^7 là ngưỡng an toàn với phần lớn hệ thống chấm bài, hoặc với một số hệ thống chấm server mạnh hơn thì có thể nâng ngưỡng lên 10^8 nhưng cũng hên xui nhé. Và thực ra ta không phải đếm chi tiết từng số phép toán trên toàn bài mà ta dựa theo số lần vòng lặp chạy bởi bên trong vòng lặp là nó xử lý lặp đi lặp lại nhiều phép toán nên cứ canh theo đó, các bạn cứ hiểu là tối đa toàn bài chỉ nên lặp (3 đến 5)*10^7 lần là an toàn hoặc tệ nhất là 10^8 (lúc này thì hên xui nhé) còn vượt ngưỡng này là khả năng TLE rất cao nhe. Lưu ý là ngưỡng mình vừa nói ở trên là với ngôn ngữ C/C++ thôi nhé chứ nếu với những ngôn ngữ khác như Python, C# hay Java nó chạy chậm hơn C/C++ thì ngưỡng đó phải thấp hơn, hoặc người ra đề sẽ chủ động đưa ra giới hạn nếu nộp với C/C++ thì thời gian chạy quy định tối đa 1 giây, các ngôn ngữ khác thì 2 giây. Và ngưỡng mình đưa ra ở trên nếu với đề cho thời gian 2 giây thì các bạn cứ tỷ lệ thuận nhân 2 lên với ngưỡng, 3 giây thì nhân 3, nếu 100 ms tức là 1/10 giây thì các bạn chia 10 cho ngưỡng đó nhé, cứ thế thôi. Rồi thì như bài này đưa ra thời gian chạy giới hạn là 1 giây nên cứ như ở trên mình đã nói nhé. Giờ ta đi phân tích cách giải quyết cho bài này. --------------------------------------------------- Trước tiên mình sẽ tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu như sau: Cho 1 mảng a có n số nguyên (1 <= n <= 10^5) a[i] với (1 <= i <= 10^5; 1 <= a[i] <= 10^5). Ở mỗi bước ta có thể chọn phần tử a[k] và xoá nó, sau đó tất cả phần tử có giá trị a[k] + 1 và a[k] - 1 cũng sẽ bị xoá bỏ. Bước đó sẽ cho mình a[k] điểm. Hãy lấy càng nhiều điểm càng tốt; in ra số điểm lớn nhất có thể lấy được. Ví dụ: n = 9. Dãy là: 1, 2, 1, 3, 2, 2, 2, 2, 3. Ta sẽ thấy có 5 phần tử có giá trị = 2; 2 phần tử có giá trị = 1; 2 phần tử có giá trị = 3. Cách tối ưu nhất là đầu tiên ta sẽ chọn phần tử có giá trị = 2; sau đó mọi phần tử có giá trị = 1 và = 3 sẽ bị xoá; ta được 2 điểm; còn 4 phần tử có giá trị = 2. Và ta sẽ chọn 4 phần tử đó nữa và kết quả sẽ = 10 thôi. --------------------------------------------------- Đầu tiên để thực hiện được bài này; ta sẽ cần phải thực hiện vài bước nho nhỏ. Ta sẽ dễ dàng nhận thấy là nếu ta chọn phần tử 2 thì ta sẽ lấy mọi phần tử 2; vì nếu ta chọn phần tử a[i] thì tất cả phần tử có giá trị a[i] - 1 và a[i] + 1 sẽ bị xoá rồi nên nếu còn phần tử a[i] thì ta lấy nữa cũng không vấn đề. Vậy với ví dụ trên có 5 phần tử 2 thì khi ta chọn phần tử 2 thì điểm ta nhận được sẽ là 2 * 5 = 10; vì có 5 phần tử 2 và ta sẽ lấy hết các phần tử 2. Để thực hiện được điều trên thì ta sẽ phải đi đếm xem vỡi mỗi số ở đầu vào sẽ xuất hiện bao nhiêu lần. Ta sẽ làm việc đó bằng cách tạo một mảng cnt để đếm các phần tử xuất hiện bao lần. Và ta sẽ tạo 1 vector<int> a để lưu trữ các phần tử khác nhau. Ví dụ ta đọc vào được số 3; ta sẽ check cnt[3] có = 0 không; nếu có thì ta sẽ cho vào vector a vì đó là lần đầu nó xuất hiện; còn không thì chứng tỏ xuất hiện rồi thì ta sẽ không cho vào. Và để có thể làm bài này dễ hơn thì sau khi thực hiện bước trên ta đã có vector a chứa các phần tử khác nhau ở đầu vào; giờ ta cần sắp xếp cho dãy tăng dần. Để khi ta lấy phần tử a[i] thì ta có thể chắc chắn rằng phần tử có giá trị a[i] - 1 nếu có thì sẽ nằm ở vị trí i - 1; phần tử có giá trị a[i] + 1 nếu có thì sẽ nằm ở vị trí i + 1. Điều này các bạn ngẫm chút là sẽ thấy; vì ta đang sắp xếp dãy các phần tử phân biệt tăng dần mà. Nên nếu ví dụ ta chọn phần tử 3 và phần tử 3 đang ở vị trí số 2 chẳng hạn; thì nếu có phần tử có giá trị = 3 - 1 = 2 thì nó phải nằm ở vị trí số 2 - 1 = 1; nếu có phần tử có giá trị = 3 + 1 = 4 thì nó phải nằm ở vị trí số 2 + 1 = 3. Vậy tổng kết lại ở đầu vào ta sẽ cần đếm số lần xuất hiện của mỗi phần tử, cho cái phần tử khác nhau vào 1 vector và sau đó phải sắp xếp vector đó theo thứ tự tăng dần nha. --------------------------------------------------- Cách làm đầu tiên của bài này sẽ là vét cạn nha, tức là ta sẽ thử mọi trường hợp đó. Cách làm này sẽ dùng tới đệ quy và sẽ khá là phức tạp cho bạn nào chưa quen với đệ quy, nhưng nó là cách dễ nghĩ tới nhất vì ý tưởng của nó là thử mọi trường hợp có thể xảy ra mà. Giờ mình sẽ phân tích rồi cài đặt để hi vọng các bạn sẽ học được thêm điều gì đó. Ý tưởng là ở mỗi phần tử ta sẽ đứng giữa lựa chọn hoặc chọn hoặc không chọn; và khi chọn thì ta sẽ phải kiểm tra rằng có được chọn hay không. Lúc này ta sẽ gán n = số phần tử khác biệt trong dãy. Vậy thì ta sẽ đi từ phần tử 1 tới phần tử n; ở mỗi phần tử ta sẽ lần lượt không chọn rồi chọn; nếu chọn thì khi tới với phần tử tiếp theo mà ta muốn chọn nó thì ta phải kiểm tra xem nó có thoả mãn điều kiện đề bài không. Nói cách khác giả sử ta chọn phần tử i, thì khi đi tới phần tử i + 1 mà ta muốn chọn phần tử i + 1 thì ta phải check a[i + 1] != a[i] + 1 thì ta mới được chọn. Vì ta chọn phần tử a[i] thì mọi phần tử a[i] + 1 sẽ bị xoá hay chính là không được chọn mà. Cụ thể ta sẽ tạo 1 hàm Try(int i, int notThis, long long sum) sẽ giúp ta thử mọi trường hợp với i là vị trí phần tử ta đang xét; notThis chính là phần tử ta không được lấy; và sum là tổng điểm ta đang có được. Đầu tiên ta phải check i <= n để đảm bảo phần tử đang xét vẫn nằm trong mảng; sau đó ta sẽ đến với trường hợp ta không chọn phần tử i; đồng nghĩa với việc phần tử tiếp theo mà ta chuẩn bị xét không có điều kiện gì ràng buộc cả, vậy biến notThis ta sẽ cho = 0. Vì a[i] >= 1 nên sẽ không có phần tử 0 nên biến tiếp theo kiểu gì cũng khác 0 mà. Và vì ta không lấy nên số điểm ta đang có vẫn giữ nguyên. Vậy với trường hợp không chọn ta sẽ gọi đệ quy là Try(i + 1, 0, sum). Còn nếu chọn thì ta sẽ phải kiểm tra là a[i] != notThis; tức là khác phần tử ta không được lấy đó. Nếu khác thì ta sẽ gọi đệ quy tiếp nhưng lúc này notThis chính là a[i] + 1 và sum sẽ được + thêm là a[i] * cnt[a[i]] nha. Vậy nếu a[i] != notThis thì ta sẽ gọi Try(i + 1, a[i] + 1, sum + a[i] * cnt[a[i]]). Và giờ ta cần có trường hợp để dừng đệ quy lại; ở trên là khi ta check i <= n; vậy khi i > n tức là trường hợp else đó thì chứng tỏ đã có 1 cách chọn trong n phần tử khác biệt đó vậy ta sẽ có một biến res để lưu kết quả là biến toàn cục; ở trường hơp này ta sẽ cập nhật biến res tức là res = max(res, sum). Sau đây là source code cho các bạn tham khảo cách làm trên của mình nha: #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const int N = (int)1e5; int cnt[N + 5], n; ll res = 0; vector<int> a; void Try(int i, int notThis, ll sum) { if(i <= n) { Try(i + 1, 0, sum); if(a[i] != notThis) { Try(i + 1, a[i] + 1, sum + a[i] * cnt[a[i]]); } } else { res = max(res, sum); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; a.push_back(-1); for(int i = 1; i <= n; ++i) { int x; cin >> x; if(cnt[x] == 0) { a.push_back(x); } cnt[x]++; } sort(a.begin(), a.end()); n = a.size() - 1; Try(1, 0, 0); cout << res; return 0; } Giải thích 1 số chỗ trong cách làm trên: 1/ 3 dòng đầu tiên của hàm main (ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ) sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài mà cần nhập xuất nhiều thì ta nên sử dụng 3 dòng trên. Ví dụ với bài này thì đầu vào có thể lên tới 10^5 số. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 3 dòng này vào đầu hàm main nhé. 2/ a.push_back(-1); Đoạn này chính là vì ta đang xét các phần tử theo vị trí từ 1 tới n nên là ta sẽ thêm 1 phần tử vào trước để nó là phần tử thứ 0 cho các phần tử ta thêm vào sẽ bắt đầu từ phần tử 1. 3/ n = a.size() - 1; Đoạn này thì vì lúc đầu ta đã thêm phần tử -1 vào để làm phần tử thứ 0 nên số phần tử khác biệt của dãy sẽ chỉ là a.size() - 1 thôi. 4/ Try(1, 0, 0); Vì ta sẽ bắt đầu từ phần tử đầu tiên nên i = 1; lúc đầu ta không có điều kiện gì cả nên notThis = 0; và biến tổng tức là sum lúc đầu cũng = 0. Đánh giá độ phức tạp của cách làm trên: - Độ phức tạp không gian (Space Complexity):O(n). Vì ta đang dùng 1 mảng cnt và 1 vector để lưu số phần tử khác biệt; nên nếu ở trường hợp xấu nhất tất cả các phần tử đều khác nhau thì vector sẽ có độ lớn là n phần tử giống như đầu vào. - Độ phức tạp thời gian (Time Complexity): Để mà tính chính xác thì mình cũng khó mà tính được cho các bạn; nhưng nếu mà nộp code trên thì sẽ bị TLE ở test 29 nha, mà bài trên có 53 test lận nha. Và các trường hợp mà AC thì giá trị N (hiểu ở đây là số phần tử khác biệt) chỉ <= 20 thôi. Vậy cách trên không thể AC được rồi, tuy nhiên hãy vẫn nên cài đặt nó để sau này ta lấy nó làm công cụ kiểm tra tính chính xác cho cách làm tối ưu. Bạn nào có chưa biết cách lấy nó làm công cụ kiểm tra tính chính xác thì có thể xem qua bài viết này của mình nha: https://www.facebook.com/100003824621962/posts/2303526743118124/?d=n --------------------------------------------------- Giờ ta sẽ đến cách làm tối ưu hơn để AC bài này nha. Để mà có thể AC được bài này thì ta sẽ dùng phương pháp quy hoạch động (Dynamic Programming) để giải quyết nha các bạn. Cho bạn nào đã biết cơ bản về quy hoạch động rồi thì ta có 4 bước như sau: Bước 1: Xác định bài toán con: Gọi F[i] (0 <= i <= n) là số điểm nhiều nhất ta có thể có được khi xét i phần tử đầu tiên. Bước 2: Xác định bài toán cơ sở: Khi ta xét 0 phần tử nào thì chắc chắn ta sẽ không có điểm nào rồi. Vậy F[0] = 0. Khi ta xét 1 phần tử đầu tiên thì số điểm lớn nhất ta lấy được chính là a[1] * cnt[a[1]] vì ta chỉ lấy được phần tử 1 thôi mà. Vậy F[1] = a[1] * cnt[a[1]]. Chốt lại ta sẽ có F[0] = 0; F[1] = a[1] * cnt[a[1]]. Bước 3: Xác định đáp án của bài toán: Hiển nhiên sẽ là F[n] rồi; ở đây các bạn lưu ý n là số phần tử khác biệt trong vector mình lưu nha. Vì ta cần in ra số điểm nhiều nhất ta có thể có được khi xét n phần tử khác biệt nên đáp án chính là F[n]. Bước 4: Xác định công thức truy hồi: Giờ giả sử ta đang xét phần tử i. Ta sẽ kiểm tra xem liệu ta có thể lấy được nó không bằng cách kiểm tra if(a[i] != a[i - 1] + 1) tức là phần tử ta đang xét thoả mãn điều kiện đề bài đó, vì nếu ta dù có chọn hay không chọn phần tử a[i - 1] thì phần tử a[i] cũng sẽ không bị xoá. Vậy ở trường hợp này (a[i] != a[i - 1] + 1) thì F[i] sẽ bằng số điểm nhiều nhất ta có thể có được khi xét i - 1 phần tử đầu tiên + số điểm ta nhận được khi lấy phần tử a[i]. Vậy ta sẽ có F[i] = F[i - 1] + a[i] * cnt[a[i]] khi a[i] != a[i - 1] + 1. Vậy còn trường hợp mà a[i] == a[i - 1] + 1 thì sao. Ở đây phải nhớ rằng F[i] sẽ lưu số điểm lớn nhất mà ta có thể có được khi xét i phần tử đầu tiên nhé chứ không bắt buộc ta phải lấy phần tử thứ i hay không đâu. Vậy từ đó F[i - 1] có thể lấy hoặc không lấy phần tử i - 1 tuỳ vào trường hợp nào lớn hơn thôi. Bạn nào mà thấy hơi lú thì đọc chút nữa rồi ngẫm là ra nha; lúc này ta sẽ đối diện 2 trường hợp đó là: - Trường hợp 1 (gọi tắt là TH1): Ta có lấy phần tử a[i] nhưng chắc chắn ta sẽ không được lấy phần tử i - 1. Và để có số điểm lớn nhất thì ta sẽ lấy số điểm nhiều nhất ta có thể có được khi xét i - 1 phần tử đầu tiên mà không lấy phần tử thứ i - 1 rồi + với số điểm ta lấy được khi lấy phần tử a[i] thôi. Và để ý nếu ta xét i - 1 phần tử đầu tiên mà không lấy phần tử thứ i - 1 thì khác gì đang xét i - 2 phần tử đầu tiên đâu. Vậy đó chính là F[i - 2] đó; từ đó ở trường hợp mà ta có lấy phần tử a[i] thì số điểm lớn nhất ta nhận được chính là = số điểm lớn nhất ta có thể có được khi xét i - 2 phần tử đầu tiên + số điểm ta lấy được khi lấy phần tử a[i]. Vậy ở trường hợp này F[i] = F[i - 2] + a[i] * cnt[a[i]] - Trường hợp 2 (gọi tắt là TH2): Ta không lấy phần tử a[i] nữa. Vậy đương nhiên là số điểm lớn nhất khi xét i phần tử đầu tiên sẽ = số điểm lớn nhất khi xét i - 1 phần tử đầu tiên rồi. Vậy F[i] = F[i - 1]. Và vì F[i] là số điểm lớn nhất có thể nên F[i] sẽ = max(TH1, TH2) và sẽ là F[i] = max(F[i - 1], F[i - 2] + a[i] * cnt[a[i]]) khi a[i] == a[i - 1] + 1. Vậy từ đó ta có công thức truy hồi sau: if(a[i] == a[i - 1] + 1) thì F[i] = max(F[i - 1], F[i - 2] + a[i] * cnt[a[i]]); else F[i] = F[i - 1] + a[i] * cnt[a[i]]. Sau đây là source code cho các bạn tham khảo cách làm trên của mình nha: #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const int N = (int)1e5; int cnt[N + 5]; ll f[N + 5]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector<ll> a; a.push_back(-1); for(int i = 1; i <= n; ++i) { int x; cin >> x; if(cnt[x] == 0) { a.push_back(x); } cnt[x]++; } n = a.size() - 1; sort(a.begin(), a.end()); f[0] = 0; f[1] = a[1] * cnt[a[1]]; for(int i = 2; i <= n; ++i) { if(a[i] == a[i - 1] + 1) { f[i] = max(f[i - 1], f[i - 2] + a[i] * cnt[a[i]]); } else { f[i] = f[i - 1] + a[i] * cnt[a[i]]; } } cout << f[n]; return 0; } Đánh giá độ phức tạp của cách làm trên: - Độ phức tạp không gian (Space Complexity): O(n). Chính xác thì mình sẽ dùng tận 3 mảng luôn đó nhưng theo quy tắc bigO thì vẫn là O(n) nha. - Độ phức tạp thời gian (Time Complexity): O(nlogn) vì lớn nhất là từ bước gọi hàm sort. Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪 . Vậy nên đừng tiếc gì cho mình một like nha để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇.

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé, các bạn nào chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen: http://lequydon.ntucoder.net/Problem/Details/6005 Trước khi đi vào vấn đề chính của bài thì mình muốn các bạn phải đảm bảo biết qua điều này để về sau các bạn xem mới hiểu: Với các hệ thống web chấm bài giới hạn thời gian chạy của bài tối đa chỉ được 1 giây thì các bạn sẽ rất dễ bị rơi vào lỗi Time Limit Exceeded (TLE: Chạy quá giới hạn thời gian cho phép). Thì như mình đã nói rất nhiều lần là với các hệ thống web chấm bài hiện nay nếu không muốn bị TLE thì tối đa số phép toán trên toàn bài của các bạn chỉ nên ở ngưỡng (3 đến 5)*10^7 là ngưỡng an toàn với phần lớn hệ thống chấm bài, hoặc với một số hệ thống chấm server mạnh hơn thì có thể nâng ngưỡng lên 10^8 nhưng cũng hên xui nhé. Và thực ra ta không phải đếm chi tiết từng số phép toán trên toàn bài mà ta dựa theo số lần vòng lặp chạy bởi bên trong vòng lặp là nó xử lý lặp đi lặp lại nhiều phép toán nên cứ canh theo đó, các bạn cứ hiểu là tối đa toàn bài chỉ nên lặp (3 đến 5)*10^7 lần là an toàn hoặc tệ nhất là 10^8 (lúc này thì hên xui nhé) còn vượt ngưỡng này là khả năng TLE rất cao nhe. Lưu ý là ngưỡng mình vừa nói ở trên là với ngôn ngữ C/C++ thôi nhé chứ nếu với những ngôn ngữ khác như Python, C# hay Java nó chạy chậm hơn C/C++ thì ngưỡng đó phải thấp hơn, hoặc người ra đề sẽ chủ động đưa ra giới hạn nếu nộp với C/C++ thì thời gian chạy quy định tối đa 1 giây, các ngôn ngữ khác thì 2 giây. Và ngưỡng mình đưa ra ở trên nếu với đề cho thời gian 2 giây thì các bạn cứ tỷ lệ thuận nhân 2 lên với ngưỡng, 3 giây thì nhân 3, nếu 100 ms tức là 1/10 giây thì các bạn chia 10 cho ngưỡng đó nhé, cứ thế thôi. Rồi thì như bài này đưa ra thời gian chạy giới hạn là 1 giây nên cứ như ở trên mình đã nói nhé. Giờ ta đi phân tích cách giải quyết cho bài này. Thì mình giải thích rõ đề bài để bạn nào chưa hiểu thì sẽ hiểu rõ, là ta có N là số gạo cần lấy, ta có 2 loại xô là xô 3 kg và xô 5 kg. Thì nguyên tắc mỗi lần chọn xô nào để múc là phải múc đầy xô đó chứ không có chuyện múc thiếu nha các bạn, hỏi xem phải múc với số lần ít nhất là bao nhiêu lần để múc đủ hết N số gạo cần lấy ? In ra đáp án số lần múc ít nhất đó, còn nếu không thể múc được đủ N số gạo với quy tắc múc ở trên thì in ra -1 Ví dụ: 1/ Nếu N = 10 thì ta có đáp án là 2 => 5 + 5 = 10 2/ Nếu N = 11 thì ta có đáp án là 3 => 5 + 3 + 3 = 11 3/ Nếu N = 12 thì ta có đáp án là 4 => 3 + 3 + 3 + 3 = 12 4/ Nếu N = 7 thì đáp án là -1 Bài này cũng nhiều dạng tương tự nên mình sẽ nói theo cách tổng quát như sau: Có 2 số A, B với nguyên tắc A < B (mình cố tình chọn A, B để các bạn hiểu A đứng trước, B đứng sau trong bảng chữ cái, để hình tượng cho dễ là A < B nhé). Như trong bài này thì A = 3, B = 5. Thì hãy xem cần tính tổng bao nhiêu số A cộng nhau cũng như bao nhiêu số B cộng nhau (không nhất thiết phải có đủ cả 2 giá trị A B, có thể chỉ có 1 trong 2) sao cho được tổng bằng N ? Và hãy đưa ra đáp án sao cho ít số cộng lại với nhau nhất. Như ví dụ khi N = 18 thì ta có thể là: 5 + 5 + 5 + 3 = 18 (4 lần cộng) nhưng cũng có thể là 3 + 3 + 3 + 3 + 3 + 3 = 18 (6 lần cộng) và đáp án sẽ tính theo số lần cộng ít nhất tức là 4 lần. Còn nếu không có cách nào để cộng lại với nhau ra được tổng bằng N thì ta sẽ in -1. Thì bài này ta có thể áp dụng phương pháp tham lam (greedy) để giải quyết. Kể cả bạn nào có không biết về phương pháp tham lam này thì thực ra đôi khi các bạn đang giải quyết vấn đề theo chính tư tưởng của tham lam mà các bạn không biết. Cho bạn nào không biết thì mình có thể nói nhanh như thế này: Tham lam ở đây nghĩa là ta sẽ cố gắng chọn ra cách giải quyết tốt nhất trong tất cả các cách ở hiện tại rồi đi theo cách giải quyết tốt nhất đó nếu lại đứng trước nhiều lựa chọn cách giải quyết khác nhau nữa thì ta lại cố gắng chọn theo cách giải quyết tốt nhất trong số đó tóm lại cứ tốt nhất mà triển vì thế tên gọi nó là tham lam. Quy luật nó là như vậy thôi chứ còn lại không có công thức từng bước cụ thể giải quyết như mấy thuật toán khác. Mà ta có thể giải quyết theo cách bất kỳ miễn cái tư tưởng mà ta giải quyết luôn là chọn theo hướng tốt nhất trong các lựa chọn thì đó chính là tư tưởng của tham lam. Thì tại sao bài này lại có thể nhìn ra tư tưởng của nó là tham lam? Đọc đề bài là thấy rõ mùi rồi hehe muốn xử lý theo quy luật gì gì đó để sau cùng đáp án phải là nhỏ nhất/lớn nhất các kiểu, đọc kiểu này phát thấy mùi tham lam ngay Thì thực ra tham lam chỉ là dạng tư tưởng thôi, còn lại để hiện thực được nó thì có thể cần đến những kỹ thuật bổ trợ khác nữa. Mình lấy ví dụ ngay trong chính bài tập này, các bạn cứ tiếp tục xem nhé. Thì ta có thể nhìn ra một số vấn đề như sau: Ví dụ nếu N mà chia hết cho B (là số lớn nhất trong 2 số) thì chắc chắn đáp án sẽ là N / B đúng không các bạn? Ví dụ A = 3, B = 5 và N = 15 thì chắc chắn đáp án sẽ là 15 / 5 = 3 tức là 5 + 5 + 5 = 15 đúng không các bạn? Mình tin tư duy này nhiều bạn sẽ nhìn ra ngay vì nó quá rõ, vì nếu có thể chia hết cho số lớn nhất thì kết quả sau khi chia sẽ là kết quả nhỏ nhất (tỷ lệ nghịch). Vậy nếu N không chia hết cho B (số lớn nhất) thì ta phải xử lý thế nào? Lúc này đây tư tưởng tham lam hiểu là ta sẽ tính X = N / B là kết quả phần nguyên của phép chia, và Y = N % B là kết quả phần dư của phép chia. Trong trường hợp hiện tại nghĩa là Y sẽ khác 0 (vì không chia hết). Thì lúc này đây ta kiểm tra xem phần dư Y này có chia hết cho A luôn không? Nếu có thì đáp án sẽ là X + Y / A. Ví dụ: A = 3, B = 5, N = 13 thì ta tính ra được X = 13 / 5 = 2, Y = 13 % 5 = 3, và ta thấy Y % A = 0 (Y chia hết cho A) => đáp án sẽ là: X + Y / A = 2 + 3 / 3 = 2 + 1 = 3. Còn nếu trong tình huống phần dư Y không chia hết cho A, ví dụ khi A = 3, B = 5, N = 16 thì X = 16 / 5 = 3, Y = 16 % 5 = 1 thì 1 không chia hết cho 3. Lúc này đây ta sẽ giảm bớt 1 giá trị của X điều đó nghĩa là Y sẽ được cộng với B, sau đó kiểm tra nếu Y chia hết cho A thì kết quả sẽ là X + Y / A. Nếu Y vẫn không chia hết cho A thì lại tiếp tục giảm bớt 1 giá trị của X và tiếp tục Y được cộng thêm với giá trị B rồi lại kiểm tra xem Y có chia hết cho A không? Cứ thế lặp đến khi nào Y chia hết A hoặc khi nào X đã về 0 thì không thể giảm được nữa, nếu vẫn không tìm ra trường hợp nào Y chia hết cho A thì kết luận -1. Như ví dụ trên thì giảm X còn 2, Y được cộng thêm 5 thành 6, thì 6 chia hết cho 3 => đáp án: 2 + 6/3 = 2 + 2 = 4. Còn nếu A = 3, B = 5, N = 7 thì ta thấy X = 7 / 5 = 1, Y = 7 % 5 = 2, thấy Y không chia hết cho A, giảm X xuống còn 0, Y += 5 => Y = 7, 7 không chia hết cho 3, lúc này không giảm X được nữa vì X đã là 0 => kết quả là -1 Vậy tổng quát lại có thể phát biểu ý tưởng giải quyết bài này như sau: Hàm xử lý nhận đầu vào 3 tham số kiểu số nguyên là N, A, B (ràng buộc A < B ). Hàm trả về kiểu số nguyên là kết quả. Quy trình xử lý trong hàm như sau: Vòng lặp for khởi tạo X = N / B, Y = N % B. Điều kiện lặp X >= 0 và bước lặp X--; Bên trong vòng lặp xét nếu Y chia hết cho A thì return X + Y / A. Nếu không thì Y += B. Trước khi kết thúc hàm thì return -1; tức là nếu nó còn chạy được xuống đó mà không kết thúc trước đó (kết thúc trong vòng lặp) nghĩa là không có giá trị Y thỏa mãn chia hết cho A thì kết quả sẽ là -1. Source code để các bạn tham khảo nếu làm theo hướng này: #include <iostream> using namespace std; int solve(int n, int a, int b){ for(int x = n / b, y = n % b; x >= 0; --x){ if(y % a == 0){ return x + y / a; } y += b; } return -1; } int main(){ int n; cin >> n; cout << solve(n, 3, 5); return 0; } Đánh giá độ phức tạp của cách làm này: + Độ phức tạp không gian (Space Complexity): O(1) + Độ phức tạp thời gian (Time Complexity): Trong trường hợp xấu nhất vòng lặp có thể sẽ chạy đủ N / B + 1 lần (vì từ N / B về 0). Như thế số lần chạy nhiều nhất sẽ là khi N lớn nhất theo như đề bài công bố và B nhỏ nhất theo như đề bài công bố thì kết quả N / B sẽ là lớn nhất. Thì ta thấy N tối đa là 4999 và B mặc định là 5, nên 4999 / 5 + 1 = 1000 lần lặp. Như thế thì yên tâm không thể bị TLE vì với giới hạn thời gian chạy 1 giây thì số lần lặp tối đa được phép ở ngưỡng (3 đến 5) * 10^7 hay cao lắm là 10^8 nên 10^3 là quá nhỏ so với ngưỡng vì thế ta yên tâm. Đến đây lẽ ra xong rồi, tuy nhiên mình cũng nói thêm cái này. Là bài này các test case trên web còn yếu lắm, bài bạn học viên mình nộp AC (và nhiều bạn khác cũng AC) tuy nhiên khi mình chạy code của các bạn đó với tool test của mình thì phát hiện ra nhiều trường hợp cùng dữ liệu đầu vào mà code của mình và code của các bạn ấy ra kết quả khác nhau điều đó nghĩa là code các bạn ấy bị sai với trường hợp đó (vì mình đảm bảo cách làm trên của mình là chính xác). Nên mình cũng muốn các bạn hãy thử dựa theo code giải trên của mình tự đi xây dựng ra tool test tự động để từ đó so với bài làm của các bạn xem có phát hiện trường hợp nào bị sai không nhé. Phần hướng dẫn làm tool test tự động mình có hướng dẫn tại bài viết này các bạn có thể xem: https://www.facebook.com/100003824621962/posts/2303526743118124/?d=n Dưới đây mình cũng share code tool test của mình để các bạn cùng tham khảo và thử kiểm tra code các bạn với tool xem có sai trường hợp nào không nhé: #include <iostream> #include <ctime> using namespace std; int solve1(int n, int a, int b){ for(int x = n / b, y = n % b; x >= 0; --x){ if(y % a == 0){ return x + y / a; } y += b; } return -1; } // để code các bạn trong hàm này nhé int solve2(int n, int a, int b){ return -1; } int main() { srand(time(0)); while(1){ int n = 1 + rand() % 4999; int res1 = solve1(n, 3, 5); int res2 = solve2(n, 3, 5); if(res1 == res2){ cout << "OK\n"; } else{ cout << "FAIL" << endl; cout << "n = " << n << endl; cout << "res1 = " << res1 << endl; cout << "res2 = " << res2 << endl; break; } } return 0; } Hàm solve1 là code của mình, code của các bạn sẽ để trong hàm solve2 nhé, hiện tại hàm đó đang mặc định return -1; các bạn để code các bạn vào và trả về kết quả tương ứng với dữ liệu N đầu vào. Rồi chạy chương trình lên nếu treo cỡ 5 phút mà thấy chỉ toàn chữ OK thì các bạn có thể yên tâm các bạn code đáp án chính xác còn nếu phát hiện trường hợp sai thì chương trình sẽ dừng lại ngay và in ra trường hợp sai cụ thể với res1 là đáp án đúng của mình và res2 là đáp án của các bạn trong trường hợp đó để các bạn có thể kiểm tra lại. Lời kết: Mình cũng nói luôn là cách giải trên chưa phải là cách tối ưu nhất cho dạng bài này. Do bài này giới hạn độ lớn dữ liệu (N, A, B ) nhỏ nên nếu các bạn lấy code trên nộp lên web thì thấy time chỉ 15 ms. Tuy nhiên có bài này tương tự nhưng độ lớn dữ liệu lớn hơn rất nhiều, nếu các bạn lấy code trên nộp thì vẫn AC nhưng time > 900 ms (như lúc mình nộp là time 921 ms) trong khi đó nếu các bạn xem trong số những người đã AC sẽ thấy có những người time chỉ 15 ms điều đó cho thấy thuật toán ở trên chưa phải là tối ưu nhất. Các bạn hãy cố gắng suy nghĩ cách làm tối ưu hơn để time được 15 ms như những người nhanh nhất cho bài này nhé, mình hẹn sẽ có bài giải trong một ngày gần nhất để các bạn tham khảo, đây là đề bài để các bạn thử thách: http://ntucoder.net/Problem/Details/3297 Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪 . Vậy nên đừng tiếc gì cho mình một like nha để động viên mình nè . Chúc anh em học tốt và gặt hái nhiều thành công 😇