結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー elphe
提出日時 2025-10-25 14:06:38
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 6,000 ms
コード長 1,865 bytes
コンパイル時間 2,794 ms
コンパイル使用メモリ 281,856 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-25 17:03:39
合計ジャッジ時間 3,897 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

[[nodiscard]] static inline constexpr std::vector<uint_least32_t> solve(const std::string& N) noexcept
{
	constexpr std::array<uint_least32_t, 8> default_array = { INT_LEAST32_MAX, INT_LEAST32_MAX, INT_LEAST32_MAX, INT_LEAST32_MAX, INT_LEAST32_MAX, INT_LEAST32_MAX, INT_LEAST32_MAX, INT_LEAST32_MAX, };
	std::vector<std::array<uint_least32_t, 8>> dp(N.size() + 1, default_array);
	dp[0][0] = 0;
	for (uint_fast32_t i = 0; i < N.size(); ++i)
		for (uint_fast32_t j = 0; j < 8; ++j)
			for (uint_fast32_t k = ((N[i] - '0') < j); k < UINT32_C(8); ++k)
			{
				const uint_fast32_t falling = k * 10 + (N[i] - '0') - j;
				dp[i + 1][j] = std::min<uint_fast32_t>(dp[i + 1][j], std::max<uint_fast32_t>(dp[i][k], falling / 8 + falling % 8));
			}

	std::vector<uint_least32_t> ans(dp[N.size()][0], 0);
	for (uint_fast32_t i = N.size(), j = 0, digit = 1; i != 0; --i, digit *= 10)
	{
		uint_fast32_t next_j = UINT_FAST32_MAX;
		for (uint_fast32_t k = ((N[i - 1] - '0') < j); k < UINT32_C(8); ++k)
		{
			const uint_fast32_t falling = k * 10 + (N[i - 1] - '0') - j;
			if (dp[i][j] == std::max<uint_fast32_t>(dp[i - 1][k], falling / 8 + falling % 8))
				next_j = k;
		}

		const uint_fast32_t falling = next_j * 10 + (N[i - 1] - '0') - j;
		for (uint_fast32_t k = 0; k < falling / 8; ++k) ans[k] += 8 * digit;
		for (uint_fast32_t k = 0; k < falling % 8; ++k) ans[falling / 8 + k] += digit;

		j = next_j;
	}

	return ans;
}

static inline void output(const std::vector<uint_least32_t>& ans) noexcept
{
	std::cout << ans.size() << '\n';
	for (const auto& res : ans)
		std::cout << res << '\n';
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	
	uint_fast32_t T;
	std::cin >> T;
	for (uint_fast32_t i = 0; i < T; ++i)
	{
		uint_fast32_t N;
		std::cin >> N;

		output(solve(std::to_string(81181819 - N)));
	}

	return 0;
}
0