Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method HTML_content::show() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/Cache/Lite/Function.php on line 98

Strict Standards: Non-static method HTML_content::_Itemid() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 452

Strict Standards: Non-static method HTML_content::_linkInfo() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 455

Strict Standards: Non-static method HTML_content::Title() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 470

Strict Standards: Non-static method HTML_content::PdfIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 473

Strict Standards: Non-static method mosHTML::PrintIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 476

Strict Standards: Non-static method mosAdminMenus::ImageCheck() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/joomla.php on line 2329

Strict Standards: Non-static method HTML_content::EmailIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 479
Dự đoán về đàn bò (Guess Which Cow)
Strict Standards: Non-static method HTML_content::EditIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 632

Strict Standards: Non-static method HTML_content::Section_Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 511

Strict Standards: Non-static method HTML_content::Section() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 755

Strict Standards: Non-static method HTML_content::Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 758

Strict Standards: Non-static method HTML_content::Author() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 514

Strict Standards: Non-static method HTML_content::CreateDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 517

Strict Standards: Non-static method HTML_content::URL() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 520

Strict Standards: Non-static method HTML_content::ModifiedDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 536

Strict Standards: Non-static method HTML_content::ReadMore() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 539
Người viết: Ngô Minh Đức   
21/04/2008

Strict Standards: Non-static method HTML_content::TOC() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 526
Bài toán: Dự đoán về đàn bò (Guess Which Cow) (bài toán yêu cầu tường tác)
Đàn bò của anh nông dân John gồm N con (1 ≤N ≤50) và được đánh số 1...N trông rất giống nhau. Khi lùa bò vào chuồng, anh ta phải xác định con bò nào đang lùa vào, để có thể lùa đúng con bò vào đúng chuồng của nó.
Các con bò được phân biệt bởi P đặc tính (1 ≤P ≤8), đánh số 1…P, mỗi đặc tính có thể có 3 giá trị. Ví dụ, vành tai của bò có thể là mầu vàng, màu lục hoặc màu đỏ. Một cách đơn giản, giá trị của các đặc tính được diễn tả bằng các chữ cái ′X ′, ′Y ′, và ′Z ′. Mỗi cặp bò khác nhau ít nhất một đặc tính.

Cho trước các đặc tính của đàn bò, hãy viết chương trình giúp John xác định con bò nào đang lùa vào chuồng. Chương trình của bạn có thể đưa ra không quá 100 câu hỏi dưới dạng: Đặc tính T có giá trị nằm trong tập hợp S phải không? Cố gắng đưa ra càng ít câu hỏi càng tốt.
Input: guess.in
Dòng đầu tiên gồm hai số N và P cách nhau bởi dấu trắng.
N dòng tiếp theo mô tả P đặc tính của đàn bò là các chữ cái cách nhau bởi dấu trắng. Chữ cái thứ nhất trong mỗi dòng là giá trị đặc tính thứ nhất, cứ tiếp tục như vậy. Dòng thứ hai trong file input mô tả con bò thứ 1, dòng thứ 3 mô tả con bò thứ 2, vv..
Example input:
X Z
X Y
Y X
Y Y
Giao tiếp của chương trình Các câu hỏi/ trả lời thông qua bàn phím và màn hình:
Chương trình của bạn phải đưa ra các câu hỏi về con bò được lùa vào bằng cách đưa ra màn hình một dòng bắt đầu là chữ ′Q ′ theo sau là một dấu cách, số đặc tính, dấu cách và một tập một hoặc nhiều giá trị cách nhau bởi dấu trắng. Ví dụ: 'Q 1 Z Y' có nghĩa là 'Đặc tính 1 của con bò đang lùa vào chuồng có giá trị là ′Z′ hoặc ′Y′ phải không?'.Đặc tính phải là một số nguyên thuộc khoảng 1...P. Tất cả các giá trị phải là ′X′, ′Y′, hoặc ′Z′ và không có giá trị nào được liệt kê quá một lần trong một câu hỏi.

Sau mỗi câu hỏi, chương trình sẽ nhận câu trả lời bằng cách đọc từ bàn phím một dòng gồm một số nguyên. Số nguyên là 1 có nghĩa khẳng định: giá trị của đặc tính nằm trong vùng đã cho. Số nguyên 0 có nghĩa phủ định.
Thông báo cuối cùng của chương trình ghi chữ ′C′ theo sau là một dấu trắng và một số nguyên chỉ rõ con bò mà anh John đang lùa vào chuồng.
Ví dụ:

Hạn chế Chương trình chạy không quá 1 giây
Bộ nhớ 64MB
Cho điểm Độ chính xác: 30% số điểm Chương trình sẽ nhận được điểm tối đa trong phần này nếu chỉ rõ chính xác con bò đang lùa vào chuông. Nếu chương trình trong mỗi test đưa ra hơn 100 câu hỏi sẽ nhận 0 điểm.

Số câu hỏi: 70% số điểm Số điểm còn lại sẽ được xác định bởi số câu hỏi được đưa ra để tìm chính xác con bò. Các bộ test được thiết kế để thưởng điểm cho việc giảm tối đa số lượng các câu hỏi trong trường hợp xấu nhất. Các câu trả lời gần tối ưu sẽ được một phần điểm.
 
Strict Standards: Non-static method HTML_content::Navigation() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 550

Strict Standards: Non-static method mosHTML::CloseButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 553

Strict Standards: Non-static method mosHTML::BackButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 556