Bài 1: (4.0 điểm) ĐỘ ĐẸP

Minh cho rằng độ đẹp của một số tự nhiên chính là tổng các ước tự nhiên lẻ của số đó. Ví dụ số 10 có hai ước lẻ là 1 và 5 nên độ đẹp của 10 là 1+5=6. Cho một số tự nhiên n, em hãy giúp Minh tính độ đẹp của n nhé!

Dữ liệu: Đọc từ thiết bị chuẩn gồm một số tự nhiên n (1 ≤ n ≤ 10^14).

Kết quả: Ghi ra thiết bị chuẩn một số nguyên duy nhất là độ đẹp của n.

Ràng buộc:

Có 60% test có 1 ≤ n ≤ 10^6;

Có 40% test có 10^6 < n ≤ 10^14.

Ví dụ:

Input 01:

4

Output 01:

1

Input 02:

1234

Output 02:

618

Bài 2: (4.0 điểm) CHÍNH PHƯƠNG

Số chính phương là số có thể viết dưới dạng bình phương của một số tự nhiên. Ví dụ: 1, 4, 49 là các số chính phương còn 2, 5, 20 không phải là số chính phương.

Hôm nay, thầy giáo cho Minh bài toán sau:

Cho số tự nhiên n, sau đó phân tích n = k1 + k2 + k3 + k4 + ... Trong đó, các giá trị k1, k2, k3, k4,... được tìm theo quy tắc:

• Tìm số chính phương k1 lớn nhất không vượt quá n.

• Tiếp theo, thực hiện tương tự bước trên với n = n - k1 để tìm k2.

• Để tìm k3, k4,... thực hiện tương tự như trên cho đến khi n = 0.

Hãy tính giá trị của S = (k1)^1+ (k2)^2 + (k3)^3 + (k4)^4 + ...

Theo em, giá trị của S là bao nhiêu?

Dữ liệu: Đọc từ thiết bị chuẩn gồm một số nguyên dương n (1 ≤ n ≤ 10^14)

Kết quả: Ghi ra thiết bị chuẩn giá trị S tìm được.

Ràng buộc:

Có 60% test có 1 ≤ n ≤ 10^6;

Có 40% test có 10^6< n ≤ 10^14.

Ví dụ:

Input 01:

30

Output 01:

42

Với n = 30

Ta có: n = 25 + 4 + 1 nên S = 25^1 + 4^2 + 1^3 = 42

Input 02:

25

Output 02:

25

Với n = 25, nên S = 25^1 = 25

Bài 3: (4.0 điểm) XẾP NHÓM

Trong buổi biểu diễn văn nghệ cuối năm của một trường trung học cơ sở có n học sinh tham gia và được đánh số từ 1 đến n. Các học sinh có chiều cao lần lượt là h1, h2, .... hn. Ban tổ chức muốn xếp các bạn có cùng chiều cao chung nhóm. Các nhóm này sẽ biểu diễn tiết mục múa để có đội hình đẹp. Còn lại, bạn nào có chiều cao riêng biệt (không bằng chiều cao với học sinh nào khác) sẽ được xếp vào cùng một nhóm riêng để diễn kịch.

Em hãy giúp ban tổ chức xác định chiều cao và số học sinh của từng nhóm múa.

Riêng nhóm kịch chỉ cần xác định có bao nhiêu học sinh.

Dữ liệu: Đọc từ thiết bị chuẩn gồm:

• Dòng thứ nhất: Chứa một số nguyên n (1 ≤ n ≤ 10^5).

• Dòng thứ hai: Chứa n số nguyên dương h1, h2, ..., hn, giữa hai số cách nhau một khoảng trắng (1≤ hi ≤ 10^9, 1 ≤ i ≤ n).

Kết quả: Ghi ra thiết bị chuẩn gồm:

• Các dòng đầu: mỗi dòng ghi hai số nguyên lần lượt là chiều cao và số lượng học sinh của từng nhóm múa, theo thứ tự tăng dần theo chiều cao, giữa hai số cách nhau một khoảng trắng. Lưu ý, nếu không có nhóm múa nào thì không có các dòng này.

• Dòng cuối: ghi một số nguyên là số học sinh của nhóm kịch.

Ràng buộc:

Có 60% test có 1 ≤ n ≤ 10^3;

Có 40% test có 10^3 < n ≤ 10^5.

Ví dụ:

Input 01:

7
165 164 150 150 164 165 165

Output 01:

150 2
164 2
165 3
0

Intput 02:

6
170 180 154 165 180 170

Output 02:

170 2
180 2
2

Bài 4: (4.0 điểm) GIẢI MÃ

Ông Nam có một tin nhắn quan trọng cần chuyển đến các nhân viên của mình.

Nội dung tin nhắn là một xâu kí tự gồm chữ cái in thường và in hoa trong bảng chữ cái tiếng Anh. Để bảo mật thông tin, ông Nam đã mã hóa nội dung tin nhắn của mình theo cách sau:

• Ký tự thứ nhất (ký tự đầu tiên) sẽ được đổi thành mã ASCII của nó.

• Ký tự thứ hai: Nếu nó là kí tự in hoa thì dịch chuyển qua phải k đơn vị theo vòng của bảng chữ cái "A.….Z". Còn nếu nó là kí tự in thường thì dịch chuyển qua phải k-1 đơn vị theo vòng của bảng chữ cái "a...z".

• Với các ký tự tiếp theo, thực hiện trình tự mã hóa như hai ký tự trên.

Sau khi mã hóa, ông Nam sẽ có được một xâu S và gửi cho nhân viên.

Ví dụ: Cần nhắn tin "HopGap" sau khi mã hóa với k = 2 thì xâu S sẽ là S="72p112I97q".

Nhận được tin nhắn, các nhân viên đang loay hoay chưa biết giải mã thế nào.

Em hãy giúp các nhân viên trong công ty của ông Nam giải mã tin nhắn nhé!

Dữ liệu: Đọc từ thiết bị chuẩn gồm hai dòng:

• Dòng thứ nhất: Chứa một xâu ký tự S khác rỗng có độ dài không quá 105 ký tự, các kí tự là số và chữ trong bảng chữ cái tiếng Anh.

• Dòng thứ hai: Chứa số nguyên k (1 ≤ k ≤ 10^9)

Lưu ý, Dữ liệu nếu các kí tự là số luôn đảm bảo là mã ASCII của các kí tự trong bảng chữ cái tiếng Anh.

Kết quả: Ghi ra thiết bị chuẩn một dòng chứa nội dung tin nhắn sau khi giải mã.

Ràng buộc:

Có 50% số test đầu tiên với xâu S có độ dài không quá 10^3 ký tự.

Có 50% số test cuối cùng có giới hạn như trong đề.

Ví dụ:

Input 01:

72p112I97q
2

Output 01:

HopGap

Input 02:

84j101C111q78g119
3

Output 02:

TheZooNew

Bai 5: (4.0 điểm) LEO NÚI

Hè rồi, Minh có chuyến du lịch leo núi thú vị. Trong chuyến du lịch này, Minh đã đi qua n địa điểm được đánh số theo thứ tự từ 1 đến n. Các điểm này có độ cao là một ãy số nguyên dương h với các phần tử là h1, h2, ..., hn. Trong đó, đoạn hành trình gồm leo núi trước rồi xuống núi thì được gọi là hành trình chinh phục ngọn núi. Tức là, hành trình này đi qua một đoạn con liên tiếp của dãy h có độ cao tăng dần rồi giảm dần và số địa điểm đi qua trong hành trình này gọi là độ dài của một hành trình chinh phục ngọn núi.

Em hãy cho biết độ dài lớn nhất một hành trình chinh phục ngọn núi trong chuyến du lịch này của Minh là bao nhiêu?

Dữ liệu: Đọc từ thiết bị chuẩn gồm hai dòng:

• Dòng thứ nhất: Chứa số nguyên n (3 ≤ n ≤ 10^6).

• Dòng thứ hai: Chứa n số nguyên h1, h2, .., hn (0 < hi ≤ 10^6), giữa hai số cách nhau một khoảng trắng.

Kết quả: Ghi ra thiết bị chuẩn một số nguyên là đáp án cần tìm. Nếu Minh không có một hành trình chinh phục ngọn núi nào thì ghi 0.

Ràng buộc:

Có 60% test có 1 ≤ n ≤ 10^3;

Có 40% test có 10^3 < n ≤ 10^6.

Ví dụ:

Input 01:

12
1 1 2 3 4 6 4 2 1 2 3 1

Output 01:

8

Hình minh họa:

Input 02:

5
9 8 1 10 12

Output 02:

0

Hình minh họa: