← 返回题目列表

AtCoder · xmascon16_c

C. 切割瑞士卷

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

配点 : 100 点

問題文

白兔和黑兔作为圣诞蛋糕购买了长度为 N cm 的卷蛋糕。这个卷蛋糕的甜度因位置而异,对于各个 i (1 \leq i \leq N) 而言,从蛋糕左端开始 i-1 cm 的位置到 i cm 的位置的甜度是整数。 A_i 表示。

白兔和黑兔打算一起吃掉这块蛋糕中正好 1 cm 的部分,剩下的部分则放入冰箱。蛋糕吃哪一部分将按照以下方式决定。 2 首先白兔将在左端开始的

  1. cm 处把蛋糕 k 分成若干块。这里 2 只要是大于等于 k 是 您也可以写 1 且小于蛋糕长度的整数都可以。
  2. 被切分的 2 在几块蛋糕中,黑兔选择自己喜欢的一块放入冰箱。

在完成这第 1、2 步之后,如果蛋糕仍然有 2 厘米以上剩余,则下一步由黑兔切蛋糕,白兔将其中一半放入冰箱。这样交替操作,直到剩下 1 厘米的蛋糕为止,白兔和黑兔轮流重复步骤 1、2。

白兔非常喜欢甜蛋糕,所以它希望通过行动使最终剩下的蛋糕尽可能甜。另一方面,黑兔更喜欢苦味,因此它希望通过行动使最终剩下的蛋糕尽可能不甜。

当双方都采取最优行动时,最终剩下蛋糕的甜度是 X 。白兔的最优行动,也就是说,不管黑兔如何行动,最终甜度 X 创建一个程序,实现能够确保剩下不少于以上蛋糕的策略(注意X 不会被明确给出).

制約

  • 2 \leq N \leq 5,000.
  • 1 \leq A_i \leq 10^9.
  • A_i 是一个整数。

採点

你的程序在遵循下面给出的输入输出格式的前提下,如果最终剩下的蛋糕甜度不少于 X ,则视为正确答案.

如果在所有测试用例中都是正确答案 100 点。 如果所有满足


入出力

首先,是表示蛋糕长度的整数 N 会被输入到标准输入。随后,表示蛋糕甜度的 N 整数 给出了 A_1, A_2, ..., A_N 会依次被输入到标准输入。

之后,蛋糕的切分开始,以下的输入输出 1〜4 会重复进行。

  1. 你的程序需要输出一个整数 k 到标准输出,这个整数表示白兔切蛋糕的位置。 k 这意味着从蛋糕的左端开始在 cm 处切开。
    • k 是 您也可以写 1 必须大于等于此值且小于当前蛋糕的长度。
  2. 文字 L 或 至少 R 会作为标准输入提供。L, R 分别表示黑兔将切口左侧和右侧的部分放入冰箱。
    • 由于黑兔的这个行为,剩下的蛋糕 1 厘米时,之后不会再输入,你的程序也必须立即结束。
  3. 表示黑兔切蛋糕位置的整数 k' 会作为标准输入提供。这是从蛋糕左端算起的 k' 这意味着从蛋糕的左端开始在 cm 处切开。
    • k' 是 您也可以写 1 大于等于此值且小于当前蛋糕的长度。
  4. 你的程序应将字符 L 或 至少 R 输出到标准输出。L, R 分别表示白兔将切口左侧和右侧的部分放入冰箱。
    • 由于白兔的这个行为,剩下的蛋糕 1 厘米时,之后不会再输入,你的程序也必须立即结束。

请参考输入输出示例。

注意点

蛋糕的长度变为 1 厘米后,你的程序必须立即结束。 如果未能结束,判断结果是不确定的。另外,如果输出不正确,结果也是不确定的(不一定会变成 WA )。

注意在输出后必须flush输出。如果不进行flush,可能会导致TLE。

每种语言的输入/输出方法都是过去 AtCoder 问题中提出的问题(链接: ABC 019 D:高桥君和树的直径)可以参考。


入出力例

N=5,\ A = \{1,2,3,4,5\} 显示了输入输出的例子。

入力 出力 説明
5 1 2 3 4 5 蛋糕的长度 N 和甜度 A 已给出。
4 白兔从左边在 4 厘米处切蛋糕。
R 黑兔把右边的部分放进冰箱。
1 黑兔从左边切蛋糕 1 厘米处切蛋糕。
L 白宇把左边的部分放进冰箱。
2 白兔从左边在 2 厘米处切蛋糕。
R 黑兔把右边的部分放进冰箱。
1 黑兔从左边切蛋糕 1 厘米处切蛋糕。
L 白宇把左边的部分放进冰箱。这时,蛋糕 1 cm,所以回应将结束。

在上述回应示例中,最终的甜味 3 蛋糕剩下。在这种情况下, X = 3 (当白兔和黑兔都表现出最佳状态时,蛋糕剩余的甜味 3) 因此,上述响应示例被认为是正确的。