← 返回题目列表

AtCoder · xmascontest2015_e

E. 奇趣编程语言?

中文机器翻译题面 查看原题

故事

黑兔:“使用普通语言是撒娇。”

白兔:“……有不好的预感。”

黑兔:“加法和减法可以原谅。”

白兔「嗯……嗯……」

黑兔:“特殊形式的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 的数量。

  1. 定数 N,M 设置为输入中给定的内容。
  2. 配列変数 a 的所有元素 执行此操作所需的最少操作数(如果可以等于 0 进行初始化。
  3. 接下来,仅执行一次“初始化处理”中描述的代码。
  4. 然后,将给出查询。
    • 类型 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 页面制作的。

程序

入力

結果