Time Limit: 3 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
1
から 9
までの数字のみで構成された文字列 S が与えられます。
この文字列に、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 行で出力しなさい。
入力例 1
2 15267315
出力例 1
315
152, 67, 315 と区切ると、最大値が 315 となり、これが答えとなります。
入力例 2
0 12456174517653111
出力例 2
12456174517653111
12456174517653111 がそのまま答えとなります。
入力例 3
8 127356176351764127645176543176531763517635176531278461856198765816581726586715987216581
出力例 3
5317635176
Score : 1000 points
Problem Statement
You are given a string S consisting of digits between 1
and 9
, inclusive.
You will insert at most K commas (,
) into this string to separate it into multiple numbers.
Your task is to minimize the maximum number among those produced by inserting commas. Find minimum possible such value.
Constraints
- 0 ≦ K < |S| ≦ 100,000
- S consists of digits between
1
and9
, inclusive.
Partial Scores
- In the test set worth 100 points, |S| ≦ 2.
- In the test set worth another 100 points, |S| ≦ 16.
- In the test set worth another 200 points, |S| ≦ 100.
- In the test set worth another 200 points, |S| ≦ 2,000.
Input
The input is given from Standard Input in the following format:
K S
Output
Print the minimum possible value.
Sample Input 1
2 15267315
Sample Output 1
315
When the string is separated into 152, 67 and 315, the maximum among these is 315, which is the minimum possible value.
Sample Input 2
0 12456174517653111
Sample Output 2
12456174517653111
12456174517653111 itself is the answer.
Sample Input 3
8 127356176351764127645176543176531763517635176531278461856198765816581726586715987216581
Sample Output 3
5317635176