結果

問題 No.362 門松ナンバー
ユーザー btk
提出日時 2016-05-24 22:32:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 3,000 ms
コード長 1,953 bytes
コンパイル時間 1,875 ms
コンパイル使用メモリ 183,676 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-11 05:08:41
合計ジャッジ時間 2,837 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
* Problem link
* 
*/

#include<bits/stdc++.h>
using namespace std;

struct INIT{INIT(){cin.tie(0);ios_base::sync_with_stdio(false);} }init;
typedef long long LL;
#define rep(i,n) for(auto i= 0*(n);i<n;i++)
#define range(it,v) for(auto &it:v)
#define mp make_pair
bool checkKadomatsu(int a, int b, int c) {
	return (a != c && ((a > b && (b < c) || (a<b&&b>c))));
}
int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	int T;
	while (cin >> T) {
		while (T--) {
			LL K;
			cin >> K;
			vector<map<pair<int,int>,LL>> dp(1);
			rep(i, 10)rep(j,10)if(i!=j) dp[0][mp(i, j)] = 1;
			LL lb = 1;
			LL ub = 1;
			auto cnt = [&]() {
				rep(i, 9) {
					range(it, dp.back()) {
						if (checkKadomatsu(i + 1, it.first.first, it.first.second))
							ub+=it.second;
					}
				}
			};
			cnt();
			while (!(lb <= K&&K<ub)) {
				lb = ub;
				map<pair<int, int>, LL> nxt;
				rep(i, 10) {
					range(it, dp.back()) {
						if (checkKadomatsu(i, it.first.first, it.first.second)) 
							nxt[mp(i, it.first.first)] += it.second;
						
					}
				}
				dp.push_back(nxt);
				cnt();
			}
			vector<int> res;
			[&]() {
				rep(i, 9) {
					range(it, dp.back()) {
						if (checkKadomatsu(i + 1, it.first.first, it.first.second)) {
							if (lb + it.second > K) {
								res.push_back(i + 1);
								res.push_back(it.first.first);
								res.push_back(it.first.second);
								return;
							}
							lb += it.second;
						}
					}
				}
			}();
			dp.pop_back();
			while (dp.size() > 0) {
				range(it, dp.back()) {
					int p = res[res.size() - 1];
					int pp = res[res.size() - 2];
					if(p==it.first.first)
						if (checkKadomatsu(pp, it.first.first, it.first.second)) {
							if (lb + it.second > K) {
								res.push_back(it.first.second);
								break;
							}
							lb += it.second;
						}
				}
				dp.pop_back();
			}
			for (auto& i : res)cout << i;
			cout << endl;
		}
	}
	return 0;
}
0