Submission #07345

ソースコード

?
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
int T;
ll K;
// [i桁目まで見た][numより小さいことが確定][前の前の数][前の数] = 場合の数
ll dp[15][2][11][10];
bool checkKado(int a, int b, int c){
if(a == b || b == c || c == a)return false;
if(a == 10)return true;
return (a<b&&b>c)||(a>b&&b<c);
}
ll count(ll num){
string digits = to_string(num);
if(sz(digits) < 3)return 0;
each(c, digits)c -= '0';
MEM(dp, 0);
for(int i = 1; i < digits[0]; ++i){
dp[1][1][10][i] = 1;
}
dp[1][0][10][digits[0]] = 1;
FOR(i, 1, digits.size()){
rep(lessThanNum, 2){
rep(prepre, 11){
rep(pre, 10){
ll val = dp[i][lessThanNum][prepre][pre];
rep(cur, 10){
if(!lessThanNum && cur > digits[i]){
continue;
}
if(!checkKado(prepre, pre, cur)){
continue;
}
dp[i + 1][lessThanNum || cur < digits[i]][pre][cur] += val;
}
}
}
}
}
ll result = 0;
rep(lessThanNum, 2)rep(pre, 10)rep(prepre, 10){
result += dp[sz(digits)][lessThanNum][prepre][pre];
}
if(sz(digits) > 3){
result += count(stoll(string(sz(digits) - 1, '9')));
}
return result;
}
void solve(){
ll ng = 99, ok = 37294859064823ll, mid;
while(ok - ng > 1){
mid = (ok + ng) / 2;
ll cnt = count(mid);
(cnt >= K ? ok : ng) = mid;
}
cout << ok << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
while(cin >> T){
while(T--){
cin >> K;
solve();
}
}
}

ステータス

項目 データ
問題 0469 - 門松ナンバー
ユーザー名 ei1430
投稿日時 2016-07-21 08:03:22
言語 C++11
状態 Accepted
得点 5
ソースコード長 2361 Byte
最大実行時間 278 ms
最大メモリ使用量 796 KB

セット

セット 得点 Cases
1 ALL 5 / 5 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
0_1_sample.txt AC 103 ms 476 KB
1
0_2_sample.txt AC 46 ms 668 KB
1
1_1.txt AC 44 ms 604 KB
1
1_2.txt AC 28 ms 668 KB
1
1_3.txt AC 23 ms 608 KB
1
1_4.txt AC 70 ms 668 KB
1
1_5.txt AC 122 ms 732 KB
1
1_6.txt AC 82 ms 796 KB
1
1_7.txt AC 113 ms 732 KB
1
1_8.txt AC 184 ms 668 KB
1
1_9.txt AC 270 ms 604 KB
1
2_1.txt AC 255 ms 668 KB
1
2_2.txt AC 258 ms 724 KB
1
2_3.txt AC 268 ms 664 KB
1
2_4.txt AC 257 ms 728 KB
1
2_5.txt AC 262 ms 660 KB
1
3_1.txt AC 241 ms 728 KB
1
3_2.txt AC 210 ms 660 KB
1
3_3.txt AC 275 ms 728 KB
1
3_4.txt AC 98 ms 784 KB
1
3_5.txt AC 278 ms 716 KB
1
4_1_sample.txt AC 42 ms 780 KB
1