3563. 校园卡清零

单点时限: 1.5 sec

内存限制: 512 MB

经过五年的艰苦奋斗,你终于要从华东遗憾大学毕业了。为了庆祝这一重大事件,你决定花光你校园卡上的钱。

在华东遗憾大学,校园卡的唯一用途就是在食堂吃饭。食堂里面有 $2n$ 种套餐,价格分别为 $a_1,a_2,\ldots,a_{2n}$,每天食堂会随机地卖 $n$ 种套餐(也就是说另外 $n$ 种套餐不卖)。校园卡充值只接受 $100$ 元纸币,所以你充钱的时候肯定是 $100$ 的倍数。你的校园卡上现在余额是 $p$ 元。

现在你可以每天充钱,然后从食堂提供的 $n$ 种套餐中选择一种或者选择「今天不去食堂吃饭,我要点外卖」。(就算点外卖你仍然可以去食堂充钱,但这件事毫无意义)。你必须在 $365$ 天内把校园卡上的钱花完;因为按照学校规定,本科在读超过六年可能就永远毕不了业了。

理论分析表明,如果你选得好的话,这件事情大概是稳的。

数据保证有解。

交互流程

你首先要从交互器读入 $n$, $p$ ($1 \le n \le 500, 1 \le p \le 100$)。

第二行是 $2n$ 个整数,表示 $a_1,a_2,\ldots,a_{2n}$,是套餐的价格。这些套餐按顺序给出,第 $i$ 种套餐价格是 $a_i$ ($1 \le a_i \le 100$)。

接下来,每一天你都要从交互器读入 $n$ 个整数 $i_1,i_2,\ldots,i_n$,表示今天出售的套餐种类;这些套餐的价格是 $a_{i_1},a_{i_2},\ldots,a_{i_n}$。

根据食堂提供的套餐种类,你需要输出两个整数 $c,s$ ($0 \le c \le 100$, $s = 0$ 或 $s \in {i_1,i_2, \ldots,i_n}$)。$c$ 表示你今天在吃饭钱充值了几个 $100$ 元(按照约定你不能充值太多,有钱也别秀);$s$ 表示你今天选择了哪种套餐。$s$ 必须是今天提供的套餐。如果你今天点外卖,那么 $s=0$。

如果当天结束之后你的余额为 $0$ 了,你可以安全地退出程序。否则你要一直读入(直到彻底延毕)。如果你在 $365$ 天之内完成任务,那么就 Accepted 了;否则可能返回 Wrong AnswerIdleness Limit Exceeded

交互器保证:每天选的 $n$ 个套餐是完全随机的,跟你之前的选择没有关系。

样例

Input
2 5
2 3 3 3
1 2

2 3
Output
0 1

0 2

提示

从交互器读入、输出使用标准输入输出流:stdin, stdout。请注意输出的缓冲区问题:在 C 语言中,请在 printf 后使用 fflush(stdout);在 C++ 中,可以使用 endlflush,在 Python 中,可以使用 stdout.flush()。其他的语言就不再列举。

39 人解决,92 人已尝试。

46 份提交通过,共有 834 份提交。

6.1 EMB 奖励。

创建: 5 年,11 月前.

修改: 5 年,11 月前.

最后提交: 1 月,1 周前.

来源: 2018 华东师范大学校赛

题目标签
DP