結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー kwm_t
提出日時 2025-10-31 22:13:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 6,000 ms
コード長 2,654 bytes
コンパイル時間 3,364 ms
コンパイル使用メモリ 297,924 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-31 22:13:44
合計ジャッジ時間 4,530 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	// 高々7個あればできる
	const int iwai = 81181819;
	vector list(8, vector(63, vector<int>()));
	auto dfs = [&](auto &&self, vector<int> &x)->void {
		if (x.size() >= 8)return;
		{
			int sum = 0;
			int sz = x.size();
			for (auto e : x)sum += e;
			if (list[sz][sum].empty()) {
				//		
		//		cout << sz << " " << sum << endl;
				list[sz][sum] = x;
			}
		}
		vector<int>v = { 0,1,8 };
		rep(i, 3) {
			x.push_back(v[i]);
			self(self, x);
			x.pop_back();
		}
	};
	vector<int>emp = {};
	dfs(dfs, emp);
	map<P, pair<bool, int>>mp;
	rep(i, 8)mp[{0, i}] = { true,0 };
	int cnt = 00;
	auto calc = [&](auto &&self, int x, int size)->pair<bool, int> {
		if (mp.count({ x,size }))return mp[{x, size}];
		mp[{x, size}] = make_pair(false, -1);
		for (int i = x % 10; i < 63; i += 10) if (!list[size][i].empty()) {
			int nx = x - i;
			if (nx < 0)continue;
			nx /= 10;
			//cout << x << "->" << nx << endl;
			auto tmp = self(self, nx, size);
			if (tmp.first)mp[{x, size}] = make_pair(true, i);
		}
		return mp[{x, size}];
	};


	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		int x = iwai - n;
		vector<int>ans;
		auto solve = [&](int x, int size)->void {
			vector<vector<int>>anssub;
			ans.resize(size);
			anssub.resize(size);
			while (x) {
				auto[can, tar] = mp[{x, size}];
				rep(i, size) {
					anssub[i].push_back(list[size][tar][i]);
				}
				x = (x - tar) / 10;
			}
			rep(i, size) {
				reverse(all(anssub[i]));
				for (auto e : anssub[i]) {
					ans[i] = ans[i] * 10 + e;
				}
			}
		};
		rep2(i, 1, 8) {
			auto res = calc(calc, x, i);
			if (res.first) {
				//	cout << "can" << i << endl;
				solve(x, i);
				break;
			}
		}
		cout << ans.size() << endl;
		for (auto e : ans)cout << e << " ";
		cout << endl;
	}
	return 0;
}
0