Băng Nhi
30-06-2006, 10:47 AM
18 bài - 180 phút thôi!
1. Cho một danh sách liên kết đơn (simple linked list) hữu hạn. Có hai trường hợp: một là cuối danh sách trỏ về NULL, hai là trỏ về một phần tử đã gặp - tạo nên một vòng tròn trong danh sách.
Ví dụ trường hợp 1: A --> B --> C --> D --> NULL.
Ví dụ trường hợp 2: A --> B --> C --> D --> E --> F --> C.
Cho trước một con trỏ vào một danh sách liên kết đơn L nào đó, hữu hạn nhưng có thể có độ dài tùy ý. Làm thế nào để kiểm tra nhanh nhất nếu danh sách L thuộc trường hợp 1 hay trường hợp 2, với điều kiện là ta chỉ được dùng vài chục bytes bộ nhớ.
2. Cho một chuỗi ký tự s bao gồm nhiều từ. Viết một đoạn chương trình C đảo thứ tự các từ.
Ví dụ: với input là "this is a nice blog" thì output là "blog nice a is this".
3. Cho hai dãy số đã xếp thứ tự tăng dần A và B, mỗi dãy có n phần tử. Xét tập hợp sau:
S = { A[i] + B[j] | 1 <= i, j <= n }.
Chú ý rằng S có thể có đến n2 phần tử. Viết một chương trình in ra n số lớn nhất trong S. Chương trình phải chạy trong thời gian O(n).
4. Chỉ với các phép tính cộng, trừ, nhân, chia, các hàm lượng giác, phép lũy thừa, và phép lấy căn, cùng với ba số 2, làm thế nào để viết một biểu thức định trị ra 2005? (Gợi ý: 2005 không có gì đặc biệt, số nguyên dương nào cũng được.)
5. Thần biết tuốt, Thần thông thái và Mít đặc đứng trước mặt bạn. Thần biết tuốt và Thần thông thái cái gì cũng biết. Mít đặc thì cái biết cái không.Thần biết tuốt luôn nói thật, Thần thông thái luôn nói dối. Với 3 câu hỏi có/không, mỗi câu chỉ hỏi một trong ba đối tượng, xác định ai là ai.
6. Cho a và b là các số nguyên dương, nguyên tố cùng nhau. Tìm công thức tính số nguyên lớn nhất không thể viết dưới dạng ax+by, trong đó x và y là các số nguyên không âm.
7. Cho hai sợi dây dài, làm bằng các vật liệu khác nhau, có mật độ vật chất khác nhau ở các điểm khác nhau của từng sợi. Cho biết mỗi sợi dây cháy trong đúng một giờ thì hết. Dùng hai sợi dây (và diêm) để đo 45 phút.
8. Cho hai hình lập phương. Ta phải gán các chữ số 0-9 (mỗi mặt một số) ra sao để có thể dùng hai hình lập phương biểu diễn được tất cả các ngày trong tháng.
9. Những điểm nào trên quả địa cầu (giả sử là đúng hình cầu) có tính chất sau đây: đi về phía Nam 1km, sau đó về phía Tây 1km, sau đó về phía Bắc 1km thì quay lại điểm cũ.
10. Cho một mảnh giấy hình chữ nhật với một lỗ hổng hình chữ nhật ở giữa.
Hỏi: Dùng dao cắt mảnh giấy một nhát như thế nào để có hai nửa có diện tích bằng nhau?
. Có 500 cái cửa nằm dọc theo một hành lang đánh số từ 1 đến 100. Lúc đầu các
11cửa đều đóng. Có 500 người xếp hàng đi dọc hành lang. Anh thứ nhất mở tất cả các cửa; anh thứ hai chuyển trạng thái (mở thành đóng, đóng thành mở) các cửa 2, 4, 6, ...; anh thứ ba chuyển trạng thái các cửa 3, 6, 9, ...; cứ như vậy đến anh thứ 500 chuyển trạng thái cửa 500.
Hỏi: cuối cùng có bao nhiêu cửa đóng?
12. Có hai căn phòng nằm cạnh nhau nhưng không thông nhau, và đứng bên này không thấy bên kia. Phòng 1 có ba cái đèn bóng tròn. Phòng 2 có ba công tắc của ba đèn ở phòng 1. Bạn là người lạ, được dẫn vào phòng 2 trước, được quyền nghịch ngợm tắt mở công tắc tùy ý. Sau đó bạn được sang phòng 1 kiểm tra đèn.
Hỏi: nghịch thế nào ở phòng 2 để biết công tắc nào tương ứng với đèn nào?
13. Tom ở tầng 3, Jerry ở tầng 33 của một chung cư. Một hôm hứng chí cả hai ra ban công hét lên cùng một lúc.
Hỏi: ai nghe thấy tiếng của người kia trước?
14. Có 10 đồng tiền, thật có giả có. Cho một cái cân đĩa không có quả cân. Các đồng thật nặng bằng nhau, các đồng giả nặng bằng nhau và nhẹ hơn các đồng thật.
Hỏi: cân ba lần và chỉ ra các đồng giả.
15. Ba người cần chia một cái bánh sao cho ai cũng thỏa mãn về phần bánh của mình.
Hỏi: tìm giải pháp chia bánh với giả thiết ai cũng tin rằng mình cắt bánh công bằng.
16. (Bài toán Monty Hall) Monty Hall làm MC của một trò chơi trên truyền hình. Có ba cái cửa chắn trước người chơi. Đằng sau một trong các cánh cửa là phần thưởng. Bạn chọn một trong ba cánh cửa. Monty Hall xem đằng sau hai cánh còn lại và mở một cửa không có phần thưởng.
Hỏi: bạn sẽ giữ chọn lựa cũ hay đổi sang cửa còn lại để lấy phần thưởng? Tại sao?
17. Tom yêu hai cô gái Mary và Tinny. Cả ba sống trên cùng một con đường, Tom ở đoạn giữa. Các xe buýt đi cả hai chiều của con đường, mỗi chiều một tiếng một lần có xe buýt đến (tốc độ đều). Sáng sáng Tom ra bến xe buýt và đón xe nào đến trước thì đi về hướng ấy. Sau một thời gian dài thì Tom đi thăm Mary gấp ba lần đi thăm Tinny.
Hỏi: sao lại thế được?
18. Có hai xe tải đứng đối diện nhau, cách nhau 100km. Xe 1 có tốc độ 50km/h, xe 2 có tốc độ 30km/h, một con ruồi đậu trên mũi xe 1 bay qua bay lại giữa hai mũi xe với tốc độ 5000km/h. Cả hai xe và con ruồi đều xuất phát cùng một lúc.
Hỏi: đến khi con ruồi bị đè bẹp gí giữa hai xe (đụng nhau) thì con ruồi bay được bao xa?
Sưu tầm
1. Cho một danh sách liên kết đơn (simple linked list) hữu hạn. Có hai trường hợp: một là cuối danh sách trỏ về NULL, hai là trỏ về một phần tử đã gặp - tạo nên một vòng tròn trong danh sách.
Ví dụ trường hợp 1: A --> B --> C --> D --> NULL.
Ví dụ trường hợp 2: A --> B --> C --> D --> E --> F --> C.
Cho trước một con trỏ vào một danh sách liên kết đơn L nào đó, hữu hạn nhưng có thể có độ dài tùy ý. Làm thế nào để kiểm tra nhanh nhất nếu danh sách L thuộc trường hợp 1 hay trường hợp 2, với điều kiện là ta chỉ được dùng vài chục bytes bộ nhớ.
2. Cho một chuỗi ký tự s bao gồm nhiều từ. Viết một đoạn chương trình C đảo thứ tự các từ.
Ví dụ: với input là "this is a nice blog" thì output là "blog nice a is this".
3. Cho hai dãy số đã xếp thứ tự tăng dần A và B, mỗi dãy có n phần tử. Xét tập hợp sau:
S = { A[i] + B[j] | 1 <= i, j <= n }.
Chú ý rằng S có thể có đến n2 phần tử. Viết một chương trình in ra n số lớn nhất trong S. Chương trình phải chạy trong thời gian O(n).
4. Chỉ với các phép tính cộng, trừ, nhân, chia, các hàm lượng giác, phép lũy thừa, và phép lấy căn, cùng với ba số 2, làm thế nào để viết một biểu thức định trị ra 2005? (Gợi ý: 2005 không có gì đặc biệt, số nguyên dương nào cũng được.)
5. Thần biết tuốt, Thần thông thái và Mít đặc đứng trước mặt bạn. Thần biết tuốt và Thần thông thái cái gì cũng biết. Mít đặc thì cái biết cái không.Thần biết tuốt luôn nói thật, Thần thông thái luôn nói dối. Với 3 câu hỏi có/không, mỗi câu chỉ hỏi một trong ba đối tượng, xác định ai là ai.
6. Cho a và b là các số nguyên dương, nguyên tố cùng nhau. Tìm công thức tính số nguyên lớn nhất không thể viết dưới dạng ax+by, trong đó x và y là các số nguyên không âm.
7. Cho hai sợi dây dài, làm bằng các vật liệu khác nhau, có mật độ vật chất khác nhau ở các điểm khác nhau của từng sợi. Cho biết mỗi sợi dây cháy trong đúng một giờ thì hết. Dùng hai sợi dây (và diêm) để đo 45 phút.
8. Cho hai hình lập phương. Ta phải gán các chữ số 0-9 (mỗi mặt một số) ra sao để có thể dùng hai hình lập phương biểu diễn được tất cả các ngày trong tháng.
9. Những điểm nào trên quả địa cầu (giả sử là đúng hình cầu) có tính chất sau đây: đi về phía Nam 1km, sau đó về phía Tây 1km, sau đó về phía Bắc 1km thì quay lại điểm cũ.
10. Cho một mảnh giấy hình chữ nhật với một lỗ hổng hình chữ nhật ở giữa.
Hỏi: Dùng dao cắt mảnh giấy một nhát như thế nào để có hai nửa có diện tích bằng nhau?
. Có 500 cái cửa nằm dọc theo một hành lang đánh số từ 1 đến 100. Lúc đầu các
11cửa đều đóng. Có 500 người xếp hàng đi dọc hành lang. Anh thứ nhất mở tất cả các cửa; anh thứ hai chuyển trạng thái (mở thành đóng, đóng thành mở) các cửa 2, 4, 6, ...; anh thứ ba chuyển trạng thái các cửa 3, 6, 9, ...; cứ như vậy đến anh thứ 500 chuyển trạng thái cửa 500.
Hỏi: cuối cùng có bao nhiêu cửa đóng?
12. Có hai căn phòng nằm cạnh nhau nhưng không thông nhau, và đứng bên này không thấy bên kia. Phòng 1 có ba cái đèn bóng tròn. Phòng 2 có ba công tắc của ba đèn ở phòng 1. Bạn là người lạ, được dẫn vào phòng 2 trước, được quyền nghịch ngợm tắt mở công tắc tùy ý. Sau đó bạn được sang phòng 1 kiểm tra đèn.
Hỏi: nghịch thế nào ở phòng 2 để biết công tắc nào tương ứng với đèn nào?
13. Tom ở tầng 3, Jerry ở tầng 33 của một chung cư. Một hôm hứng chí cả hai ra ban công hét lên cùng một lúc.
Hỏi: ai nghe thấy tiếng của người kia trước?
14. Có 10 đồng tiền, thật có giả có. Cho một cái cân đĩa không có quả cân. Các đồng thật nặng bằng nhau, các đồng giả nặng bằng nhau và nhẹ hơn các đồng thật.
Hỏi: cân ba lần và chỉ ra các đồng giả.
15. Ba người cần chia một cái bánh sao cho ai cũng thỏa mãn về phần bánh của mình.
Hỏi: tìm giải pháp chia bánh với giả thiết ai cũng tin rằng mình cắt bánh công bằng.
16. (Bài toán Monty Hall) Monty Hall làm MC của một trò chơi trên truyền hình. Có ba cái cửa chắn trước người chơi. Đằng sau một trong các cánh cửa là phần thưởng. Bạn chọn một trong ba cánh cửa. Monty Hall xem đằng sau hai cánh còn lại và mở một cửa không có phần thưởng.
Hỏi: bạn sẽ giữ chọn lựa cũ hay đổi sang cửa còn lại để lấy phần thưởng? Tại sao?
17. Tom yêu hai cô gái Mary và Tinny. Cả ba sống trên cùng một con đường, Tom ở đoạn giữa. Các xe buýt đi cả hai chiều của con đường, mỗi chiều một tiếng một lần có xe buýt đến (tốc độ đều). Sáng sáng Tom ra bến xe buýt và đón xe nào đến trước thì đi về hướng ấy. Sau một thời gian dài thì Tom đi thăm Mary gấp ba lần đi thăm Tinny.
Hỏi: sao lại thế được?
18. Có hai xe tải đứng đối diện nhau, cách nhau 100km. Xe 1 có tốc độ 50km/h, xe 2 có tốc độ 30km/h, một con ruồi đậu trên mũi xe 1 bay qua bay lại giữa hai mũi xe với tốc độ 5000km/h. Cả hai xe và con ruồi đều xuất phát cùng một lúc.
Hỏi: đến khi con ruồi bị đè bẹp gí giữa hai xe (đụng nhau) thì con ruồi bay được bao xa?
Sưu tầm