Problem:
 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 and 9 , 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

Solution (Python):
k = input()
s = raw_input()

if k==0:
    print s
    exit(0)
if len(s) % (k+1) == 0:
    p = len(s) / (k+1)
    print max(int(s[i:i+p]) for i in xrange(0,len(s),p))
    exit(0)

l = len(s) / (k+1)
r = (len(s)+k) / (k+1)
left = (10**l-1)/9
right = 10**r
while right-left > 1:
    mid = (left + right) / 2
    cnt = 0
    mid_c = str(mid)
    cp = idx = 0
    for c in s:
        if not cp and idx < len(mid_c) and c != mid_c[idx]:
            cp = 1 if c > mid_c[idx] else -1
        idx += 1
        if (idx == len(mid_c) and cp == 1) or idx > len(mid_c):
            cnt += 1
            idx = 1; cp = 0
            if int(c) > mid:
                cnt = 100003
                break
            if c != mid_c[0]:
                cp = 1 if c > mid_c[0] else -1
    if cnt > k:
        left = mid
    else:
        right = mid
print left+1

Solution (Python):
k = input()
s = raw_input()

if k==0:
    print s
    exit(0)
if len(s) % (k+1) == 0:
    p = len(s) / (k+1)
    print max(int(s[i:i+p]) for i in xrange(0,len(s),p))
    exit(0)

l = len(s) / (k+1)
r = (len(s)+k) / (k+1)
left = 10**(l-1)
right = 10**r
while 1:
    mid = (left + right) / 2
    cnt = 0
    now = ""
    mid_c = str(mid)
    cp = idx = 0
    for c in s:
        now += c
        if not cp and idx < len(mid_c) and c != mid_c[idx]:
            cp = 1 if c > mid_c[idx] else -1
        idx += 1
        if (idx == len(mid_c) and cp == 1) or idx > len(mid_c):
            cnt += 1
            idx = 1; cp = 0
            if int(c) > mid:
                cnt = 100003
                break
            now = c
            if c != mid_c[0]:
                cp = 1 if c > mid_c[0] else -1
    if cnt > k:
        if left == mid:
            break
        left = mid
    else:
        if right == mid:
            break
        right = mid
print left+1