题目描述

难度分:$2400$

输入$T(\leq 10^3)$表示$T$组数据。每组数据输入$n(1 \leq n \leq 10^{18})$。

这是一道交互题。你和评测机玩游戏，轮流操作$n$。

每回合，当前玩家把$n$分解为$p_1$和$p_2$，满足$0 \lt p_1 < n$且$0 \lt p_2 \lt n$且$p_1 \oplus p_2 = n$。然后对手选择$p_1$或者$p_2$，替换掉$n$。下一回合轮到对手操作。无法把 n 分解的玩家输掉游戏。

你可以决定扮演先手（打印first表示先操作$n$）还是后手（打印second表示让评测机先操作$n$）。

你需要保证自己获胜。轮到你操作的回合数必须$\leq 63$。

具体的交互格式见原题。

输入样例

4
1

0 0
3


0 0
13


3 4

0 0
777777770001


0 0

输出样例

second


first
2 1


first
10 7

1 2


first
777777770000 1

算法

博弈论+构造

假设$popcount(x)$表示求$x$的二进制中$1$的个数，当$popcount(n)=1$时$n$是无法被拆分的，先手必败。$popcount(n)=2$时$n$可以拆分为$popcount(p_1)=popcount(p_2)=1$，先手必胜。

因此猜测，$popcount(n)$为偶数时先手必胜。可以发现：

1. $popcount(n)$为奇数时，选择后手。先手拆出来的两个数$p_1$和$p_2$一定满足$popcount(p_1)$和$popcount(p_2)$一奇一偶，此时我们选择将$n$变成$popcount$值为偶数的那个数，这样我们就又回到了必胜态。
2. $popcount(n)$为偶数时，选择先手。先手拆出来的两个数$p_1$和$p_2$一定满足$popcount(p_1)$和$popcount(p_2)$奇偶性相同，那么我们选择将$n$拆成两个$popcount$值为奇数的两个数，把$popcount$值为奇数的情况扔给了对手，对手仍然处于必败态。

我们可以每次将$n$拆成$higbit(n)$和$n \oplus highbit(n)$（其中$highbit(x)$表示获得$x$的最高位），这样每拆分一次就会使得$n$少一位，从而使游戏控制在$O(log_2n)$步$\leq 63$。

注意$highbit$操作不能替换成$lowbit$操作。用$lowbit$来拆的操作次数可以达到$O(n)$级别。具体的，对于$m$位的二进制数把后 $2$位分离，每次后手给前$m−2$位做$−1$操作，并用后两位平衡$1$的数量奇偶性。先手每次只能拆最后两位，无法影响前面$m−2$位，操作数量是$O(n)$级别的。

复杂度分析

时间复杂度

$highbit$和$popcount$操作都是$O(1)$的，拆分过程每次至少会去掉一位，因此最多进行$O(log_2n)$次操作就能结束游戏。因此，整个算法的时间复杂度为$O(log_2n)$。

空间复杂度

整个算法过程中仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int T;
LL n;

void solve(LL n) {
    function<bool(LL)> get = [&](LL x) {
        return __builtin_popcountll(x) & 1;
    };
    function<LL(LL)> highbit = [&](LL x) {
        return 1ll << (63 - __builtin_clzll(x));
    };
    puts(get(n)? "second": "first");
    fflush(stdout);
    if(!get(n)) {
        // 先手
        printf("%lld %lld\n", highbit(n), n^highbit(n));
    }
    fflush(stdout);
    while(1) {
        LL p1, p2;
        scanf("%lld%lld", &p1, &p2);
        if(p1 == -1) assert(0);
        if(p1 == 0 && p2 == 0) break;     // 对手分解不了，游戏结束
        if(get(p1)) {
            // 让n变为p2
            printf("%lld %lld\n", highbit(p2), p2^highbit(p2));
        }else {
            // 让n变为p1
            printf("%lld %lld\n", highbit(p1), p1^highbit(p1));
        }
        fflush(stdout);
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%lld", &n);
        solve(n);
    }
    return 0;
}