Black and White Nim


Submit solution

Points: 1.78 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem source:
Code Craft 09
Problem type

Trò chơi Nim Đen Trắng được chơi như sau: Có ~N~ hàng, mỗi hàng chứa một số hạt màu đen và trắng. Hai người chơi lần lượt thực hiện lượt đi bằng cách bỏ đi các hạt cho đến hết.

Trong mỗi lượt đi, một người chơi phải bỏ đi một hoặc nhiều hạt liên tiếp từ đầu bên trái của một hàng.

Các hạt bị bỏ đi phải chứa hoặc là không hạt nào màu đen, hoặc là có duy nhất một hạt đen. Nếu một hạt màu đen bị bỏ đi, hạt đó phải là hạt bên phải nhất của dãy các hạt bị bỏ.

Người nào đi lượt cuối cùng là người chiến thắng.

Cho số lượng hạt màu đen và màu trắng ở mỗi hàng. Thứ tự của các hạt trên một hàng được tạo ra một cách ngẫu nhiên vào thời điểm bắt đầu trò chơi. Thứ tự của các hàng phân biệt có thể giống nhau. Các hạt màu đen giống hệt nhau, và các hạt màu trắng cũng giống hệt nhau (không thể phân biệt các hạt cùng màu).

In ra xác suất mà người đi trước thắng nếu như cả hai người đều chơi tối ưu.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ là số test

Sau đó là ~t~ test, mỗi test có ~3~ dòng, trong đó:

  • Dòng đầu chứa ~N~ là số hàng.
  • Dòng thứ hai chứa ~N~ số nguyên dương ~b_1,b_2,\ldots,b_N~, ~b_i \leq 100~, thể hiện số lượng hạt màu đen trên mỗi hàng.
  • Dòng thứ ba chứa ~N~ số nguyên dương ~w_1,w_2,\ldots,w_N~, ~w_i \leq 100~ thể hiện số lượng hạt màu trắng trên mỗi hàng.

Output

Với mỗi test, in ra trên một dòng một số thực, thể hiện đáp số.

Sai số tối đa cho đáp án của bạn so với đáp án của VNOI là ~10^{-6}~.

Sample Input

4

1
0
2

1
2
0

1
2
2

2
2 5
2 0

Sample Output

1.000000
0.000000
0.666667
0.666667

Comments

There are no comments at the moment.