(cache)Submission #76210913 - AtCoder Beginner Contest 451

Contest Duration: 2026-03-28(Sat) 21:00 - 2026-03-28(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #76210913

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <string.h>
int llen;
char limit[16];
int gen;
int memo[16][2][2][2];
int memo_gen[16][2][2][2];
int calc(int pos, int sati, int canskip, int is16) {
  int ans = 0;
  int i;
  if (pos >= llen) return !canskip;
  if (memo_gen[pos][sati][canskip][is16] == gen) return memo[pos][sati][canskip][is16];
  if (canskip) ans += calc(pos + 1, 0, canskip, 0);
  for (i = 0; i < 31; i++) {
    int v = 1 << i;
    char delta[16];
    int vlen;
    if (v == 128 || (is16 && v == 4)) continue;
    vlen = snprintf(delta, sizeof(delta), "%d", v);
    if (pos + vlen <= llen) {
      int cres = sati ? strncmp(limit + pos, delta, vlen) : 0;
      if (!sati || cres >= 0) {
        ans += calc(pos + vlen, sati && cres == 0, 0, v == 16);
      }
    }
  }
  memo[pos][sati][canskip][is16] = ans;
  memo_gen[pos][sati][canskip][is16] = gen;
  return ans;
}
int main(void) {
  int N;
  int no = 0, yes = 1010101010;
  if (scanf("%d", &N) != 1) return 1;
  while (no + 1 < yes) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <string.h>

int llen;
char limit[16];

int gen;
int memo[16][2][2][2];
int memo_gen[16][2][2][2];

int calc(int pos, int sati, int canskip, int is16) {
	int ans = 0;
	int i;
	if (pos >= llen) return !canskip;
	if (memo_gen[pos][sati][canskip][is16] == gen) return memo[pos][sati][canskip][is16];

	if (canskip) ans += calc(pos + 1, 0, canskip, 0);
	for (i = 0; i < 31; i++) {
		int v = 1 << i;
		char delta[16];
		int vlen;
		if (v == 128 || (is16 && v == 4)) continue;
		vlen = snprintf(delta, sizeof(delta), "%d", v);
		if (pos + vlen <= llen) {
			int cres = sati ? strncmp(limit + pos, delta, vlen) : 0;
			if (!sati || cres >= 0) {
				ans += calc(pos + vlen, sati && cres == 0, 0, v == 16);
			}
		}
	}

	memo[pos][sati][canskip][is16] = ans;
	memo_gen[pos][sati][canskip][is16] = gen;
	return ans;
}

int main(void) {
	int N;
	int no = 0, yes = 1010101010;
	if (scanf("%d", &N) != 1) return 1;
	while (no + 1 < yes) {
		int m = no + (yes - no) / 2;
		llen = snprintf(limit, sizeof(limit), "%d", m);
		gen++;
		if (calc(0, 1, 1, 0) >= N) yes = m; else no = m;
	}
	printf("%d\n", yes);
	return 0;
}

/*

指定の数以下の「良い整数」が N 個以上か？で二分探索
「良い整数」の数を数えるにあたり、「128」 は 1 と 2 と 8 で作れるので、除外

https://oeis.org/A381259

164 → 1 64 と 1 64 で 2 通り作れる

print("\n".join([str(1<<x) for x in range(32)]))

*/

Submission Info

Submission Time	2026-05-30 08:35:33
Task	D - Concat Power of 2
User	mikecat
Language	C23 (GCC 14.2.0)
Score	400
Code Size	1507 Byte
Status	AC
Exec Time	2 ms
Memory	1664 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 3

× 28

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_min_01.txt, 01_min_02.txt, 01_min_03.txt, 01_min_04.txt, 01_min_05.txt, 02_small_01.txt, 02_small_02.txt, 02_small_03.txt, 02_small_04.txt, 02_small_05.txt, 03_medium_01.txt, 03_medium_02.txt, 03_medium_03.txt, 03_medium_04.txt, 03_medium_05.txt, 04_large_01.txt, 04_large_02.txt, 04_large_03.txt, 04_large_04.txt, 04_large_05.txt, 05_max_01.txt, 05_max_02.txt, 05_max_03.txt, 05_max_04.txt, 05_max_05.txt

Case Name	Status	Exec Time	Memory
00_sample_01.txt	AC	1 ms	1624 KiB
00_sample_02.txt	AC	1 ms	1552 KiB
00_sample_03.txt	AC	2 ms	1652 KiB
01_min_01.txt	AC	1 ms	1648 KiB
01_min_02.txt	AC	1 ms	1568 KiB
01_min_03.txt	AC	1 ms	1632 KiB
01_min_04.txt	AC	1 ms	1620 KiB
01_min_05.txt	AC	1 ms	1648 KiB
02_small_01.txt	AC	1 ms	1568 KiB
02_small_02.txt	AC	1 ms	1588 KiB
02_small_03.txt	AC	1 ms	1624 KiB
02_small_04.txt	AC	1 ms	1616 KiB
02_small_05.txt	AC	1 ms	1624 KiB
03_medium_01.txt	AC	1 ms	1552 KiB
03_medium_02.txt	AC	1 ms	1648 KiB
03_medium_03.txt	AC	1 ms	1652 KiB
03_medium_04.txt	AC	1 ms	1632 KiB
03_medium_05.txt	AC	1 ms	1504 KiB
04_large_01.txt	AC	1 ms	1648 KiB
04_large_02.txt	AC	1 ms	1468 KiB
04_large_03.txt	AC	1 ms	1508 KiB
04_large_04.txt	AC	1 ms	1624 KiB
04_large_05.txt	AC	1 ms	1652 KiB
05_max_01.txt	AC	2 ms	1588 KiB
05_max_02.txt	AC	1 ms	1568 KiB
05_max_03.txt	AC	2 ms	1664 KiB
05_max_04.txt	AC	1 ms	1648 KiB
05_max_05.txt	AC	1 ms	1652 KiB