結果

問題 No.362 門松ナンバー
ユーザー bal4u
提出日時 2019-08-31 22:10:00
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,214 bytes
コンパイル時間 680 ms
コンパイル使用メモリ 33,024 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-25 09:30:25
合計ジャッジ時間 1,491 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 18 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// yukicoder: 362 門松ナンバー
// 2019.8.31 bal4u
#include <stdio.h>
#include <string.h>
typedef long long ll;
#define FIRST 102
#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0