Cây quyết định (decision tree) -- cụ thể là một loại được gọi là cây phân loại (classification trees) -- là cấu trúc dữ liệu được sử dụng để phân loại các đối tượng (items) vào các nhóm (categories) bằng cách sử dụng các đặc điểm (features) của những đối tượng đó. Ví dụ, mỗi loài động vật có thể "đáng yêu" (cute) hoặc không. Với bất kỳ loài động vật nào, chúng ta có thể quyết định xem nó có đáng yêu hay không bằng cách xem xét các đặc điểm của nó và sử dụng cây quyết định sau:

(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)

Một cây quyết định được định nghĩa đệ quy. Nó luôn có một nút gốc và một trọng số (weight). Nó cũng có thể có (tùy chọn) một tên đặc điểm và hai cây con, bản thân chúng cũng là các cây quyết định.

Nói một cách trang trọng hơn, một cây quyết định được định nghĩa bằng ngữ pháp sau:

tree ::= (weight [feature tree tree])
weight is a real number between 0 and 1, inclusive
feature is a string of 1 or more lower case English letters

Phần nằm trong dấu ngoặc vuông, [], là tùy chọn. Các dấu ngoặc đơn (), weight và feature là các token. Sẽ có ít nhất một ký tự khoảng trắng giữa hai token bất kỳ, ngoại trừ (có thể) sau dấu ngoặc mở '(' hoặc trước dấu ngoặc đóng ')'. Các ký tự khoảng trắng bao gồm dấu cách (' ') và dấu xuống dòng ('\n').

Để tính toán khả năng một con vật đáng yêu như thế nào, chúng ta bắt đầu tại gốc của cây với xác suất \(p\) được đặt bằng \(1\). Tại mỗi nút, chúng ta nhân \(p\) với trọng số của nút đó. Nếu nút đó là lá (không có cây con), chúng ta dừng lại, và giá trị của \(p\) chính là xác suất con vật đó đáng yêu. Ngược lại, chúng ta xem xét đặc điểm liên quan đến nút đó. Nếu con vật có đặc điểm này, chúng ta đi xuống cây con thứ nhất và tiếp tục đệ quy. Nếu nó không có đặc điểm này, chúng ta đi xuống cây con thứ hai và tiếp tục theo cách tương tự.

Ví dụ, một con hải ly (beaver) là một loài động vật có hai đặc điểm: furry (có lông) và freshwater (sống ở nước ngọt). Chúng ta bắt đầu tại gốc với \(p\) bằng \(1\). Chúng ta nhân \(p\) với \(0.2\) (trọng số của gốc) và đi vào cây con thứ nhất vì hải ly có đặc điểm furry. Tại đó, chúng ta nhân \(p\) với \(0.81\), làm cho \(p\) bằng \(0.162\). Từ đó, chúng ta đi xuống cây con thứ hai vì hải ly không có đặc điểm fast. Cuối cùng, chúng ta nhân \(p\) với \(0.2\) và kết thúc với \(0.0324\) -- xác suất mà con hải ly đó đáng yêu.

Bạn sẽ được cung cấp một cây quyết định và một danh sách các loài động vật cùng với các đặc điểm của chúng. Với mỗi đối tượng, bạn cần trả về xác suất con vật đó đáng yêu.

Dữ liệu vào

Dòng đầu tiên của đầu vào chứa một số nguyên duy nhất, N, là số lượng bộ thử nghiệm. N bộ thử nghiệm tiếp theo.

Mỗi mô tả bộ thử nghiệm sẽ bắt đầu bằng một dòng chứa một số nguyên L -- số dòng mô tả cây quyết định. L dòng tiếp theo sẽ chứa một cây quyết định theo định dạng mô tả ở trên. Dòng sau đó sẽ chứa A -- số lượng động vật. A dòng tiếp theo, mỗi dòng sẽ chứa mô tả của một con vật theo định dạng sau:

animal n feature1 feature2 ... featuren

Dữ liệu ra

Với mỗi bộ thử nghiệm, xuất một dòng chứa "Case #x:" theo sau là chính xác A dòng, mỗi dòng cho một con vật, theo đúng thứ tự xuất hiện trong đầu vào. Mỗi dòng nên chứa xác suất con vật đó đáng yêu. Các câu trả lời có sai số tuyệt đối hoặc tương đối trong khoảng \(10^{-6}\) sẽ được coi là chính xác.

Ràng buộc

• \(1 \le \mathbf{N} \le 100\)
• Tất cả các trọng số sẽ nằm trong khoảng từ \(0\) đến \(1\), bao gồm cả hai đầu.
• Tất cả các trọng số sẽ chỉ bao gồm các chữ số với tối đa một dấu chấm thập phân.
• Các trọng số sẽ không bắt đầu hoặc kết thúc bằng dấu chấm thập phân.
• Các trọng số sẽ không có nhiều hơn một chữ số \(0\) trước dấu chấm thập phân.
• Tất cả tên động vật và đặc điểm sẽ bao gồm từ \(1\) đến \(10\) chữ cái tiếng Anh viết thường.
• Tất cả tên động vật trong một bộ thử nghiệm sẽ khác nhau.
• Tất cả các tên đặc điểm cho một con vật duy nhất sẽ khác nhau.
• Mỗi dòng trong số L dòng định nghĩa cây quyết định sẽ có tối đa 80 ký tự, không bao gồm ký tự xuống dòng.

Phân nhóm

• Small dataset: \(1 \le \mathbf{L} \le 10\), \(1 \le \mathbf{A} \le 10\), \(0 \le \mathbf{n} \le 5\).
• Large dataset: \(1 \le \mathbf{L} \le 100\), \(1 \le \mathbf{A} \le 100\), \(0 \le \mathbf{n} \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

1
3
(0.5 cool
  ( 1.000)
  (0.5 ))
2
anteater 1 cool
cockroach 0

Case #1:
0.5000000
0.2500000

Nguồn

Google Code Jam 2009, Vòng 1B, bài Decision Tree.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.