这里有一道老实题,大家快来踩爆它!
交互题:根据你的输出决定下一次的输入。
请听题:
管理员有个乱序数列(举例:{14, 24, 9, 19}),排序以后是个等差数列({9, 14, 19, 24}),现在他只告诉你有n个数(样例n = 4)却不给你数列,让你求出最小的那个数(9)和公差d(5)。
而你可以在不超过60次的询问之后再给出结果,询问有两种方式:
1. 输出“> x”,暗示是否存在大于x的数,如果存在,管理员回复“1”,否则回复“0”。(这个回复自己读入一下谢谢~)
2. 输出“? i”,请求查询乱序数列第i个数是几,然后管理员会告诉你哒。
最后你得到结果后最终输出“! minnum d”。
样例:
input:
4
(注意以下输入数据是对应你的输出的)
0
1
14
24
9
19
output: > 25(之后有了输入0)
> 15(之后有了输入1)
? 1 (之后有了输入14)
? 2
? 3
? 4
! 9 5(这个就是答案了)
题解:
头一次遇到这么简单的E题大家自己AC吧全剧终。
好,大家A掉了以后我来分享一下我做这个题的思路历程:
首先自鸣得意地想到如果数列长度不足60那在下岂不是厚着脸皮问出来就行了……于是有了下面这段代码:
void work1() {
for (int i = 1; i <= n; i++) {
printf("? %d\n", i);
fflush(stdout);scanf("%d", &a[i]);
}
sort(a + 1, a + 1 + n);
printf("! %d %d\n", a[1], a[2] - a[1]);
}
int main() {
scanf("%d", &n);
if (n <= 60) work1();
然后果然这段代码是没卵用的,还是要想个更一般的方法。
那么根据这题的询问模式我们不难意淫到这样一个场景:你让心仪的妹子心中默念一个1~2147483647的数字,因为不忍心拒绝激动而又熟稔地背出一串奇怪数字的你,正在和吴彦祖聊天的妹子于是默念520。好的君已入瓮,你遂使出了(非)计算机专业引以为傲的“二分莽猜之术”猜了二三十次以后猜到了答案并说了出来,然后……
然后AlphaWA过来问你可以用这种方法得到最小值咩?啊不能。but问个log1e9(≈30)次总能得到个最大值了对吧?
好,好。30是60的一半,这路子很稳。有了最大值和项数,根据小学奥数知识我们不难搞出最小值了。
那么剩下的30次询问怎么用呢?可以得到其中的一些数喽。于是有了以下思考历程:
1. 用30次可以抽到(排序后)连续的两个数吗,这样公差d就出来了?欧皇可,非酋不可。
2. 那能搞到第二大的值吗,道理同上?回答同上。
3. emmm那随便来几个数,有什么办法搞到d?唔,他们的差一定是d的倍数,gcd一遍就好啦!
4. 稳吗?不稳,比如2,4,6,8,10,12,我们如果抽到4,8,12,会得到d = 4这一错误结果。
5. 所以根据大数据的原理(大雾),数字越多错误率越低,且请随机抽取,免得有规律抽取被一些居心不良的红名同学出一组针对数据hack掉。
嗯,那就做完了。参考代码,请无视掉:小家子气的60以下特判、写1024次1024个模样的二分、未使用mt19937的乡下随机。
#include <bits/stdc++.h>
using namespace std;
int n, d, maxx;
int a[65];
bool mark[1000005];
int random(int n) {
return (double)rand()/RAND_MAX * n + 0.5;
}
void work1() {
for (int i = 1; i <= n; i++) {
printf("? %d\n", i);
fflush(stdout);
scanf("%d", &a[i]);
}
sort(a + 1, a + 1 + n);
printf("! %d %d\n", a[1], a[2] - a[1]);
}
int main() {
scanf("%d", &n);
if (n <= 60) work1();
else {
int l = 0, r = 1e9, cnt = 0;
while (l < r) {//二分莽猜
int mid = (l + r) >> 1;
printf("> %d\n", mid);fflush(stdout);
cnt++;
scanf("%d", &d);
if (d) l = mid + 1, maxx = l;
else r = mid;
}
//随机序列
srand(time(0));
for (int i = cnt + 1; i <= 60; i++) {
d = 0;
do {
mark[d] = true;
d = random(n) + 1;
} while (mark[d]);
printf("? %d\n", d);
fflush(stdout);
scanf("%d", &a[i]);
}
sort(a + cnt + 1, a + 61);
//gcd
d = a[cnt+2] - a[cnt+1];
for (int i = cnt + 3; i <= 60; i++) {
d = __gcd(d, a[i] - a[i-1]);
}
printf("! %d %d\n", maxx - (n-1) * d, d);
}
return 0;
}
最后奉上御用std:
#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
int n, Max = -1000000000, d = 0;
int queryRemaining = 60; vector<int> id;
void findMax() {
int top = -1000000000, bot = +1000000000;
while (top <= bot) {
int hasHigher;
int mid = (top + bot) / 2;
cout << "> " << mid << endl;
fflush(stdout); cin >> hasHigher;
queryRemaining--;
if (hasHigher) top = mid + 1;
else {bot = mid - 1; Max = mid;}
}
}
void findD() {
vector<int> List; int RandomRange = n;
while (queryRemaining > 0 && RandomRange > 0) {
int demandedIndex = rng32() % RandomRange;
cout << "? " << id[demandedIndex] << endl; fflush(stdout);
int z; cin >> z; List.push_back(z);
RandomRange--; queryRemaining--;
swap(id[demandedIndex], id[RandomRange]);
}
sort(List.begin(), List.end());
if (List.back() != Max) List.push_back(Max);
for (int i=1; i<List.size(); i++) {
d = __gcd(d, List[i] - List[i-1]);
}
}
void Input() {
cin >> n; id.resize(n);
for (int i=0; i<n; i++) id[i] = i+1;
}
void Solve() {
findMax(); findD();
int Min = Max - d * (n - 1);
cout << "! " << Min << " " << d;
cout << endl; fflush(stdout);
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0);
Input(); Solve(); return 0;
}