結果

問題 No.362 門松ナンバー
ユーザー bal4ubal4u
提出日時 2019-08-31 22:11:50
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 14 ms / 3,000 ms
コード長 1,214 bytes
コンパイル時間 468 ms
コンパイル使用メモリ 32,640 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-25 09:32:55
合計ジャッジ時間 1,006 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 5 ms
5,248 KB
testcase_06 AC 8 ms
5,248 KB
testcase_07 AC 5 ms
5,248 KB
testcase_08 AC 7 ms
5,248 KB
testcase_09 AC 10 ms
5,248 KB
testcase_10 AC 14 ms
5,248 KB
testcase_11 AC 13 ms
5,248 KB
testcase_12 AC 13 ms
5,248 KB
testcase_13 AC 12 ms
5,248 KB
testcase_14 AC 12 ms
5,248 KB
testcase_15 AC 12 ms
5,248 KB
testcase_16 AC 12 ms
5,248 KB
testcase_17 AC 11 ms
5,248 KB
testcase_18 AC 13 ms
5,248 KB
testcase_19 AC 6 ms
5,248 KB
testcase_20 AC 13 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yukicoder: 362 門松ナンバー
// 2019.8.31 bal4u

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

typedef long long ll;

#define FIRST 101
#define LAST  37294859064824LL;

ll dp[20][100][2];
char ss[25], *s; int w;

inline static void add(ll *a, ll b) { *a += b; }

ll calc(ll x) {
	int i, j, k, f, a;
	
	i = 20; for (w = 0; x; w++) ss[--i] = x % 10, x /= 10;
	s = ss + i;
	
	memset(dp, 0, sizeof(dp));
	for (i = 2; i < w; i++) {
		if (i == 2) a = s[0]*10 + s[1]; else a = 99;
		for (j = 10; j <= a; j++) if (j % 10 != j / 10) dp[i][j][i==2 && j==a]++;
			
		for (j = 0; j < 100; j++) {
			int x = j/10, y = j%10; if (x != y) {
				for (f = 0; f < 2; f++) if (dp[i][j][f]) {
					a = f? s[i]: 9; for (k = 0; k <= a; k++) {
						if (x != k && (x < y && y > k || x > y && y < k)) {
							add(&dp[i+1][y*10+k][f && k==a], dp[i][j][f]);
						}
					}
				}
			}
		}
	}
	
	ll sum = 0;
	for (j = 0; j < 100; j++) add(&sum, dp[w][j][0]+dp[w][j][1]);
	return sum;
}


int main()
{
	int T; ll t, K, l, m, r;
	
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &K);
		
		l = FIRST, r = LAST;
		while (l + 1 < r) {
			m = (l + r) >> 1;
			if ((t = calc(m)) >= K) r = m; else l = m;
		}
		printf("%lld\n", r);
	}
	return 0;
}
0