Codeforces #341 Div2 C
考察
・が素数Pで割り切れる場合はとで1000ドルずつ、合わせて2000ドル発生する。
・が素数Pで割り切れるときは、または最低でも一方がPで割り切れなければならない。
・つまり、とがどちらもPで割り切れないのならば、2000ドルは発生しない。
・はからまで通りある。
・そのうち、がPで割り切れるのは通り。
・ということはがPで割り切れる確率は
・そして、間で2000ドルが発生する確率は(1 - (1-がPで割り切れる確率) * (1 - がPで割り切れる確率))で求まる。
・ * 2000 = 間で2000ドルが発生する期待値
・問題文にある通りはと隣り合っていることになるので、正確にははである。
・以上の計算をすべての間で行い、その和が解となる。
参考:
pakapa104.hatenablog.com
pekempey.hatenablog.com
kmjp.hatenablog.jp
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class C { //http://codeforces.com/contest/621/problem/C int N,P; int[] l,r; double[] zero; public void solve() { N = nextInt(); P = nextInt(); l = new int[N]; r = new int[N]; zero = new double[N]; for(int i = 0;i < N;i++){ l[i] = nextInt(); r[i] = nextInt(); } zero = new double[N]; for(int i = 0;i < N;i++){ zero[i] = (r[i] / P - (l[i] - 1) / P) * (1.0 / (r[i] - l[i] + 1)); } double dollars = 0; for(int i = 0;i < N;i++){ int j = (i + 1) % N; dollars += 1.0 - (1.0 - zero[i]) * (1.0 - zero[j]); } dollars *= 2000; out.println(String.format("%.9f",dollars)); } public static void main(String[] args) { out.flush(); new C().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }