Google Code Jam 2009 - Round 1B

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.

Giả sử chúng ta có một hình vuông có \(W\) ô mỗi cạnh, và do đó có tổng cộng \(W^2\) ô. Hãy lấp đầy mỗi ô bằng một trong các loại sau:

• Một chữ số từ 0 đến 9;
• Dấu cộng (+);
• Dấu trừ (-).

Nếu chúng ta thêm ràng buộc rằng không có 2 chữ số nào nằm kề nhau theo chiều ngang hoặc chiều dọc, và không có 2 toán tử (+ hoặc -) nào nằm kề nhau theo chiều ngang hoặc chiều dọc, thì hình vuông của chúng ta được gọi là một "hình vuông số học".

Square Math là tên của một trò chơi đố chữ, trong đó, cho trước một hình vuông số học, chúng ta bắt đầu từ bất kỳ ô chứa chữ số nào và di chuyển theo chiều ngang hoặc chiều dọc mỗi lần một ô, cuối cùng kết thúc ở một ô chứa chữ số. Biểu thức toán học chúng ta nhận được từ quá trình di chuyển sẽ được tính toán để ra một giá trị duy nhất. Ví dụ:

2+3
+4-
1+0

Trên đây là một hình vuông số học hợp lệ kích thước \(W = 3\). Nếu chúng ta bắt đầu từ "2", di chuyển sang phải, sau đó xuống dưới, chúng ta sẽ có "2+4", cho giá trị là "6". Nếu chúng ta tiếp tục di chuyển sang phải, sau đó lên trên, chúng ta sẽ có "2+4-3", bằng "3".

Trong Square Math, không có giới hạn về số lần bạn có thể sử dụng một ô cụ thể. Việc di chuyển từ một ô sang ô lân cận, rồi quay lại ô ban đầu là hoàn toàn hợp lệ. Cho một hình vuông số học và một danh sách các truy vấn, nhiệm vụ của bạn là tìm một biểu thức Square Math có giá trị bằng mỗi truy vấn.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất, \(T\). \(T\) bộ dữ liệu kiểm tra theo sau. Dòng đầu tiên của mỗi bộ dữ liệu chứa 2 số nguyên, \(W\) và \(Q\). \(W\) dòng tiếp theo, mỗi dòng chứa \(W\) ký tự, đại diện cho hình vuông số học. Đừng lo lắng, tất cả các hình vuông số học trong dữ liệu vào đều được định dạng đúng. Dòng tiếp theo chứa một danh sách \(Q\) số nguyên cách nhau bởi dấu cách, đại diện cho các giá trị cần được tính toán bằng Square Math (các truy vấn). Bạn có thể giả định rằng tất cả các giá trị cho trước sẽ có ít nhất một giải pháp Square Math khả thi.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, bắt đầu đầu ra với "Case #\(X\):" trên một dòng riêng biệt, trong đó \(X\) là số thứ tự bộ dữ liệu, bắt đầu từ 1. Sau đó, đối với mỗi truy vấn trong bộ dữ liệu, hãy in biểu thức Square Math có giá trị bằng truy vấn đó trên một dòng riêng biệt.

Trong trường hợp có nhiều biểu thức Square Math khả thi, hãy in biểu thức ngắn nhất. Nếu vẫn còn hòa, hãy in biểu thức nhỏ nhất theo thứ tự từ điển. Lưu ý rằng '+' nhỏ hơn '-' theo thứ tự từ điển.

Ràng buộc

• \(1 \le T \le 60\)

Phân nhóm

• Small dataset:

  • \(2 \le W \le 10\)
  • \(1 \le Q \le 20\)
  • \(1 \le \text{mỗi truy vấn} \le 50\)

  • Large dataset:

  • \(2 \le W \le 20\)

  • \(1 \le Q \le 50\)
  • \(1 \le \text{mỗi truy vấn} \le 250\)

Đ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ụ

2
5 3
2+1-2
+3-4+
5+2+1
-4-0-
9+5+1
20 30 40
3 2
2+1
+4+
5+1
2 20

Case #1:
1+5+5+9
3+4+5+9+9
4+9+9+9+9
Case #2:
2
5+5+5+5

Nguồn

Google Code Jam 2009, Vòng 1B, bài Square Math.

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

Bạn đang viết một danh sách các số. Danh sách của bạn chứa tất cả các số có đúng \(D_i\) chữ số trong biểu diễn thập phân của nó bằng \(i\), với mỗi \(i\) từ 1 đến 9, bao gồm cả hai đầu. Bạn đang viết chúng theo thứ tự tăng dần.

Ví dụ, bạn có thể đang viết mọi số có hai chữ số '1' và một chữ số '5'. Danh sách của bạn sẽ bắt đầu bằng 115, 151, 511, 1015, 1051.

Cho \(N\), là số cuối cùng bạn đã viết, hãy tính số tiếp theo trong danh sách sẽ là gì.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên \(T\), số lượng bộ dữ liệu kiểm tra. \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\).

Dữ liệu ra

Đối với mỗi bộ dữ liệu, hãy xuất:

Case #X: K

Ràng buộc

• \(1 \le T \le 500\) (đối với Large dataset).

Phân nhóm

• Small dataset: \(1 \le N \le 10^6\), \(1 \le T \le 50\).
• Large dataset: \(1 \le N \le 10^{20}\), \(1 \le T \le 500\).

Đ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ụ

3
115
1051
6233

Case #1: 151
Case #2: 1105
Case #3: 6323

Nguồn

Google Code Jam 2009, Vòng 1B, bài The Next Number.

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