問題一覧 > 通常問題

No.2126 MEX Game

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 67
作問者 : 👑 qand / テスター : 👑 p-adic 👑 potato167
お気に入りにしたユーザー ProblemId : 8761 / 自分の提出
問題文最終更新日: 2023-05-31 10:38:25
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 368 (順位表) の他の問題:

Problem Statement

You are given a sequence of non-negative integers $A=(A_1,\ldots,A_N)$ of length $N$.

Sente and Gote play a game using this sequence of non-negative integers.

Starting with Sente, the $2$ players alternately perform the following action $1$ time each, for a total of $10^{5000}$ actions by the $2$ players combined:

  • Choose an integer $k$ satisfying $1\le k\le N$ and an integer $x$ satisfying $0\le x\le 10^5$, and change $A_k$ to $x$.
  • Sente acts so that the mex of $A$ after all operations by the $2$ players are finished becomes large, and Gote acts so that it becomes small.

    Find the value of the mex of $A$ after all operations by the $2$ players are finished, when both players follow optimal strategies to achieve their respective goals.


    Here, the mex of $A$ is defined as follows:

  • The smallest non-negative integer $X$ such that $A_i\neq X$ for all $1\le i\le N$.
  • Constraints

  • $1\le N\le 10^5$
  • $0\le A_i\le 10^5$
  • All inputs are integers.
  • Input

    $N$
    $A_1$ $A_2$ $\ldots$ $A_N$
    

    Output

    Output the value of the mex of $A$ after all operations are finished.

    Sample

    Sample 1
    Input
    3
    0 1 0
    Output
    1

    By repeating the operation of changing an element of $A$ that is not $0$ to $0$ (or changing $A_1$ to $0$ if no such element exists), Sente can make the final mex of $A$ equal to $1$.
    Conversely, Sente cannot make the mex of $A$ $2$ or greater, so output $1$.

    Sample 2
    Input
    1
    2022
    Output
    0

    No matter how Sente operates, Gote can make the final mex of $A$ equal to $0$, for example by changing $A_1$ to $2040$.

    Sample 3
    Input
    9
    0 0 0 1 1 0 0 1 1
    Output
    2

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。