(cache)Submission #65284747 - AtCoder Beginner Contest 403

Contest Duration: 2025-04-27(Sun) 21:00 - 2025-04-27(Sun) 22:40 (local time) (100 minutes) Back to Home

Submission #65284747

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solve(N):
    dp=[""]*(N+1)
    dp[1]="1"
    for n in range(2,N+1):
        bst=None
        # 111
        s=str(n)
        if all(ch=="1" for ch in s):
            bst=s
        # tasi
        for a in range(1,n//2+1):
            b=n-a
            cand=dp[a]+"+"+dp[b]
            if bst is None or len(cand)<len(bst):
                bst = cand
                
        #kake
        for a in range(2,int(n**0.5)+1):
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def solve(N):
    dp=[""]*(N+1)
    dp[1]="1"

    for n in range(2,N+1):
        bst=None

        # 111
        s=str(n)
        if all(ch=="1" for ch in s):
            bst=s

        # tasi
        for a in range(1,n//2+1):
            b=n-a
            cand=dp[a]+"+"+dp[b]
            if bst is None or len(cand)<len(bst):
                bst = cand
                
        #kake
        for a in range(2,int(n**0.5)+1):
            if n%a==0:
                b=n//a
                cand=f"({dp[a]})*({dp[b]})"
                if bst is None or len(cand)<len(bst):
                    bst=cand

        dp[n]=bst

    return dp[N]

N=int(input())
print(solve(N))

Submission Info

Submission Time	2025-04-27 22:27:26
Task	F - Shortest One Formula
User	kotafuku
Language	Python (PyPy 3.10-v7.3.12)
Score	0
Code Size	703 Byte
Status	WA
Exec Time	92 ms
Memory	83416 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 500

Status

× 3

AC	× 37
WA	× 17

Set Name	Test Cases
Sample	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 01_test_36.txt, 01_test_37.txt, 01_test_38.txt, 01_test_39.txt, 01_test_40.txt, 01_test_41.txt, 01_test_42.txt, 01_test_43.txt, 01_test_44.txt, 01_test_45.txt, 01_test_46.txt, 01_test_47.txt, 01_test_48.txt, 01_test_49.txt, 01_test_50.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	56 ms	76444 KiB
00_sample_01.txt	AC	56 ms	76836 KiB
00_sample_02.txt	AC	65 ms	81968 KiB
01_test_00.txt	AC	57 ms	76464 KiB
01_test_01.txt	AC	57 ms	76624 KiB
01_test_02.txt	AC	90 ms	82844 KiB
01_test_03.txt	AC	89 ms	83180 KiB
01_test_04.txt	WA	89 ms	83020 KiB
01_test_05.txt	WA	90 ms	82984 KiB
01_test_06.txt	AC	89 ms	83248 KiB
01_test_07.txt	AC	89 ms	83300 KiB
01_test_08.txt	WA	90 ms	83260 KiB
01_test_09.txt	WA	88 ms	83268 KiB
01_test_10.txt	WA	89 ms	83268 KiB
01_test_11.txt	WA	89 ms	83172 KiB
01_test_12.txt	AC	88 ms	82992 KiB
01_test_13.txt	AC	71 ms	82168 KiB
01_test_14.txt	AC	77 ms	82984 KiB
01_test_15.txt	WA	75 ms	82824 KiB
01_test_16.txt	AC	68 ms	82112 KiB
01_test_17.txt	AC	75 ms	83072 KiB
01_test_18.txt	AC	70 ms	82152 KiB
01_test_19.txt	AC	59 ms	81032 KiB
01_test_20.txt	AC	70 ms	81848 KiB
01_test_21.txt	AC	64 ms	81892 KiB
01_test_22.txt	WA	74 ms	82728 KiB
01_test_23.txt	WA	70 ms	81824 KiB
01_test_24.txt	AC	63 ms	81568 KiB
01_test_25.txt	AC	80 ms	83104 KiB
01_test_26.txt	AC	81 ms	83348 KiB
01_test_27.txt	AC	70 ms	82376 KiB
01_test_28.txt	AC	82 ms	83224 KiB
01_test_29.txt	AC	70 ms	81936 KiB
01_test_30.txt	WA	84 ms	83416 KiB
01_test_31.txt	AC	65 ms	81888 KiB
01_test_32.txt	AC	82 ms	83164 KiB
01_test_33.txt	AC	92 ms	83176 KiB
01_test_34.txt	WA	86 ms	83400 KiB
01_test_35.txt	WA	88 ms	82872 KiB
01_test_36.txt	AC	88 ms	83344 KiB
01_test_37.txt	WA	89 ms	82964 KiB
01_test_38.txt	WA	89 ms	83248 KiB
01_test_39.txt	WA	90 ms	82944 KiB
01_test_40.txt	WA	90 ms	83184 KiB
01_test_41.txt	WA	90 ms	82976 KiB
01_test_42.txt	AC	89 ms	83192 KiB
01_test_43.txt	AC	75 ms	83124 KiB
01_test_44.txt	AC	62 ms	80788 KiB
01_test_45.txt	AC	76 ms	83132 KiB
01_test_46.txt	AC	77 ms	83024 KiB
01_test_47.txt	AC	86 ms	83068 KiB
01_test_48.txt	AC	83 ms	83136 KiB
01_test_49.txt	AC	86 ms	83228 KiB
01_test_50.txt	AC	89 ms	82860 KiB