Playoff-Codeforces

問題リンク-Playoff

問題

$2^n$人のトーナメントを考えます。各選手には$1$から$2^n$の番号がついています。
ペアは以下のようにして決まります。

• 最初のステージでは$1$と$2$, $3$と$4$... のペアが戦います。
• 次のステージでは$1-2$の勝者と$3-4$の勝者、$5-6$と$7-8$の勝者が戦います。
• その次のステージでも同様のルールで戦って行きます。

勝敗は以下ように決まります。

• $x+y$が奇数ならば小さい番号の人が勝利
• $x+y$が偶数ならば大きい番号の人が勝利

誰がこのトーナメントで優勝するか出力してください。

解法

最初のステージを考えます。戦うペアは$2x-1$と$2x$で示される組み合わせとなります。合計は奇数となるので番号の小さい奇数プレイヤーが次へ進みます。
この結果より、2ステージ移行は番号が奇数同士の対戦となるので和は常に偶数となり、番号の大きい人が勝利します。よって、奇数の最大値がこのトーナメントの優勝者となります。

実装

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    long long pow2 = 1;
    for(int i = 0;i < n; ++i){
        pow2 *= 2;
    }
    cout << (pow2 - 1) << endl;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}