# A. Closest Picks

## Description

You are entering a raffle for a lifetime supply of pancakes. $N$ tickets have already been sold. Each ticket contains a single integer between 1 and $K$, 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 1 and $K$, 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 c between 1 and $K$, inclusive, is chosen uniformly at random. If one of your tickets is strictly closer to c than all other tickets or if both of your tickets are the same distance to c and strictly closer than all other tickets, then you win the raffle. Otherwise, you do not win the raffle.

Given the integers on the $N$ 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?

$N \leq 30,K \leq 10^9$

## Tutorial

$N$ 很小，所以随便来。

## Code

constexpr int N = 35;
int n, k, a[N];
int case_num = 1;
void preInit() { }
void init() {
n = sc.n(); k = sc.n();
for (int i: range(n)) a[i] = sc.n();
std::sort(a, a+n); }
void solve() {
Vector<int> bars { a[0] - 1, k - a[n-1] };
for (int i=0; i+1<n; ++i) bars.push_back((a[i+1] - a[i]) / 2);
std::sort(bars.begin(), bars.end(), std::greater<int>());
int ans1 = bars[0] + bars[1];
int ans2 = std::max(a[0] - 1, k - a[n-1]);
for (int i=0; i+1<n; ++i) checkMax(ans2, a[i + 1] - a[i] - 1);
printf("Case #%d: %.12lf\n", case_num++,
1.0 * std::max(ans1, ans2) / k); }


# B. Roaring Years

## Description

$n \leq 10^{18}$

## Code

def gen(a, n):
res = ""
for i in range(n):
res = res + str(a)
a += 1
return int(res)
def main():
n = int(input())
ans = 10 ** 100
for length in range(2, 18):
l, r = 1, 10 ** 20
while l < r:
mid = (l + r) // 2
if gen(mid, length) > n:
r = mid
else:
l = mid + 1
pos = gen(l, length)
if ans > pos:
ans = pos
return ans
T = int(input())
for i in range(T):
print("Case #{}: {}".format(i + 1, main()))


# C. Double or NOTing

## Description

Test Set 1: $|s|, |t| \leq 8$

Test Set 2: $|s|, |t| \leq 100$

## Code

def trim(n):
while len(n) > 1 and n[0] == "0":
n = n[1:]
return n
def noting(n):
return trim("".join(map(lambda c: "1" if c == "0" else "0", n)))
def doubling(n):
if n == "0":
return "0"
return n + "0"
def doit(f, t, param):
pos = param[0] if len(param) >= 1 else " "
ans = 0
for c in param:
if c != pos:
f = noting(f)
ans += 1
f = doubling(f)
ans += 1
pos = c
if pos == "1":
f = noting(f)
ans += 1
while len(f) > len(t):
f = noting(noting(f))
ans += 2
if f == t:
return ans
return 10 ** 100
def main():
a, b = input().split()
ans = 10 ** 100
lb = len(b)
for i in range(lb+1):
# 第一步是 doubling
ans = min(ans, doit(a, b, b[lb-i:]))
# 第一步是 noting
ans = min(ans, doit(noting(a), b, b[lb-i:]) + 1)
if ans >= 10 ** 100:
return "IMPOSSIBLE"
return ans
T = int(input())
for i in range(T):
print("Case #{}: {}".format(i + 1, main()))