Submission #57611714

Source Code Expand

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>
#define MAX_DIGIT 20
int gen;
int limit[MAX_DIGIT];
int memo[MAX_DIGIT][10][2][2];
int memo_gen[MAX_DIGIT][10][2][2];
uint64_t calc(int pos, int prev, int zero, int sati) {
  uint64_t ans = 0;
  int i, max;
  if (pos >= MAX_DIGIT) return !zero;
  if (memo_gen[pos][prev][zero][sati] == gen) return memo[pos][prev][zero][sati];
  max = sati ? limit[pos] : 9;
  for (i = 0; i <= max; i++) {
    if (i != prev || (i == 0 && zero)) {
      ans += calc(pos + 1, i, zero && i == 0, sati && i == max);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define MAX_DIGIT 20

int gen;
int limit[MAX_DIGIT];
int memo[MAX_DIGIT][10][2][2];
int memo_gen[MAX_DIGIT][10][2][2];

uint64_t calc(int pos, int prev, int zero, int sati) {
	uint64_t ans = 0;
	int i, max;
	if (pos >= MAX_DIGIT) return !zero;
	if (memo_gen[pos][prev][zero][sati] == gen) return memo[pos][prev][zero][sati];

	max = sati ? limit[pos] : 9;
	for (i = 0; i <= max; i++) {
		if (i != prev || (i == 0 && zero)) {
			ans += calc(pos + 1, i, zero && i == 0, sati && i == max);
		}
	}

	memo_gen[pos][prev][zero][sati] = gen;
	memo[pos][prev][zero][sati] = ans;
	return ans;
}

uint64_t query(uint64_t n) {
	int i;
	for (i = 0; i < MAX_DIGIT; i++) {
		limit[MAX_DIGIT - 1 - i] = n % 10;
		n /= 10;
	}
	gen++;
	return calc(0, 0, 1, 1);
}

int main(void) {
	int T, tc;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		uint64_t K;
		uint64_t no = 0, yes = UINT64_C(10000000000000000000);
		if (scanf("%" SCNu64, &K) != 1) return 1;
		while (no + 1 < yes) {
			uint64_t m = no + (yes - no) / 2;
			if (query(m) >= K) yes = m; else no = m;
		}
		printf("%" PRIu64 "\n", yes);
	}
	return 0;
}

/*

指定の数以下の "Neq Number" が何個あるかをメモ化探索
→ K以上になる最小の数を二分探索

*/

Submission Info

Judge Result