問題一覧 > 通常問題

No.2906 Strange Online Judge

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : 👑 獅子座じゃない人 / テスター : 👑 amentorimaru Mizar cleantted 👑 Nachia
お気に入りにしたユーザー ProblemId : 10903 / 自分の提出
問題文最終更新日: 2024-09-28 13:46:06
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 448 (順位表) の他の問題:

Problem Statement

You are participating in a programming contest that uses the online judge "StrOnJ". The problem statement is as follows.

Problem

For a set $S$ of non-negative integers, let $\operatorname{mex}{S}$ be "the smallest non-negative integer not contained in $S$".

Formally, for the set $\mathbb{N}$ of all non-negative integers and a set $S$ of non-negative integers, $\operatorname{mex}{S}$ is defined by $\operatorname{mex}{S}=\min(\mathbb{N}\setminus S)$.

Given a positive integer $K$, define the sequence $(a_n)$ recursively as follows.

  • $a_1=1$
  • $a_{n+1}=\operatorname{mex}(\{0\}\cup\{a_i\ |\ 1\leq i\leq n\}\cup\{a_i+Ki\ |\ 1\leq i\leq n\})\ (n\geq 1)$

Find $a_N$.

Constraints
  • All input values are integers
  • $1\leq K\leq 10^9$
  • $1\leq N\leq 10^9$

However, StrOnJ accepts only source code written in "StLang", a programming language created for this problem.

Following the StLang specification below, output StLang source code that can find $a_N$. Due to judge constraints, the output must be at most 1000 lines.

Input

There is no input for this problem as such.

In the judge, integers $K,N$ satisfying $1\leq K\leq 10^9,\ 1\leq N\leq 10^9$ are given to the program you output.

Output

Output StLang source code that can find $a_N$. The output must be at most 1000 lines.

About Judging

To distinguish these from runtime errors of the submitted program, if the output is produced within the execution limit and memory limit, the judge result will be AC or WA.

StLang Specification

Sample Code

These are sample codes in StLang that compute the binomial coefficient ${}_NC_K\quad(N\leq 62)$. The first is an example without whitespace or comment strings, and the second is an example with them.

ifN>=K
$0=1
$1=1
$2=N
while$1<=K
$0=$0*$2
$0=$0/$1
$2=$2-1
$1=$1+1
end
end
return$0
# 二項係数 nCk の計算 (N > 62 の時は演算オーバーフローする可能性あり)
if N >= K         # N < K の時の出力は 0 とする
  $0 = 1
  $1 = 1
  $2 = N
  while $1 <= K   # for $1 in 1..=K
    $0 = $0 * $2  # $2 == N + 1 - $1
    $0 = $0 / $1  # ここで割り算の余りは生じない
    $2 = $2 - 1
    $1 = $1 + 1
  end
end
return $0

# return 行より後のコメント行も可

If you write StLang source code directly, you can submit it as is by selecting Text (cat 8.3) as the language.

Overview of the StLang Specification
  • Main specifications of StLang

    • StLang can handle only integers that are at least $0$ and less than $2^{64}$.
    • Only the 10 variables $0 to $9 can be used. At the start of execution for each test case, the variables $0 to $9 are initialized to $0$.
    • The constants $K$ and $N$ given for each test case can be used as the values K and N.
    • Arithmetic operations (+,-,*,/,%) can be used at most once in an assignment statement. Operations cannot be chained.
    • The conditional expressions of the control structures, the if statement and the while statement, handle only a comparison operation (==,!=,>=,<=,>,<) between two values.
    • Everything from a # character to the end of the line is treated as a comment.
    • Half-width spaces are ignored, except in the middle of multi-character keywords (if,while,end,return,==,!=,>=,<=) and decimal integer strings.
  • Points to note

    • No literals, constants, or variables other than decimal integers, the constant K, the constant N, and the variables $0 to $9 can be used.
    • Outputting a program exceeding 1000 lines results in WA. One line cannot contain multiple statements.
    • If the total number $C$ of executed assignment operations and comparison operations in one case exceeds $1000$, the result is WA.
    • If a decimal integer or an arithmetic operation (+,-,*,/,%) produces a value less than $0$, a value of $2^{64}$ or more, or a division by $0$, the result is WA.
    • For control structures (if,while), the end of the block must be explicitly indicated with a matching end.
    • The return statement must be written exactly once, at the end of the program. A return statement cannot be included inside a block of a control structure.
    • Arithmetic operations (+,-,*,/,%) cannot be included in the conditional expression of a control structure (if,while) or in the return value of a return statement.
Details of Syntax and Processing
(Click here to expand/collapse)

The input program is parsed and a syntax tree like the one in the figure below is built (nodes not necessarily needed for execution may be omitted). For each input case, the initial values of the variables and constants are set, and this syntax tree is executed by traversing it in order from the root (basically, except for control structures).

The sample StLang execution environment (described later) is implemented using Lark.

Lark - a parsing toolkit for Python : https://github.com/lark-parser/lark

The conversion from the input program to the syntax tree follows the rules below.

StLang syntax definition (for the parser generator Lark) using EBNF (Extended Backus-Naur Form) + regular expressions + α:

?start: program
program: statements "return" value lineends
?value: number | const_k | const_n | variable
number: /[0-9]+/
const_k: "K"
const_n: "N"
variable: "$" var_ident
var_ident: /[0-9]/
?statements: statement*
?statement: assignment | branching | repeating | lineend
assignment: "$" var_ident "=" expression lineend
?expression: value | add | sub | mul | div | rem
add: value "+" value
sub: value "-" value
mul: value "*" value
div: value "/" value
rem: value "%" value
branching: "if" condition lineend statements "end" lineend
repeating: "while" condition lineend statements "end" lineend
?condition: eq | ne | ge | le | gt | lt
eq: value "==" value
ne: value "!=" value
ge: value ">=" value
le: value "<=" value
gt: value ">" value
lt: value "<" value
?lineends: lineend* ST_COMMENT?
?lineend: ST_COMMENT? CR? LF
ST_COMMENT: "#" /[^\n]*/
CR : /\r/
LF : /\n/
WS_INLINE: (" "|/\t/)+
%ignore WS_INLINE

Execution of the program on the syntax tree is performed by the following implementation.

For an example implementation of the entire interpreter using the parser generator Lark, see "StLang @ Lark Sample Execution Environment" below.

Example implementation of the interpreter using the parser generator Lark:

class StLangInterpreter(lark.visitors.Interpreter):
    """StLang Interpreter"""
    def __init__(self, k=0, n=0) -> None:
        super().__init__()
        assert 0 <= int(k) < 2**64 and 0 <= int(n) < 2**64, "OutOfRangeNumber"
        self.env = { 'C': 0, 'K': int(k), 'N': int(n), '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0 }
    def program(self, tree) -> int:
        self.visit(tree.children[0]) # statements
        return self.visit(tree.children[1]) # value
    def number(self, tree) -> int:
        ret = int(tree.children[0].value)
        assert 0 <= ret < 2**64, "OutOfRangeNumber"
        return ret
    def const_k(self, _tree) -> int:
        return self.env['K']
    def const_n(self, _tree) -> int:
        return self.env['N']
    def variable(self, tree) -> int:
        return self.env[self.visit(tree.children[0])]
    def var_ident(self, tree) -> str:
        return str(tree.children[0].value)
    def assignment(self, tree) -> None:
        self.env['C'] += 1
        assert self.env['C'] <= 1000, "StepLimitExceed"
        self.env[self.visit(tree.children[0])] = self.visit(tree.children[1])
    def add(self, tree) -> int:
        ret = self.visit(tree.children[0]) + self.visit(tree.children[1])
        assert 0 <= ret < 2**64, "OutOfRangeNumber"
        return ret
    def sub(self, tree) -> int:
        ret = self.visit(tree.children[0]) - self.visit(tree.children[1])
        assert 0 <= ret < 2**64, "OutOfRangeNumber"
        return ret
    def mul(self, tree) -> int:
        ret = self.visit(tree.children[0]) * self.visit(tree.children[1])
        assert 0 <= ret < 2**64, "OutOfRangeNumber"
        return ret
    def div(self, tree) -> int:
        lhs, rhs = self.visit(tree.children[0]), self.visit(tree.children[1])
        assert 0 < rhs, "OutOfRangeNumber"
        return lhs // rhs
    def rem(self, tree) -> int:
        lhs, rhs = self.visit(tree.children[0]), self.visit(tree.children[1])
        assert 0 < rhs, "OutOfRangeNumber"
        return lhs % rhs
    def branching(self, tree) -> None:
        self.env['C'] += 1
        assert self.env['C'] <= 1000, "StepLimitExceed"
        if self.visit(tree.children[0]): # condition
            self.visit(tree.children[2]) # statements
    def repeating(self, tree) -> None:
        while True:
            self.env['C'] += 1
            assert self.env['C'] <= 1000, "StepLimitExceed"
            if not self.visit(tree.children[0]): # condition
                break
            self.visit(tree.children[2]) # statements
    def eq(self, tree) -> bool:
        return self.visit(tree.children[0]) == self.visit(tree.children[1])
    def ne(self, tree) -> bool:
        return self.visit(tree.children[0]) != self.visit(tree.children[1])
    def ge(self, tree) -> bool:
        return self.visit(tree.children[0]) >= self.visit(tree.children[1])
    def le(self, tree) -> bool:
        return self.visit(tree.children[0]) <= self.visit(tree.children[1])
    def gt(self, tree) -> bool:
        return self.visit(tree.children[0]) > self.visit(tree.children[1])
    def lt(self, tree) -> bool:
        return self.visit(tree.children[0]) < self.visit(tree.children[1])

Below, an explanation of StLang's syntax and processing is given together with the syntax definition, mainly using EBNF (Extended Backus-Naur Form) + regular expressions, and an example interpreter implementation using Lark. The entire source code must be written in the syntax program and be at most $1000$ lines. If the source code is not written in the correct syntax, defined recursively as below, the result is WA.

The computer executing the program has a sequence of non-negative integers $(V_0,V_1,V_2,\ldots,V_9)$ and a non-negative integer $C$.

For each test case, the values of $K,N$ given by the test case are set to the constant values K,N, the values of the variables $V_0$ to $V_9$ ($0 to $9) are initialized to $0$, and the value of the execution step counter $C$ is initialized to $0$. If the value of $C$ becomes greater than $1000$ during execution, the result is WA.

    def __init__(self, k=0, n=0) -> None:
        super().__init__()
        assert 0 <= int(k) < 2**64 and 0 <= int(n) < 2**64, "OutOfRangeNumber"
        self.env = { 'C': 0, 'K': int(k), 'N': int(n), '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0 }

A ? at the beginning of a line of the syntax definition is attached to rules whose nodes are omitted from the syntax tree. Here it is applied to rules that have no direct functional implementation of their own, since the implementations of their child elements are used as they are.

A part enclosed in " and " represents a literal token string.

A part enclosed in / and / specifies string matching by a regular expression.

A trailing ? indicates repetition 0 to 1 times (that is, it may be omitted).

A trailing * indicates repetition 0 or more times (optional repetition).

A trailing + indicates repetition 1 or more times (repetition).

Alternatives written with | indicate that one of them is chosen (choice).

The regular expression /[0-9]+/ matches a string of one or more digits.

The regular expression /[0-9]/ matches a string of one digit.

"#" /[^\n]*/ matches a string of any length that starts with the character # and contains no newline character.

The regular expression /\r/ matches the carriage return control character.

The regular expression /\n/ matches the newline character.

(" "|/\t/)+ matches one or more half-width space or horizontal tab characters.

  • start: [Summary] Specifies the root node of the syntax tree [Processing] Executes program

    ?start: program
  • program: [Summary] Definition of the entire program [Processing] Executes statements, then outputs the value of value and terminates

    program: statements "return" value lineends
        def program(self, tree) -> int:
            self.visit(tree.children[0]) # statements
            return self.visit(tree.children[1]) # value
    
  • value: [Summary] Integer value [Syntax] One of number, const_k, const_n, variable [Processing] Returns the corresponding value

    ?value: number | const_k | const_n | variable
  • number: [Summary] Decimal integer value [Exception] WA unless the value is at least $0$ and at most $2^{64}-1=18446744073709551615$

    const_k: [Summary] Constant $K$ [Processing] Returns the value determined for each test case

    const_n: [Summary] Constant $N$ [Processing] Returns the value determined for each test case

    variable: [Summary] Variable value [Processing] Returns the value, among the variables $V_0$ to $V_9$, corresponding to var_ident

    var_ident: [Summary] Variable identifier [Syntax] A one-digit integer [Processing] Indicates the correspondence to the variables $V_0$ to $V_9$

    number: /[0-9]+/
    const_k: "K"
    const_n: "N"
    variable: "$" var_ident
    var_ident: /[0-9]/
    
        def number(self, tree) -> int:
            ret = int(tree.children[0].value)
            assert 0 <= ret < 2**64, "OutOfRangeNumber"
            return ret
        def const_k(self, _tree) -> int:
            return self.env['K']
        def const_n(self, _tree) -> int:
            return self.env['N']
        def variable(self, tree) -> int:
            return self.env[self.visit(tree.children[0])]
        def var_ident(self, tree) -> str:
            return str(tree.children[0].value)
    
  • statements: [Summary] Block statement [Syntax] Consists of zero or more lines of statement [Processing] Executes each contained statement in order

    ?statements: statement*
  • statement: [Summary] Statement [Syntax] One of assignment, branching, repeating, or an empty line (or comment line) [Processing] Executes the corresponding one

    ?statement: assignment | branching | repeating | lineend
  • assignment: [Summary] Assignment

    [Processing] Assigns the value (unsigned 64-bit integer) obtained by evaluating expression to the variable var_ident

    The value of $C$ increases by $1$ for each assignment [Exception] WA if the value of $C$ becomes greater than $1000$

    assignment: "$" var_ident "=" expression lineend
        def assignment(self, tree) -> None:
            self.env['C'] += 1
            assert self.env['C'] <= 1000, "StepLimitExceed"
            self.env[self.visit(tree.children[0])] = self.visit(tree.children[1])
    
  • expression: [Summary] Evaluation of an integer value [Processing] Returns the value obtained by evaluating the corresponding one of value, add, sub, mul, div, rem

    ?expression: value | add | sub | mul | div | rem
  • add: [Summary] Addition $a+b$ [Exception] WA unless the resulting value is at least $0$ and at most $2^{64}-1=18446744073709551615$

    sub: [Summary] Subtraction $a-b$ [Exception] WA unless the resulting value is at least $0$ and at most $2^{64}-1=18446744073709551615$

    mul: [Summary] Multiplication $a\times b$ [Exception] WA unless the resulting value is at least $0$ and at most $2^{64}-1=18446744073709551615$

    div: [Summary] Division $\lfloor a/b\rfloor$ [Exception] WA if the divisor is $0$

    rem: [Summary] Remainder $a-b\lfloor a/b\rfloor$ [Exception] WA if the divisor is $0$

    add: value "+" value
    sub: value "-" value
    mul: value "*" value
    div: value "/" value
    rem: value "%" value
    
        def add(self, tree) -> int:
            ret = self.visit(tree.children[0]) + self.visit(tree.children[1])
            assert 0 <= ret < 2**64, "OutOfRangeNumber"
            return ret
        def sub(self, tree) -> int:
            ret = self.visit(tree.children[0]) - self.visit(tree.children[1])
            assert 0 <= ret < 2**64, "OutOfRangeNumber"
            return ret
        def mul(self, tree) -> int:
            ret = self.visit(tree.children[0]) * self.visit(tree.children[1])
            assert 0 <= ret < 2**64, "OutOfRangeNumber"
            return ret
        def div(self, tree) -> int:
            lhs, rhs = self.visit(tree.children[0]), self.visit(tree.children[1])
            assert 0 < rhs, "OutOfRangeNumber"
            return lhs // rhs
        def rem(self, tree) -> int:
            lhs, rhs = self.visit(tree.children[0]), self.visit(tree.children[1])
            assert 0 < rhs, "OutOfRangeNumber"
            return lhs % rhs
    
  • branching: [Summary] Branching (if)

    [Processing] Executes statements if the evaluation (bool) of condition is true

    The value of $C$ increases by $1$ when condition is evaluated [Exception] WA if the value of $C$ becomes greater than $1000$

    branching: "if" condition lineend statements "end" lineend
        def branching(self, tree) -> None:
            self.env['C'] += 1
            assert self.env['C'] <= 1000, "StepLimitExceed"
            if self.visit(tree.children[0]): # condition
                self.visit(tree.children[2]) # statements
    
  • repeating: [Summary] Repetition (while)

    [Processing] Repeatedly executes statements while the evaluation (bool) of condition is true

    The value of $C$ increases by $1$ each time condition is evaluated [Exception] WA if the value of $C$ becomes greater than $1000$

    repeating: "while" condition lineend statements "end" lineend
        def repeating(self, tree) -> None:
            while True:
                self.env['C'] += 1
                assert self.env['C'] <= 1000, "StepLimitExceed"
                if not self.visit(tree.children[0]): # condition
                    break
                self.visit(tree.children[2]) # statements
    
  • condition: [Summary] Comparison operation [Processing] Returns the evaluation (bool) of the corresponding one of eq, ne, ge, le, gt, lt

    ?condition: eq | ne | ge | le | gt | lt
  • eq: [Summary] EQual [Processing] true if the two values are equal, otherwise false

    ne: [Summary] Not Equal [Processing] true if the two values are different, otherwise false

    ge: [Summary] Greater than or Equal to [Processing] true if the first value is greater than or equal to the second value, otherwise false

    le: [Summary] Less than or Equal to [Processing] true if the first value is less than or equal to the second value, otherwise false

    gt: [Summary] Greater Than [Processing] true if the first value is greater than the second value, otherwise false

    lt: [Summary] Less Than [Processing] true if the first value is less than the second value, otherwise false

    eq: value "==" value
    ne: value "!=" value
    ge: value ">=" value
    le: value "<=" value
    gt: value ">" value
    lt: value "<" value
    
        def eq(self, tree) -> bool:
            return self.visit(tree.children[0]) == self.visit(tree.children[1])
        def ne(self, tree) -> bool:
            return self.visit(tree.children[0]) != self.visit(tree.children[1])
        def ge(self, tree) -> bool:
            return self.visit(tree.children[0]) >= self.visit(tree.children[1])
        def le(self, tree) -> bool:
            return self.visit(tree.children[0]) <= self.visit(tree.children[1])
        def gt(self, tree) -> bool:
            return self.visit(tree.children[0]) > self.visit(tree.children[1])
        def lt(self, tree) -> bool:
            return self.visit(tree.children[0]) < self.visit(tree.children[1])
    
  • lineends: [Summary] The end of program, after the return statement [Syntax] Zero or more lineends, followed by at most one comment string without a newline [Processing] Does nothing

    ?lineends: lineend* ST_COMMENT?
  • lineend: [Summary] End of a line (may include a comment string) [Syntax] ST_COMMENT and CR may be omitted [Processing] Does nothing

    ?lineend: ST_COMMENT? CR? LF
  • ST_COMMENT: [Summary] Comment string [Syntax] Everything from the "#" character to the end of the line, excluding the newline character, is regarded as a comment string [Processing] Does nothing

    ST_COMMENT: "#" /[^\n]*/
  • CR: [Summary] Carriage return control character [Processing] Does nothing

    LF: [Summary] Newline character [Processing] Does nothing

    CR : /\r/
    LF : /\n/
    
  • WS_INLINE: [Summary] Whitespace characters within a line [Syntax] Either a half-width space or a horizontal tab control character [Processing] Does nothing

    WS_INLINE: (" "|/\t/)+
  • [Syntax] Ignores whitespace characters within a line

    %ignore WS_INLINE
Tokens
(Click here to expand/collapse)

The following tokens can be used. Here, [0-9] represents any single digit, [0-9]+ represents any sequence of one or more digits, .* represents any sequence of zero or more characters excluding newlines, and \n represents a newline.

  • [0-9]+
  • K
  • N
  • $
  • [0-9]
  • +
  • -
  • *
  • /
  • %
  • if
  • while
  • end
  • ==
  • !=
  • >=
  • <=
  • >
  • <
  • =
  • return
  • #
  • .*
  • \n

Half-width spaces ( ) are ignored. Note that newlines are not ignored.

Syntax
(Click here to expand/collapse)

The syntax is defined recursively as follows. The entire source code must be written in the syntax program.

The tokens defined above are represented by enclosing them in double quotation marks, and concatenation of tokens or syntax elements is represented by space separation. Also, is the empty string.

  • program is defined as follows.
    • statements "return" value lineends
  • statements is one of the following.
    • statement statements
  • statement is one of the following.
    • lineend
    • assignment
    • branching
  • assignment is defined as follows.
    • "$" "[0-9]" "=" expression lineend
  • branching is defined as follows.
    • control condition lineend statements "end" lineend
  • control is one of the following.
    • "if"
    • "while"
  • expression is one of the following.
    • value
    • value "+" value
    • value "-" value
    • value "*" value
    • value "/" value
    • value "%" value
  • condition is one of the following.
    • value "==" value
    • value "!=" value
    • value ">=" value
    • value "<=" value
    • value ">" value
    • value "<" value
  • value is one of the following.
    • number
    • "K"
    • "N"
    • variable
  • number is the following.
    • "[0-9]+"
  • variable is the following.
    • "$" var_ident
  • var_ident is the following.
    • "[0-9]"
  • lineends is one of the following.
    • "#" ".*"
    • lineend lineends
  • lineend is one of the following.
    • "\n"
    • "#" ".*" "\n"
Processing
(Click here to expand/collapse)

If the source code is not written in the correct syntax, the result is WA.

Next, number is evaluated as a numeric literal. If the written sequence of digits, interpreted as a non-negative integer, is not at least $0$ and at most $2^{64}-1=18446744073709551615$, the result is WA.

The computer executing the program has a sequence of non-negative integers $(V_0,V_1,V_2,\ldots,V_9)$ and a non-negative integer $C$. All initial values are $0$.

"K" is a constant representing the value of $K$, and "N" is a constant representing the value of $N$. These values are determined for each case.

For variable, where $i$ is a digit, "$i" is a variable representing the value of $V_i$.

The values of number, "K", "N", and variable are passed on to value.

Consider a, a value with value $a$, and b, a value with value $b$. For an expression of the form a operator b, its value is as follows.

  • If operator is "+", $a+b$
  • If operator is "-", $a-b$
  • If operator is "*", $a \times b$
  • If operator is "/", $\lfloor a / b\rfloor$
  • If operator is "%", $a-b\lfloor a / b\rfloor$
If the value is not at least $0$ and at most $2^{64}-1=18446744073709551615$, the result is WA.

Also, a condition of the form a comparator b has the following as its value.

  • If comparator is "==", whether $a=b$
  • If comparator is "!=", whether $a\neq b$
  • If comparator is ">=", whether $a\geq b$
  • If comparator is "<=", whether $a\leq b$
  • If comparator is ">", whether $a\gt b$
  • If comparator is "<", whether $a\lt b$

The program performs the processing described by the statements of program, then returns the value specified as value and terminates. If the returned value is not $a_N$ for the given $K,N$, the result is WA.

For lineend and endcomment, the content is ignored and no processing is performed.

For statements, if it has the form , no processing is performed. If it has the form statement statements, the processing described by statement is performed, and then processing moves on to statements.

assignment changes the value of the $V_i$ corresponding to the var_ident of variable to the value of expression. Also, the value of $C$ increases by $1$.

For a branching of the form "if" condition statements "end", first the value of $C$ increases by $1$ regardless of the value of condition. Next, the processing described by statements is performed only if the value of condition is true.

For a branching of the form "while" condition statements "end", as long as the value of condition is true, increasing the value of $C$ by $1$ and performing the processing described by statements are repeated. When the value of condition becomes false, the value of $C$ increases by $1$ and the processing of this branching ends.

If the value of $C$ becomes greater than $1000$, the result is WA.

StLang @ Lark Sample Execution Environment

The StLang sample code is set by default, so please rewrite it as appropriate into a program that fits the problem statement.

  • Python code (simplified version) (Click here to expand/collapse)
    """StLang@Lark 実行環境サンプル 簡易版"""
    """こちらは Lark モジュールのインストールが必要です"""
    """ Lark - a parsing toolkit for Python : https://github.com/lark-parser/lark """
    #%pip install lark>=1.1.9 --upgrade
    import lark
    
    ### TODO: ここからを本番の問題用の正しいコードに書き換える
    PROGRAM = r"""
    # サンプルプログラム: 二項係数 nCk の計算 (N > 62 の時は演算オーバーフローする可能性あり)
    if N >= K         # N < K の時の出力は 0 とする
      $0 = 1
      $1 = 1
      $2 = N
      while $1 <= K   # for $1 in 1..=K
        $0 = $0 * $2  # $2 == N + 1 - $1
        $0 = $0 / $1  # ここで割り算の余りは生じない
        $2 = $2 - 1
        $1 = $1 + 1
      end
    end
    return $0
    
    # return 行より後のコメント行も可
    """
    ### TODO: ここまでを本番の問題用の正しいコードに書き換える
    
    import itertools
    import random
    import sys
    
    """ランダムテストケースの生成"""
    def gen_test(_: int) -> tuple[int, int, int]:
        k = min(random.randrange(1, 2**random.randrange(1, 32)), 10**9)
        n = min(random.randrange(1, 2**random.randrange(1, 32)), 10**9)
        ### TODO: k,n の値から回答すべき値 an を生成するコードを書く
        an = 0
        return k, n, an
    
    ### TODO: ランダムテストケースの生成を正しく書いた後、ランダムテストケース生成数を書き換える
    """ランダムテストケースの生成数"""
    GEN_CASES = 0
    
    def main() -> None:
        stlang_parser = lark.Lark(
            STLANG_GRAMMER,
            parser='lalr',
        )
        assert len(PROGRAM.splitlines()) <= 1000
        stlang_tree = stlang_parser.parse(PROGRAM)
        for k, n, an in itertools.chain([ # 本番問題用のサンプルケース
            ( 3, 5, 6 ),
            ( 8, 1, 1 ),
            ( 10, 1000000000, 1099019513 ),
        ], map(gen_test, range(GEN_CASES))):
            assert 1 <= k <= 10**9 and 1 <= n <= 10**9 and 0 <= an < 2**64
            result, judge, worker = None, None, StLangInterpreter(k, n)
            try:
                result = worker.visit(stlang_tree)
                judge = "Accepted" if result == an else "WrongAnswer"
            except AssertionError as e:
                judge, tb = "RuntimeError", e.__traceback__
                print(type(e), e, file=sys.stderr)
                while tb is not None:
                    print(tb.tb_frame, file=sys.stderr)
                    tb = tb.tb_next
            print(f"{judge}: K={k} N={n} a_N={an} prog_return:{result} C:{worker.env['C']}")
    
    STLANG_GRAMMER = r"""
    ?start: program
    program: statements "return" value lineends
    ?value: number | const_k | const_n | variable
    number: /[0-9]+/
    const_k: "K"
    const_n: "N"
    variable: "$" var_ident
    var_ident: /[0-9]/
    ?statements: statement*
    ?statement: assignment | branching | repeating | lineend
    assignment: "$" var_ident "=" expression lineend
    ?expression: value | add | sub | mul | div | rem
    add: value "+" value
    sub: value "-" value
    mul: value "*" value
    div: value "/" value
    rem: value "%" value
    branching: "if" condition lineend statements "end" lineend
    repeating: "while" condition lineend statements "end" lineend
    ?condition: eq | ne | ge | le | gt | lt
    eq: value "==" value
    ne: value "!=" value
    ge: value ">=" value
    le: value "<=" value
    gt: value ">" value
    lt: value "<" value
    ?lineends: lineend* ST_COMMENT?
    ?lineend: ST_COMMENT? CR? LF
    ST_COMMENT: "#" /[^\n]*/
    CR : /\r/
    LF : /\n/
    WS_INLINE: (" "|/\t/)+
    %ignore WS_INLINE
    """
    
    class StLangInterpreter(lark.visitors.Interpreter):
        """StLang Interpreter"""
        def __init__(self, k=0, n=0) -> None:
            super().__init__()
            assert 0 <= int(k) < 2**64 and 0 <= int(n) < 2**64, "OutOfRangeNumber"
            self.env = { 'C': 0, 'K': int(k), 'N': int(n), '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0 }
        def program(self, tree) -> int:
            self.visit(tree.children[0])
            return self.visit(tree.children[1])
        def number(self, tree) -> int:
            ret = int(tree.children[0].value)
            assert 0 <= ret < 2**64, "OutOfRangeNumber"
            return ret
        def const_k(self, _tree) -> int:
            return self.env['K']
        def const_n(self, _tree) -> int:
            return self.env['N']
        def variable(self, tree) -> int:
            return self.env[self.visit(tree.children[0])]
        def var_ident(self, tree) -> str:
            return str(tree.children[0].value)
        def assignment(self, tree) -> None:
            self.env['C'] += 1
            assert self.env['C'] <= 1000, "StepLimitExceed"
            self.env[self.visit(tree.children[0])] = self.visit(tree.children[1])
        def add(self, tree) -> int:
            ret = self.visit(tree.children[0]) + self.visit(tree.children[1])
            assert 0 <= ret < 2**64, "OutOfRangeNumber"
            return ret
        def sub(self, tree) -> int:
            ret = self.visit(tree.children[0]) - self.visit(tree.children[1])
            assert 0 <= ret < 2**64, "OutOfRangeNumber"
            return ret
        def mul(self, tree) -> int:
            ret = self.visit(tree.children[0]) * self.visit(tree.children[1])
            assert 0 <= ret < 2**64, "OutOfRangeNumber"
            return ret
        def div(self, tree) -> int:
            lhs, rhs = self.visit(tree.children[0]), self.visit(tree.children[1])
            assert 0 < rhs, "OutOfRangeNumber"
            return lhs // rhs
        def rem(self, tree) -> int:
            lhs, rhs = self.visit(tree.children[0]), self.visit(tree.children[1])
            assert 0 < rhs, "OutOfRangeNumber"
            return lhs % rhs
        def branching(self, tree) -> None:
            self.env['C'] += 1
            assert self.env['C'] <= 1000, "StepLimitExceed"
            if self.visit(tree.children[0]): # condition
                self.visit(tree.children[2]) # statements
        def repeating(self, tree) -> None:
            while True:
                self.env['C'] += 1
                assert self.env['C'] <= 1000, "StepLimitExceed"
                if not self.visit(tree.children[0]): # condition
                    break
                self.visit(tree.children[2]) # statements
        def eq(self, tree) -> bool:
            return self.visit(tree.children[0]) == self.visit(tree.children[1])
        def ne(self, tree) -> bool:
            return self.visit(tree.children[0]) != self.visit(tree.children[1])
        def ge(self, tree) -> bool:
            return self.visit(tree.children[0]) >= self.visit(tree.children[1])
        def le(self, tree) -> bool:
            return self.visit(tree.children[0]) <= self.visit(tree.children[1])
        def gt(self, tree) -> bool:
            return self.visit(tree.children[0]) > self.visit(tree.children[1])
        def lt(self, tree) -> bool:
            return self.visit(tree.children[0]) < self.visit(tree.children[1])
    
    main()
    
  • Source code: Python (standalone version, no Lark installation required) You can copy the source code and run it on yukicoder online execution
  • Source code: Jupyter Notebook (for local environments such as VSCode + the Jupyter Notebook extension)
  • Online execution environment: Google Colab (Google account required)

Sample

These are samples of the $K$ and $N$ given as constants by the judge and the value to return. The $2$ numbers under "Constants" are $K$ and $N$, in this order.

Sample 1
Constants
3 5
Value to Return
6

Here, $K=3,\ N=5$.

Since $a_1=1,\ a_2=\operatorname{mex}\{0,1,4\}=2,\ a_3=\operatorname{mex}\{0,1,2,4,8\}=3,\ a_4=\operatorname{mex}\{0,1,2,3,4,8,12\}=5,\ a_5=\operatorname{mex}\{0,1,2,3,4,5,8,12,17\}=6$, the answer is $6$.

Sample 2
Constants
8 1
Value to Return
1

Sample 3
Constants
10 1000000000
Value to Return
1099019513

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