Submission #67530366

Source Code Expand

import itertools

def read():
    return int(input())

def reads():
    return [int(s) for s in input().split()]


def str_base(n, b):
    ret = ''
    while n > 0:
        ret += str(n % b)
        n //= b
    return ret


def is_palin(n, b):
    s = str_base(n, b)
    return s == s[::-1]


def gen(n, b):
    ret = []
    for i in itertools.count(1):
        x = str(i)
        u, v = int(x + x[::-1]), int(x[:-1] + x[::-1])
        if u > n and v > n:
            break
        if u <= n and is_palin(u, b):
            ret.append(u)
        if v <= n and is_palin(v, b):
            ret.append(v)
    return ret

SOLUTION = {2: [1, 33, 3, 5, 7, 99, 9, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 585585, 73737, 13500531, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485, 1290880921, 719848917, 7451111547, 910373019, 939474939, 10050905001, 110948849011, 136525525631, 18462126481, 32479297423, 75015151057], 3: [1, 2, 4, 8, 121, 151, 212, 242, 484, 656, 757, 29092, 48884, 74647, 75457, 76267, 848848, 92929, 93739, 1521251, 27711772, 2985892, 4022204, 4219124, 4251524, 4287824, 5737375, 7875787, 7949497, 83155138, 112969211, 123464321, 211131112, 239060932, 2518338152, 387505783, 520080025, 885626588, 58049094085, 81234543218], 4: [1, 2, 3, 55, 5, 373, 393, 666, 787, 7997, 939, 506605, 53235, 55255, 55655, 57675, 1801081, 2215122, 3826283, 3866683, 5051505, 5226225, 5259525, 5297925, 53822835, 5614165, 5679765, 623010326, 954656459, 506802208605, 508152251805, 51717171715, 53406060435, 59201610295, 73979697937], 5: [1, 2, 3, 4, 6, 88, 1221, 252, 282, 626, 676, 15751, 18881, 10088001, 10400401, 27711772, 30322303, 47633674, 65977956, 2512882152, 2596886952, 2893553982, 6761551676, 808656808, 831333138, 831868138, 836131638, 836181638, 12114741121, 12185058121], 6: [1, 2, 3, 4, 55, 5, 7, 111, 1441, 141, 191, 343, 434, 7667, 7777, 777, 868, 168861, 22022, 39893, 74647, 808808, 909909, 15266251, 1867681, 24466442, 3097903, 4232324, 4265624, 4298924, 4516154, 4565654, 4598954, 4849484, 5100015, 5182815, 5400045, 5433345, 5482845, 5733375, 5766675, 5799975, 6901096, 6934396, 6983896, 8164618, 9081809, 103656301, 104888401, 108151801, 290222092, 310393013, 342050243, 3733113373, 4368778634, 7111881117, 7786556877, 8801331088, 11271517211, 12482428421, 18013531081, 61662426616, 71771717717, 75535653557], 7: [1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 61255216, 6597956, 6958596, 9470749, 230474032, 466828664, 485494584, 638828836, 657494756, 858474858, 25699499652, 40130703104, 426970079624, 45862226854, 61454945416, 64454545446, 65796069756, 75016161057, 75431213457, 775350053577, 90750705709, 91023932019, 95365056359], 8: [1, 2, 3, 4, 5, 6, 7, 9, 121, 292, 333, 3663, 373, 414, 585, 8778, 13131, 13331, 207702, 26462, 26662, 30103, 30303, 628826, 660066, 1496941, 1935391, 1970791, 4198914, 55366355, 130535031, 1820330281, 2464554642, 4424994244, 4480880844, 4637337364, 532898235, 719848917, 799535997, 20855555802, 294378873492, 390894498093, 94029892049, 94466666449], 9: [1, 2, 3, 4, 5, 6, 7, 8, 191, 282, 373, 464, 555, 646, 656, 6886, 25752, 27472, 42324, 50605, 626626, 1540451, 1713171, 1721271, 1828281, 1877781, 1885881, 2401042, 2434342, 2442442, 2450542, 3106013, 3114113, 3122213, 3163613, 3171713, 3303033, 3360633, 65666656, 167191761, 181434181, 232000232, 382000283, 5435665345, 8901111098, 9565335659, 827362263728]}

def solve():
    a = read()
    n = read()
    print(sum(num for num in SOLUTION[a] if num <= n))


if __name__ == '__main__':
    # print({b: gen(10**12, b) for b in range(2, 10)})
    solve()

Submission Info

Submission Time
Task C - Palindromic in Both Bases
User prabowo
Language Python (PyPy 3.10-v7.3.12)
Score 350
Code Size 3672 Byte
Status AC
Exec Time 58 ms
Memory 76652 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 350 / 350
Status
AC × 3
AC × 33
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 58 ms 76584 KiB
00-sample-02.txt AC 58 ms 76296 KiB
00-sample-03.txt AC 58 ms 76440 KiB
01-01.txt AC 58 ms 76576 KiB
01-02.txt AC 57 ms 76616 KiB
01-03.txt AC 57 ms 76496 KiB
01-04.txt AC 58 ms 76428 KiB
01-05.txt AC 57 ms 76596 KiB
01-06.txt AC 57 ms 76416 KiB
01-07.txt AC 58 ms 76560 KiB
01-08.txt AC 57 ms 76472 KiB
01-09.txt AC 57 ms 76288 KiB
01-10.txt AC 56 ms 76476 KiB
01-11.txt AC 56 ms 76572 KiB
01-12.txt AC 57 ms 76212 KiB
01-13.txt AC 56 ms 76432 KiB
01-14.txt AC 57 ms 76500 KiB
01-15.txt AC 57 ms 76572 KiB
01-16.txt AC 57 ms 76444 KiB
01-17.txt AC 57 ms 76296 KiB
01-18.txt AC 56 ms 76448 KiB
01-19.txt AC 57 ms 76640 KiB
01-20.txt AC 57 ms 76652 KiB
01-21.txt AC 56 ms 76412 KiB
01-22.txt AC 56 ms 76440 KiB
01-23.txt AC 57 ms 76380 KiB
01-24.txt AC 57 ms 76360 KiB
01-25.txt AC 57 ms 76544 KiB
01-26.txt AC 57 ms 76648 KiB
01-27.txt AC 57 ms 76424 KiB
01-28.txt AC 57 ms 76404 KiB
01-29.txt AC 58 ms 76280 KiB
01-30.txt AC 56 ms 76540 KiB