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

Cho một xâu họ tên nhập từ bàn phím khá lộn xộn (thừa khoảng trắng, chữ thường chữ hoa lẫn lộn). Hãy chuẩn hóa về dạng: Chữ cái đầu mỗi từ in hoa, các chữ còn lại in thường, mỗi từ cách nhau đúng 1 khoảng trắng.

Dữ liệu: Xâu S.

Kết quả: Xâu S sau khi chuẩn hóa.

Ví dụ:

Ví dụ 1:

Input:

nguYen VAN aN

Output:

Nguyen Van An

Ví dụ 2:

Input:

le thi Be

Output:

Le Thi Be

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

Cho số nguyên dương N. Hãy liệt kê tất cả các hoán vị của các số từ 1 đến N theo thứ tự từ điển.

Dữ liệu: N (N <= 9).

Kết quả: Mỗi dòng một hoán vị.

Ràng buộc: N <= 9.

Ví dụ:

Ví dụ 1:

Input:

2

Output:

1 2 
2 1

Ví dụ 2:

Input:

3

Output:

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

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

Cho xâu S. Hãy tìm độ dài của xâu con (liên tiếp) đối xứng dài nhất trong S.

Dữ liệu: Xâu S (độ dài <= 2000).

Kết quả: Độ dài xâu con đối xứng dài nhất.

Ràng buộc: độ dài xâu <= 2000

Ví dụ:

Ví dụ 1:

Input:

abacaba

Output:

7

Ví dụ 2:

Input:

banana

Output:

5

(anana)

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

Hai từ được gọi là Anagram (đảo chữ) của nhau nếu chúng có cùng các ký tự với số lượng như nhau (chỉ khác thứ tự). Cho danh sách N từ, hãy đếm số nhóm Anagram.

Dữ liệu:

Dòng 1: N.

N dòng tiếp theo: các từ.

Kết quả: Số lượng nhóm.

Ràng buộc:

Ví dụ: "listen" và "silent" là cùng nhóm.

Ví dụ:

Ví dụ 1:

Input:

3 
act 
cat 
dog

Output:

2

(Nhóm 1: act, cat. Nhóm 2: dog)

Ví dụ 2:

Input:

2 
a b

Output:

2

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

Cho bản đồ kích thước NxM gồm nước (ký hiệu 0) và đất liền (ký hiệu 1). Các ô đất liền kề nhau (trên, dưới, trái, phải) tạo thành một đảo. Hãy đếm số lượng đảo.

Dữ liệu: Dòng 1: N, M (N, M <= 1000).

N dòng sau: Ma trận 0/1.

Kết quả: Số lượng đảo.

Ràng buộc:

Dùng BFS hoặc DFS (Thuật toán Loang).

Ví dụ:

Ví dụ 1:

Input:

3 3 
1 0 1 
1 0 0 
0 0 1

Output:

3

Ví dụ 2:

Input:

2 2 
1 1 
1 1

Output:

1