TỔNG QUAN ĐỀ THI

Lưu ý: Dấu * được thay thế bởi PAS, PY hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal, Python hoặc C++.

Câu 1. Số lớn thứ K (3.0 điểm)

Bo là cậu bé thích đọc sách. Tuy chưa được học đến chuyên đề “Số học” nhưng Bo muốn nghiên cứu trước về nó. Bo đã đến thư viện tìm kiếm cuốn sách có bài toán liên quan đến nội dung này để thử sức mình. Bài toán Bo tìm thấy có yêu cầu như sau: “Cho một số nguyên dương N (N ≤ 5x10¹⁷). Tìm chữ số lớn thứ K trong N”.

Theo em, Bo làm thế nào để tìm ra đáp án đúng?

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

• Dòng đầu tiên chứa số N;
• Dòng thứ hai chứa số K (0 < K ≤ 9).

Kết quả: Ghi ra file văn bản SOTK.OUT gồm một số là chữ số lớn thứ K trong N.

Ví dụ:

Ràng buộc:

• Có 50% test tương ứng 50% số điểm của bài với n ≤ 10⁶;
• Có 40% test tương ứng 40% số điểm của bài với n ≤ 10⁹;
• Có 10% test tương ứng 10% số điểm của bài với n ≤ 5x10¹⁷.

Câu 2. Tổng chính phương (2.0 điểm)

Quảng Nam là mảnh đất hiếu học. Trường THCS Nguyễn Du là nơi nuôi dưỡng ước mơ của cậu bé An. Em là người đam mê Tin học và rất giỏi lập trình nên các bạn thường gọi em là “siêu nhân Tin”. Được nghe danh tiếng của An, các anh chị khóa trước tìm đến và nhờ em giải giúp bài toán về chuyên đề “dãy số”. Nội dung cụ thể bài toán như sau:

“Cho một dãy gồm n số tự nhiên a_i (i =1, 2, …, n). Hãy lập trình tính tổng các số chính phương không xuất hiện trong dãy sao cho các số này không vượt quá giá trị lớn nhất có mặt trong dãy đó”. (Số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên, hay nói cách khác, số chính phương bằng bình phương của một số nguyên).

Yêu cầu: Bạn nghĩ xem, An sẽ làm cách nào để giúp anh chị khóa trước tìm ra kết quả của bài toán?

Dữ liệu vào: Từ file văn bản SUMSOCP.INP gồm 02 dòng:

     - Dòng thứ nhất ghi giá trị của n (0 < n ≤ 10⁶);

- Dòng thứ hai, ghi n số tự nhiên a_i của dãy (0 ≤ a_i ≤ 10⁹) các số cách nhau một khoảng trắng.

Kết quả: Ghi ra file văn bản SUMSOCP.OUT gồm một dòng là đáp án cần tìm.

Ví dụ:

Ràng buộc:

• Có 40% test tương ứng 40% số điểm của bài với n ≤ 10³,0 ≤ a_i ≤ 10⁴;
• Có 30% test tương ứng 30% số điểm của bài với n ≤ 10⁴, 0 ≤ a_i ≤ 10⁶;
• Có 30% test tương ứng 30% số điểm của bài với n ≤ 10⁶, 0 ≤ a_i ≤ 10⁹.

Câu 3. Biến đổi xâu (3.0 điểm)

Để kỳ thi tuyển sinh vào lớp 10 THPT chuyên năm 2023 đạt kết quả cao, thầy Nam luôn dặn dò các học trò của mình phải nắm chắc khái niệm về xâu ký tự để áp dụng giải các bài toán liên quan đến nội dung này. Trong buổi học ôn cuối cùng tại lớp, thầy Nam muốn kiểm tra lại kiến thức của các em học sinh bằng cách nêu ra yêu cầu đề bài với câu hỏi cụ thể như sau:

Cho một xâu ký tự bao gồm các chữ cái (không phân biệt chữ hoa, chữ thường) và các khoảng trắng. Hãy in ra xâu đảo ngược theo từng ký tự trong từ và cho biết từ dài nhất (kể cả từ giống nhau) sau khi đảo ngược cùng vị trí xuất hiện tương ứng của nó. Nếu trong xâu có nhiều từ có độ dài bằng nhau thì in ra tất cả các từ đó.

Dữ liệu vào: Từ file văn bản LONGWORD.INP gồm một dòng chứa xâu S cho trước (S không quá 10⁶ ký tự, giữa các từ có thể cách nhau một hoặc nhiều khoảng trắng).

Kết quả: Ghi ra file văn bản LONGWORD.OUT gồm:

• Dòng đầu tiên trong xâu ký tự chứa các từ được đảo ngược theo yêu cầu;
• Các dòng tiếp theo là từ dài nhất theo thứ tự của từng từ được tính từ trái qua phải sau khi đảo ngược và vị trí xuất hiện tương ứng của nó (các giá trị cách nhau một khoảng trắng).

Ví dụ:

Ràng buộc:

• Có 10% test tương ứng 10% số điểm của bài với độ dài xâu st không quá 255 ký tự;
• Có 50% test tương ứng 50% số điểm của bài với độ dài xâu st không quá 10⁴ ký tự;
• Có 20% test tương ứng 20% số điểm của bài với độ dài xâu st không quá 10⁵ ký tự;
• Có 20% test tương ứng 20% số điểm của bài với độ dài xâu st không quá 10⁶ ký tự.

Câu 4. Chuyến thiện nguyện (2.0 điểm)

Sau trận đại dịch Covid -19 năm 2020, nhiều tỉnh thành đã rơi vào hoàn cảnh khốn khó. Với tinh thần đoàn kết tương trợ, doanh nghiệp A dự định lên kế hoạch sẽ tổ chức đi thiện nguyện đến vùng cao. Địa điểm đầu tiên doanh nghiệp A dự tính đến là các đồng bào có hoàn cảnh khó khăn thuộc tỉnh Lai Châu.

Trong chuyến đi này, có n đoàn tham gia, được đánh số từ 1 đến n (0 < n ≤ 10⁶). Mỗi đoàn sẽ đến thăm và tặng quà cho bà con tại một ngôi làng trong huyện trên địa bàn tỉnh Lai Châu. Trong đó, đoàn thứ i sẽ di chuyển đến ngôi làng cách thành phố Lai Châu với quãng đường d_i km (1 ≤ d_i ≤ 10⁶, i =1, 2,…, n).

Doanh nghiệp A mong muốn chuyến đi diễn ra kịp thời, đúng tiến độ nên phải chuẩn bị m chiếc xe được đánh số từ 1 đến m (n ≤ m ≤ 10⁶). Các xe được đổ đầy nhiên liệu, xe thứ j có mức tiêu thụ nhiên liệu v_j (1 ≤ v_j ≤ 10⁶, j =1, 2, …, m) đơn vị thể tích/ km.

Yêu cầu: Để quá trình vận chuyển thuận lợi và ít tốn kém cho doanh nghiệp, bộ phận kế toán phải tính thế nào để chọn được n chiếc xe phục vụ chuyến đi sao cho tổng chi phí nhiên liệu được sử dụng là ít nhất (biết rằng mỗi xe chỉ phục vụ một đoàn).

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

• Dòng đầu tiên ghi hai số nguyên dương n, m (các số cách nhau một khoảng trắng);
• Dòng thứ hai ghi các số nguyên dương d₁, d_2, …_, d_n (các số cách nhau một khoảng trắng);
• Dòng thứ ba ghi các số nguyên dương v₁, v₂, …, v_m (các số cách nhau một khoảng trắng).

Kết quả: Ghi ra file văn bản VISIT.OUT gồm:

• Dòng đầu tiên ghi tổng số nhiên liệu cần dùng cho việc đưa các đoàn đi thiện nguyện (chỉ tính lượt đi);
• Dòng thứ hai ghi chỉ số xe phục vụ chuyến đi theo thứ tự tăng dần của nhiên liệu bị tiêu tốn (các số cách nhau một khoảng trắng).

Ví dụ:

Ràng buộc

• Có 25% test tương ứng 25% số điểm của bài với 1≤ n, m ≤ 50; d_i, v_j ≤ 10²;
• Có 25% test tương ứng 25% số điểm của bài với 1≤ n, m ≤ 100; d_i, v_j ≤ 10³;
• Có 25% test tương ứng 25% số điểm của bài với 1≤ n, m ≤ 10³; d_i, v_j ≤ 10⁶;
• Có 25% test tương ứng 25% số điểm của bài với 1≤ n, m ≤ 10⁶; d_i, v_j ≤ 10⁶.

---------- HẾT ----------

* Thí sinh không được sử dụng tài liệu, cán bộ coi thi không giải thích gì thêm.

* Họ và tên thí sinh: ………………………………….. Số báo danh: ……........

(Bản hướng dẫn này gồm 02 trang)

TỔNG QUAN ĐỀ THI

HƯỚNG DẪN CHẤM

Bài thi được chấm bằng phần mềm Themis (theo cấu hình đã cài đặt sẵn)

Bài 1. (3.0 điểm) Số lớn thứ K: gồm có 30 test; mỗi test 0,1 điểm, thời gian 1 giây, bộ nhớ 1024 MB

Bài 2. (2.0 điểm) Tổng chính phương: gồm có 40 test, mỗi test 0,05 điểm, thời gian 1 giây, bộ nhớ 1024 MB

Bài 3. (3.0 điểm) Biến đổi xâu: gồm có 30 test; mỗi test 0,1 điểm, thời gian 1 giây, bộ nhớ 1024 MB

Bài 4. (2.0 điểm) Thiện nguyện: gồm có 40 test; mỗi test 0,05 điểm, thời gian 1 giây, bộ nhớ 1024 MB

---------------HẾT---------------