← 返回题目列表

AtCoder · pakencamp_2019_day4_h

H. 重叠的板

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

配点: 100 点

問題文

N 块板,并且每块板 它的编号为 1,板 2,...,板 N 。

板 i 的长度是 L_i 以厘米为单位,从左边数起,j-1 从厘米起 j 厘米以内的部分均已着色 它涂有 S_{i, j} 。 当S_{i, j} = 0 时透明,S_{i, j} = 1 时为红色。

现在,你 N 您可以将板放置在适当的位置并将它们堆叠在一起。
「i 第二块板的左端来自原点。 m_i 对于每个板,m_i 是 0 以上 10 \ 000 可以由以下整数确定。

当你从上面看重叠的木板时,你可以看到木板的红色部分是 1 重叠部分显示为红色。
找到一种放置对象的方法,使得从上方观察时连续“红色部分”的最大长度尽可能大。然而,没有必要寻找最佳的。

制約

  • N = 300.
  • 31 \leq L_i \leq 62.
  • S_{i, j} 是 0 或 通过替换 1.

关于测试用例生成

测试用例是根据以下步骤生成的。

  1. L_i 的值为31 以上 62 从以下整数中均匀随机选择。
  2. B ,0.15 以上 0.55 令其为基于以下均匀概率分布确定的随机值。
  3. 各 j (1 \leq j \leq L_i)独立 S_{i, j} 的值被确定。概率 B 出现 S_{i, j} = \ 1 和概率 1-B 出现 S_{i, j} = \ 0 变为。 (23:11更正)
  4. 已获得 S_{i, 1}, S_{i, 2}, S_{i, 3}, ..., S_{i, L_i} 就是全部 如果 0 ,则从步骤 1 重新开始。


得点

提交的分数将按如下方式确定。

  • 用于评分 在 10 测试用例中,1 任何不满足条件的输出 (0 \leq m_i \leq 10 \ 000 、无效的输出格式等),0 点。
  • 否则,i 测试用例的得分为 a_i 分,提交分数为 \frac{a_{1}+a_{2}+a_{3}+...+a_{10}}{10} 该值向下舍入到最接近的整数。

每个测试用例的分数如下。 可能会超出(100 点。 )然而,连续的“红色部分”的最大长度是 比方说 D 。

  • D \leq 199 时,5 点.
  • 200 \leq D \leq 4 \ 209 时,100 - 30log_2(\frac{4810 - D}{600}) 分数向下舍入到最接近的整数。
  • 4 \ 210 \leq D 时,100 + \frac{D - 4 \ 210}{10} 点.


入力

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

N
s_{1,1}s_{1,2}s_{1,3}...s_{1,L_{1}}
s_{2,1}s_{2,2}s_{2,3}...s_{2,L_{2}}
s_{3,1}s_{3,2}s_{3,3}...s_{3,L_{3}}
:
s_{N,1}s_{N,2}s_{N,3}...s_{N,L_{N}}

出力

请按以下格式输出。 必须是小于或等于

m_1
m_2
m_3
:
m_N

但是, 如果是m_i 是 0 以上 10 \ 000 的整数。


入出力例

例如,请考虑以下输入示例。 (N, L_i 不满足约束条件,因此不包含在用于评分的数据中。 )
3
1101
011
10101

出力例 1

4
7
3

该输出对应的图如下所示。

从左数起,7 从厘米起 10 长度可达厘米 3 厘米部分呈现连续红色。另外,这是最大长度。因此,该输出的分数为 5 点。

这个输入示例是 它不包含在测试数据中,因为它不满足N = 300,31 \leq L_i \leq 62 条件。
用于评分的所有测试用例都是N = 300,31 \leq L_i \leq 62 满意。