Submission #07347

ソースコード

?
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <set>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
string ltos(long long x){
stringstream ss;
ss << x;
return ss.str();
}
long long cnt_kadomatsu_digit(string s){
//vector<vector<vector<long long> > > dp;
//resize(dp, 11,11, 2);
long long dp[11][11][2] = {{{0}}};
long long dp_[11][11][2] = {{{0}}};
dp[10][10][0] = 1;
for(int i=0; i<s.size(); i++){
//vector<vector<vector<long long> > > dp_;
//resize(dp_, 11,11, 2);
for(int a=0; a<=10; a++) {
for(int b=0; b<=10; b++) {
for(int c=0; c<2; c++) {
//swap(dp[a][b][c], dp_[a][b][c]);
//long long tmp = dp[a][b][c];
//dp[a][b][c] = dp_[a][b][c];
//dp_[a][b][c] = tmp;
dp_[a][b][c] = 0;
}
}
}
int k = s[i] - '0';
for(int a=0; a<=10; a++) {
for(int b=0; b<=10; b++) {
for(int s=0; s< 2 ; s++){
if(!dp[a][b][s]) continue;
for(int c=0; c<10; c++){
if(s==0 && c>k) break;
int next_s = s || c<k;
bool ok = (a<b && b>c && a!=c) || (a>b && b<c && a!=c) || (a==10 || b==10);
if(ok){
dp_[b][(b==10&&c==0) ? 10 : c][next_s] += dp[a][b][s];
}
}
}
}
}
//swap(dp, dp_);
for(int a=0; a<=10; a++) {
for(int b=0; b<=10; b++) {
for(int c=0; c<2; c++) {
//swap(dp[a][b][c], dp_[a][b][c]);
//long long tmp = dp[a][b][c];
//dp[a][b][c] = dp_[a][b][c];
//dp_[a][b][c] = tmp;
dp[a][b][c] = dp_[a][b][c];
}
}
}
}
long long ret = 0;
for(int a=0; a<10; a++)
for(int b=0; b<10; b++)
for(int s=0; s<2 ; s++){
ret += dp[a][b][s];
}
return ret;
}
int main_(){
long long n = 0;
cin >> n;
n += cnt_kadomatsu_digit("99");
long long lb = 1;
long long ub = 500000000000000LL;
while(ub-lb>1){
long long mid = (lb+ub)/2;
bool ok = cnt_kadomatsu_digit(ltos(mid)) >= n;
(ok? ub : lb) = mid;
}
cout << ub << endl;
return 0;
}
#include <ctime>
int main(){
//auto s = clock();
int t;
cin >> t;
while(t--){
main_();
}
//cerr << clock()-s << endl;
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
0_1_sample.txt AC 23 ms 476 KB
1
0_2_sample.txt AC 17 ms 452 KB
1
1_1.txt AC 19 ms 428 KB
1
1_2.txt AC 13 ms 532 KB
1
1_3.txt AC 11 ms 636 KB
1
1_4.txt AC 20 ms 616 KB
1
1_5.txt AC 28 ms 592 KB
1
1_6.txt AC 19 ms 568 KB
1
1_7.txt AC 25 ms 672 KB
1
1_8.txt AC 29 ms 520 KB
1
1_9.txt AC 38 ms 496 KB
1
2_1.txt AC 36 ms 472 KB
1
2_2.txt AC 35 ms 448 KB
1
2_3.txt AC 38 ms 428 KB
1
2_4.txt AC 38 ms 404 KB
1
2_5.txt AC 35 ms 512 KB
1
3_1.txt AC 38 ms 488 KB
1
3_2.txt AC 35 ms 468 KB
1
3_3.txt AC 36 ms 572 KB
1
3_4.txt AC 25 ms 548 KB
1
3_5.txt AC 39 ms 524 KB
1
4_1_sample.txt AC 13 ms 628 KB
1