Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Diễn đàn arrow Thư viện arrow Đề thi arrow IOI (thi quốc tế) arrow 2003 arrow Dự đoán về đàn bò (Guess Which Cow)
Dự đoán về đàn bò (Guess Which Cow) In E-mail
(2 votes)
Người viết: Ngô Minh Đức   
21/04/2008
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.
 
< Trước   Tiếp >