Submission #8229129


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・どうせ、十分先では適切な周期で3次関数
・小さい方を調べると、12個おきに見ると3次関数であることが分かる
"""

MOD = 10**9 + 7

L = int(readline())

def naive_solution(L):
    cnt = 0
    for a in range(1,L):
        for b in range(a+1,L):
            for c in range(b+1,L):
                if b-a != 1 and c-b != 1:
                    continue
                if a+b <= c:
                    break
                if a+b+c > L:
                    break
                cnt += 1
    return cnt

A = [naive_solution(L) for L in range(100)]

if L < 100:
    answer = A[L]
else:
    x = 99
    while (L-x)%12:
        x -= 1
    x -= 36
    n = (L-x)//12
    a,b,c,d = A[x:x+37:12]
    """
    f(0)=a,f(1)=b,f(2)=c,f(3)=d,f(n)=answer 
    """
    answer = a*(n-1)*(n-2)*(n-3)//(-6)
    answer += b*(n-0)*(n-2)*(n-3)//2
    answer += c*(n-0)*(n-1)*(n-3)//(-2)
    answer += d*(n-0)*(n-1)*(n-2)//6
answer %= MOD
print(answer)

Submission Info

Submission Time
Task C - 擬二等辺三角形
User maspy
Language Python (3.4.3)
Score 100
Code Size 1138 Byte
Status AC
Exec Time 209 ms
Memory 3064 KB

Judge Result

Set Name small All
Score / Max Score 25 / 25 75 / 75
Status
AC × 61
AC × 83
Set Name Test Cases
small 00_sample_1.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 20_subtask_00.txt, 20_subtask_01.txt, 20_subtask_02.txt, 20_subtask_03.txt, 20_subtask_04.txt, 20_subtask_05.txt, 20_subtask_06.txt, 20_subtask_07.txt, 20_subtask_08.txt, 20_subtask_09.txt, 20_subtask_10.txt, 20_subtask_11.txt, 20_subtask_12.txt, 20_subtask_13.txt, 20_subtask_14.txt, 20_subtask_15.txt, 20_subtask_16.txt, 20_subtask_17.txt, 20_subtask_18.txt, 20_subtask_19.txt, 20_subtask_20.txt, 20_subtask_21.txt, 20_subtask_22.txt, 20_subtask_23.txt, 20_subtask_24.txt, 20_subtask_25.txt, 20_subtask_26.txt, 20_subtask_27.txt, 20_subtask_28.txt, 20_subtask_29.txt, 20_subtask_30.txt, 20_subtask_31.txt, 20_subtask_32.txt, 20_subtask_33.txt, 20_subtask_34.txt, 20_subtask_35.txt, 20_subtask_36.txt, 20_subtask_37.txt, 20_subtask_38.txt, 20_subtask_39.txt
All 00_sample_1.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 20_subtask_00.txt, 20_subtask_01.txt, 20_subtask_02.txt, 20_subtask_03.txt, 20_subtask_04.txt, 20_subtask_05.txt, 20_subtask_06.txt, 20_subtask_07.txt, 20_subtask_08.txt, 20_subtask_09.txt, 20_subtask_10.txt, 20_subtask_11.txt, 20_subtask_12.txt, 20_subtask_13.txt, 20_subtask_14.txt, 20_subtask_15.txt, 20_subtask_16.txt, 20_subtask_17.txt, 20_subtask_18.txt, 20_subtask_19.txt, 20_subtask_20.txt, 20_subtask_21.txt, 20_subtask_22.txt, 20_subtask_23.txt, 20_subtask_24.txt, 20_subtask_25.txt, 20_subtask_26.txt, 20_subtask_27.txt, 20_subtask_28.txt, 20_subtask_29.txt, 20_subtask_30.txt, 20_subtask_31.txt, 20_subtask_32.txt, 20_subtask_33.txt, 20_subtask_34.txt, 20_subtask_35.txt, 20_subtask_36.txt, 20_subtask_37.txt, 20_subtask_38.txt, 20_subtask_39.txt, 30_large_00.txt, 30_large_01.txt, 30_large_02.txt, 30_large_03.txt, 30_large_04.txt, 30_large_05.txt, 30_large_06.txt, 30_large_07.txt, 30_large_08.txt, 30_large_09.txt, 30_large_10.txt, 30_large_11.txt, 30_large_12.txt, 30_large_13.txt, 30_large_14.txt, 30_large_15.txt, 30_large_16.txt, 30_large_17.txt, 30_large_18.txt, 30_large_19.txt, 50_maximum_1.txt, 80_sample_2.txt
Case Name Status Exec Time Memory
00_sample_1.txt AC 200 ms 3064 KB
10_small_00.txt AC 199 ms 3064 KB
10_small_01.txt AC 198 ms 3064 KB
10_small_02.txt AC 198 ms 3064 KB
10_small_03.txt AC 198 ms 3064 KB
10_small_04.txt AC 201 ms 3064 KB
10_small_05.txt AC 199 ms 3064 KB
10_small_06.txt AC 198 ms 3064 KB
10_small_07.txt AC 198 ms 3064 KB
10_small_08.txt AC 199 ms 3064 KB
10_small_09.txt AC 199 ms 3064 KB
10_small_10.txt AC 200 ms 3064 KB
10_small_11.txt AC 199 ms 3064 KB
10_small_12.txt AC 199 ms 3064 KB
10_small_13.txt AC 200 ms 3064 KB
10_small_14.txt AC 199 ms 3064 KB
10_small_15.txt AC 199 ms 3064 KB
10_small_16.txt AC 198 ms 3064 KB
10_small_17.txt AC 200 ms 3064 KB
10_small_18.txt AC 200 ms 3064 KB
10_small_19.txt AC 199 ms 3064 KB
20_subtask_00.txt AC 199 ms 3064 KB
20_subtask_01.txt AC 199 ms 3064 KB
20_subtask_02.txt AC 199 ms 3064 KB
20_subtask_03.txt AC 200 ms 3064 KB
20_subtask_04.txt AC 200 ms 3064 KB
20_subtask_05.txt AC 198 ms 3064 KB
20_subtask_06.txt AC 199 ms 3064 KB
20_subtask_07.txt AC 200 ms 3064 KB
20_subtask_08.txt AC 198 ms 3064 KB
20_subtask_09.txt AC 200 ms 3064 KB
20_subtask_10.txt AC 199 ms 3064 KB
20_subtask_11.txt AC 199 ms 3064 KB
20_subtask_12.txt AC 200 ms 3064 KB
20_subtask_13.txt AC 199 ms 3064 KB
20_subtask_14.txt AC 199 ms 3064 KB
20_subtask_15.txt AC 200 ms 3064 KB
20_subtask_16.txt AC 198 ms 3064 KB
20_subtask_17.txt AC 199 ms 3064 KB
20_subtask_18.txt AC 198 ms 3064 KB
20_subtask_19.txt AC 198 ms 3064 KB
20_subtask_20.txt AC 204 ms 3064 KB
20_subtask_21.txt AC 209 ms 3064 KB
20_subtask_22.txt AC 208 ms 3064 KB
20_subtask_23.txt AC 208 ms 3064 KB
20_subtask_24.txt AC 208 ms 3064 KB
20_subtask_25.txt AC 208 ms 3064 KB
20_subtask_26.txt AC 209 ms 3064 KB
20_subtask_27.txt AC 201 ms 3064 KB
20_subtask_28.txt AC 202 ms 3064 KB
20_subtask_29.txt AC 199 ms 3064 KB
20_subtask_30.txt AC 199 ms 3064 KB
20_subtask_31.txt AC 199 ms 3064 KB
20_subtask_32.txt AC 199 ms 3064 KB
20_subtask_33.txt AC 199 ms 3064 KB
20_subtask_34.txt AC 198 ms 3064 KB
20_subtask_35.txt AC 199 ms 3064 KB
20_subtask_36.txt AC 198 ms 3064 KB
20_subtask_37.txt AC 201 ms 3064 KB
20_subtask_38.txt AC 199 ms 3064 KB
20_subtask_39.txt AC 199 ms 3064 KB
30_large_00.txt AC 198 ms 3064 KB
30_large_01.txt AC 200 ms 3064 KB
30_large_02.txt AC 199 ms 3064 KB
30_large_03.txt AC 200 ms 3064 KB
30_large_04.txt AC 199 ms 3064 KB
30_large_05.txt AC 201 ms 3064 KB
30_large_06.txt AC 200 ms 3064 KB
30_large_07.txt AC 202 ms 3064 KB
30_large_08.txt AC 198 ms 3064 KB
30_large_09.txt AC 199 ms 3064 KB
30_large_10.txt AC 202 ms 3064 KB
30_large_11.txt AC 200 ms 3064 KB
30_large_12.txt AC 199 ms 3064 KB
30_large_13.txt AC 201 ms 3064 KB
30_large_14.txt AC 198 ms 3064 KB
30_large_15.txt AC 198 ms 3064 KB
30_large_16.txt AC 199 ms 3064 KB
30_large_17.txt AC 199 ms 3064 KB
30_large_18.txt AC 198 ms 3064 KB
30_large_19.txt AC 202 ms 3064 KB
50_maximum_1.txt AC 200 ms 3064 KB
80_sample_2.txt AC 198 ms 3064 KB