聪明的质检员 |【TYOI】NOIP模拟赛1-T2

静思，致远

题目描述

这是一道交互题。

你是“皮薄馅大”牌餐盘制造厂的质检员。作为一个聪明的质检员，你接到了一个任务：检测你家盘子的质量。

已知你家的盘子从$0$米的高度摔下不会碎，从$N+1$米的高度摔下一定会碎，也就是说，我们一开始知道盘子的耐摔度在$[0,N]$之间。

你的测试方法是：选定一个整数高度$H$，然后把盘子从$H$米处扔下来，如果盘子碎了，说明你家盘子的耐摔度在$[0,H−1]$之间，如果没碎，说明你家盘子的耐摔度在$[H,N]$之间。

你需要通过若干次测试，把盘子的耐摔度确定成一个长度为$0$的整数区间。

由于你家的盘子皮薄馅大，生产难度很高，所以盘子很贵，你只拿到了$K$个盘子，也就是，盘子碎完你就不能继续测试了。

由于你的领导完美主义，追求极致，所以只让你测试最多$M$次。

现在，请你在$M$次内测试出这个盘子真正的耐摔度。
输入格式

首先，请你从标准读入里面读入$N,K,M$，参数如题意所示。

然后，你需要通过如下形式与交互库交互：

1：输出一个$[1,N]$范围内的正整数给标准输出，然后执行fflush(stdout)。

2：从标准输入中读入结果，如果盘子碎了，标准输入会输入到字符串gg，否则会输入到字符串notgg。

当你测试的过程中交互库发现已经能确定答案的时候，请输出$−ans$，然后记得执行fflush(stdout)。

输出格式

无。

样例输入1

5 1 5
notgg
notgg
gg

样例输出1

1
2
3
-2

样例解释1

你首先读入了5,1,5三个参数，由于你只有一个盘子，所以只能按顺序询问。

交互库会回答notgg,notgg,gg，当第盘子在高度$3$碎了，而高度$2$没碎的时候，我们已经可以确定答案是$2$了，所以输出了答案−2。

样例输入2

4 2 3
gg
notgg
gg

样例输出2

3
1
2
-1

样例解释2

这次你有$2$个盘子，你先询问了$3$米的高度，盘子碎了，因此你得知答案在$[0,2]$范围内，你又询问了$1$，盘子没碎，答案在$[1,2]$范围内，接下来你询问了$2$，盘子碎了，因此你得知答案是$1$。

数据范围

因为出题人的懒惰，本题交互库不是自适应的，而是会预先选好一个答案。

Subtask 1（5分）：$K=1,N=M$。

Subtask 2（15分）：$K=M=10,N≤1000$。

Subtask 3（15分）：$N≤100$。

Subtask 4（10分）：$K=2,N≤1000,M=45$。

Subtask 5（15分）：$K=3,N≤1000,M=19$。

Subtask 6（10分）：$N≤1000,K≤10$。

Subtask 7（30分）：无特殊限制。

对于所有数据：$N≤109,K≤30，1≤M≤40000$，给定的$M$保证有解。

希望能先有所思考

% aqx

% wvr

% momoli

% Equfix

% Shijiuwan

% SKUec

% aqx_AK_xyf

% wfb

% LKX

% TYOI

题解部分

入题

首先，看到摔盘子这么多限制是茫然的，于是开始水$Subtask$

Subtask 1（5分）：$K=1,N=M$。

看到这个5pts，我就知道这场比赛我保底5pts了，毕竟样例一解释的太清楚了。只有一个盘子，为了做到保证，必须得从最下面往上摔，因为要保证如果这一层摔碎了，剩下的盘子能确定这层楼以下的未确定摔不摔得碎的区间，由于 $1$ 个盘子摔完只剩 $0$ 个，无法再次进行任何确定，所以要保证每次摔的时候下面的楼层能否摔碎都是确定的，这样要是在 $x$ 层碎了，我们由于知道在 $x-1$ 层不会碎，答案就是 $x-1$ 了

Subtask 2（15分）：$K=M=10,N≤1000$。

当$K=M$时，有多少次机会就能摔几次盘子，还不用关心摔不摔得碎，加上$N$不超过1000，这时候只需要用二分法，每次从中间摔盘子，倍增的利用$log_2{N}$的复杂度不断减小待定区间，完成精确确定。

subtask3显然不会

Subtask 4（10分）：$K=2,N≤1000,M=45$。

$K=2$，你有俩盘子，手头稍微松了一点，换言之，可以拿一个盘子挥霍一下。

于是你拿一个盘子上楼，心想
“没事，我还有一个。”

你爬上了一楼，要扔时，突然想起来：“要是碎了，不就确定是零层了吗，另一个盘子不就浪费了吗？要是没碎，不就白扔了吗？”

你吓了一跳，庆幸自己刚才没出手，爬上二楼，刚欲掷下，又想到：“要是碎了，剩下一个盘子只用在一楼扔一次就可以确定是在哪一层了，但这样一共45次机会只用了两次，太浪费了吧！”

于是你一口气爬到了45楼。

要是碎了，一个盘子从1楼摔到44楼，刚好用完次数，还确定的楼层数，这可太完美了

没碎，那好呀，还剩两个盘子，不慌

你随手一抛，盘子在空中来了个完美的自由落体

问：盘子的收尾速度v的上限。

—— 真没碎

也好，至少知道了盘子的耐摔度≥45

现在用了一次机会，还剩44次

于是你往上又爬了44层，一样的trick，仍然能保证摔碎了依然可以用一个盘子确定未知层数

你心想这可太爽了吧

于是又往上爬了43层，42层，41层……

突然你灵只因一动，弗如Gauss转世，推出了一个式子

记$f(x)$为有x次机会时，两个盘子最多能确定$f(x)$未知的楼层数

由经验可得

$$ f(x)=x+(x-1)+(x-2)+...+1 $$

稍加变换

$$ f(x)=1+2+3+...+x $$

$$ f(x)=\sum_{i=1}^{x}i =\frac{x(x+1)}{2} $$

（别着急，以后会用）

Subtask 5（15分）：$K=3,N≤1000,M=19$。

ok,现在三个盘子了，这也太爽了。

持盘上楼，不免嚣张跋扈：我就算摔碎了还有俩盘子，我想咋摔就咋摔。

于是你一直向上爬

你想的是，我就算摔碎了，剩两个盘子，还有$18$次机会，根据上一个subtask推的公式，我还能确定一个$18 \times (18+1) \div 2=171$的区间，那我就在$171+1=172$层扔，反正剩下的有两个盘子的方案保底，不怕碎。

于是你在$172$层驻足，把盘子扔了下去

—— 又没碎

现在还剩$18$次机会，于是你用你5GHz的大脑运算了一下，$17 \times (17+1) \div 2=153$，那往上跳到$172+153+1=326$层即可，以此类推，k=3就解决了。

好了该推式子方便下一次使用了，要是有个泛函数能算出每一层的公式就太好了

开颓（bushi）

记$g(x)$为有x次机会时，三个盘子最多能确定$f(x)$未知的楼层数

由经验可得

$$ g(x)=1+\frac{(x-1)(x-2)}{2}+1+\frac{(x-2)(x-3)}{2}+...+1+\frac{(1)(0)}{2} $$

$$ g(x)=\sum_{i=0}^{x-2}(1+\frac{i(i+1)}{2}) $$

$$ g(x)=x-1+\frac{1}{2}\sum_{i=0}^{x-2}i(i+1) $$

$$ g(x)=x-1+\frac{1}{2}\sum_{i=1}^{x-2}i^2+\frac{1}{2}\sum_{i=0}^{x-2}i $$

$$ g(x)=x-1+\frac{1}{2}\sum_{i=1}^{x-2}i^2+\frac{(x-2)(x-1)}{4} $$

$$ g(x)=x-1+\frac{1}{12}(x-2)(x-1)(2x-1)+\frac{(x-2)(x-1)}{4} $$

$$ g(x)=x-1+\frac{1}{12}(x^2-3x+2)(2x-1)+\frac{(x-2)(x-1)}{4} $$

$$ g(x)=x-1+\frac{1}{12}(2x^3-7x^2+7x-2)+\frac{(x-2)(x-1)}{4} $$

$$ g(x)=x-1+\frac{1}{12}(2x^3-7x^2+7x-2)+\frac{1}{4}(x^2-3x+2) $$

$$ g(x)=x-1+\frac{1}{12}(2x^3-7x^2+7x-2+3x^2-9x+6) $$

$$ g(x)=x-1+\frac{1}{12}(2x^3-4x^2-2x+4) $$

$$ g(x)=x-1+\frac{1}{6}(x^3-2x^2-x+2) $$

$$ g(x)=\frac{1}{6}(x^3-2x^2+5x-4) $$

$$ g(x)=\frac{1}{6}x^3-\frac{1}{3}x^2+\frac{5}{6}x-\frac{2}{3} $$

可好玩了

不急，k=4呢？那，k=30呢？

我希望你面对$30$次多项式还能笑得出来

什么？你说你可以不化简？

也可以，有点复杂度罢了，区区$O(k!)$罢了

电脑好用点的，2.65e+32几年就算出来了

骗你的几年都算不出来

正解

我们刚想推广我们刚发现的神奇方法，却发现式子太难推。

然后就不会啦？

OIer有办法。咱是学计算机的，计算机算的快，记得多，咱可以吧算过的答案存起来啊

在$m_0$次机会下把$k_0$个盘子进行一次尝试的扔后，我们就知道了$k_0$个盘子扔$m_0$次能确定多长的区间，直接记下来，下次$k_0+1$个盘子扔$m_0+1$次的问题就不需要公式求$k_0$个盘子扔$m_0$次所能确定的区间长，直接用记住的数据即可。

那么就到OIer喜闻乐见的环节了

记$dp_{i,j}$为有$i$个盘子，$j$次机会，最多能确定的区间长度

我如果有$i$个盘子，$j$次机会，那我就可以先找到有$i-1$个盘子，$j-1$次机会最多能扔的区间长度，即$dp_{i-1,j-1}$，加一后就是我这次扔的位置，扔完后，若碎了，那就好确定了；没碎，我还有$i$个盘子，$j-1$次机会，能再确定$dp_{i,j-1}$的区间

注意自已扔的这一次不算上下任何一个区间，要单独算

换言之，意思就是$dp_{i,j}$比$dp_{i,j-1}$能多扔$1+dp_{i-1,j-1}$次

$$ dp_{i,j}=dp_{i-1,j-1}+1+dp_{i,j-1} $$

那么我们只需要在扔盘子之前预处理一下这个二维数组就好了

小细节：由于转移防止后效性，要按照拓扑序转移，简言之，每次j都是依赖j-1，那么按照j先转移，把j作为外循环就不会出问题了

这时候回到交互题，刚上面也说过了

我如果有$i$个盘子，$j$次机会，那我就可以先找到有$i-1$个盘子，$j-1$次机会最多能扔的区间长度，即$dp_{i-1,j-1}$，加一后就是我这次扔的位置

所以交互的时候按照这个思路交互即可

AC code：

#include<iostream>
using namespace std;
int dp[32][100005];
void init(){  
    for(int j=1;j<=100000;j++){
        dp[1][j]=j;//边界条件
        for(int i=2;i<=30;i++){
            dp[i][j]=dp[i-1][j-1]+1+dp[i][j-1];
        }
    }
}
int n,m,k;
void meiju(int l,int r){
    for (int i=l;i<=r;i++){
        cout<<i<<endl; fflush(stdout);
        string s;
        cin>>s;
        if (s=="gg") {
            cout<<-(i-1);
            return;
        }
    }
    cout<<-r;//枚举完了都没gg，说明是最后一层
}
void solve(){
    cin>>n>>k>>m;
    int l=0,r=n;
    for (;;){
        if(m<=0){cout<<-l;return;}
        if(k==1){meiju(l+1,r);return;}//k==1就要干活了，没有子情况给你递归了
        int pos=min(dp[k-1][m-1]+1,n);//防越界
        m--;
        cout<<l+pos<<endl; fflush(stdout);
        string s;
        cin>>s;
        if(s=="gg") k--,r=l+pos-1; else l+=pos;//待定区间，方便枚举边界
    }
}
signed main(){
    init();
    solve();
    return 0;
}

代码很短，不是吗？