← 返回题目列表

AtCoder · asaporo_f

B. 逗号分隔数字的问题

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

分数: 1000 点

问题陈述

给你一个字符串 S 由之间的数字组成 1 和 9,包括在内。 您最多将插入 K 逗号 (,) 插入该字符串以将其分成多个数字。

您的任务是最小化通过插入逗号产生的最大数量。找到该值的最小可能值。

约束

  • 0 ≦ K < |S| ≦ 100,000
  • S 由之间的数字组成 1 和 9,包括在内。

部分分数

  • 在测试集中值得 100 点, |S| ≦ 2.
  • 在测试集中值得另一个 100 点, |S| ≦ 16.
  • 在测试集中值得另一个 200 点, |S| ≦ 100.
  • 在测试集中值得另一个 200 点, |S| ≦ 2,000.

输入

输入由标准输入按以下格式给出:

K
S

输出

打印最小可能值。


示例输入 1

2
15267315

示例输出 1

315

当字符串被分成 152, 67 和 315,其中最大的是 315,这是可能的最小值。


示例输入 2

0
12456174517653111

示例输出 2

12456174517653111

12456174517653111 本身就是答案。


示例输入 3

8
127356176351764127645176543176531763517635176531278461856198765816581726586715987216581

示例输出 3

5317635176