Một vườn chuối nằm cạnh một sa mạc. Vườn có 3000 chuối. Chủ rừng muốn vận chuyển chuối đến chợ bằng lạc đà, trên một đoạn km 1000 của sa mạc. Chủ nhà chỉ có một con lạc đà, có thể mang theo tối đa là 1000 chuối ở bất kỳ lần vận chuyển nào và ăn một quả chuối mỗi km nó đi. Số lượng lớn nhất của chuối có thể được giao tại chợ là bao nhiêu?
Để ý là khi còn hơn 2k chuối thì lừa phải mất 5 lần quay đi quay lại cùng 1 tuyến đường, từ 1k đến 2k thì 3 lần, dưới 1k thì 1 lần (không quay lại nữa)
Giả sử sau khi dừng đi dừng lại nhiều lần sau khi đi được x1…xn con lừa còn có từ 1k đến 2k, khi đó gọi A là quãng đường nó đi được A=x1+…+xn và a là số quả nó bỏ lại. Do số chuối <= 2000 nên 3000-5A-a<=2000 <=> X=5A+a>=1000 (Ta không phải quan tâm nó dừng lại bao nhiêu lần vì mỗi lần đều phải quay đi quay lại 5 lần cùng 1 tuyến đường)
Tiếp đó nó đi được thêm B km và bỏ lại b quả thì còn <= 1000 quả. Trong quá trình này nó phải quay đi quay lại 3 lần cùng 1 tuyến đường nên số quả còn 3000 – 5A - a – 3B -b phải <= 1000 <=> Y=5A+3B+a+b phải >=2000
Chặng còn lại dưới 1000 nên 1 đi không trở lại trên quãng đường 1000-A-B, số quả cuối cùng là 3000-5A-3B-a-b- (1000-A-B) = 2000-(4A-2B+a+b) và số này phải max tức là 4A+2B+a+b phải min mà 6A+3B+1.5a+1.5b = 5A+3B+a+b+A+0.2a+0.3a+0.5b =(0.5X+0.3a)+(Y+0.5b) min
*0.5X+0.3 min khi a min=0 X min =1000 khi đó A=200
*để tìm min của Y+0.5b ta xét
b min=0 tuy nhiên khi đó Y=1000+3B+0>=2000 suy ra 3B>=1000 nên B>=334 <=>Y>=2002 hay Y+0.5b>=2002
b = 1 khi đó 3B>=999 nên Y min = 2000 khi B=333, khi đó Y+0.5b=2000.5
nếu b>1 khi đó Y+0.5b>2000+0.5=2000.5 nên loại
Vậy a=0 A=200 b=1 B=333 là đáp án cần tìm. Khi đó số chuối còn lại là: 2000-(4A+2B+a+b) =533 quả
Vậy cách đi là dừng bao nhiều lần cũng được nhưng phải dừng ở điểm 200 và không bỏ lại quả nào, tiếp đó phải dừng ở điểm 533 và trong thời gian đi từ 200 đến 533 phải bỏ bớt 1 quả, cuối cùng đ về đích với 533 quả
đúng nhé
