Các câu hỏi phỏng vấn [28]

5 Comments

1. dongnl
   Posted 17/05/2007 at 2:04 am | Permalink

   78. Giả sử chỉ có 200 lít xăng thì giải pháp như sau:
   – Lượt 1: chở 100 lít xăng từ điểm xuất phát, đến cây số 33 1/3 km, để lại 33 1/3 lít xăng, sau đó quay lại điểm xuất phát.
   – Lượt 2: chở 100 lít xăng từ điểm xuất phát, đến cây số 33 1/3 km, nhặt 33 1/3 lít xăng ở đó, đi về đích.
   Theo cách này, xe tải mang đến đích được 33 1/3 lít xăng.

   Với 300 lít xăng thì một giải pháp (chưa chứng minh được là tối ưu) như sau:
   – Lượt 1: chở 100 lít xăng từ điểm xuất phát, đến cây số 25 km, để lại 50 lít xăng, quay lại điểm xuất phát.
   – Lượt 2: chở 100 lít xăng từ điểm xuất phát, đến cây số 25 km, nhặt 25 lít xăng ở đó, đến cây số 50 km, để lại 25 lít xăng, quay lại điểm xuất phát.
   – Lượt 3: chở 100 lít xăng từ điểm xuất phát, đến cây số 25 km, nhặt 25 lít xăng ở đó, đến cây số 50 km, nhặt 25 lít xăng ở đó, đi về đích.
   Theo cách này xe tải mang đến đích được 50 lít xăng.

   Không biết ai có thể có giải pháp tổng quát với x lít xăng bất kỳ thì tốt quá.

   79. Câu hỏi tổng quát hơn có thể là: cho một hình gốc tạo bởi các ô vuông đơn vị, chọn một mảnh giấy sao cho với bất kỳ một ô vuông nào trong hình gốc có thể dùng mảnh giấy phủ lên hình gốc không che ô vuông đã chọn, không phủ thừa ra ngoài mà diện tích không được phủ là ít nhất.

   Với trường hợp hình chữ nhật, chia làm 4 hình chữ nhật con bằng nhau, khi đó bất kỳ một ô X nào trên hình gốc cũng phải thuộc 1 trong 4 hình chữ nhật con. Vì vậy chọn mảnh giấy phủ có hình của 3 hình chữ nhật con hợp lại (hình chữ L).

   Khi hình gốc cụ thể là bàn cờ 8×8, chọn 3 mảnh giấy hình chữ L là hợp của 3 hình 4×4, 3 hình 2×2, 3 hình 1×1 thì sẽ đảm bảo yêu cầu phủ kín, không thừa và không che ô vuông đơn vị bât kỳ.

   Reply
2. lihavim
   Posted 17/05/2007 at 3:40 am | Permalink

   78. Không biết xài chương trình có ăn gian không nhỉ?
   Với bước nhảy 1 và 2 thì số xăng có thẻ đua về là 52. Trình tự như sau:
   -Chở 100 lít xăng đến km số 1, để lại 98 lít, về và chở tiếp.
   Xe cuối cùng (ce thứ 3) đến km số 1 mất 1 lít, còn 99 lít. Bơm đầy và cứ tiếp túc từng km như thế, cuối cùng đêm về đích được 52 lít.
   Tương tự, bước nhảy 2 km một lần cũng thế.

   Reply
3. holo
   Posted 17/05/2007 at 8:30 am | Permalink

   Với 100 lít : ta chỉ có một cách là chở hết và đem thẳng tới đích.
   Với 200 lít : gọi a là vị trí sau 2 lượt chuyển xe còn 100 lít. KHi đó số xăng do lượt 1 cung cấp tại vị trí tối đa là 100 – 2a, lượt 1 là 100 – a, do đó vị trí a tối ưu là (100 -2a) + (100 – a) = 100 => a = 33+ 1/3 km.
   Với 300 lít : ta cần tìm vị trí tối ưu a’ để dịch chuyển mà tại đó ta còn 200 lít.
   lượt 1,2 tối ưu cũng chỉ cung cấp được 100 – 2a’
   lượt 3 tối ưu cung cấp được 100 – a’ do đó vị trí tối ưu là
   2(100 – 2a’) + 100 – a’ = 200 => a’= 20 km;
   Như vậy ta thấy số xăng tối đa có thể dich chuyển được là 20 + 33 + 1/3 = 53+1/3 lít
   Bài toán có thể giải tổng quát với n lít xăng > 200

   Reply
4. choconlangthang
   Posted 17/05/2007 at 10:11 am | Permalink

   78.
   Tất cả bài giải trên đều dựa vào giả định xe chở xăng trong bình xăng xe (hoặc xe lấy xăng trực tiếp từ cái xi-tẹc nó đang chở, ). Tuy nhiên tôi không thấy điều này trong đề bài!

   Reply
5. lihavim
   Posted 19/05/2007 at 2:56 am | Permalink

   @choconlangthang: Xe hết xăng dừng lại láy trong tẹc dùng thì có sao?

   Reply