No.2908 Strange Online Judge (Extra)
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$ and a non-negative integer $M$ (where $0\leq M\leq 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-M+1\ |\ 1\leq i\leq n\})\ (n\geq 1)$
Find $a_N$.
Constraints
- All inputs are integers
- $1\leq K\leq 10^9$
- $0\leq M\leq K$
- $1\leq N\leq 10^9$
However, StrOnJ accepts only source code written in "StLang", a programming language created for this problem.
Output StLang source code that can find $a_N$, following the StLang specification shown below. Due to judging constraints, the output must be at most 1000 lines.
Input
This problem has no input.
In the judge, integers $K,M,N$ satisfying $1\leq K\leq 10^9,\ 0\leq M\leq K,\ 1\leq N\leq 10^9$ are given to the output program.
Output
Output StLang source code that can find $a_N$. The output must be at most 1000 lines.
About the Judge
To distinguish them from runtime errors of the submitted program, if the output is produced within the execution limit and the memory limit, the judge result will be AC or WA.
StLang Specification
Sample Code
Sample code that computes the binomial coefficient ${}_NC_K\quad(N\leq 62)$ in StLang. They are an example without spaces and comment strings and an example with them, respectively.
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
- The difference from the specification in the problem "Strange Online Judge" is that the constant $M$ can additionally be used as the value
M. - StLang can only handle integers at least $0$ and less than $2^{64}$.
- Only 10 variables,
$0to$9, can be used. At the start of execution for each test case, the variables$0to$9are initialized to $0$. - The constant $K$, the constant $M$, and the constant $N$ given for each test case can be used as the values
K,M,N. - Arithmetic operations (
+,-,*,/,%) can be used at most once in an assignment statement. Operations cannot be chained. - The condition expressions of the
ifandwhilestatements, which are the available control structures, handle only a comparison operation (==,!=,>=,<=,>,<) between two values. - Everything from the
#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.
- The difference from the specification in the problem "Strange Online Judge" is that the constant $M$ can additionally be used as the value
-
Points to note
- No literals, constants, or variables other than decimal integer values, the constant
K, the constantM, the constantN, and the variables$0to$9can be used. - Outputting a program exceeding 1000 lines results in WA. A single 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 value or an arithmetic operation (
+,-,*,/,%) produces a value less than $0$ or a value at least $2^{64}$, or a division by $0$ occurs, the result is WA. - Control structures (
if,while) must explicitly mark the end of the block statement with a pairedend. - The
returnstatement must be written exactly once, at the end of the program. Areturnstatement cannot be placed inside a block of a control structure. - Arithmetic operations (
+,-,*,/,%) cannot be included in the condition expressions of control structures (if,while) or in the return value of thereturnstatement.
- No literals, constants, or variables other than decimal integer values, the constant
Details of Syntax and Processing
(Click here to expand/collapse)
The input program is parsed and a syntax tree like the figure below is built (nodes not necessarily required 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 (basically, except for control structures) in order from the root.
The StLang sample 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 using EBNF (Extended Backus–Naur Form) + regular expressions + α (for the parser generator Lark):
?start: program
program: statements "return" value lineends
?value: number | const_k | const_m | const_n | variable
number: /[0-9]+/
const_k: "K"
const_m: "M"
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 carried out by an implementation like the following.
For an example implementation of the entire interpreter with the parser generator Lark, see "StLang @ Lark Sample Execution Environment" below.
Example implementation of the interpreter with the parser generator Lark:
class StLangInterpreter(lark.visitors.Interpreter):
"""StLang Interpreter"""
def __init__(self, k=0, m=0, n=0) -> None:
super().__init__()
assert 0 <= int(k) < 2**64 and 0 <= int(m) < 2**64 and 0 <= int(n) < 2**64, "OutOfRangeNumber"
self.env = { 'C': 0, 'K': int(k), 'M': int(m), '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_m(self, _tree) -> int:
return self.env['M']
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 the StLang syntax and processing is given together with the syntax definition, mainly using EBNF (Extended Backus–Naur Form) + regular expressions, and an example interpreter implementation with Lark.
The entire source code must be written in the syntax program with at most $1000$ lines.
If the source code is not written in the correct syntax recursively defined 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,M,N$ given by the test case are set to the constant values K,M,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, m=0, n=0) -> None:
super().__init__()
assert 0 <= int(k) < 2**64 and 0 <= int(m) < 2**64 and 0 <= int(n) < 2**64, "OutOfRangeNumber"
self.env = { 'C': 0, 'K': int(k), 'M': int(m), '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 syntax definition line marks a rule whose node is omitted from the syntax tree; here, it is applied to rules that use the implementation of their child elements as is and therefore have no direct functional implementation of their own.
A part enclosed in " and " represents a literal token string
A part enclosed in / and / specifies string matching with a regular expression
A trailing ? indicates repetition 0 to 1 times (that is, it is optional)
A trailing * indicates repetition 0 or more times (optional repetition)
A trailing + indicates repetition 1 or more times (repetition)
Items listed 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 arbitrary length starting with the # character and containing no newline characters
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: [Overview] Specifies the root node of the syntax tree [Processing] Executesprogram?start: program
-
program: [Overview] Definition of the whole 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: [Overview] Integer value [Syntax] One ofnumber,const_k,const_n,variable[Processing] Returns the corresponding value?value: number | const_k | const_m | const_n | variable
-
number: [Overview] Decimal integer value [Exception] WA unless the value is at least $0$ and at most $2^{64}-1=18446744073709551615$const_k: [Overview] Constant $K$ [Processing] Returns the value determined for each test caseconst_m: [Overview] Constant $M$ [Processing] Returns the value determined for each test caseconst_n: [Overview] Constant $N$ [Processing] Returns the value determined for each test casevariable: [Overview] Variable value [Processing] Returns the value among the variables $V_0$ to $V_9$ corresponding tovar_identvar_ident: [Overview] 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_m: "M" 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_m(self, _tree) -> int: return self.env['M'] 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: [Overview] Block statement [Syntax] Consists of zero or more lines ofstatement[Processing] Executes each containedstatementin order?statements: statement*
-
statement: [Overview] Statement [Syntax] Consists of one ofassignment,branching,repeating, or an empty line (or comment line) [Processing] Executes the corresponding one?statement: assignment | branching | repeating | lineend
-
assignment: [Overview] Assignment[Processing] Assigns the value obtained by evaluating
expression(an unsigned 64-bit integer) to the variablevar_identEach time an assignment is performed, the value of $C$ increases by $1$ [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: [Overview] 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: [Overview] Addition $a+b$ [Exception] WA unless the resulting value is at least $0$ and at most $2^{64}-1=18446744073709551615$sub: [Overview] Subtraction $a-b$ [Exception] WA unless the resulting value is at least $0$ and at most $2^{64}-1=18446744073709551615$mul: [Overview] Multiplication $a\times b$ [Exception] WA unless the resulting value is at least $0$ and at most $2^{64}-1=18446744073709551615$div: [Overview] Division $\lfloor a/b\rfloor$ [Exception] WA if the divisor is $0$rem: [Overview] 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: [Overview] Branching (if)[Processing] Executes
statementsif the evaluation (bool) ofconditionistrueWhen
conditionis evaluated, the value of $C$ increases by $1$ [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: [Overview] Repetition (while)[Processing] Repeatedly executes
statementswhile the evaluation (bool) ofconditionistrueEach time
conditionis evaluated, the value of $C$ increases by $1$ [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: [Overview] 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: [Overview] EQual [Processing]trueif the values of the twovalues are equal, otherwisefalsene: [Overview] Not Equal [Processing]trueif the values of the twovalues differ, otherwisefalsege: [Overview] Greater than or Equal to [Processing]trueif the firstvalueis greater than or equal to the secondvalue, otherwisefalsele: [Overview] Less than or Equal to [Processing]trueif the firstvalueis less than or equal to the secondvalue, otherwisefalsegt: [Overview] Greater Than [Processing]trueif the firstvalueis greater than the secondvalue, otherwisefalselt: [Overview] 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: [Overview] The end ofprogramafter thereturnstatement [Syntax] Zero or morelineends, and at most one comment string without a newline [Processing] Does nothing?lineends: lineend* ST_COMMENT?
-
lineend: [Overview] End of line (may contain a comment string) [Syntax]ST_COMMENTandCRcan be omitted [Processing] Does nothing?lineend: ST_COMMENT? CR? LF
-
ST_COMMENT: [Overview] 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: [Overview] Carriage return control character [Processing] Does nothingLF: [Overview] Newline character [Processing] Does nothingCR : /\r/ LF : /\n/
-
WS_INLINE: [Overview] 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 other than newlines, and \n represents a newline.
[0-9]+KMN$[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 written enclosed in double quotation marks, and concatenation of tokens or syntax elements is written separated by spaces. Also, denotes 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""M""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. When the written sequence of digits is interpreted as a non-negative integer, the result is WA unless it is at least $0$ and at most $2^{64}-1=18446744073709551615$.
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$, "M" is a constant representing the value of $M$, and "N" is a constant representing the value of $N$. These values are determined for each case.
Regarding variable, where $i$ is a digit, "$i" is a variable representing the value of $V_i$.
The values of number, "K", "M", "N", 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
- $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$ if
operatoris"%"
Also, a condition of the form a comparator b has as its value
- 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$ if
comparatoris"<"
The program performs the processing described by statements of program, then returns the value specified as value and terminates. If the returned value is not $a_N$ for the given $K,M,N$, the result is WA.
The contents of lineend and endcomment are ignored, and no processing is performed for them.
For statements, if it is of the form , no processing is performed. If it is of the form statement statements, the processing described by statement is performed, and then processing moves on to statements.
assignment changes the value of $V_i$ corresponding to 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. (Whether $1000$ is appropriate needs verification.)
StLang @ Lark Sample Execution Environment
The StLang sample code is set by default, so rewrite it as appropriate into a program suited to the problem statement before use.
-
Python code (simple 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) m = random.randrange(0, k+1) n = min(random.randrange(1, 2**random.randrange(1, 32)), 10**9) ### TODO: k,m,n の値から回答すべき値 an を生成するコードを書く an = 0 return k, m, 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, m, n, an in itertools.chain([ # 本番問題用のサンプルケース ( 3, 1, 5, 6 ), ( 8, 1, 1, 1 ), ( 10, 1, 1000000000, 1099019513 ), ( 3, 0, 5, 6 ), ( 8, 8, 1, 1 ), ( 10, 6, 1000000000, 1099019514 ), ], 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_m | const_n | variable number: /[0-9]+/ const_k: "K" const_m: "M" 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), 'M': int(m), '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_m(self, _tree) -> int: return self.env['M'] 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 $K\ M\ N$ given as constants by the judge and the values to be returned. The $3$ numbers in "Constants" are $K\ M\ N$, in this order.
Sample 1
Constants
3 0 5
Value to Return
6
Here, $K=3,\ M=0,\ N=5$.
Since $a_1=1,\ a_2=\operatorname{mex}\{0,1,5\}=2,\ a_3=\operatorname{mex}\{0,1,2,5,9\}=3,\ a_4=\operatorname{mex}\{0,1,2,3,5,9,13\}=4,\ a_5=\operatorname{mex}\{0,1,2,3,4,5,9,13,17\}=6$, the answer is $6$.
Sample 2
Constants
8 8 1
Value to Return
1
Sample 3
Constants
10 6 1000000000
Value to Return
1099019514
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。