結果

問題 No.362 門松ナンバー
コンテスト
ユーザー bal4u
提出日時 2019-08-31 22:11:50
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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