Mọi người giúp em hướng giải của bài này với ạ.
Đây là hướng giải của em,nhưng lại bị sai ngay test 1 ạ:
-trong dãy số mình chọn ra 1 số a[i] sau đó đếm số lượng các số trong dãy là bội của a[i](gọi là d) rồi lấy d*a[i] sau đó chọn ra tích d*a[i] là lớn nhất.
Em cảm ơn!
Bạn tham khảo hướng giải thuật của mình thử xem nhé:
N: là số câu lạc bộ (CLB)
Mảng SL[i]: số lượng thành viên của CLB i
Phân tích về số lượng thành viên một đội có thể có:
Min: 2 thành viên. (vì không thể đội chỉ có 1 thành viên)
Max: số thành viên của CLB có nhiều thành viên nhất hay Max(SL)
Nếu gọi số thành viên của một đội là j thì số đội có thể vào chung kết chính là số CLB có số thành viên là bội số của j (Giả sử = m) => số Lập trình viên cuối cùng tham gia chung kết là m * j
Như vậy hướng giải sẽ như sau:
tạo biến đếm “dem” (để đếm số câu lạc bộ có thể tham gia sau khi chia đội)
Mảng A[j]: để lưu số lập trình viên tham gia chung kết nếu chia mỗi đội gồm j thành viên.
Bước 1: đếm số lập trình viên tham gia chung kết tương ứng với mỗi cách chia j thành viên
{
dem = 0
+ Cho biến i chạy từ 0 đến (N-1) //Duyệt qua các CLB
{
Nếu SL[i] chia hết cho j thì dem++
}
gán A[j] = dem * j
}
Bước 2: Tìm cách chia j có số lập trình viên tham gia chung kết ở bước 1 là lớn nhất
=> Max (A)
P/s: Có thể trong quá trình lưu A[j] sẽ có 1 mảng trung gian để link giữa A và j, tùy cách xử lý.
Biến j là mình sẽ cho chạy từ 2 đến max(SL) hay sao vậy ạ
Có thể nói rõ hơn giúp em được không ạ!
Số thành viên phải chia chẵn vậy thì nó sẽ ntn:
# pseudo
import NumberTheory as nt
def try(arr):
tmp = Hash.new(0)
for n in arr:
for teamCount in nt.TrialDivisors(n,range(1,sqrt(n)):
tmp[teamCount] += teamCount
tmp[n//teamCount] += n//teamCount
divisor = floor(sqrt(n))
tmp[divisor] += divisor if divisor*divisor == n
return tmp.max()
"""
def TrialDivisors(n, r = range(2..sqrt(n))
return lambda n : for i in r : yield i if n % i == 0
"""Đúng rồi đó. Ngân có thể tham khảo đoạn code sau (theo ngôn ngữ C) và điều chỉnh lại cho phù hợp yêu cầu bài toán:
Các biến sử dụng: n: Số CLB đăng ký tham gia; SL[size] là mảng lưu số lượng tương ứng của từng đội, Size là số tự nhiên nào đó đủ lớn để lớn hơn số CLB. VD: 1000; dem: biến đếm số CLB có thể thỏa điều kiện chia j thành viên, ThuTuCachChiaDoi: số thứ tự cách chia tương ứng với CachChia[ ] (j thành viên), SoTV[.]: mảng lưu số thành viên tham gia chung kết tương ứng cách chia thứ ThuTuCachChiaDoi và số thành viên 1 đội là CachChia [.] thành vien.
Ví dụ: Có 3 cách chia thành viên mỗi đội gồm {2,3,4} thành viên tương ứng số thành viên tham gia chung kết là {6,9,12} lập trình viên => ThuTuCachChiaDoi = 3, CachChia[1]=2;SoTV[1] = 6; CachChia[2]=3;SoTV[2] = 9; CachChia[3]=4;SoTV[3] = 12;
void main()
{
int SL[SIZE], n,dem,SoTV[SIZE],ThuTuCachChiaDoi=0, CachChia[SIZE];
NhapMang(SL, n); // Nhập số CLB tham gia. và số thành viên tương ứng mỗi đội
InPhanTuMang(SL, n); // Hiển thị số thành viên mỗi câu lạc bộ
printf("\n Phan tu lon nhat la: %d\n", Max(SL, n)); // In giá trị lớn nhất của mảng SL. Giả sử đã code hàm Max của mảng SL, n phần tử
for (int j = 2; j <= Max(SL, n); j++) //Biến j duyệt qua lần lượt số thành viên 1 đội có thể có
{
dem = 0; //Khởi tạo biến đếm để đếm số CLB có thể thỏa cách chia j thành viên
for (int i = 0; i < n; i++) //Duyệt qua lần lượt từng CLB
{
if (SL[i]%j==0) //Kiểm tra CLB i có thỏa cách chia j thành viên 1 đội không
dem++; // thỏa thì tăng biến đếm.
}
if (dem >1) //sau khi duyệt qua các đội, thì nếu với cách chia j thành viên, có dem > 1 CLB thì cách j sẽ được chọn. chỉ chọn cách có dem > 1 tương ứng với từ 2 CLB thỏa điều kiện trở lên mới hợp lý.
{
ThuTuCachChiaDoi++; // tăng thứ tự lên 1, chỉ xét từ 1 trở đi cho dễ hiểu.
CachChia[ThuTuCachChiaDoi] = j; //Lưu số thành viên 1 đội vào thứ tự chia tương ứng với j thành viên 1 đội (Mảng này sẽ có (ThuTuCachChiaDoi +1) phần tử
SoTV[ThuTuCachChiaDoi] = dem*j; // Lưu Số lập trình viên tham gia chung kết tương ứng thứ tự chia và cách chia j thành viên viên. Mảng này sẽ có (ThuTuCachChiaDoi +1) phần tử
}
}
printf("\nCo %d cach chia doi\n", ThuTuCachChiaDoi);
printf("\nCo %d thanh vien tham gia chung ket\n", Max(SoTV, ThuTuCachChiaDoi + 1));
for (int i = 1; i <= ThuTuCachChiaDoi; i++) //Duyệt qua lần lượt các cách chia có thể có
{
if (SoTV[i]==Max(SoTV,ThuTuCachChiaDoi+1)) (Cách chia nào có số lập trình viên tham gia chung kết là nhiều nhất
printf("\nChia moi doi: %d thanh vien se co so thanh vien tham gia chung ket la: %d\n", CachChia[i], SoTV[i]); // in ra số thành viên lớn nhất
}
Kỹ thuật BruteForce mình chưa biết đến. Vì mình không chuyên về lập trình. Cho mình hỏi là sao phải chia chẵn vậy @rogp10, Vì có thể là số lẻ mà.
Ban đầu mình cũng thắc mắc 
p/s: đã sửa ở trên
Nếu như vậy thì có thể là lẻ chứ phải không bạn. ví dụ: {3,2,6,12} thì cách chia là 3 thành viên 1 đội, và có 3 CLB tham gia: 1, 2, 4. số lập trình viên max là: 9
Không lẻ đâu mà [3, 2, 6, 12] thì ra 12 nhé 
Mình nhầm. :D. Nhưng nếu là {5,15,5,14,6} thì chia là 5 thành viên và max là 15 phải không bạn?
Đúng vậy
bài này tóm tắt lại là mỗi đội sẽ cử ra 1 đội để đi thi vòng chung kết, do đó nên giả sử chỉ có 1 thằng cũng phải đi thi =)) . Nói tóm lại là ta sẽ đưa bài toán này về tìm số lượng thành viên của mỗi đội sao cho số lượng đó xuất hiện nhiều nhất hoặc nói cách khác dễ hiểu hơn là
"Tìm ước chung của mỗi thằng a[i] sao cho nó xuất hiện nhiều nhất ".
Cách làm là ta sẽ sử dụng map để đếm số lần xuất hiện các ước của các a[i] . Kết quả là
max(số lần xuất hiện của một ước * chính ước đó)
int mx = -1e9-1;
for(auto x: cnt){
int u = x.fi, v = x.se;
mx = max(mx, u*v);
}
cout << mx;
cái này là cách làm của mình thôi ai có ý kiến hơn thì góp ý nhé
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?