DRLINES - Vẽ đoạn thẳng

Giới hạn
  • Thời gian: 0.157s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Đề bài

Bờm vẽ một hình chữ nhật. Ở cạnh trên của hình, Bờm vẽ n điểm và đánh số 1..n từ trái sang phải. Ở cạnh dưới, Bờm cũng vẽ n điểm và đánh số 1..n từ trái sang phải.

Bờm sẽ vẽ n đoạn thẳng. Với mỗi đoạn, Bờm sẽ chọn một điểm chưa chọn ở cạnh trên, sau đó sẽ chọn một điểm chưa chọn ở cạnh dưới. Cuối cùng Bờm nối hai điểm với nhau để tạo thành đoạn thẳng.

Bờm đã vẽ được một số đoạn thẳng rồi. Với các đoạn còn lại, Bờm sẽ chọn ngẫu nhiên một điểm ở cạnh trên và một điểm ở cạnh dưới để nối lại với nhau. Hãy tính giá trị kỳ vọng (expected value) của số cặp đoạn thẳng cắt nhau sau khi Bờm hoàn thành bức vẽ.

Dữ liệu

  • Mỗi test bắt đầu bằng thẻ "[CASE]", các test cách nhau bởi một dòng trắng. Thẻ "[END]" báo hiệu kết thúc file input.
  • Với mỗi test, dòng đầu tiên chứa N
  • Tiếp theo là dòng "<<".
  • Các dòng tiếp theo chứa số hiệu các điểm ở cạnh trên của các đoạn thẳng mà Bờm đã vẽ.
  • Tiếp theo là dòng ">>'.
  • Tiếp theo là dòng "<<".
  • Các dòng tiếp theo chứa số hiệu các điểm ở cạnh dưới của các đoạn thẳng mà Bờm đã vẽ.
  • Tiếp theo là dòng ">>'.

Kết quả

  • Với mỗi test, in ra giá trị kỳ vọng tìm được, với sai số không quá 1E-6.

Giới hạn

  • N nằm trong phạm vi từ 1..10000.
  • Số đoạn thẳng Bờm đã vẽ từ 1..50.

Ví dụ 

Dữ liệu
[CASE]
3
<<
2
>>
<<
3
>>

[CASE]
5
<<
1
4
>>
<<
3
1
>>

[END]
Kết quả
1.5
5.5

Ví dụ 1:

Có 4 cách để Bờm chọn các điểm 

[Trên 1]-[Dưới 1] [Trên 3]-[Dưới 2]
[Trên 1]-[Dưới 2] [Trên 3]-[Dưới 1]
[Trên 3]-[Dưới 1] [Trên 1]-[Dưới 2]
[Trên 3]-[Dưới 2] [Trên 1]-[Dưới 1]

Cách 1 và 4 tương ứng với hình bên trái. Cách 2 và 3 tương ứng với hình bên phải. Đoạn thẳng xanh là đoạn thẳng vẽ ban đầu bởi Bờm. Trong hình trái, có 1 cặp đoạn thẳng cắt nhau. Trong hình phải, có 2 cặp đoạn thẳng cắt nhau. Do đó giá trị kỳ vọng của số cặp đoạn thẳng cắt nhau là 1.5.

  • Người up: voj
  • Nguồn bài: SRM 470, Div 1- Level 2Người dịch: Ngô Minh Ðức