Contest Duration: - (local time) (120 minutes) Back to Home

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 2019-10-31 21:21:44+0900 C - 擬二等辺三角形 maspy Python (3.4.3) 100 1138 Byte AC 209 ms 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