题目概述

交互题，现在有一个数 $x(1\le x\le 10004205361450474)$ ，每次可以询问 $k(k\le x\land k<10000)$ 个数，将会回答 $a_{pos-1}<x<a_{pos}$ 或者 $x=a_{pos}$ ，此时胜利。在 $5$ 次询问内胜利。

解题报告

神仙题，由于并不知道 $x$ ，所以不敢询问太大的 $k$ 。考虑这样的策略：目前还有 $t$ 次询问，已经知道 $x\ge L$ ，那么我求出在 $L$ 花 $t-1$ 次能够到达的最远位置 $R$ ，然后从 $R+1$ 开始，求出花 $t-1$ 次能够到达的最远位置 $R'$ ，做 $min\{L,10000\}+1$ 次（询问 $k$ 有 $k+1$ 个区域）之后的 $R$ 就是 $t$ 次询问能到达的最远位置，这样能保证所有区域内都可以回答。

这其实就是个DP，定义 $f_{t,L}$ ，然后转移一下。

ps:你会发现 $f_{5,1}=10004205361450474$ ，只能呵呵。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxq=5,maxk=10000;const LL M=1e18;

LL a[maxk+5],f[maxq+5][maxk+5],pos=1;

LL DP(int t,LL L){
    if (!t) return L;if (L>maxk) return min(M,DP(t,maxk)-maxk+L);if (f[t][L]) return f[t][L];
    f[t][L]=L;for (int i=1;i<=L;i++) f[t][L]=DP(t-1,f[t][L])+1;f[t][L]=DP(t-1,f[t][L]);return f[t][L];
}
int main(){
    printf("%lld\n",DP(2,1));return 0;
    for (int t=5;t;t--){
        int K=min(pos,(LL)maxk);LL R=pos;printf("%d",K);a[0]=pos-1;
        for (int i=1;i<=K;i++) pos=DP(t-1,R),R=pos+1,printf(" %lld",pos),a[i]=pos;puts("");
        fflush(stdout);int now;scanf("%d",&now);if (now<0) return 0;pos=a[now]+1;
    }return 0;
}