No.2906 Strange Online Judge
タグ : / 解いたユーザー数 8
作問者 : 👑
amentorimaru
cleantted
👑
Nachia
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
$0to$9can be used. At the start of execution for each test case, the variables$0to$9are initialized to $0$. - The constants $K$ and $N$ given for each test case can be used as the values
KandN. - Arithmetic operations (
+,-,*,/,%) can be used at most once in an assignment statement. Operations cannot be chained. - The conditional expressions of the control structures, the
ifstatement and thewhilestatement, 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 constantN, and the variables$0to$9can 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 matchingend. - The
returnstatement must be written exactly once, at the end of the program. Areturnstatement 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 areturnstatement.
- No literals, constants, or variables other than decimal integers, the constant
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] Executesprogram?start: program
-
program: [Summary] Definition of the entire program [Processing] Executesstatements, then outputs the value ofvalueand terminatesprogram: 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 ofnumber,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 caseconst_n: [Summary] Constant $N$ [Processing] Returns the value determined for each test casevariable: [Summary] Variable value [Processing] Returns the value, among the variables $V_0$ to $V_9$, corresponding tovar_identvar_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 ofstatement[Processing] Executes each containedstatementin order?statements: statement*
-
statement: [Summary] Statement [Syntax] One ofassignment,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
expressionto the variablevar_identThe 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 ofvalue,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
statementsif the evaluation (bool) ofconditionistrueThe value of $C$ increases by $1$ when
conditionis 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
statementswhile the evaluation (bool) ofconditionistrueThe value of $C$ increases by $1$ each time
conditionis 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 ofeq,ne,ge,le,gt,lt?condition: eq | ne | ge | le | gt | lt
-
eq: [Summary] EQual [Processing]trueif the twovalues are equal, otherwisefalsene: [Summary] Not Equal [Processing]trueif the twovalues are different, otherwisefalsege: [Summary] Greater than or Equal to [Processing]trueif the firstvalueis greater than or equal to the secondvalue, otherwisefalsele: [Summary] Less than or Equal to [Processing]trueif the firstvalueis less than or equal to the secondvalue, otherwisefalsegt: [Summary] Greater Than [Processing]trueif the firstvalueis greater than the secondvalue, otherwisefalselt: [Summary] Less Than [Processing]trueif the firstvalueis less than the secondvalue, otherwisefalseeq: 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 ofprogram, after thereturnstatement [Syntax] Zero or morelineends, 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_COMMENTandCRmay 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 nothingST_COMMENT: "#" /[^\n]*/
-
CR: [Summary] Carriage return control character [Processing] Does nothingLF: [Summary] Newline character [Processing] Does nothingCR : /\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 nothingWS_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]+KN$[0-9]+-*/%ifwhileend==!=>=<=><=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.
programis defined as follows.statements"return"valuelineends
statementsis one of the following.statementstatements
statementis one of the following.lineendassignmentbranching
assignmentis defined as follows."$""[0-9]""="expressionlineend
branchingis defined as follows.controlconditionlineendstatements"end"lineend
controlis one of the following."if""while"
expressionis one of the following.valuevalue"+"valuevalue"-"valuevalue"*"valuevalue"/"valuevalue"%"value
conditionis one of the following.value"=="valuevalue"!="valuevalue">="valuevalue"<="valuevalue">"valuevalue"<"value
valueis one of the following.number"K""N"variable
numberis the following."[0-9]+"
variableis the following."$"var_ident
var_identis the following."[0-9]"
lineendsis one of the following."#"".*"lineendlineends
lineendis 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
operatoris"+", $a+b$ - If
operatoris"-", $a-b$ - If
operatoris"*", $a \times b$ - If
operatoris"/", $\lfloor a / b\rfloor$ - If
operatoris"%", $a-b\lfloor a / b\rfloor$
Also, a condition of the form a comparator b has the following as its value.
- If
comparatoris"==", whether $a=b$ - If
comparatoris"!=", whether $a\neq b$ - If
comparatoris">=", whether $a\geq b$ - If
comparatoris"<=", whether $a\leq b$ - If
comparatoris">", whether $a\gt b$ - If
comparatoris"<", 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もしくは右上の雲マークをクリックしてアカウントを作成してください。