orz p_b_p_b。
下文令 \(a_i\) 为原题面中的 \(x_i\)。
拿到题目无从下手，不妨简化一下。
考虑 \(n = 2\) 怎么做。不妨设 \(a_1 \ge a_2\)。发现若 \(a_2 \le \left\lfloor\frac{m}{2}\right\rfloor\) 时 A 必胜，否则 B 必胜。
于是我们大胆猜测结论是将 \(a\) 从大到小排序后，\(\forall i \in [2, n], a_i \le \left\lfloor\frac{m}{i}\right\rfloor\) 时 A 必胜，否则 B 必胜。
证明是容易的。根据抽屉原理，第 \(i\) 轮开始前不包含选过的元素的极长连续段长度的最大值最小是 \(\left\lceil\frac{m - i + 1}{i}\right\rceil = \left\lfloor\frac{m}{i}\right\rfloor\)。因此：
- 如果不满足 \(\forall i \in [2, n], a_i \le \left\lfloor\frac{m}{i}\right\rfloor\)，设 \(p\) 为使得 \(a_p > \left\lfloor\frac{m}{i}\right\rfloor\) 的位置，那么 A 选择长度 \(\ge a_p\) 的区间时，Bob 一定可以在这个区间内找到 \([1, m]\) 的 \(a_p\) 等分点（即 \(a_p \mid x\) 的点），这样 A 选完 \([1, p]\) 的区间后，B 一定能获胜。
- 否则，第 \(i\) 轮 A 随便选一个长度 \(= a_i\) 的未被覆盖的区间即可。因为满足 \(\forall i \in [2, n], a_i \le \left\lfloor\frac{m}{i}\right\rfloor\)，所以第 \(i\) 轮一定存在一个长度 \(= a_i\) 的未被覆盖的区间。
交互就直接按上面模拟即可。
code
// Problem: C. Library game
// Contest: Codeforces - SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
// URL: https://codeforces.com/problemset/problem/1776/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 5050;
int n, m, a[maxn];
namespace Sub1 {
struct cmp {
inline bool operator () (const pii &a, const pii &b) {
return a.scd - a.fst > b.scd - b.fst;
}
};
void solve() {
puts("Alessia");
fflush(stdout);
multiset<pii, cmp> st;
st.emplace(1, m);
for (int i = 1; i <= n; ++i) {
pii p = *st.begin();
int l = p.fst, r = p.scd;
st.erase(st.begin());
printf("%d %d\n", a[i], l);
fflush(stdout);
int x;
scanf("%d", &x);
if (l < x) {
st.emplace(l, x - 1);
}
if (x < r) {
st.emplace(x + 1, r);
}
}
}
}
namespace Sub2 {
bool vis[maxn];
void solve() {
puts("Bernardo");
fflush(stdout);
int p = -1;
for (int i = 1; i <= n; ++i) {
if (a[i] > m / i) {
p = i;
break;
}
}
for (int i = 1, l, r; i <= n; ++i) {
scanf("%d%d", &r, &l);
r += l - 1;
int len = r - l + 1;
if (len < a[p]) {
printf("%d\n", l);
fflush(stdout);
vis[l] = 1;
continue;
}
for (int j = l; j <= r; ++j) {
if (j % a[p] == 0) {
printf("%d\n", j);
fflush(stdout);
vis[j] = 1;
break;
}
}
}
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1, greater<int>());
bool flag = 1;
for (int i = 1; i <= n; ++i) {
if (a[i] > m / i) {
flag = 0;
break;
}
}
if (flag) {
Sub1::solve();
} else {
Sub2::solve();
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}