Sinh Test

Xem PDF

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Gần đây thoi_bay_corona ra bài Không Chia Hết trong đó input gồm hai số \(n, k\). Giới hạn bài toán như sau: \(2 \leq n \leq M; 1 \leq k \leq M\) (trong bài gốc \(M=10^9\)). Tuy nhiên admin phát hiện SPyofgame làm thuật \(O(\frac{k}{n})\) nhưng lại AC. Các admin ngay lập tức ngồi lại tìm hiểu nguyên nhân. Họ nghi ngờ rằng chương trình sinh test của thoi_bay_corona có dạng như sau:

cout << randInt(2, M) << " " << randInt(1, M);

trong đó randInt(a, b) là một hàm trả về một số nguyên ngẫu nhiên trong đoạn \([a, b]\). Nói cách khác chương trình in ra hai số \(n, k\) ngẫu nhiên trong đoạn \([2, M]\)\([1, M]\)

Biết rằng máy chấm của LQDOJ có thể tính được \(N\) phép tính trong 1s. Vì sao lời giải của SPyofgame lại AC? Hãy giúp các admin tính xác suất mà \(\dfrac{k}{n} \leq N\) nhé.

Input

  • Gồm một dòng có 2 số nguyên \(M, N (M \geq 2, N \geq 1)\).

Output

  • In ra một số thực là kết quả bài toán. Kết quả sẽ được chấp nhận nếu chênh lệch so với đáp án không vượt quá \(10^{-6}\)

Scoring

  • Subask \(1\) (\(30\%\) số điểm): \(M, N \leq 10^6\)
  • Subask \(2\) (\(30\%\) số điểm): \(M, N \leq 10^9\)
  • Subask \(3\) (\(40\%\) số điểm): \(M, N \leq 10^{18}\)

Example

Test 1

Input
100 15
Output
0.9797979798

Test 2

Input
100 10
Output
0.9636363636
Note

Xác suất cần tính là: \(\dfrac {\textbf{Số cặp (k, n) thỏa mãn}: \ \dfrac{k}{n} \leq N}{\textbf{Tổng số cặp (k, n)}}\)


Bình luận

Không có bình luận nào.