CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1003624

Source codeソースコード

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

Submission

Task問題 B - 数字列をカンマで分ける問題 / Problem where Commas Separate Digits
User nameユーザ名 tjake
Created time投稿日時
Language言語 Python2 (2.7.6)
Status状態 AC
Score得点 1000
Source lengthソースコード長 878 Byte
File nameファイル名
Exec time実行時間 1070 ms
Memory usageメモリ使用量 2948 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask_02_ex1.txt,subtask_03_ex2.txt,subtask_03_ex3.txt
Dataset1 100 / 100 subtask_01_01.txt,subtask_01_02.txt,subtask_01_03.txt,subtask_01_04.txt,subtask_01_05.txt,subtask_01_06.txt,subtask_01_07.txt,subtask_01_08.txt,subtask_01_09.txt,subtask_01_10.txt,subtask_01_11.txt,subtask_01_12.txt,subtask_01_13.txt,subtask_01_14.txt,subtask_01_15.txt,subtask_01_16.txt,subtask_01_17.txt
Dataset2 100 / 100 subtask_01_01.txt,subtask_01_02.txt,subtask_01_03.txt,subtask_01_04.txt,subtask_01_05.txt,subtask_01_06.txt,subtask_01_07.txt,subtask_01_08.txt,subtask_01_09.txt,subtask_01_10.txt,subtask_01_11.txt,subtask_01_12.txt,subtask_01_13.txt,subtask_01_14.txt,subtask_01_15.txt,subtask_01_16.txt,subtask_01_17.txt,subtask_02_01.txt,subtask_02_02.txt,subtask_02_03.txt,subtask_02_04.txt,subtask_02_05.txt,subtask_02_06.txt,subtask_02_07.txt,subtask_02_08.txt,subtask_02_09.txt,subtask_02_10.txt,subtask_02_11.txt,subtask_02_12.txt,subtask_02_13.txt,subtask_02_14.txt,subtask_02_ex1.txt
Dataset3 200 / 200 subtask_01_01.txt,subtask_01_02.txt,subtask_01_03.txt,subtask_01_04.txt,subtask_01_05.txt,subtask_01_06.txt,subtask_01_07.txt,subtask_01_08.txt,subtask_01_09.txt,subtask_01_10.txt,subtask_01_11.txt,subtask_01_12.txt,subtask_01_13.txt,subtask_01_14.txt,subtask_01_15.txt,subtask_01_16.txt,subtask_01_17.txt,subtask_02_01.txt,subtask_02_02.txt,subtask_02_03.txt,subtask_02_04.txt,subtask_02_05.txt,subtask_02_06.txt,subtask_02_07.txt,subtask_02_08.txt,subtask_02_09.txt,subtask_02_10.txt,subtask_02_11.txt,subtask_02_12.txt,subtask_02_13.txt,subtask_02_14.txt,subtask_02_ex1.txt,subtask_03_01.txt,subtask_03_02.txt,subtask_03_03.txt,subtask_03_04.txt,subtask_03_05.txt,subtask_03_06.txt,subtask_03_07.txt,subtask_03_08.txt,subtask_03_09.txt,subtask_03_10.txt,subtask_03_11.txt,subtask_03_12.txt,subtask_03_13.txt,subtask_03_14.txt,subtask_03_15.txt,subtask_03_ex2.txt,subtask_03_ex3.txt
Dataset4 200 / 200 subtask_01_01.txt,subtask_01_02.txt,subtask_01_03.txt,subtask_01_04.txt,subtask_01_05.txt,subtask_01_06.txt,subtask_01_07.txt,subtask_01_08.txt,subtask_01_09.txt,subtask_01_10.txt,subtask_01_11.txt,subtask_01_12.txt,subtask_01_13.txt,subtask_01_14.txt,subtask_01_15.txt,subtask_01_16.txt,subtask_01_17.txt,subtask_02_01.txt,subtask_02_02.txt,subtask_02_03.txt,subtask_02_04.txt,subtask_02_05.txt,subtask_02_06.txt,subtask_02_07.txt,subtask_02_08.txt,subtask_02_09.txt,subtask_02_10.txt,subtask_02_11.txt,subtask_02_12.txt,subtask_02_13.txt,subtask_02_14.txt,subtask_02_ex1.txt,subtask_03_01.txt,subtask_03_02.txt,subtask_03_03.txt,subtask_03_04.txt,subtask_03_05.txt,subtask_03_06.txt,subtask_03_07.txt,subtask_03_08.txt,subtask_03_09.txt,subtask_03_10.txt,subtask_03_11.txt,subtask_03_12.txt,subtask_03_13.txt,subtask_03_14.txt,subtask_03_15.txt,subtask_03_ex2.txt,subtask_03_ex3.txt,subtask_04_01.txt,subtask_04_02.txt,subtask_04_03.txt,subtask_04_04.txt,subtask_04_05.txt,subtask_04_06.txt,subtask_04_07.txt,subtask_04_08.txt,subtask_04_09.txt,subtask_04_10.txt,subtask_04_11.txt,subtask_04_12.txt,subtask_04_13.txt,subtask_04_14.txt,subtask_04_15.txt
Dataset5 400 / 400 subtask_01_01.txt,subtask_01_02.txt,subtask_01_03.txt,subtask_01_04.txt,subtask_01_05.txt,subtask_01_06.txt,subtask_01_07.txt,subtask_01_08.txt,subtask_01_09.txt,subtask_01_10.txt,subtask_01_11.txt,subtask_01_12.txt,subtask_01_13.txt,subtask_01_14.txt,subtask_01_15.txt,subtask_01_16.txt,subtask_01_17.txt,subtask_02_01.txt,subtask_02_02.txt,subtask_02_03.txt,subtask_02_04.txt,subtask_02_05.txt,subtask_02_06.txt,subtask_02_07.txt,subtask_02_08.txt,subtask_02_09.txt,subtask_02_10.txt,subtask_02_11.txt,subtask_02_12.txt,subtask_02_13.txt,subtask_02_14.txt,subtask_02_ex1.txt,subtask_03_01.txt,subtask_03_02.txt,subtask_03_03.txt,subtask_03_04.txt,subtask_03_05.txt,subtask_03_06.txt,subtask_03_07.txt,subtask_03_08.txt,subtask_03_09.txt,subtask_03_10.txt,subtask_03_11.txt,subtask_03_12.txt,subtask_03_13.txt,subtask_03_14.txt,subtask_03_15.txt,subtask_03_ex2.txt,subtask_03_ex3.txt,subtask_04_01.txt,subtask_04_02.txt,subtask_04_03.txt,subtask_04_04.txt,subtask_04_05.txt,subtask_04_06.txt,subtask_04_07.txt,subtask_04_08.txt,subtask_04_09.txt,subtask_04_10.txt,subtask_04_11.txt,subtask_04_12.txt,subtask_04_13.txt,subtask_04_14.txt,subtask_04_15.txt,subtask_05_01.txt,subtask_05_02.txt,subtask_05_03.txt,subtask_05_04.txt,subtask_05_05.txt,subtask_05_06.txt,subtask_05_07.txt,subtask_05_08.txt,subtask_05_09.txt,subtask_05_10.txt,subtask_05_11.txt,subtask_05_12.txt,subtask_05_13.txt,subtask_05_14.txt,subtask_05_15.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 17 ms 2696 KB
subtask_01_02.txt AC 17 ms 2696 KB
subtask_01_03.txt AC 17 ms 2696 KB
subtask_01_04.txt AC 17 ms 2696 KB
subtask_01_05.txt AC 17 ms 2696 KB
subtask_01_06.txt AC 17 ms 2696 KB
subtask_01_07.txt AC 17 ms 2696 KB
subtask_01_08.txt AC 17 ms 2696 KB
subtask_01_09.txt AC 17 ms 2696 KB
subtask_01_10.txt AC 17 ms 2696 KB
subtask_01_11.txt AC 16 ms 2696 KB
subtask_01_12.txt AC 17 ms 2696 KB
subtask_01_13.txt AC 17 ms 2696 KB
subtask_01_14.txt AC 17 ms 2696 KB
subtask_01_15.txt AC 17 ms 2696 KB
subtask_01_16.txt AC 17 ms 2696 KB
subtask_01_17.txt AC 17 ms 2696 KB
subtask_02_01.txt AC 17 ms 2696 KB
subtask_02_02.txt AC 17 ms 2696 KB
subtask_02_03.txt AC 17 ms 2696 KB
subtask_02_04.txt AC 17 ms 2696 KB
subtask_02_05.txt AC 17 ms 2696 KB
subtask_02_06.txt AC 17 ms 2696 KB
subtask_02_07.txt AC 17 ms 2696 KB
subtask_02_08.txt AC 17 ms 2696 KB
subtask_02_09.txt AC 17 ms 2696 KB
subtask_02_10.txt AC 18 ms 2696 KB
subtask_02_11.txt AC 17 ms 2696 KB
subtask_02_12.txt AC 18 ms 2696 KB
subtask_02_13.txt AC 18 ms 2696 KB
subtask_02_14.txt AC 17 ms 2696 KB
subtask_02_ex1.txt AC 17 ms 2696 KB
subtask_03_01.txt AC 18 ms 2696 KB
subtask_03_02.txt AC 17 ms 2696 KB
subtask_03_03.txt AC 17 ms 2696 KB
subtask_03_04.txt AC 17 ms 2696 KB
subtask_03_05.txt AC 18 ms 2696 KB
subtask_03_06.txt AC 18 ms 2696 KB
subtask_03_07.txt AC 17 ms 2696 KB
subtask_03_08.txt AC 18 ms 2696 KB
subtask_03_09.txt AC 17 ms 2696 KB
subtask_03_10.txt AC 18 ms 2696 KB
subtask_03_11.txt AC 17 ms 2696 KB
subtask_03_12.txt AC 18 ms 2696 KB
subtask_03_13.txt AC 16 ms 2824 KB
subtask_03_14.txt AC 18 ms 2696 KB
subtask_03_15.txt AC 16 ms 2696 KB
subtask_03_ex2.txt AC 17 ms 2696 KB
subtask_03_ex3.txt AC 18 ms 2696 KB
subtask_04_01.txt AC 29 ms 2696 KB
subtask_04_02.txt AC 33 ms 2696 KB
subtask_04_03.txt AC 18 ms 2696 KB
subtask_04_04.txt AC 17 ms 2696 KB
subtask_04_05.txt AC 27 ms 2696 KB
subtask_04_06.txt AC 17 ms 2696 KB
subtask_04_07.txt AC 16 ms 2696 KB
subtask_04_08.txt AC 17 ms 2696 KB
subtask_04_09.txt AC 17 ms 2696 KB
subtask_04_10.txt AC 30 ms 2696 KB
subtask_04_11.txt AC 29 ms 2696 KB
subtask_04_12.txt AC 30 ms 2696 KB
subtask_04_13.txt AC 38 ms 2696 KB
subtask_04_14.txt AC 19 ms 2696 KB
subtask_04_15.txt AC 23 ms 2696 KB
subtask_05_01.txt AC 543 ms 2820 KB
subtask_05_02.txt AC 578 ms 2820 KB
subtask_05_03.txt AC 55 ms 2820 KB
subtask_05_04.txt AC 37 ms 2820 KB
subtask_05_05.txt AC 527 ms 2820 KB
subtask_05_06.txt AC 27 ms 2820 KB
subtask_05_07.txt AC 26 ms 2820 KB
subtask_05_08.txt AC 82 ms 2948 KB
subtask_05_09.txt AC 18 ms 2820 KB
subtask_05_10.txt AC 635 ms 2820 KB
subtask_05_11.txt AC 651 ms 2820 KB
subtask_05_12.txt AC 678 ms 2820 KB
subtask_05_13.txt AC 865 ms 2696 KB
subtask_05_14.txt AC 1070 ms 2820 KB
subtask_05_15.txt AC 321 ms 2696 KB