Tổng quan bài thi:

Tên bài	File nguồn	File Input	File Output	Thời gian chaỵ
SỐ LỚN NHẤT	MAXNUM.*	MAXNUM.INP	MAXNUM.OUT	1 giây
XÂU ĐẢO	AD.*	AD.INP	AD.OUT	1 giây
TỔNG SỮA	MILK.*	MILK.INP	MILK.OUT	1 giây
SỐ HOÀN HẢO	SEQUENCE.*	SEQUENCE.INP	SEQUENCE.OUT	1 giây

Chú ý : Phần mở rộng .* được thay thế bằng Cpp, Py ứng với các ngôn ngữ lập trình C++, Python.

BÀI 1 (5 điểm): SỐ LỚN NHẤT                                        Tên file MAXNUM*

Trong một buổi chuyên đề về môn Toán của một trường, thầy giáo đưa ra một câu đố vui để thử tài các học sinh của mình. Cho trước số nguyên X (1<=X <20²⁵). Các em hãy tìm số nguyên lớn nhất nhưng nhỏ hơn X và có cùng các chữ số với X. Câu đố này làm nhiều học sinh khá đau đầu.

Yêu cầu: Cho trước số nguyên X, Em hãy giúp các bạn tìm nhanh số nguyên lớn nhất thỏa yêu cầu của thầy giáo nhé.

Dữ liệu vào: File MAXNUM.INP gồm một dòng duy nhất chứa số X.

Dữ liệu ra: File MAXNUM.OUT gồm một dòng ghi số tìm được, nếu không tìm được ghi số 0.

Ví dụ:

MAXNUM.INP	MAXNUM.OUT	MAXNUM.INP	MAXNUM.OUT
342	324	567	0

BÀI 2: (6 điểm) XÂU ĐẢO                                                       Tên file: AD.*

Hai xâu ký tự được gọi là đảo của nhau nếu ta có thể hoán vị các ký tự của xâu để được xâu còn lại. Ví dụ: xâu “occurs” là đảo của xâu “succor”, tuy nhiên “dear” không phải là đảo của xâu “daerd” (vì chữ “d” xuất hiện 2 lần trong “deard” còn “dear” thì chỉ xuất hiện 1 lần).

Độ đo giữa 2 xâu ký tự là số ký tự ít nhất cần phải xóa (trên cả 2 xâu) để 2 xâu còn lại là đảo của nhau. Ví dụ: độ đo giữa hai xâu “sleep” và “leap” là 3, độ đo giữa hai xâu “dog” và “cat” là 6.

Yêu cầu: Hãy tìm độ đo giữa hai xâu cho trước.

Dữ liệu vào: file AD.INP:

• Gồm 2 dòng, mỗi dòng chứa một xâu ký tự chỉ gồm các chữ cái tiếng Anh thường, mỗi dòng chứa không quá 10⁶ ký tự.

Kết quả: file AD.OUT:

• Một số nguyên duy nhất là độ đo giữa hai xâu cho trước.

Ví dụ:

AD.INP	AD.OUT
Begin End	4

BÀI 3: (5 điểm) TỔNG SỮA                                                     Tên file: MILK.*

Công ty Merry Milk Makers có một số nông dân chuyên cung cấp sữa và mỗi người có một giá bán khác nhau cho công ty. Tuy nhiên vì mỗi con bò chỉ có thể cho một lượng sữa nhất định mỗi ngày nên những người nông dân đó cũng chỉ có một lượng sữa nhất định để bán mỗi ngày. Mỗi ngày, công ty có thể mua một số nguyên lít sữa từ mỗi người nông dân, ít hơn hoặc bằng giới hạn sữa của mỗi người nông dân đó.

Cho trước nhu cầu mua sữa mỗi ngày của công ty, giá mỗi lít sữa và số lít sữa có sẵn của mỗi người nông dân. Hãy tính số tiền ít nhất mà công ty cần để mua lượng sữa yêu cầu. Giả thiết rằng tổng số sữa của các người nông dân đủ để đáp ứng lượng sữa của công ty.

Yêu cầu: Đưa ra số tiền nhỏ nhất mà công ty Merry Milk Makers có thể mua sữa mỗi ngày.

Dữ liệu vào: Dòng đầu tiên của file vào chứa hai số nguyên N và M ngăn cách nhau bởi một dấu cách. N (0 ≤ N ≤ 2000000) là số lít sữa mà công ty cần mỗi ngày, 𝑀 (0 ≤ 𝑀 ≤ 5000) là số người nông dân cung cấp sữa cho công ty. Dòng thứ i trong số M dòng tiếp theo, chứa hai số nguyên P_i và A_i ngăn cách nhau bởi một dấu cách 𝑃𝑖 (0 ≤ 𝑃𝑖  ≤ 10000) là giá một lít sữa của bác nông dân i,

𝐴𝑖 (0 ≤ 𝐴𝑖 ≤ 2000000) là số lít sữa tối đa mà bác nông dân có thể bán cho công ty

mỗi ngày.

Kết quả: File ra gồm một dòng chứa đúng một số nguyên là số tiền nhỏ nhất mà công ty Merry Milk Makers có thể mua sữa mỗi ngày.

Ví dụ:

MILK.INP	MILK.OUT
100 5 5 20 9 40 3 10 8 80 6 30	630

BÀI  4 (4 điểm)  DÃY HOÀN HẢO                                Tên file SEQUENCE.*

Cho dãy n phần tử nguyên dương, dãy con của dãy đã cho là dãy các phần tử liên tiếp của dãy đó. Độ hoàn hảo của một dãy con là trung bình cộng của dãy con đó. Rõ ràng ta có thể thấy rằng dãy có độ hoàn hảo lớn nhất chính là số lớn nhất trong dãy, như vậy thì quá đơn giản để tìm được dãy con có độ hoàn hảo lớn nhất. Vì vậy ở đây ta chỉ xét những dãy có tổng của các phần tử không nhỏ hơn k.

Yêu cầu: Cho n, k và dãy n phần tử, tìm dãy con có độ hoàn hảo lớn nhất.

Dữ liệu vào: Vào từ file văn bản SEQUENCE.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương 𝑛 và 𝑘 (1 ≤ 𝑛 ≤ 10⁵, 0 ≤ 𝑘 ≤ 10⁹)
• Dòng thứ hai chứa n số nguyên dương ai  các phần tử của dãy đã cho(𝑎_𝑖  ≤  10⁹ )

Kết quả: Ghi ra file văn bản SEQUENCE.OUT một số duy nhất là kết quả tìm được, làm tròn xuống thành số nguyên.

Ví dụ:

SEQUENCE.INP	SEQUENCE.OUT
5 6 1 5 2 4 3	3

          – Hết

Tham khảo test và code tại đây:

https://drive.google.com/drive/folders/1chiwe0x8cuH6OuRnve1LU8wY_-u3wy0W?usp=sharing