AT_pakencamp_2019_day4_h 板の重なり

有 $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 之间的整数。 从上面观察这些叠放的木板，如果有某些区域至少有一层是红色的，此区域就呈现为红色。你的任务是找出一种放置方案，使得从上面看到的连续的红色区域长度最大化。请注意，你不需找到绝对最优的放置方案，只需提供一种合理的方案即可。

输入从标准输入读取，格式如下： ``` 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 = 300$。 - $31 \leq L_i \leq 62$。 - $S_{i, j}$ 为 0 或 1。 ### 测试用例生成方法 测试用例的生成步骤如下： 1. 在 31 到 62 之间随机选择 $L_i$。 2. 确定一个在 0.15 到 0.55 之间的随机数 $B$。 3. 对每个 $j$（$1 \leq j \leq L_i$），以概率 $B$ 设 $S_{i, j} = 1$，以概率 $1-B$ 设 $S_{i, j} = 0$。 4. 如果结果是所有 $S_{i, j}$ 都为 0，则重做第 1 步。 ### 得分规则 提交的得分计算方式如下： - 只要有一个测试用例不符合要求（例如 $0 \leq m_i \leq 10,000$ 或输出格式错误），得分即为 0。 - 否则，假设第 $i$ 个测试用例的得分为 $a_i$，则总分为 $\frac{a_1 + a_2 + \ldots + a_{10}}{10}$，并向下取整。 各测试用例的得分计算如下： - 如果 $D \leq 199$，得 5 分。 - 如果 $200 \leq D \leq 4,209$，得分为 $100 - 30 \log_2 \left( \frac{4,810 - D}{600} \right)$，并向下取整。 - 如果 $4,210 \leq D$，得分为 $100 + \frac{D - 4,210}{10}$。 ### 输入输出示例 例如，考虑以下输入示例： ``` 3 1101 011 10101 ``` ### 示例解释 对于该输出而言，从左数第 7 厘米到第 10 厘米的区间，其长度为 3 厘米的部分会显示为连续红色，这是最长的连续红色部分。因此，该输出的得分为 5 分。注意，这个输入示例不符合 $N = 300$ 和 $31 \leq L_i \leq 62$ 的要求，因此不包含在评分的测试数据中。所有用于评分的测试用例均满足这些条件。 **本翻译由 AI 自动生成**