E. Санамсаргүй эрэмблэлт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Магадлалын шалгалтанд $1$-ээс $n$ гэж дугаарлагдсан $n$ сурагч оролцож байгаа. Шалгалтыг илүү сонирхолтой болгохын тулд өмнөх үр дүнгүүдээ ашиглан энэ шалгалтанд хэн хэрхэн орохыг таамагласан статистик гаргахаар болжээ.

Сурагч бүрийн оноо нь $[l_i, r_i]$ (оноо нь бодит тоо байна) завсарт жигд тархалттай байна гэж үзье.

Сурагчдын оноог багаас нь их рүү нь дугаарлахад $i$ дүгээр сурагч $j$ дүгээр байранд орох магадлал бүрийг ол. ($1 ≤ i ≤ n$, $1 ≤ j ≤ n$). Онооны жагсаалтанд хамгийн өндөр оноотой хүн хамгийн сүүлийн байранд бичигддэг.

Оролт

Эхний мѳрѳнд сурагчдын тоо $n$ ($1 ≤ n ≤ 80$) ѳгѳгднѳ. Дараагийн $n$ мѳр бүрт сурагчдын авах онооны муж $l_i$, $r_i$ ($0 ≤ l_i < r_i ≤ 10^9$) бүхэл тоонууд өгөгдөнө.

Сурагчдыг $1$-с $n$ хүртэл дугаарлагдсан гэж үз.

Гаралт

Гаралт нь $n$ мөртэй ба мөр бүрт $n$ тоо хэвлэнэ. $i$ дүгээр мөрний $j$ дүгээр тоо нь $i$ дүгээр сурагч $j$ дүгээр байранд орох магадлалыг заана. ($1 ≤ i ≤ n$, $1 ≤ j ≤ n$).

Хэрвээ таны хариу зөв хариунаас $10^{-6}$-с бага абсолют зөрүүтэй байвал зөв гэж үзнэ.

Орчуулсан: Сүрэнбаяр

Жишээ тэстүүд

Оролт
2
1 6
4 9
Гаралт
0.9200000000 0.080 
0.080 0.9200000000 
Оролт
8
0 2
1 3
2 4
3 5
4 6
5 7
6 8
7 9
Гаралт
0.875 0.125 0 0 0 0 0 0 
0.125 0.750 0.125 0 0 0 0 0 
0 0.125 0.750 0.125 0 0 0 0 
0 0 0.125 0.750 0.125 0 0 0 
0 0 0 0.125 0.750 0.125 0 0 
0 0 0 0 0.125 0.750 0.125 0 
0 0 0 0 0 0.125 0.750 0.125 
0 0 0 0 0 0 0.125 0.875 

Тэмдэглэл

The score probability distribution is continuous, which means, there is no possibility for a draw.

Сэтгэгдлүүдийг ачааллаж байна...