#549. 「LibreOJ β Round #7」康普·莱克·西提

题目类型:答案提交 评测方式:Special Judge
上传者: liu_cheng_ao

题目描述

LCR 最近发明了一种新的编程语言 A++。然而令她始料未及的是,小明刚刚学会循环就开始祸害全国 OIer。LCR 决定教他做人,于是写了一些程序要小明计算渐进时间复杂度。
由于小明利用 A++ 参与的 NOI 系列赛事将常数优化作为一大考点,LCR 还要求小明计算出这些程序的渐进常数因子。

A++ 语言有语句、正整数常数,正整数型变量、For 循环和一元函数这几种语法。

一份 A++ 源代码只包含以下字符:

  • 可见字符,包括大小写拉丁字母 A~Za~z,数字 0~9
  • 空白字符,包括半角空格,换行 \n,回车 \r,制表 \t

我们定义一个是一段长度达到极大的由可见字符组成的连续段。

A++ 的基本单位是语句,其按换行 \n 分隔,每行开头一个词表示语句类型:

  • Func 表示这是个函数的开头
  • F 表示这是个 For 循环的开头
  • E 表示这是某个函数或 For 循环的结束
  • <函数名> 表示调用该函数
  • S 表示时间复杂度标志语句

FuncFES 称为关键字。

每种语句完整的语法格式如下:

  • Func <函数名> 表示声明一个一元函数 <函数名>。调用函数时,一个名为 n 的变量建立,作用域开始,表示传入函数的参数。
    函数名是一个以大写字母开头的词,不同函数不重名,函数不与关键字重名,该函数结束之前的语句不能调用该函数(即,先声明的函数不能调用后声明的函数,也不允许递归调用)。
  • F <变量名> <起始> <终止> 表示变量 <变量名>的建立,作用域开始并初始化为 <起始>,然后比较 <变量名><终止> 的大小,若 <变量名> 小于等于 <终止> 则进入循环,否则不进入;每次循环结束后 <变量名> 都会被修改成 <变量名>+1 并继续执行循环,一旦 <变量名> 大于 <终止> 立即终止循环。
    变量名是一个以小写字母开头的词,不与作用域未结束的其它变量(包括 n)重名。<起始><终止> 均为作用域内除 <变量名> 之外的变量或常数。
  • E 表示之前离其最近的未结束的函数或 For 循环的结束,同时该函数或循环建立的变量作用域结束。
  • <函数名> <参数> 表示以 <参数> 为参数调用该函数。<参数> 为某个作用域未结束的变量或常数。
  • S 表示时间复杂度标志语句。

程序的最后一个函数名必定是 Main,执行程序相当于以输入的参数 n 调用一次 Main 函数。

为了方便你计算时间复杂度,LCR 定义程序运行时间为标志语句 S 的总执行次数。
可以证明,当 n 充分大(即,对于每个给定的程序存在一个常数 M 使得 n>M 时后面的结论均成立)时,S 的总执行次数是一个关于 n 的多项式。规定渐进复杂度的次数 w 多项式最高次项的次数,常数因子 k 多项式最高次项的系数。即 T(n)\sim kn^w

LCR 身经百战,见得多了,自然不会出现语法错误这种低级失误啦!

输入格式

本题为提交答案题。所有输入数据 1.app ~ 13.app 见选手文件,请从题目描述上方附加文件中下载。每个文件对应一组输入。

每组输入共若干行,每行一条语句,以文件结束符 EOF 结束。

输出格式

输出文件为 1.out ~ 13.out,分别对应相应的输入文件。

每个输出文件包含两行,第一行一个十进制非负整数 w 表示次数。注意 w=0 表示常数复杂度。

第二行两个十进制正整数 A,B 表示常数因子为 A/B A,B 的位数均不应超过 500 。若位数过多,我们不保证你在 A/B 的数值满足要求的情况下能得到相应的分数,但也不保证一定得不到分数。

样例

样例输入 1

Func Main
	F i 1 n
		F j 1 i
			F k 1 j
				S
			E
		E
	E
E

样例输出 1

3
1 6

样例输入 2

Func Floyd
	F k 1 n
		F i 1 n
			F j 1 n
				S
			E
		E
	E
E

Func Main
	Floyd n
E

样例输出 2

3
1 1

样例输入 3

Func Fib1
	S
E
Func Fib2
	S
E
Func Fib3
	Fib2 2
	Fib1 1
E
Func Fib4
	Fib3 3
	Fib2 2
E
Func Fib5
	Fib4 4
	Fib3 3
E
Func Main
	Fib5 5
E

样例输出 3

0
5 1

数据范围与提示

输入数据已经给出。以下是对于所有输入数据,均满足的限制:

  • 程序一定合法。
  • 保证对于充分大的 n S 至少被调用一次。
  • 程序总行数不超过 500
  • 程序中的常数是 [1,100] 中的整数。
  • 函数名、变量名的长度不超过 10 个字符。

评分方式

对于每组数据,如果 w 错误得 0 分。

w 正确的基础上,我们有 8 组评分参数: l_3,l_4,\cdots,l_{10} r_3,r_4,\cdots,r_{10} 。你的程序的得分占该组数据满分的比例是最大的满足 l_s\le A/B\le r_s s 10 之比。如果这个 s 不存在,得 20\% 分数。

以下是每个测试点的分值:

1 2 3 4 5 6 7 8 9 10 11 12 13
5 6 8 9 8 9 8 11

提示

我们在附加文件中为 C++ 语言提供了一个高精度模板 number.h。该模板需要 C++11 标准,但通过简单的修改也可以在更低的 C++ 标准下使用。

我们提供了一个 A++ 语言在 Notepad++ 中的自定义语言配置 notepad++_lang_A++.xml 以帮助选手理解 A++ 语言及阅读程序。

另外,请注意,有相当特殊性质的数据并不多。

关于提交

你可以直接在提交框的每个标签页中写入你的答案。

或者,你可以提交文件:请直接将答案文件(1.out ~ 13.out)压缩成一个 ZIP 文件,不要在答案文件外套一层文件夹

如果提交文件出错了,可以换个浏览器试试(建议使用最新版 Chrome 或 Firefox)。

请注意 IOI 赛制取得分最高的单次提交,所以请一次性交完,不要分多次提交每个文件。

编辑器加载中 …