結果
問題 | No.362 門松ナンバー |
ユーザー | mayoko_ |
提出日時 | 2016-04-21 21:58:16 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 673 ms / 3,000 ms |
コード長 | 2,542 bytes |
コンパイル時間 | 985 ms |
コンパイル使用メモリ | 105,836 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-04-19 07:20:50 |
合計ジャッジ時間 | 10,816 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 172 ms
6,812 KB |
testcase_01 | AC | 139 ms
6,812 KB |
testcase_02 | AC | 138 ms
6,940 KB |
testcase_03 | AC | 74 ms
6,940 KB |
testcase_04 | AC | 39 ms
6,944 KB |
testcase_05 | AC | 229 ms
6,940 KB |
testcase_06 | AC | 416 ms
6,944 KB |
testcase_07 | AC | 231 ms
6,940 KB |
testcase_08 | AC | 314 ms
6,940 KB |
testcase_09 | AC | 504 ms
6,940 KB |
testcase_10 | AC | 635 ms
6,944 KB |
testcase_11 | AC | 621 ms
6,944 KB |
testcase_12 | AC | 620 ms
6,940 KB |
testcase_13 | AC | 630 ms
6,940 KB |
testcase_14 | AC | 626 ms
6,940 KB |
testcase_15 | AC | 625 ms
6,944 KB |
testcase_16 | AC | 607 ms
6,940 KB |
testcase_17 | AC | 531 ms
6,944 KB |
testcase_18 | AC | 673 ms
6,944 KB |
testcase_19 | AC | 341 ms
6,944 KB |
testcase_20 | AC | 664 ms
6,940 KB |
testcase_21 | AC | 68 ms
6,944 KB |
ソースコード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> //#include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> //#include<list> #include<queue> #include<deque> #include<algorithm> //#include<numeric> #include<utility> #include<complex> //#include<memory> #include<functional> #include<cassert> #include<set> #include<stack> #include<random> const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<ll> vll; typedef pair<int, int> pii; bool isKadomatsu(const vector<int>& A) { if (A[0] == A[1] || A[0] == A[2] || A[1] == A[2]) return false; if (A[0] > A[1] && A[1] < A[2]) return true; if (A[0] < A[1] && A[1] > A[2]) return true; return false; } // keta, %100, small, renzoku ll dp[17][100][2][4]; // x 以下の門松ナンバーの数を数える ll calc(ll x) { memset(dp, 0, sizeof(dp)); string s = to_string(x); dp[1][0][1][0] = 1; for (int i = 1; i < 10; i++) { int num = (s[0]-'0'); if (i > num) break; dp[1][i][i < num][1] = 1; } int n = s.size(); for (int keta = 1; keta < n; keta++) for (int q = 0; q < 100; q++) { for (int small = 0; small < 2; small++) for (int renzoku = 0; renzoku < 4; renzoku++) { for (int num = 0; num < 10; num++) { if (!small && num > (s[keta]-'0')) break; if (renzoku >= 2) { vi A(3); A[0] = (q/10), A[1] = q%10, A[2] = num; if (!isKadomatsu(A)) continue; } int nrenzoku = renzoku; if (renzoku != 0 || num != 0) nrenzoku = min(3, nrenzoku+1); int nsmall = small; nsmall |= (num < s[keta]-'0'); int nq = (q*10+num)%100; dp[keta+1][nq][nsmall][nrenzoku] += dp[keta][q][small][renzoku]; } } } ll ret = 0; for (int i = 0; i < 100; i++) for (int j = 0; j < 2; j++) { ret += dp[n][i][j][3]; } return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; while (T--) { ll K; cin >> K; ll low = 100, high = 1e15; while (high-low > 1) { const ll med = (high+low)/2; if (calc(med) >= K) high = med; else low = med; } cout << high << endl; } return 0; }