Nội dung Bài tập
Mã:
ROBOTTAO
Tên:
Robot táo (Olympic 30/4 lần XXII năm 2016)
Dạng thi:
oi
Thang điểm:
10 điểm
Giới hạn thời gian:
1 giây
Giới hạn bộ nhớ:
64 MB
Được tạo bởi:
admin
Một  nhà  máy  chế  biến  hoa  quả  đang  chế  biến  một sản phẩm từ táo. Nhà máy này đã có một dây chuyền sản xuất gồm nhiều công đoạn. Trong công đoạn đầu tiên, có N quả táo với trọng lượng đã biết  được đưa ngẫu nhiên lên băng chuyền thành hàng dọc và được đánh số từ 1 đến N. Chúng được ngầm phân thành M  =  [N/K]  đoạn, mỗi đoạn gồm đúng K quả (N là bội của K). Các đoạn này cũng được đánh số từ 1 đến  M, kể  từ  đầu băng chuyền. Do yêu cầu kỹ thuật, chúng cần được sắp xếp lại sao cho: 
  • Đoạn 1 sẽ gồm  K quả có trọng lượng lớn nhất trong số các quả có mặt trên băng chuyền. 
  • Nếu  M  > 1 thì đoạn thứ  i  (i   = 2,…,M) sẽ  là  K  quả  táo lớn nhất trong số các quả còn lại (không có mặt trong  các đoạn từ 1 đến  i - 1).

Một robot sẽ di chuyển dọc theo băng chuyền để  thực hiện yêu cầu kỹ thuật nói trên. Mỗi thao tác 
của robot  sẽ  gồm việc rút ra khỏi băng chuyền 1 quả táo (các quả còn lại được dồn lại) rồi chèn quả táo này vào vị  trí thích hợp trên băng chuyền (bao gồm cả vị trí đầu và cuối dãy).
Yêu  cầu :  Hãy viết  chương trình tính xem robot cần thực hiện ít nhất bao nhiêu thao tác để xếp lại số táo trên băng  chuyền  theo đúng  yêu cầu kỹ thuật.
Dữ liệu : Vào từ file  văn bản  APROBOT.INP  gồm:
  •  Dòng đầu gồm hai số nguyên  N và  K (1  ≤  K  ≤  N  ≤  5000);
  •  Dòng thứ  hai ghi N số nguyên Wi  (1 ≤  Wi  ≤ 1000,  i   = 1, 2,…,  N) là số đơn vị trọng lượng của quả  táo  i 
.Các số trên cùng mỗi hàng đều được ghi cách nhau bởi ít nhất một dấu cách.
Kết  quả:  Ghi  ra  file  văn  bản  APROBOT.OUT  duy nhất một số nguyên,  là số thao tác ít nhất  mà robot cần thực hiện 



    Quảng cáo
       Ngôn ngữ : 

       Theme : 
Mời bạn soạn code



		



      Ai có thể xem bài này : 

Thông tin



Phần thảo luận