結果
問題 |
No.3245 Payment with 8-rep Currency
|
ユーザー |
|
提出日時 | 2025-08-22 23:01:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 1,819 bytes |
コンパイル時間 | 1,961 ms |
コンパイル使用メモリ | 203,852 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-22 23:01:45 |
合計ジャッジ時間 | 8,157 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); vector<int> stk; vector<int> a = {1, 11, 111, 1111}; vector<vector<int>> ope(593); reverse(a.begin(), a.end()); int sv = 0; constexpr int r = 10; vector<int> S2(12); vector<vector<int>> op2(12); auto dfs = [&](auto dfs, int p, int pay) -> void { if(p == 4){ for(auto v : stk){ if(2 * v >= sv) return; } ope[pay] = stk; // mod 12 で分類 if(S2[pay % 12] == 0){ S2[pay % 12] = pay; op2[pay % 12] = stk; } return; } for(int i = 0; pay + a[p] * i <= 592; i++){ stk.emplace_back(i); sv += i; dfs(dfs, p + 1, pay + a[p] * i); sv -= i; stk.pop_back(); } }; dfs(dfs, 0, 0); int T; cin >> T; array<ll, 4> ans; while(T--){ ll n; cin >> n; ans.fill(0); if(n % 8 != 0){ cout << "-1\n"; continue; } n /= 8; if(n <= 592){ if(ope[n].empty()){ cout << "-1\n"; }else{ for(int i = 0; i < 4; i++) cout << ope[n][3 - i] << (i == 3 ? '\n' : ' '); } continue; } int mod = n % 12; for(int i = 0; i < 4; i++){ ans[i] += op2[mod][3 - i]; } n -= S2[mod]; n /= 12; ans[0] += n; ans[1] += n; ll sv = accumulate(ans.begin(), ans.end(), 0ll); for(int i = 0; i < 4; i++){ assert(2 * ans[i] < sv); cout << ans[i] << (i == 3 ? '\n' : ' '); } } }