Học sinh giỏi 9 Lào Cai 2025-2026

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\).

Input

• Một dòng duy nhất chứa số nguyên dương \(N\) \((N \le 10^9)\).

Output

• Một số duy nhất là số tối giản của \(N\).

Example

5432

5

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.

Input

• 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.

Output

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

Example

A12bcde543cec123

543

Scoring

• Có \(70\%\) số test với các số có trong xâu có giá trị \(\le 10^{18}\).
• Có \(30\%\) số test với các số trong xâu có giá trị \(> 10^{18}\).

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.

Input

• Số nguyên dương \(N\) \((1 \le N \le 10^7)\).

Output

• Một số duy nhất là số lượng số đẹp trong đoạn từ \(1\) đến \(N\).

Example

10

6

Scoring

• Có \(40\%\) số test/điểm ứng với \(1 \le N \le 10^3\).
• Có \(30\%\) số test/điểm ứng với \(10^3 \le N \le 5 \times 10^5\).
• Có \(30\%\) số test/điểm ứng với \(10^6 \le N \le 10^7\).

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 các đ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 đối tác trong mỗi cặp đôi phải 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,\ldots,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,\ldots,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 để tham gia lễ kỷ niệm 50 năm thành lập trường thỏa mãn điều kiện độ chênh lệch về kỹ năng khiêu vũ của các đối tác trong mỗi cặp đôi không quá 1.

Input

• Dòng đầu tiên chứa một số nguyên \(N\) \((1 \le N \le 10^5)\) là số lượng các bạn nam trong CLB.
• Dòng thứ hai chứa dãy số \(a_1, a_2, \ldots, a_N\) \((1 \le a_i \le 10^9)\), 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 \le M \le 10^5)\) là số lượng các bạn nữ trong CLB.
• Dòng thứ tư chứa dãy số \(b_1, b_2, \ldots, b_M\) \((1 \le b_j \le 10^9)\), trong đó \(b_j\) là kỹ năng khiêu vũ của bạn nữ thứ \(j\).

Output

• 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.

Example

4
1 4 6 2
5
5 1 5 7 9

3

4
4 2 3 6
4
8 9 8 10

0

Scoring

• Có \(20\%\) số test/điểm ứng với \(1 \le N, M \le 10^3\); \(0 < a_i, b_j \le 10^6\).
• Có \(80\%\) số test/điểm ứng với \(10^4 \le N, M \le 10^5\); \(10^6 < a_i, b_j \le 10^9\).

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 \(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 đội bất kỳ có khoảng thời gian sử dụng sân không giao nhau.

Input

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

Output

• Số tiền lớn nhất mà chủ sân nhận được.

Example

4
1 2 7
3 4 3
2 5 3
3 5 9

16

Scoring

• Có \(20\%\) số test/điểm ứng với \(1 \le N \le 100\);
• Có \(80\%\) số test/điểm ứng với \(100 < N \le 3000\).