Tài liệu hướng dẫn giải đề thi đợt 8 UIT Code Contest 2021

Đề Bài:  Số hạnh phúc

Ý tưởng: sử dụng vòng lặp để tách từng con số, bình phương và cộng chúng lại với nhau, các số trước khi tách ra để bình phương cộng vào thì sẽ được lưu vào một mảng. Cộng được một số mới và kiểm tra số đó đã xuất hiện trong mảng đã lưu trước đó (nếu tiếp tục cộng thì sẽ thành vòng lặp vô hạn) thì số đó không phải số hạnh phúc,  hoặc nếu tổng bình phương của từng chữ số bằng 1 thì số đó là số hạnh phúc.

Xử lí đầu vào: số đầu tiên là số lượng phần tử cần để kiểm tra, n số tiếp theo sẽ kiểm tra theo thuật toán ở trên, nếu là số hạnh phúc thì biến đếm tăng lên 1 đơn vị.

Đề Bài  : Tặng bút

Vấn đề này có thể được giải quyết bằng một kỹ thuật tham lam.

Ở đây đề thể hiện tặng Ci cây bút cho sinh viên i.

Phân loại sinh viên thành 4 loại, tùy thuộc vào sự so sánh điểm số tích lũy của sinh viên i với hai người hàng xóm i-1, i+1.

Nếu SV(i-1)>=SV(i)<=SV(i+1) thì SV(i) này loại 1.

Nếu SV(i-1)<SV(i)<=SV(i+1) thì SV(i) này loại 2.

Nếu SV(i-1)>=SV(i)>SV(i+1) thì SV(i) này loại 3.

Nếu SV(i-1) < SV(i) > SV(i+1) thì SV(i) này loại 4.

Đối với SV ở vị trí đầu danh sách và với SV cuối danh sách, giả sử họ có một người hàng xóm xếp ở số thứ tự vô hạng, thì khi đó danh sách này có thể được phân loại như trên.

Với sự phân loại này ta có thể phân phối bút như sau:

– Đối với sinh viên loại 1, hãy tặng họ 1 cây bút.

– Đối với sinh viên loại 2, hãy tặng họ C(i-1)+1 cây bút.

– Đối với sinh viên loại 3, hãy tặng họ C(i+1)+1 cây bút.

– Đối với sinh viên loại 4, hãy tặng họ max(C(i-1),C(i+1))+1 cây bút.

Sau đây là một phương án để phân phối tối ưu theo quy tắc trên:

– Phân phối 1 cây bút đến các sinh viên loại 1.

– Phân phối bút cho các sinh viên loại 2 từ trái sang phả.

– Phân phối bút cho các sinh viên loại 3 từ phải sang trái.

– Cuối cùng phân phối bút cho các sinh viên loại 4.

Đề Bài : Cuộc thi đánh giá năng lực

Sau khi đọc qua bài toán ta có thể tóm tắt lại bài toán như sau: Đếm số lượng tập hợp con có thể tạo được trong mảng mà tổng giá trị chia kết cho số k.

Sử dụng giải thuật vét cạn sẽ đúng nhưng không thể giải quyết với bài toán có dữ liệu lớn.

Ý tưởng: Sử dụng Qui hoạch động

-Hàm mục tiêu:  Gọi F[i][x]  là tổng số tập hợp trong đoạn từ 1 đến i có tổng chia cho k dư x.

-Công thức truy hồi:

F[i][x] = (F[i][x] + F[i – 1][x] + F[i – 1][x_old]) % base  (Với i = 2 à n, j = 0 à k – 1)

Tính F[i – 1][x_old]:

if x – A[i] < 0:

x_old = (x + k – A[i]  %  k) % k;

else:

x_old = x – A[i]  %  k;

-Bài toán cơ sở:

F = {0};

F[i][A[i] % k]++; (Với i = 1 à n)

-Kết quả bài toán: F[n][0].

Hy vọng tài liệu trên đây sẽ giúp các bạn chưa đạt được 300đ trong đợt 8 vừa rồi sẽ tìm được hướng giải cho mình, cũng như cải thiện và nâng cao thuật toán của bản thân trong thời gian sắp tới.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *