Đây là bài toán khó hiểu nhất trong vòng này. Nếu bạn là người mới tham gia Code Jam, bạn nên thử giải các bài toán khác trước.

Naomi và Ken thỉnh thoảng chơi trò chơi cùng nhau. Trước khi chơi, mỗi người nhận được \(N\) khối gỗ trông giống hệt nhau với khối lượng nằm trong khoảng từ \(0.0\)kg đến \(1.0\)kg (không bao gồm hai đầu mút). Tất cả các khối gỗ đều có trọng lượng khác nhau. Có rất nhiều trò chơi họ có thể chơi với những khối gỗ đó, nhưng họ thường chơi một trò gọi là War (Chiến tranh). Đây là cách trò War hoạt động:

1. Mỗi người chơi cân từng khối gỗ của mình, vì vậy mỗi người đều biết trọng lượng của tất cả các khối gỗ của mình, nhưng không biết trọng lượng các khối gỗ của người kia.
2. Họ lặp lại quy trình sau \(N\) lần:
   1. Naomi chọn một trong các khối gỗ của mình, có khối lượng Chosen_Naomi.
   2. Naomi nói cho Ken biết khối lượng của khối gỗ cô ấy đã chọn.
   3. Ken chọn một trong các khối gỗ của mình, có khối lượng Chosen_Ken.
   4. Mỗi người đặt khối gỗ của mình lên một bên của một chiếc cân bàn, và người có khối gỗ nặng hơn sẽ được một điểm.
   5. Cả hai khối gỗ đều bị tiêu hủy trong một đám cháy.

Naomi đã nhận ra ba điều về trò War. Thứ nhất, cô ấy nhận ra mình thua rất nhiều. Thứ hai, cô ấy nhận ra rằng có một chiến thuật duy nhất mà Ken có thể tuân theo để tối đa hóa điểm số của anh ấy mà không cần giả định bất cứ điều gì về chiến thuật của Naomi, và Ken luôn sử dụng nó. Thứ ba, cô ấy nhận ra rằng mình ghét thua cuộc. Naomi đã quyết định rằng thay vì chơi War, cô ấy sẽ chơi một trò chơi mà cô ấy gọi là Deceitful War (Chiến tranh Gian lận). Điều tuyệt vời về Deceitful War là Ken sẽ nghĩ rằng họ đang chơi War!

Dưới đây là cách Deceitful War hoạt động, với những điểm khác biệt giữa Deceitful War và War được in đậm:

1. Mỗi người chơi cân từng khối gỗ của mình. Naomi cũng cân các khối gỗ của Ken trong khi anh ấy không nhìn, vì vậy Naomi biết trọng lượng của tất cả các khối gỗ và Ken chỉ biết trọng lượng các khối gỗ của mình.
2. Họ lặp lại quy trình sau \(N\) lần:
   1. Naomi chọn một trong các khối gỗ của mình, có khối lượng Chosen_Naomi.
   2. Naomi nói với Ken một con số, Told_Naomi, nằm trong khoảng từ \(0.0\)kg đến \(1.0\)kg (không bao gồm hai đầu mút). Ken, người nghĩ rằng họ đang chơi War, nghĩ rằng con số Naomi vừa nói với anh ấy là Chosen_Naomi.
   3. Ken chọn một trong các khối gỗ của mình, có khối lượng Chosen_Ken.
   4. Mỗi người đặt khối gỗ của mình lên một bên của một chiếc cân bàn, và người có khối gỗ nặng hơn sẽ được một điểm.
   5. Cả hai khối gỗ đều bị tiêu hủy trong một đám cháy.

Naomi không muốn Ken biết rằng cô ấy không chơi War; vì vậy khi cô ấy chọn khối gỗ để chơi và khối lượng để nói với Ken, cô ấy phải đảm bảo rằng chiếc cân bàn sẽ không tiết lộ rằng Chosen_Naomi \(\neq\) Told_Naomi. Nói cách khác, cô ấy phải đưa ra quyết định sao cho:

• Chosen_Naomi > Chosen_Ken khi và chỉ khi Told_Naomi > Chosen_Ken, và
• Told_Naomi không bằng khối lượng của bất kỳ khối gỗ nào của Ken, vì anh ấy biết điều đó là không thể.

Có vẻ như Naomi sẽ không giành thêm được điểm nào bằng cách gian lận, vì Ken có thể phát hiện ra cô ấy không chơi War; nhưng Naomi biết Ken nghĩ cả hai người chơi đang chơi War, và cô ấy biết những gì anh ấy biết, và cô ấy biết Ken sẽ luôn tuân theo chiến thuật tối ưu duy nhất của anh ấy cho trò War, vì vậy cô ấy luôn có thể dự đoán anh ấy sẽ chơi gì.

Bạn sẽ được cung cấp khối lượng của các khối gỗ mà Naomi và Ken bắt đầu. Naomi sẽ chơi Deceitful War một cách tối ưu để giành được số điểm tối đa. Ken sẽ chơi War một cách tối ưu để giành được số điểm tối đa giả định rằng cả hai người chơi đang chơi War. Điểm của Naomi sẽ là bao nhiêu? Điểm của cô ấy sẽ là bao nhiêu nếu cô ấy chơi War một cách tối ưu?

Ví dụ

Nếu mỗi người chơi còn một khối gỗ duy nhất, trong đó Naomi có \(0.5\)kg và Ken có \(0.6\)kg, thì Ken chắc chắn sẽ ghi điểm. Naomi không thể nói số của mình \(\ge 0.6\)kg, nếu không Ken sẽ biết cô ấy không chơi War khi chiếc cân cho thấy khối gỗ của anh ấy nặng hơn.

Nếu mỗi người chơi còn hai khối gỗ, trong đó Naomi có \([0.7\text{kg}, 0.2\text{kg}]\) và Ken có \([0.8\text{kg}, 0.3\text{kg}]\), thì Naomi có thể chọn khối gỗ \(0.2\)kg của mình và lừa Ken bằng cách nói với anh ấy rằng cô ấy đã chọn một khối gỗ nặng \(0.6\)kg. Ken giả định Naomi đang nói thật (như trong cách trò chơi War hoạt động) và sẽ chơi khối gỗ \(0.8\)kg của mình để ghi điểm. Ken vừa bị lừa, nhưng anh ấy sẽ không bao giờ nhận ra vì chiếc cân cho thấy khối gỗ \(0.8\)kg của anh ấy, đúng như anh ấy mong đợi, nặng hơn khối gỗ Naomi đã chơi. Bây giờ Naomi có thể chơi khối gỗ \(0.7\)kg của mình, nói với Ken đó là \(0.7\)kg và ghi điểm. Nếu Naomi chơi War thay vì Deceitful War, Ken sẽ ghi được hai điểm và Naomi ghi được không điểm.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên duy nhất \(N\), số lượng khối gỗ mỗi người chơi có. Tiếp theo là một dòng chứa \(N\) số thực cách nhau bởi dấu cách: khối lượng các khối gỗ của Naomi, tính bằng kg. Cuối cùng sẽ là một dòng chứa \(N\) số thực cách nhau bởi dấu cách: khối lượng các khối gỗ của Ken, tính bằng kg.

Mỗi khối lượng được đưa cho Ken và Naomi sẽ được biểu diễn dưới dạng số \(0\), tiếp theo là dấu thập phân, tiếp theo là \(1\)-\(5\) chữ số. Mặc dù tất cả các số trong dữ liệu vào có \(1\)-\(5\) chữ số sau dấu thập phân, Ken và Naomi không biết điều đó; vì vậy Naomi vẫn có thể nói với Ken rằng cô ấy đã chơi một khối gỗ có khối lượng \(0.5000001\)kg, và Ken không có lý do gì để không tin cô ấy.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(x\): \(y\) \(z\)", trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), \(y\) là số điểm Naomi sẽ ghi được nếu cô ấy chơi Deceitful War tối ưu, và \(z\) là số điểm Naomi sẽ ghi được nếu cô ấy chơi War tối ưu.

Ràng buộc

• \(1 \le T \le 50\).
• Tất cả các khối lượng đưa cho Ken và Naomi là phân biệt và nằm trong khoảng từ \(0.0\) đến \(1.0\) (không bao gồm hai đầu mút).

Phân nhóm

• Small dataset: \(1 \le N \le 10\).
• Large dataset: \(1 \le N \le 1000\).

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

4
1
0.5
0.6
2
0.7 0.2
0.8 0.3
3
0.5 0.1 0.9
0.6 0.4 0.3
9
0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899
0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458

Case #1: 0 0
Case #2: 1 0
Case #3: 2 1
Case #4: 8 4

Nguồn

Google Code Jam 2014, Vòng loại, bài Deceitful War.

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