#2875. 「JOISC 2014 Day1」拉面比较

内存限制:256 MiB 时间限制:1000 ms 题目类型:交互
上传者: Planet6174

题目描述

题目译自 JOISC 2014 Day1 T4「ラーメンの食べ比べ

JOI 君和 IOI 酱都喜欢吃拉面。JOI 君喜欢吃清汤拉面,而 IOI 酱喜欢吃浓汤拉面,在 JOI 君和 IOI 酱居住的城镇里,共有 N 家拉面馆,编号为 0 N-1

我们不知道每家拉面馆卖的是清汤拉面还是浓汤拉面,因此,JOI 君和 IOI 酱决定去附近的一些拉面馆寻找最好吃的清汤和浓汤拉面。

JOI 君和 IOI 酱到附近的拉面馆,分别确定两家拉面馆拉面的浓厚度,浓厚度是一个大于等于 0 小于等于 N-1 的整数,每家面馆拉面的浓厚度两两不同。JOI 君和 IOI 酱每天每人去一家拉面馆,通过品尝味道,可以比较出两家拉面馆哪一家浓厚度更高。

出于健康因素考虑,JOI 君和 IOI 酱最多吃 600 天拉面。

任务

给出城镇里拉面馆数 N ,在最多吃 600 天拉面的情况下,确定浓厚度最高的拉面馆和浓厚度最低的拉面馆。

实现细节

你需要实现一个程序,在给出城镇里拉面馆数 N ,在最多吃 600 天拉面的情况下,确定浓厚度最高的拉面馆和浓厚度最低的拉面馆。

该程序必须实现以下过程:

void Ramen(int N)
  • 对于每个测试用例,该函数仅调用一次,参数 N 是城镇上拉面馆的数量;
  • 只允许通过调用 Compare 函数确定两家店浓厚度的大小关系,只允许通过调用 Answer 函数给出浓厚度最高的拉面馆和浓厚度最低的拉面馆。

可以在程序中调用以下函数:

int Compare(int X, int Y)
  • 在比较两家面馆 \texttt{X,Y} 的浓厚度时调用此函数, \texttt{X,Y} 是大于等于 0 且小于等于 N-1 的整数,如果不满足以上条件,会被判为 Wrong Answer [1],程序结束;
  • 如果拉面馆 \texttt{X} 的浓厚度大于 \texttt{Y} ,则函数返回 1 ,否则返回 -1
  • 如果 Compare 函数调用次数超过 600 ,会被判为 Wrong Answer [2],程序结束。

Ramen 函数必须调用 Answer 函数来结束,如果 Ramen 没有调用 Answer,会被判为 Wrong Answer [3]

int Answer(int X, int Y)
  • 这个函数用来回答哪家拉面馆的浓厚度最低与哪家拉面馆浓厚度最高。参数 \texttt{X} 表示拉面馆 \texttt{X} 的浓厚度最低,参数 \texttt{Y} 表示拉面馆 \texttt{Y} 的浓厚度最高。 \texttt{X,Y} 都大于等于 0 且小于等于 N-1 ,如果不满足条件会被判为 Wrong Answer [4]
  • 可以保证,与调用 Compare 的结果一致的答案是唯一的,如果 \texttt{X,Y} 与答案不一致,则会被判为 Wrong Answer [5],一致则会被判为 Accepted
  • 调用此函数后,程序结束。

注意

在评分时,只要你的回答与调用 Compare 的结果不一致,都会被判为 Wrong Answer [5]

在评分时,一些测试点可能会根据之前 Compare 的调用情况修改返回值,但是 Compare 的返回值与之前 Compare 的调用结果不矛盾。

编译与运行方法

「附加文件」中提供了 ramen.hgrader.cgrader.cpp 三个文件。若你编写的程序名称为 ramen.cramen.cpp,请运行以下命令来编译:

  • C 语言
gcc -O2 -lm -o grader grader.c ramen.c
  • C++ 语言
g++ -O2 -o grader grader.cpp ramen.cpp

当命令成功时,会产生一个可执行文件 grader

注意实际评测时的程序与下发的样例评测程序并不相同。实际的 ramen.h 函数实现将通过标准输入/输出与单独运行的交互器进行交互。

样例评测程序输入格式

样例评测程序将从标准输入读入以下数据:

  • 第一行两个整数 N,T ,用一个空格隔开。 N 表示拉面馆数,评测程序只会处理 T=1 的数据;
  • 接下来 N 行,第 i+1 行表示拉面馆 i 的浓厚度 A_i

样例评测程序输出格式

样例评测程序将向标准输出输出以下信息。

  • 判为正确时,输出 Accepted
  • 运行过程中被判为错误时,以 Wrong Answer [x] 的格式报告并退出。

程序执行过程中违反了多种限制时,只会报告其中的一种。

注意,如果样例中 A_X=0,A_Y=N-1 ,调用了 Answer(X, Y),即使应当是 Wrong Answer [5] 的情况,测评程序也会判定 Accepted。请注意,下发的 grader 与实际测评时使用的不同。

样例

样例测评程序输入

3 1
1
2
0

样例交互

调用函数 返回值
Compare(0, 1) -1
Compare(0, 2) 1
Answer(2, 1) 测评程序结束

数据范围与提示

对于全部数据, 1\le N\le 400

详细子任务分数与附加限制见下表。

Subtask 附加限制 分数
1 N\le 30 20
2 N\le 300 30
3 无附加限制 50