Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DRLINES - Vẽ đoạn thẳng

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/drlines


Đề 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.


Được gửi lên bởi:VOJ Team
Ngày:2010-06-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:SRM 470, Div 1- Level 2
Người dịch: Ngô Minh Đức

hide comments
2010-06-04 16:47:56 Trần Hải Ðãng
use printf("%.6lf\n",r) to get AC!
2010-06-04 12:14:11 Huy Luu
Xuất như thế nào vậy anh? Có làm tròn không ?

Last edit: 2010-06-04 12:29:44
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.