Câu 1. (4,0 điểm)

Trong giờ toán học Minh được An đưa cho một con số với yêu cầu hãy biến đổi số đó thành số tối giản. An đưa ra quy tắc tìm số tối giản như sau: Tính tổng các chữ số của nó cho đến khi thu được số có một chữ số. Hãy giúp Minh lập trình giải bài toán trên.

Ví dụ: Cho số 12, ta có: 12 biến đổi 1+2=3. Vậy số tối giản của số 12 là 3.

Yêu cầu: Cho số nguyên dương N. Em hãy lập trình tìm số tối giản của N.

Dữ liệu vào: Một dòng duy nhất chứa số nguyên dương N (N ≤ 10⁹).

Kết quả: Một số duy nhất là số tối giản của N.

Ví dụ:

Câu 2. (4,0 điểm)

Tại vương quốc Baza nhà vua thường xuyên phải chuyển thư cho các Quý tộc ở địa phương, để đảm bảo tính bảo mật các mật thư luôn có một dãy mật mã. Các Quý tộc ở địa phương muốn đọc được nội dung thư cần tìm ra khóa trong dãy mật mã. Khóa là số có giá trị lớn nhất có trong dãy mật mã. Bạn hãy giúp các nhà Quý tộc địa phương tìm ra khóa.

Yêu cầu: Hãy tìm khóa trong dãy mật mã. Dữ liệu vào đảm bảo luôn có khóa.

Dữ liệu vào: Cho xâu ký tự S với độ dài không quá 1000 ký tự gồm các ký tự chữ cái và ký tự số. Các ký tự số liền nhau sẽ tạo thành một số duy nhất.

Kết quả: Khóa tìm được thỏa mãn yêu cầu bài toán.

Ví dụ:

Ràng buộc:
- Có 70% số test với các số có trong xâu có giá trị ≤ 10¹⁸.
- Có 30% số test với các số có trong xâu có giá trị > 10¹⁸.

Câu 3. (4,0 điểm)

Theo quan điểm của người Mazan những số đẹp là số có số lượng các ước của nó là số nguyên tố. Ví dụ: Số 9 có số lượng các ước là 3 gồm các ước (1, 3, 9) vì vậy số 9 là số đẹp. Bạn hãy giúp người Mazan tìm số lượng số đẹp trong đoạn từ 1 đến N cho trước.

Dữ liệu vào: Số nguyên dương N (1 ≤ N ≤ 10⁷).

Kết quả: Một số duy nhất là số lượng số đẹp trong đoạn từ 1 đến N.

Ví dụ:

Ràng buộc:
- Có 40% test tương ứng với 40% số điểm ứng với 1 ≤ N ≤ 10³.
- Có 30% test tương ứng với 30% số điểm ứng với 10³ < N < 5.10⁵.
- Có 30% test tương ứng với 30% số điểm ứng với 10⁶ < N ≤ 10⁷.

Câu 4. (4,0 điểm)

Trường THCS A chuẩn bị kỷ niệm 50 năm thành lập trường. Trong buổi kỷ niệm nhà trường có tổ chức một buổi khiêu vũ dạ hội và sẽ mời các thành viên trong câu lạc bộ (CLB) khiêu vũ của trường tham gia. Trong câu lạc bộ khiêu vũ của trường có N bạn nam và M bạn nữ đang tích cực tập luyện cho điệu nhảy như waltz, minuet, polonaise và quadrille...

Để buổi kỷ niệm diễn ra hoàn hảo nhất cô giáo giao cho trưởng CLB khiêu vũ chọn ra một số cặp đôi để tham gia buổi khiêu vũ sao cho kỹ năng khiêu vũ của các cặp đôi được chọn phải có độ chênh lệch không quá 1.

Với N bạn nam trong CLB mỗi bạn nam sẽ có kỹ năng khiêu vũ là a_i (i = 1,2,3,...,N).

Và M bạn nữ trong CLB mỗi bạn nữ sẽ có kỹ năng khiêu vũ là b_j (j = 1,2,3,...,M).

Yêu cầu: Hãy lập trình để xác định số lượng cặp đôi tối đa có thể được hình thành từ N bạn nam và M bạn nữ trong CLB của trường sao cho kỹ năng khiêu vũ của các cặp đôi không quá 1.

Dữ liệu vào:

- Dòng đầu tiên chứa một số nguyên N (1 ≤ N ≤ 10⁵) là số lượng các bạn nam trong CLB.
- Dòng thứ hai chứa dãy số a₁, a₂, …, a_N (1 ≤ a_i ≤ 10⁹), trong đó a_i là kỹ năng khiêu vũ của bạn nam thứ i.
- Dòng thứ ba chứa một số nguyên M (1 ≤ M ≤ 10⁵) là số lượng các bạn nữ trong CLB.
- Dòng thứ tư chứa dãy số b₁, b₂, …, b_M (1 ≤ b_j ≤ 10⁹), trong đó b_j là kỹ năng khiêu vũ của bạn nữ thứ j.

Kết quả: In ra một số duy nhất là số lượng cặp đôi tối đa có thể được hình thành.

Ví dụ:

Ràng buộc:
- Có 20% test tương ứng với 20% số điểm ứng với 1 ≤ N, M ≤ 10³; 0 < a_i, b_j ≤ 10⁶.
- Có 80% test tương ứng với 80% số điểm ứng với 10⁴ < N, M ≤ 10⁵; 10⁶ < a_i, b_j ≤ 10⁹.

Câu 5. (4,0 điểm)

Một sân Pickleball nhận được nhiều đơn đặt sân từ N đội chơi. Các đội chơi muốn sử dụng sân bóng trong khoảng thời gian từ a_i đến b_i và trả số tiền là c_i. Em hãy giúp chủ sân tính toán để sắp xếp lịch thuê sân làm sao nhận được nhiều tiền nhất và thỏa mãn điều kiện hai bất kỳ có khoảng thời gian sử dụng sân không giao nhau.

Dữ liệu vào:

- Dòng đầu là số nguyên dương N, là số đội đặt sân (1 < N ≤ 3000);
- N dòng sau mỗi dòng gồm 3 chỉ số a_i, b_i, c_i (1 ≤ a_i, b_i, c_i ≤ 10⁴).

Kết quả: Số tiền lớn nhất mà chủ sân nhận được.

Ví dụ:

Ràng buộc:
- 20% test tương ứng với 20% số điểm ứng với 1 ≤ N ≤ 100;
- 80% test tương ứng với 80% số điểm ứng với 100 < N ≤ 3000.