Problem
You are entering a raffle for a lifetime supply of pancakes. NN tickets have already been sold. Each ticket contains a single integer between 11 and KK, inclusive. Different tickets are allowed to contain the same integer. You know exactly which numbers are on all of the tickets already sold and would like to maximize your odds of winning by purchasing two tickets (possibly with the same integer on them). You are allowed to choose which integers between 11 and KK, inclusive, are on the two tickets.
You know you are the last customer, so after you purchase your tickets, no more tickets will be purchased. Then, an integer cc between 11 and KK, inclusive, is chosen uniformly at random. If one of your tickets is strictly closer to cc than all other tickets or if both of your tickets are the same distance to cc and strictly closer than all other tickets, then you win the raffle. Otherwise, you do not win the raffle.
Given the integers on the NN tickets purchased so far, what is the maximum probability of winning the raffle you can achieve by choosing the integers on your two tickets optimally?
Input
The first line of the input gives the number of test cases, TT. TT test cases follow. Each test case consists of two lines. The first line of a test case contains two integers NN and KK: the number of tickets already sold and the limit of the range of integers to pick from, respectively. The second line contains NN integers P1,P2,…,PNP1,P2,…,PN, representing the integers on the tickets that have already been purchased.
Output
For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the maximum win probability you can achieve if you choose your tickets optimally.
yy will be considered correct if it is within an absolute or relative error of 10−610−6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.
Limits
Time limit: 10 seconds.
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
1≤N≤301≤N≤30.
1≤Pi≤K1≤Pi≤K, for all ii.
Test Set 1 (Visible Verdict)
1≤K≤301≤K≤30.
Test Set 2 (Visible Verdict)
1≤K≤1091≤K≤109.
Sample
Sample Input
4 3 10 1 3 7 4 10 4 1 7 3 4 3 1 2 3 2 4 4 1 2 4 2
Sample Output
Case #1: 0.5 Case #2: 0.4 Case #3: 0.0 Case #4: 0.25
In Sample Case #1, you can purchase tickets with the integers 44 and 88 on them and then win if 4,5,8,94,5,8,9, or 1010 are chosen giving you 5/10=0.55/10=0.5 probability of winning. Purchasing tickets with the integers 66 and 88 on them also yields a 0.50.5 probability of winning, but no combination yields more.
In Sample Case #2, 66 and 88 is a possible optimal pair of tickets, which wins when cc is one of 6,8,96,8,9, or 1010. Note that the integers on the tickets are not necessarily given in sorted order.
In Sample Case #3, every possible cc is at distance 00 from an already purchased ticket, so you cannot win regardless of your choices.
In Sample Case #4, if you pick 33 for at least one of your tickets, you win on c=3c=3, for 1/4=0.251/4=0.25 win probability. There is no way to win when cc is any other integer, so that is the best you can do.
Solution:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int T;
int n, k;
int a[maxn + 10], b[maxn + 10], bcnt;
int main() {
scanf(“%d”, &T);
for (int cas = 1; cas <= T; ++cas) {
scanf(“%d%d”, &n, &k);
for (int i = 1; i <= n; ++i)
scanf(“%d”, &a[i]);
sort(a + 1, a + n + 1);
bcnt = 0;
b[++bcnt] = a[1] – 1;
b[++bcnt] = k – a[n];
for (int i = 1; i < n; ++i)
b[++bcnt] = (a[i + 1] – a[i]) / 2;
sort(b + 1, b + bcnt + 1);
int ans = b[bcnt] + b[bcnt – 1];
for (int i = 1; i < n; ++i)
ans = max(ans, a[i + 1] – a[i] – 1);
printf(“Case #%d: %.10lf\n”, cas, 1. * ans / k);
}
}
