Đề thi Cuối kỳ môn Thuật toán ứng dụng - Kỳ 20201

Download

Đề thi CUỐI KỲ môn THUẬT TOÁN ỨNG DỤNG kỳ 20201

16/01/2021, Chỉ được phép truy cập vào trang nộp bài 202.191.56.251:18888/TTUD20201

Mục lục

CAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

LIS1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

GROUPUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ROUTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

MỌI HÌNH THỨC COPY BÀI NHAU ĐỀU BỊ XỬ LÝ KỶ LUẬT NẶNG!

Bài A. CAP

Cho 2 dãy số nguyên dương a = a₁, . . . , a_nvà b = b₁, . . . , b_m. Hãy đếm số lượng số nguyên dương x mà x xuất hiện

trong a và x xuất hiện trong b.

Dữ liệu vào

Dòng đầu chứa một số nguyên là số testcase: T (0 ≤ T ≤ 10). Tiếp theo, mỗi testcase được cho trên 4 dòng như

• Dòng đầu chứa số nguyên dương: n

• Dòng tiếp theo chứa dãy a: a₁a₂... a_n

• Dòng tiếp theo chứa số nguyên dương: m

• Dòng tiếp theo chứa dãy b: b₁b₂... b_m

Kết quả

Ghi ra T dòng, mỗi dòng là số lượng số xuất hiện trong cả hai dãy, tương ứng cho T testcase trong input.

Ví dụ

test

answer

2 1 4 3

1 5 4

Hạn chế

• 2 ≤ n ≤ 100, 1 ≤ a_i≤ 10⁹

Bài B. LIS1

Cho dãy số nguyên a. Dãy con của a là dãy thu được bằng cách xóa đi một số phần tử của a (có thể không xóa

phần tử nào, cũng có thể xóa hết tất cả). Một dãy con được gọi là đẹp nếu phần tử đứng sau lớn hơn phần tử

đứng trước đúng một đơn vị.

Yêu cầu: Hãy tìm dãy con đẹp dài nhất của dãy a.

Dữ liệu vào

Dòng đầu chứa một số nguyên là số testcase: T (0 ≤ T ≤ 10). Tiếp theo, mỗi testcase được cho trên 2 dòng như

Trang 1 trên 4

Đề thi CUỐI KỲ môn THUẬT TOÁN ỨNG DỤNG kỳ 20201

16/01/2021, Chỉ được phép truy cập vào trang nộp bài 202.191.56.251:18888/TTUD20201

• Dòng đầu chứa số phần tử của dãy a: n

• Dòng tiếp theo chứa dãy a

Kết quả

Ghi ra T dòng, mỗi dòng một số nguyên duy nhất là độ dài của dãy con đẹp dài nhất tìm được tương ứng với

testcase trong input.

Ví dụ

test

answer

3 1 2 4 3 5

Giải thích

Dãy con đẹp dài nhất là: 3 4 5. Một dãy con khác cũng đẹp và dài nhất là: 1 2 3

Hạn chế

• Trong tất cả các test: n ≤ 10⁵, 1 ≤ a_i≤ 10⁹

• 25% test với n ≤ 20

• 25% test tiếp theo với n ≤ 1000

• 25% test tiếp theo với 1 ≤ a_i≤ 10⁶

• 25% test còn lại không có ràng buộc gì thêm

Bài C. GROUPUP

Đêm Giao Thừa năm nay có n nhóm người tụ tập đứng dọc đường bờ hồ để xem pháo hoa. Các nhóm được đánh

số từ 1 đến n theo thứ tự từ đầu đường đến cuối đường, nhóm thứ i có a_ingười.

Sắp đến giờ xem pháo hoa, các nhóm này sẽ hợp nhất với nhau để tạo thành một nhóm duy nhất. Quá trình hợp

nhất nhóm diễn ra như sau:

• Nếu chỉ còn một nhóm thì dừng quá trình.

• Ngược lại, hai nhóm kề nhau sẽ hợp lại với nhau: Nhóm 1 hợp lại với nhóm 2, nhóm 3 hợp lại với nhóm 4,

... Nếu có lẻ nhóm, nhóm sau cùng sẽ không phải làm gì.

• Đánh số lại các nhóm mới từ đầu đường đến cuối đường, bắt đầu từ 1.

• Lặp lại bước một.

Thời gian cần để hai nhóm hợp nhất với nhau bằng tổng số người trong hai nhóm. Mỗi lần hợp nhất, các nhóm sẽ

thực hiện song song, sau đó chờ các nhóm khác thực hiện xong để tiếp tục lần hợp mới. Do đó thời gian cần cho

mỗi lần hợp nhất (tức mỗi vòng lặp) sẽ là lượng thời gian lớn nhất trong số các cặp nhóm cần hợp. Cụ thể, thời

gian mà k nhóm b₁, b₂, . . . , b_kcần để thực hiện một lần hợp nhất là max(b₁+ b₂, b₃+ b₄, . . . , b_k−1+ b_k) nếu k chẵn,

và max(b₁+ b₂, b₃+ b₄, . . . , b_k−2+ b_k−1) nếu k lẻ.

Yêu cầu: Hãy tính tổng thời gian hợp nhất của tất cả các nhóm người.

Dữ liệu vào

Dòng đầu chứa một số nguyên là số testcase: T (0 ≤ T ≤ 10). Tiếp theo, mỗi testcase được cho trên 2 dòng như

• Dòng đầu chứa số nguyên dương: n

Trang 2 trên 4

Đề thi CUỐI KỲ môn THUẬT TOÁN ỨNG DỤNG kỳ 20201

16/01/2021, Chỉ được phép truy cập vào trang nộp bài 202.191.56.251:18888/TTUD20201

• Dòng tiếp theo chứa dãy a: a₁a₂... a_n

Kết quả

Ghi ra T dòng, mỗi dòng là tổng thời gian tìm được tương ứng với testcase trong input.

Ví dụ

test

answer

3 1 2 5 4 3

Giải thích

Lần 1 mất max(3 + 1, 2 + 5, 4 + 3) = 7 đơn vị thời gian. Các nhóm sau đó: 4 7 7

Lần 2 mất 4+7=11 đơn vị thời gian. Các nhóm sau đó: 11 7

Lần 3 mất 11+7=18 đơn vị thời gian. Tổng là 36

Hạn chế

• 2 ≤ n ≤ 10⁵, 1 ≤ a_i≤ 100

• Có 50% số test với n ≤ 1000

Bài D. ROUTE

Trong kho có n điểm 1, 2, . . . , n chứa hàng. Biết rằng điểm i có lượng hàng là a_i(i = 1, . . . , n). Nhân viên kho vận

đứng tại cửa kho (điểm 0) và cần lấy 1 lượng hàng là Q. Biết d(i, j) là khoảng cách giữa điểm i và j (i, j = 0, 1, . . . , n).

Hãy tìm lộ trình cho nhân viên kho xuất phát từ cửa kho (điểm 0), đi qua 1 số điểm chứa hàng để lấy đủ lượng

hàng Q và quay trở ra cửa kho với tổng độ dài quãng đường là nhỏ nhất. Lưu ý là đến mỗi điểm lấy hàng i thì

không nhất thiết phải lấy hết toàn bộ lượng hàng a_i.

Đây là bài toán NP-khó có dạng Output-Only, nghĩa là bạn sẽ được cung cấp toàn bộ input chuẩn và bạn chỉ cần

nộp lên chấm output bạn tìm được. Kết quả output càng tốt thì điểm của bạn càng cao với cách tính điểm cho 1

test như sau:

• Gọi GK là tổng quãng đường cần đi theo kết quả của Ban giám khảo (giá trị này thí sinh không được biết,

chỉ dùng khi chấm), TS là tổng quãng đường cần đi theo kết quả của thí sinh.

T S−GK

• Đặt x =

• Nếu x < 0 bạn được 10 điểm cho test này.

• Nếu x ≥ 0 bạn được

điểm cho test này.

1+10∗x

Điểm của bài thi là tổng điểm của từng test, mỗi test đều tự động lấy điểm cao nhất của tất cả các lần nộp.

Bạn có thể nộp output từng test hoặc nén nhiều output thành file submission.zip rồi nộp (cần đặt tên các file là

output_0.txt, output_1.txt, ..., output_9.txt). Các input được cho sẽ đính kèm trên mục đề bài của hệ thống.

Bạn cũng được cho sẵn một file output ví dụ (output_0.txt) là một output hợp lệ cho input_0.txt.

Dữ liệu vào

Dữ liệu đầu vào có cấu trúc như sau:

• Dòng 1 ghi giá trị nguyên dương n, Q (1 ≤ n ≤ 50)

• Dòng 2 chứa n số nguyên không âm a₁, a₂, . . . , a_n(a_i≤ 10⁴, ∀i = 1, . . . n)

• Dòng i + 3(i = 0, . . . , n) ghi các phần tử ở hàng thứ i của ma trận d (1 ≤ d(i, j) ≤ 100)

Trang 3 trên 4

Đề thi CUỐI KỲ môn THUẬT TOÁN ỨNG DỤNG kỳ 20201

16/01/2021, Chỉ được phép truy cập vào trang nộp bài 202.191.56.251:18888/TTUD20201

Kết quả

Nếu không có hành trình nào lấy đủ lượng hàng Q thì in ra -1, ngược lại:

• Dòng đầu tiên ghi giá trị tổng quãng đường của lộ trình tìm được.

• Dòng tiếp theo chứa k là số lượng điểm lấy hàng

• Dòng tiếp theo ghi k số là vị trí các điểm lấy hàng theo thứ tự sẽ lấy

Ví dụ

test

answer

5 10

3 6 2 4 1

0 3 6 4 6 2

3 0 7 8 2 1

6 7 0 1 4 9

4 8 1 0 3 4

6 2 4 3 0 1

2 1 9 4 1 0

1 5 4 3

Giải thích

Hành trình ngắn nhất lấy đủ lượng hàng là 0 - 1 - 5 - 4 - 3 - 0 với độ dài là 3 + 1 + 1 + 3 + 4 = 12 và tổng lượng

hàng của các điểm đi qua là 3 + 1 + 4 + 2 = 10

Hạn chế

• Có 30% số test với n ≤ 10

• Có 30% số test với n ≤ 20

Trang 4 trên 4

4 trang Thùy Anh 13040

Download

Bạn đang xem tài liệu "Đề thi Cuối kỳ môn Thuật toán ứng dụng - Kỳ 20201", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

de_thi_cuoi_ky_mon_thuat_toan_ung_dung_ky_20201.pdf