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

 Bài 4. Thử nghiệm robot (100 điểm) 
Công ty HP vừa thiết kế một loại robot thông minh mới. Để đánh giá khả năng tự vận hành của 
robot, người ta tạo ra một bức tường từ cột các khối lập phương, các cột đặt cạnh nhau, bề dày 
bức tường là , độ cao cột thứ là (do khối lập phương tạo lên). Có robot tham gia thử 
 
nghiệm. Trước tiên người ta chia cột thành đoạn bằng điểm cắt 
 1    
 . Robot thứ được giao nhiệm vụ xếp lại đoạn từ cột đến 
    −1 , ,..,  ( =
cột sao cho các cột trong đoạn có độ cao bằng nhau. Robot chỉ có thể thực hiện một trong hai 
0<  <..<  <  = )   +1
loại thao tác, mỗi thao tác mất 1 đơn vị thời gian. 
 
 • Thao tác 1: Lấy khối trên cùng của một cột trong đoạn được giao để bỏ đi; 
 • Thao tác 2: Lấy một khối mới, đặt khối đó lên trên cùng của một cột trong đoạn được giao. 
Thời gian kết thúc thử nghiệm là thời gian mà robot cuối cùng hoàn thành xong nhiệm vụ. 
Yêu cầu: Cho và . Hãy tìm điểm cắt để chia cột thành đoạn sao cho thời 
gian thử nghiệm là nhanh nhất, biết các robot đều thực hiện các thao tác tối ưu. 
 , ,..,    −1  
Dữ liệu: Vào từ thiết bị nhập chuẩn: 
 - Dòng đầu chứa hai số nguyên ; 
 - Dòng thứ hai gồm số nguyên không âm . 
 , 
Kết quả: Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là thời gian ít nhất để thử nghiệm. 
  , ,..,  ( ≤ 10 )
Ràng buộc: 
 - Có 25% số test ứng với 25% số điểm của bài thỏa mãn: 
 - Có 25% số test khác ứng với 25% số điểm của bài thỏa mãn: 
  = 1;  ≤ 10;
 - Có 25% số test khác ứng với 25% số điểm của bài thỏa mãn: 
  = 2;  ≤ 1000;
 - Có 25% số test còn lại ứng với 25% số điểm của bài thỏa mãn: 
  ≤ ;  ≤ 100;
  ≤ ;  ≤ 1000.
Ví dụ: 
 Dữ liệu vào Kết quả ra 
 6 2 1 
 1 1 2 3 4 3 
 --------------------------- 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. 
 Trang 4/4