Giúp hướng giải của bài tập

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

  • Cho biến j chạy từ 2 đến Max ( SL) //Đây là số thành viên một đội có thể có
{
   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ý.

2 Likes

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 ạ!:cry:

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
"""
4 Likes

Đú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à.

3 Likes

Ban đầu mình cũng thắc mắc :smiley:

p/s: đã sửa ở trên

2 Likes

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

1 Like

Không lẻ đâu :smiley: mà [3, 2, 6, 12] thì ra 12 nhé :slight_smile:

3 Likes

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 :slight_smile:

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?