Đề thi Tin học trẻ toàn quốc THCS vòng chung kết - Bảng B - Bài 1 - Năm học 2

 HỘI THI TIN HỌC TRẺ TOÀN QUỐC ĐỀ THI CHUNG KẾT 
 Năm 2021 BẢNG B - TRUNG HỌC CƠ SỞ 
 ĐỀ CHÍNH THỨC Thời gian làm bài 150 phút, không kể thời gian phát đề 
 Ngày thi: 21/11/2021 
 TỔNG QUAN 
 Tên bài File chương trình Điểm 
 Bài 1 Sắp xếp sort.* 100 điểm 
 Bài 2 Bài tập tasks.* 100 điểm 
 Bài 3 Bài khó dtask.* 100 điểm 
 Bài 4 Thử nghiệm robot robot.* 100 điểm 
 Dấu * được thay thế bởi pas/cpp/py của ngôn ngữ lập trình được sử dụng tương ứng là Pascal/C++/Python. 
 Hãy lập trình giải các bài toán sau: 
 Bài 1. Sắp xếp (100 điểm) 
 Xâu được gọi là lớn hơn xâu nếu xâu là đoạn đầu của xâu hoặc xét kí tự đầu tiên khác nhau 
 thì kí tự của xâu lớn hơn kí tự của xâu . 
    
 Để luyện tập về việc so sánh hai xâu,  Hồng đã tạo ra bài toán sau: Từ hai số nguyên dương 
 , tạo ra một dãy số gồm số: . Sau đó, sắp xếp lại các số theo 
 thứ tự từ điển (coi mỗi số là một xâu và sắp xếp tăng dần) bằng các thao tác như sau: Mỗi lần chọn 
 ,  ( < )  −  +1 ,  +1,, 
 và lấy ra một số trong dãy rồi chèn lại vào dãy ở vị trí bất kì. 
 Ví dụ, nếu ta có dãy số gồm số , dãy số được sắp xếp theo thứ tự từ điển 
 là và cần ít nhất một thao tác (rút số khỏi dãy và chèn vào cuối dãy). 
  = 9,  = 11 3 9,10,11
 Yêu cầu: Cho hai số nguyên dương , hãy tính số thao tác ít nhất để sắp xếp các số 
 10,11,9 9
 theo thứ tự từ điển. 
 ,  ( < )
 Dữ liệu: Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên dương . 
 ,  +1,, 
 Kết quả: Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên là số thao tác ít nhất để sắp 
 ,  ( <  ≤ 10 )
 xếp các số theo thứ tự từ điển. 
 Ràng buộc: ,  +1,, 
 - Có 20% số test ứng với 20% số điểm của bài có ; 
 - Có 20% số test khác ứng với 20% số điểm của bài có ; 
  −  =1
 - Có 30% số test khác ứng với 30% số điểm của bài có ; 
  −  ≤ 10
 - Có 30% số test còn lại ứng với 30% số điểm của bài có ; 
  −  ≤ 1000
 Ví dụ: 
  −  ≤ 10
 Dữ liệu vào Kết quả ra 
 9 11 1 
 Trang 1/4