← 返回题目列表

AtCoder · tenka1_2014_qualB_e

E. 卡拉OK排名

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

問題文

智明喜欢天下一王国的偶像,并且只在卡拉 OK 时唱天下一王国偶像的歌曲。
天下一王国的偶像歌曲总数 L 您可以在卡拉 OK 唱歌并播放歌曲 1、曲 2、…、曲 L称为。
智明君用力歌唱 每次我唱 i 时,我都会得到卡拉 OK 乐谱。 K_i 您可以获得积分。
智明君从不侮辱天下一王国的偶像歌曲,所以每次都会用尽全力地唱。

排名基于最新的 它由 M “包括修正的分数”之和确定。
“包括修正的分数”是评分结果的分数。 x 当它是一个点时, 通过 x + (x - その曲のその時点での平均点) 计算。
“该歌曲在该点的平均得分”意味着 x 这是在歌曲被评分之前(包括在内)演唱歌曲时获得的平均分数。

智明君利用他超人的编程能力,预测了本月天下一王国的偶像相关歌曲将在什么时间演唱以及获得多少积分。
根据智明的预测,本月 i 唱天下一王国偶像歌的人就是唱这首歌的人。 唱歌 A_i 唱歌,S_i 意味着获得积分。
这个月才刚刚开始,还没有人唱任何天下一王国偶像的歌曲。
智明君想什么时候唱就什么时候唱,随时都可以唱。 2 当其他人唱歌时,您可以唱任意多次,在第一个唱歌的人之前和最后一个唱歌的人之后。
智明君不会预测下个月会发生什么,他每次都会用尽全力唱歌。 只唱 M 次并瞄准排名第一。
智明君, M 我想知道最大化点数总和的最佳策略,包括修正。
因此,假设智明君的预测是正确的,请编写一个程序来找出智明君应该唱歌的时间。


入力

输入是按以下格式从标准输入给出的。

L N M
K_1 K_2 .. K_L
A_1 S_1
A_2 S_2
:
A_N S_N
  • 1 行包含一个整数,表示 Tenkaichi Kingdom 中偶像歌曲的数量。 L\ (1 ≦ L ≦ 100,000) ,一个整数,表示本月除 Tomoaki 之外的其他人演唱天下一王国的偶像歌曲的次数。 N\ (1 ≦ N ≦ 100,000) ,一个整数,表示本月智明君唱歌的次数。 M\ (1 ≦ M ≦ 100,000) 用空格分隔。
  • 2 行包含有关 Tomoaki 在演唱 Tenkaichi Kingdom 偶像的歌曲时可以获得的积分的信息。 L 数字以空格分隔。其中, i\ (1≦i≦L) 第一个号码 K_i\ (68.000 ≦ K_i ≦ 100.000) 是 可以表示为 i 代表Tomoaki 可以为第th 首歌曲获得的积分。 在
  • 3 从行 N 行中,显示了Tomoaki以外的人演唱的歌曲及其乐谱数据。1 逐行给出。这几天之一 i\ (1≦i≦N)
  • 中, 代表第i一个整数,表示所唱歌曲的编号。 A_i\ (1≦A_i≦L) 以及当时的分数 S_i\ (68.000 ≦ S_i ≦ 100.000) 用空格分隔。
  • K_i 和 S_i 正好在小数点后面。 3 给出的数字。 如果所有满足

部分点

  • L = 1 和 1 ≦ N,M ≦ 2,000 的测试用例都被正确回答,将给出部分分数。 如果所有满足 30 点。 如果您正确回答了所有满足
  • 1 ≦ L,N,M ≦ 2,000 的测试用例都回答正确,除上述之外还将给出部分分数。 30 点。 如果您正确回答了所有满足

出力

表示智明的最优策略 输出行 M 。
在这里,i 行是 第 2 空格分隔的整数 T_i, B_i ,T_i 是 您也可以写 i 智明君唱歌的时机,B_i 是 您也可以写 i 指 Tomoaki 演唱的歌曲。
该输出是 0 ≦ T_1 ≦ T_2 ≦ ... ≦ T_M ≦ N 。 当
T_i = k 那是因为除了智明君之外,只有天下一王国偶像的歌曲。 k 被唱了两遍之后,智明君 i 唱的歌 意思是唱 B_i 。
如果有多个最优策略,则任意一个最优策略 1 输出一。
在输出末尾插入换行符。


入力例1

1 5 3
80.000
1 68.000
1 70.000
1 85.000
1 72.000
1 68.000

出力例1

2 1
2 1
5 1

在本例中,歌曲数为 1 仅存在歌曲。

首先,除了智明君之外, 2 如果您在第二个人唱完后唱歌,则修正后的分数将为 80.000 + (80.000 - \frac{68.000 + 70.000 + 80.000}{3}) = 87.33333... 。 对于
如果你连续唱歌,修正后的分数将为 80.000 + (80.000 - \frac{68.000 + 70.000 + 80.000 + 80.000}{4}) = 85.5 。 对于
3 除了Tomoaki之外,没有人会第二次演唱这首歌。 5 第一人唱完后,修正后的分数将为
80.000 + (80.000 - \frac{68.000 + 70.000 + 80.000 + 80.000 + 85.000 + 72.000 + 68.000 + 80.000}{8}) = 84.625 。 对于
采用这种策略,Tomoaki 的校正分数总和为 87.33333... + 85.5 + 84.625 = 257.45833... 点,这是Tomoaki可以获得的最高点。


入力例2

2 2 2
90.000 90.000
1 80.000
2 80.000

出力例2

2 2
2 1

有多个输出可以作为答案,但输出哪一个并不重要。

曲 1 、曲 2 一起,其他人唱完后 1 如果你每次唱歌,修正后的分数将为 95.000 点。


入力例3

4 8 9
78.245 74.123 79.254 81.111
1 69.241
2 68.000
3 81.255
4 80.582
4 80.895
3 87.433
2 100.000
1 76.365

出力例3

1 1
1 1
4 4
5 4
5 4
5 4
5 4
5 4
5 4