BÀI 1: (4.0 điểm)

Cho dãy số A đã được sắp xếp tăng dần và số X. Hãy tìm vị trí xuất hiện đầu tiên và cuối cùng của X trong dãy. Nếu không thấy X in ra -1 -1.

Dữ liệu: Dòng 1: n, X (n <= 10^5). Dòng 2: Dãy a.

Kết quả: Hai số nguyên là vị trí đầu và vị trí cuối (tính từ 1).

Ràng buộc: n <= 10^5.

Ví dụ:

Ví dụ 1:

Input:

6 2 
1 2 2 2 3 4

Output:

2 4

Ví dụ 2:

Input:

5 10 
1 2 3 4 5

Output:

-1 -1

BÀI 2: (4.0 điểm)

Cho dãy số A gồm n số nguyên và số nguyên K > 0. Hãy đếm số lượng cặp (i, j) sao cho a[i] - a[j] = K.

Dữ liệu: Dòng 1: n, K (n <= 10^5). Dòng 2: Dãy a (a_i <= 10^9).

Kết quả: Số lượng cặp số.

Ràng buộc: Dùng Map hoặc Sắp xếp + Hai con trỏ.

Ví dụ:

Ví dụ 1:

Input:

4 2 
1 5 3 4

Output:

2

(Cặp 3-1=2, 5-3=2)

Ví dụ 2:

Input:

3 10 
1 2 3

Output:

0

BÀI 3: (4.0 điểm)

Mộc muốn chặt gỗ để xây nhà. Hiện tại có N cây gỗ với độ cao khác nhau. Mộc cài đặt máy cưa ở độ cao H. Tất cả phần cây cao hơn H sẽ bị cắt (lấy phần ngọn), phần thấp hơn giữ nguyên. Mộc cần tổng độ dài gỗ thu được ít nhất là M. Hãy tìm H lớn nhất để Mộc lấy đủ gỗ nhưng không lãng phí.

Dữ liệu: Dòng 1: N, M (N <= 10^6, M <= 2*10^9). Dòng 2: Độ cao các cây.

Kết quả: Độ cao H lớn nhất.

Ràng buộc: Dùng Chặt nhị phân trên kết quả (Binary Search on Answer).

Ví dụ:

Ví dụ 1:

Input:

4 7 
20 15 10 17

Output:

15

(Cắt ở 15: 20->5, 15->0, 10->0, 17->2. Tổng 7. Đủ M=7)

Ví dụ 2:

Input:

5 20 
4 42 40 26 46

Output:

36

BÀI 4: (4.0 điểm) TỪ ĐIỂN Cho danh sách n từ. Hãy sắp xếp các từ này theo nguyên tắc: từ ngắn hơn đứng trước, nếu cùng độ dài thì xếp theo thứ tự từ điển (Alphabet).

Dữ liệu: n (n <= 10^5) và danh sách từ.

Kết quả: Danh sách sau khi sắp xếp.

Ràng buộc: Xây dựng hàm so sánh (Comparator) tùy chỉnh.

Ví dụ:

Ví dụ 1:

Input:

4 
abc a ab ad

Output:

a ab ad abc

Ví dụ 2:

Input:

2 
tin hoc

Output:

hoc tin

BÀI 5: (4.0 điểm)

Một kẻ trộm đột nhập vào nhà với một cái túi có sức chứa tối đa W kg. Trong nhà có N đồ vật, vật thứ i có trọng lượng wi và giá trị vi. Hãy chọn các vật để bỏ vào túi sao cho tổng giá trị là lớn nhất mà tổng trọng lượng không quá W.

Dữ liệu: Dòng 1: N, W (N <= 100, W <= 10^5). N dòng sau: wi, vi.

Kết quả: Giá trị lớn nhất.

Ràng buộc: N <= 100, W <= 10^5.

Ví dụ:

Ví dụ 1:

Input:

3 4 
1 1 
2 3 
3 4

Output:

5 (

Chọn vật 1 và 3: trọng lượng 1+3=4, giá trị 1+4=5)

Ví dụ 2:

Input:

2 10 
5 10 
6 20

Output:

20