C++Hỏi bài Part 2

Được viết bởi: ❧Frog☆Fox➻❥


Bài 1: Nhảy trên các bậc thang

Trong nhiều trò chơi điện tử, nhân vật chính phải nhảy từ trái sang phải theo các bậc thang lơ lửng trong không trung. Xét trường hợp khi nhân vật chính có thể nhảy sang bậc thang kề cạnh (Bước nhảy loại I) hay nhảy cách một bậc thang (Bước nhảy loại II). Nếu khoảng cách tới mặt đất của các bậc thang từ trái sang phải tương ứng là y1, y2 và y3, thì bước nhảy loại I đòi hỏi chi phí năng lượng là |y2-y1|, còn năng lượng cho bước nhảy loại II là 3x|y3-y1|. Đoạn đường phải vượt qua có n bậc thang, bậc thứ i lơ lửng ở độ cao nguyên yi (0 ≤ yi ≤ 30000, i = 1 ÷ n, 1 ≤ n ≤ 30000). Để giữ sức thực hiện các công việc khác, người chơi phải tìm cách vượt qua đoạn đường này với chi phí năng lượng nhỏ nhất. Ban đầu người chơi đứng ở bậc thang số 1.

Yêu cầu: Cho n và yi (i = 1 ÷ n). Hãy xác định chi phí năng lượng nhỏ nhất vượt qua đoạn đường này.

Dữ liệu vào: Đọc từ tệp văn bản JUMP.INP có cấu trúc:
Dòng 1 chứa số nguyên n
Dòng 2 chứa n số nguyên y1, y2, . . ., yn.

Kết quả: Ghi ra tệp văn bản JUMP.OUT một số nguyên là chi phí năng lượng nhỏ nhất tìm được.

Ví dụ:

JUMP.INP: 3
___________1 5 2
JUMP.OUT: 3



Bài 3: Bờm và Phú Ông

Sau khi Bờm đáp ứng hết các điều kiện mà Phú Ông đưa ra, Bờm lại thắng cuộc một lần nữa. Vì phần thưởng lần này quá lớn nên Bờm vội chạy về và lục soát khắp nhà mới tìm được một cái ba lô chứa được trọng lượng không vượt quá S. Bờm vội vã mang đến nhà Phú Ông nhận thưởng. Phú Ông có N thỏi vàng được đánh số hiệu từ 1 đến N. Các thỏi vàng có trọng lượng lần lượt là a1, a2, …, aN để cho Bờm lựa chọn. Bờm rất cẩn thận lựa chọn các thỏi vàng cho vào ba lô sao cho tổng trọng lượng lớn nhất mà ba lô không bị rách (ba lô sẽ bị rách khi chứa trọng lượng lớn hơn S và khi đó Bờm phải đền gấp đôi số vàng lấy được).

Yêu cầu: Bạn hãy tính toán giúp Bờm có thể chọn những thỏi vàng để tổng trọng lượng lớn nhất và có bao nhiêu cách lựa chọn như vậy?

Dữ liệu vào: Đọc từ tệp văn bản BOM.INP có cấu trúc như sau:
Dòng 1 ghi số N và S (0 < N ≤ 1000; 0 < S ≤ 50000; N*S < 5x106).
Dòng 2 chứa N số a[i] (0 < a[i] ≤ 1000).

Kết quả: Ghi ra tệp văn bản BOM.OUT có cấu trúc như sau:
Nếu có phương án:
Dòng 1 ghi tổng trọng lượng lớn nhất có thể.
Dòng 2 ghi số cách Bờm có thể lựa chọn để đạt tổng trọng lượng lớn nhất (hai cách chọn khác nhau nếu có ít nhất hai thỏi vàng có số hiệu khác nhau).
Ngược lại nếu ba lô của Bờm quá tồi nên không đựng được bất cứ một thỏi vàng nào thì ghi duy nhất số 0.

Ví dụ:
BOM.INP: 4 7
___________4 6 2 6
BOM.OUT: 6
____________3

Chú ý: 60% test S ≤ 1000; Đúng dòng 1 đạt 70% điểm 1 test; Đúng dòng 2 đạt 30% điểm 1 test.

Posted on April 26, 2021 08:28:23 PM


3
Donate free




Đăng nhập để tham gia thảo luận! Hoặc bạn có thể bình luận bằng facebook ở dưới.