故事
黑兔:“使用普通语言是撒娇。”
白兔:“……有不好的预感。”
黑兔:“加法和减法可以原谅。”
白兔「嗯……嗯……」
黑兔:“特殊形式的while语句可以使用。啊,还有其他各种限制。”
白兔:“条件分k”
黑兔:“所以这次也加油哦。”
(原作:Xmas Contest 2014 Problem A: A+B Problem)
問題文
N 有个兔子窝,M 里面有羽兔子。 每个兔子窝都有 1 ~ N 编号,每只兔子都有 1 ~ M 。 满足
你的工作是处理如下查询, Q 会给出个数量,然后依次处理。
- 类型 1 : 番号 Y 兔子进入兔舍。 X 进入里面。
- 类型 2 :兔舍 X 中的兔子里,把最先进入的兔子编号记为 1 ,请回答第Y 只进入兔舍的兔子的编号。
你必须用本查询所述语言概述中描述的语言来实现,并创建“初始化处理”“类型 1 查询的处理”“类型 2 查询的处理” 3 三种程序,并提交其源代码。格式请参照输出项。
但是,不仅需要实现,还必须确保在语言概述中所述的 BNF 里非终结符 expr 的评估次数不超过给定常数。 L 必须如下。
言語概要
用于实现的语言具有以下特征。
- 内存基本上,每个元素只能存储 [0,9999] 范围内的整数的长度 10000 数组 给出了 a 。可以通过 a[i] 访问第 i 个(0-indexed)元素。在类型 2 的查询中,可以使用存储答案的变量 A 。
- 可使用的常数也是 [0,9999] 范围内的整数。
- 运算过程中出现的数值也必须在 [0,9999] 范围内,如果不在范围内将出错。加法和减法全部从左结合进行。
- 可以使用的主要功能只有“赋值”“加法·减法”“while (表达式 < 表达式) {执行语句}”。while(表达式<表达式){执行语句} 是只有在“表达式<表达式”为真时才执行执行语句的循环语句。
- 输入通过常量接收。
- 类型 2 的回答以赋值给变量 A 的形式进行。 A 的访问每个查询只能进行 1 次,并且2 超过次数访问时会发生错误。
- 各部分(初始化、类型 1、类型 2 )中,可参考和赋值的常量及变量不同。如果尝试对该部分无法使用的常量或变量进行操作,会发生错误。
各部分可使用的常量列表如下。
- 初期化: N,M
- 类型1: N,M,X,Y
- 类型2: N,M,X,Y
各部分可以使用的变量列表如下。
- 初期化: a
- 类型1: a
- 类型2: a,A
语言的 BNF 如下。
<program> ::= <command> | <command> "\n" <program>
<command> ::= <assign> | <repetition>
<assign> ::= <var> "=" <expr>
<expr> ::= <param> | <param> "+" <expr> | <param> "-" <expr>
<repetition> ::= "while(" <expr> "<" <expr> "){\n" <program> "\n}"
<param> ::= "(" <expr> ")" | <var> | <const>
<var> ::= "a[" <expr> "]" | "A"
<const> ::= <number> | "N" | "M" | "X" | "Y"
<number> ::= <nonzero-digit> | <number> <digit>
<digit> ::= "0" | <digit>
<nonzero-digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
採点方法
评分通过评分程序进行。
评分程序的运行方式如下。如果语法不符合给定的 BNF,或者在运行时发生错误,将被视为错误答案。此外,如果调用的 expr 非终结符超过指定数量,将显示“QLE”,并被视为错误答案。 L 的数量。
- 定数 N,M 设置为输入中给定的内容。
- 配列変数 a 的所有元素 执行此操作所需的最少操作数(如果可以等于 0 进行初始化。
- 接下来,仅执行一次“初始化处理”中描述的代码。
- 然后,将给出查询。
- 类型 1 的查询到来时,将常量 X,Y 设置为查询中给定的内容,“类型 1 的查询处理中的代码。 将
- 类型 2 的查询到来时,将常量 X,Y 设置为查询中给定的内容,并初始化变量 A 该值应乘以 0 ,执行记载在“类型 2 的查询处理”中的代码。代码执行后,输出写入变量 A 的值。
但是,评分程序(解释器)在进行语法解析之前,会进行如下预处理。
- 空格、制表符、回车码、空行会事先删除。由于这样的规定,例如 "A = 1 0" 这样记载的内容会在内部作为 "A=10" 来处理,请注意。
- 每行开头出现的 ";" 之后的字符串会被认定为注释,并在语法解析前删除。
评分程序的解释器的 JavaScript 版本可以在本页底部使用。
入力
输入以以下格式描述,但评分程序会将其作为常量提供给你编写的程序,因此你无需特别注意。在使用解释器进行测试时可以参考。
N M Q L T_1 X_1 Y_1 T_2 X_2 Y_2 : T_Q X_Q Y_Q
- 1 行中,表示兔子笼的数量 N、兔子的数量 M、查询的数量 Q、非终结符expr的调用上限次数 L。N,M,Q,L 的约束请参照部分分项。
- 2 从线 Q 行 i (1≦i≦Q) 行中,i 给出了第番查询的信息。这个 i 表示,第番查询的类型 T_i(1≦T_i≦2) 的查询被 (X,Y)=(X_i,Y_i) 调用。
- 类型 1 的查询中,不会出现一只兔子进入多个兔子笼的查询。
- 类型 2 的查询中,不会出现无答案的查询。
部分点
针对此问题设置了部分分数。
- N=400,1≦M≦500,1≦Q≦1000,L=4000000 约束的数据集上正确时, 在满足 30 点。 如果您正确回答了所有满足
- N=400,1≦M≦4000,1≦Q≦8000,L=1500000 约束的数据集上正确时,与上述情况不同, 70 点。 如果您正确回答了所有满足
出力
输出应在标准输出进行(推荐使用 cat)。
你必须输出用指定语言编写的程序源代码。同时, 必须采用如
初期化処理 ---- タイプ 1 のクエリの処理 ---- タイプ 2 のクエリの処理
所示的以“----”分隔的格式。每个处理不能为空,必须至少包含 1 条以上的指令。
如果包括多字节字符(包括注释),即使在 JavaScript 版本中能够运行,判题端也可能无法正确运行,因此不应包含。
尾部的换行符是否存在,对评分程序的运行没有影响。
过长的代码(数MB规模)很可能无法被正确评分。在这种情况下会出现 IE(内部错误)。另外,程序的执行时间不包括评分程序的运行时间。
入力例1
10 5 8 54 1 1 5 2 1 1 1 10 4 1 10 2 1 10 3 2 10 1 2 10 2 2 10 3
出力例1
a[0] = 1 ; This is a comment a[1] = 5 ; Don't include any multibyte character in your program a[2] = 4 a[3] = 2 a[4] = 3 ---- a[2015] = X ; no meaning a[2016] = Y ; no meaning too ---- A = a[a[0]]; a[0] = a[0] + 1
- 1 在第...个查询中,兔舍 1 中编号为 5 的兔子将进入。
- 2 在第...个查询中,兔舍 1 至 该值是 1 被要求求出第几个进入的兔子的编号。 5 就是答案。
- 3 在第...个查询中,兔舍 10 中编号为 4 的兔子将进入。
- 4 在第...个查询中,兔舍 10 中编号为 2 的兔子将进入。
- 5 在第...个查询中,兔舍 10 中编号为 3 的兔子将进入。
- 6 在第...个查询中,兔舍 10 至 该值是 1 被要求求出第几个进入的兔子的编号。4 就是答案。
- 7 在第...个查询中,兔舍 10 至 该值是 2 被要求求出第几个进入的兔子的编号。2 就是答案。
- 8 在第...个查询中,兔舍 10 至 该值是 3 被要求求出第几个进入的兔子的编号。3 就是答案。
输出示例1的程序是把输入示例1的答案嵌入进去的,expr 非终端符号的评估次数恰好为 54 次,所以对于该测试用例可以得到正确答案。 但,理所当然地,即使提交这个程序也无法获得分数。
输入是通过评分程序提供给你输出的程序的,请注意标准输入将不会提供任何内容。也就是说,像自动生成嵌入源代码那样的解法是困难的。
另外,这个输入输出例是 L=54 的案例,由于不满足任何部分分数的约束,因此未包含在评分数据中。
语言解释器
- 可以使用这个解释器的源代码来制作解决问题的工具。
- 如果发现有什么奇怪的行为,请联系 clar。不过,“输入”部分的格式未进行检查。
- 是参考去年 hos 先生的比赛(Xmas Contest 2014)的 A+B Problem 页面制作的。
程序
入力
結果