(cache)Submission #67858398 - Mirrativ Programming Contest 2025 (AtCoder Beginner Contest 414)

Contest Duration: 2025-07-12(Sat) 21:00 - 2025-07-12(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #67858398

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
#include <stdio.h>
#include <inttypes.h>
const uint64_t tables[10][100] = {
  { /* 0 */
    0
  }, { /* 1 */
    0
  }, { /* 2 */
    UINT64_C(1),
    UINT64_C(3),
    UINT64_C(5),
    UINT64_C(7),
    UINT64_C(9),
    UINT64_C(33),
    UINT64_C(99),
    UINT64_C(313),
    UINT64_C(585),
    UINT64_C(717),
    UINT64_C(7447),
    UINT64_C(9009),
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

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

int main(void) {
	int A;
	uint64_t N;
	uint64_t ans = 0;
	int i;
	if (scanf("%d", &A) != 1) return 1;
	if (scanf("%" SCNu64, &N) != 1) return 1;
	for (i = 0; tables[A][i] <= N; i++) {
		ans += tables[A][i];
	}
	printf("%" PRIu64 "\n", ans);
	return 0;
}

/*

出力例1 の
1,2,3,4,5,6,7,9,121,292,333,373,414,585
をOEISに突っ込む → https://oeis.org/A029804 (Numbers that are palindromic in bases 8 and 10.)
CROSSREFS で 2～7進数と9進数版が載ってる
https://oeis.org/A007632
https://oeis.org/A007633
https://oeis.org/A029961
https://oeis.org/A029962
https://oeis.org/A029963
https://oeis.org/A029964
https://oeis.org/A029965

それぞれ Table of n, a(n) を開いて、
0超、最初に13桁になる項までを持ってきて、CyberChef で加工
https://gchq.github.io/CyberChef/#recipe=Find_/_Replace%28%7B%27option%27:%27Regex%27,%27string%27:%27%20%2A%5C%5Cd%2B%20%2B%28%5C%5Cd%2B%29%27%7D,%27%5C%5Ct%5C%5CtUINT64_C%28$1%29,%27,true,false,true,false%29

*/

Submission Info

Submission Time	2025-07-24 03:08:09
Task	C - Palindromic in Both Bases
User	mikecat
Language	C (gcc 12.2.0)
Score	350
Code Size	8610 Byte
Status	AC
Exec Time	1 ms
Memory	1744 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

350 / 350

Status

× 3

× 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	0 ms	1624 KiB
00-sample-02.txt	AC	0 ms	1744 KiB
00-sample-03.txt	AC	0 ms	1640 KiB
01-01.txt	AC	1 ms	1628 KiB
01-02.txt	AC	0 ms	1620 KiB
01-03.txt	AC	0 ms	1744 KiB
01-04.txt	AC	0 ms	1596 KiB
01-05.txt	AC	0 ms	1624 KiB
01-06.txt	AC	0 ms	1624 KiB
01-07.txt	AC	0 ms	1724 KiB
01-08.txt	AC	0 ms	1596 KiB
01-09.txt	AC	0 ms	1740 KiB
01-10.txt	AC	0 ms	1620 KiB
01-11.txt	AC	0 ms	1728 KiB
01-12.txt	AC	0 ms	1728 KiB
01-13.txt	AC	1 ms	1612 KiB
01-14.txt	AC	0 ms	1624 KiB
01-15.txt	AC	0 ms	1628 KiB
01-16.txt	AC	0 ms	1732 KiB
01-17.txt	AC	0 ms	1620 KiB
01-18.txt	AC	0 ms	1624 KiB
01-19.txt	AC	0 ms	1620 KiB
01-20.txt	AC	0 ms	1632 KiB
01-21.txt	AC	1 ms	1704 KiB
01-22.txt	AC	1 ms	1620 KiB
01-23.txt	AC	0 ms	1732 KiB
01-24.txt	AC	0 ms	1624 KiB
01-25.txt	AC	0 ms	1572 KiB
01-26.txt	AC	0 ms	1648 KiB
01-27.txt	AC	0 ms	1608 KiB
01-28.txt	AC	0 ms	1708 KiB
01-29.txt	AC	0 ms	1728 KiB
01-30.txt	AC	0 ms	1624 KiB