背景
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将根据以下公式计算。
- 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点。 |
测试仪
以下链接提供了测试仪。