cashier
21-11-2007, 10:29 PM
mong các bạn chuyên Tin Lam Sơn giúp đỡ :
Bài 01. Ông già Nôen.
Dọc theo một tuyến phố thẳng có N ô đất kế tiếp nhau đánh số từ 1 đến N. Hiện tại chỉ có ô đất thứ K (1 ≤ K ≤ N) đã xây dựng nhà có độ cao là H[K], còn các ô đất khác để trống. Theo qui hoạch, thành phố sẽ xây dựng tại ô đất thứ i (1 ≤ i ≤ N, i ≠ K) ngôi nhà với độ cao H[i].
Sau khi lấy ý kiến của dân phố, người ta muốn xây dựng các ngôi nhà liền nhau và các cầu thang giữa hai ngôi nhà kề nhau để ông già Nôen có thể theo các thang để phát quà cho trẻ em. Độ dài của thang nối hai nhà kề nhau có độ dài bằng giá trị tuyệt đối của hiệu độ cao của hai nhà.
Yêu cầu: Hãy sắp xếp các nhà vào các ô ( trừ ô K) sao cho tổng độ dài của thang nhỏ nhất.
Dữ liệu vào cho trong tệp SC.INP:
+ Dòng đầu chứa số nguyên dương N ≤ 10000.
+ Dòng sau chứa N số nguyên dương H[i] ≤ 106, 1 ≤ i ≤ N.
+ Dòng cuối cùng chứa số nguyên dương K.
Kết quả xuất ra tệp SC.OUT:
+ Dòng đầu là tổng độ dài ngắn nhất của các thang.
+ Một số dòng tiếp theo là dãy độ cao của các nhà sẽ xây dựng tại các ô thứ i (1 ≤ i ≤ N), trong đó độ cao của ngôi nhà thứ K vẫn giữ nguyên.
Chỉ cần đưa ra một phương án kết quả.
Ví dụ.
SC.INP
5
7 3 4 2 6
2
SC.OUT
5
2 3 4 6 7
nếu có thể thì cho mình luôn code hoặc chỉ cần chỉ cho mình thuật toán thôi :)
cám ơn trước
Bài 01. Ông già Nôen.
Dọc theo một tuyến phố thẳng có N ô đất kế tiếp nhau đánh số từ 1 đến N. Hiện tại chỉ có ô đất thứ K (1 ≤ K ≤ N) đã xây dựng nhà có độ cao là H[K], còn các ô đất khác để trống. Theo qui hoạch, thành phố sẽ xây dựng tại ô đất thứ i (1 ≤ i ≤ N, i ≠ K) ngôi nhà với độ cao H[i].
Sau khi lấy ý kiến của dân phố, người ta muốn xây dựng các ngôi nhà liền nhau và các cầu thang giữa hai ngôi nhà kề nhau để ông già Nôen có thể theo các thang để phát quà cho trẻ em. Độ dài của thang nối hai nhà kề nhau có độ dài bằng giá trị tuyệt đối của hiệu độ cao của hai nhà.
Yêu cầu: Hãy sắp xếp các nhà vào các ô ( trừ ô K) sao cho tổng độ dài của thang nhỏ nhất.
Dữ liệu vào cho trong tệp SC.INP:
+ Dòng đầu chứa số nguyên dương N ≤ 10000.
+ Dòng sau chứa N số nguyên dương H[i] ≤ 106, 1 ≤ i ≤ N.
+ Dòng cuối cùng chứa số nguyên dương K.
Kết quả xuất ra tệp SC.OUT:
+ Dòng đầu là tổng độ dài ngắn nhất của các thang.
+ Một số dòng tiếp theo là dãy độ cao của các nhà sẽ xây dựng tại các ô thứ i (1 ≤ i ≤ N), trong đó độ cao của ngôi nhà thứ K vẫn giữ nguyên.
Chỉ cần đưa ra một phương án kết quả.
Ví dụ.
SC.INP
5
7 3 4 2 6
2
SC.OUT
5
2 3 4 6 7
nếu có thể thì cho mình luôn code hoặc chỉ cần chỉ cho mình thuật toán thôi :)
cám ơn trước