← 返回题目列表

AtCoder · rco_contest_2018_final_b

B. 库库鲁寿司

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

背景

X 在某家回转寿司店一个人制作寿司。

今天是 X 的熟人Q人会去回转寿司店用餐。X 不认识熟人的长相,并且也在顾客看不到的地方,但熟人会把自己吃的寿司的照片逐一上传到社交媒体,所以 X 希望通过看到这些照片,大致确定熟人所坐的位置。熟人会M上传回照片。

X 无论与想要特定的熟人是否有关,都会不断流动固定长度的寿司列。N的寿司列。i第几位熟人一坐下时,其面前会有寿司列的第几件寿司(不一定熟人会取这个寿司)。start_i来到。

此外,X 还可以通过赶走已经在店里的其他顾客,来操作每件寿司被熟人取走的准确率。

当然,赶走顾客会降低店铺的声誉,所以请巧妙决定寿司列,尽量在不降低声誉的情况下确定熟人的位置。

問題文

这个问题是互动类型的。N给出后,请决定长度N字符串S和实数D。裁判将生成S,\ D它们的编号最大为Q个查询。q_i对第 i个查询,裁判将根据0到N未满的整数的均匀随机选择start_i。此时字符串q_i将根据以下伪代码决定。

q_i = ""
for (pos = start_i; q_i.length < M; pos++)
    確率 1.0 / D で、q_i の末尾に S[pos \% N] を付け足す
return q_i

各i关于start_i请进行估计。

各个测试用例的得分以及该问题的得分计算方式如下。

  • 各i,start_i的估计值为guess_i时,得分score_i将根据以下公式计算。 \begin{aligned} distance_i &= \min\left(\left| guess_i-start_i\right|, N-\left| guess_i-start_i\right|\right),\\ score_i &= \sqrt{D} * \exp(-distance_i^2/25.0)\end{aligned}
    • y=exp(-x^2/25)将获得以下类型的图表。
      y=exp(-x^2/25)
  • 1个测试的得分是各i分数的总计向上取整的值。
  • 测试总共有10个。每个测试的得分总和,就是本题的得分。
  • 另外,用于计算分数的变量是64位浮点数表示,因此可能会产生微小误差,请理解。

入出力

输入以以下格式从标准输入提供。

首先,将提供如下内容。

N M Q
  • N 是S中的字符数, 满足N = 3000 。
  • M 是q_i中的字符数, 满足M = 7 。
  • Q 是一个整数,表示查询次数,Q = 30000 。

对于此输入, 请按以下格式输出S和 将其放在D。

S
D
  • S是长度N由半角小写字母组成的字符串。
  • D是1.0以上10.0是下面的实数。

然后您将获得类似于以下内容的输入:

q_0
q_1
:
q_{Q-1}
  • q_i 是,M字符串。 满足

各q_i,guess_i。

guess_0
guess_1
:
guess_{Q-1}
  • guess_i 是,0≤ guess_i< N 的整数。
  • 输出完成后,请退出程序。
  • 请务必在输出后添加换行符并刷新。
  • 由于判断程序的原因,Q的 阅读完所有q_i后 请开始输出guess_i。

入出力例

程序的输入 程序输出 给出了 説明
13 7 2
N=13,\ M=7,\ Q=2。请注意,该值不满足测试用例约束。
nosushinolife
1.8
在回转寿司店吃寿司以外的配菜的平均数量
S=nosushinolife,\ D=1.8。S中的字符数为 生成并给出N=13。
osushin
nolifos
q_0,\ q_1。每个长度为 输出M=7。
1
7

guess_0,\ guess_1 。这些是 必须小于0以上N。

start_0=1,\ start_1=0,则得分为 这种情况下的分数计算为

distance_0 = min(abs(1-1),\ N - abs(1-1)) = 0,

score_0 = sqrt(D) * exp(-0^2/25.0)≒1.341641,

distance_1 = min(abs(7-0),\ N - abs(7-0)) = 6,

score_1 = sqrt(D) * exp(-6^2/25.0)≒0.317872

。 将

score_0 + score_1≒1.659513向上舍入到最接近的整数。2点。


测试仪

以下链接提供了测试仪。

测试仪