fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define endl '\n'
  5. #define fi first
  6. #define se second
  7. const int N = 1e3 + 5;
  8. ll a, b, c;
  9. string n;
  10. int dp[20][30][1005][2][2][2];
  11. struct Trace {
  12.     int a = 0, b = 0, c = 0, carry = 0, s = 0, ok = 0, okb = 0, okc = 0;
  13. } trace[20][30][1005][2][2][2], check;
  14. int Try(int i, int carry, int ok, int okb, int okc, int S) {
  15.     //cout << i << ' ' << carry << ' ' << S << ' ' << ok<< endl;
  16.     if(dp[i][carry][S][ok][okb][okc] != -1) return dp[i][carry][S][ok][okb][okc];
  17.     if(i == 0) return dp[i][carry][S][ok][okb][okc] = (!carry && ok && okb && okc);
  18.  
  19.     int &res = dp[i][carry][S][ok][okb][okc];
  20.     res = 0;
  21.     int digit = n[i] - '0';
  22.     for(int c = 9; c >= 0; c--)
  23.         for(int b = c; b >= 0; b--)
  24.             for(int a = b; a >= 0; a--) {
  25.                 int s = a + b + c + carry;
  26.                 if(s % 10 == digit) {
  27.                     int noka = (ok | (a != 0));
  28.                     int nokb = (okb | (b > a));
  29.                     int nokc = (okc | (c > b));
  30.                     res |= Try(i - 1, s / 10, noka, nokb, nokc, S + a + b + c);
  31.                     if(dp[i - 1][s / 10][S + a + b + c][noka][nokb][nokc] == 1) {
  32.                         //cout << 1 << endl;
  33.                         Trace &next = trace[i - 1][s / 10][S + a + b + c][noka][nokb][nokc];
  34.                         next.a = a;
  35.                         next.b = b;
  36.                         next.c = c;
  37.                         next.carry = carry;
  38.                         next.s = S;
  39.                         next.ok = ok;
  40.                         next.okb = okb;
  41.                         next.okc = okc;
  42.                         //return res;
  43.                         //cout << i - 1 << ' ' << s / 10 << ' ' << S + s << ' '  << noka << endl;
  44.                     }
  45.                 }
  46.             }
  47.     return res;
  48. }
  49. ll logg3(ll x) {
  50.     ll ans = 1;
  51.     for (ans = 1; ans * 3 <= x; ans *= 3){};
  52.     return ans;
  53. }
  54. vector<ll> tach(ll x) {
  55.     vector<ll> ans;
  56.     ll add = 1;
  57.     while(x > 0) {
  58.         if(x & 1) {
  59.             ll lg = logg3(x);
  60.             ans.push_back(lg * add);
  61.             x -= lg;
  62.         } else {
  63.             x /= 2;
  64.             add *= 2;
  65.         }
  66.     }
  67.     return ans;
  68. }
  69. void reset() {
  70.     memset(dp, -1, sizeof dp);
  71. }
  72. signed main() {
  73.     if (fopen("vd.inp", "r")) {
  74.         freopen("vd.inp", "r", stdin);
  75.         freopen("vd.out", "w", stdout);
  76.     }
  77.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  78.     int ntest; cin >> ntest;
  79.     //cout << d[0][0] << ' ';
  80.     while(ntest--) {
  81.         cin >> n;
  82.         n = ' ' + n;
  83.         reset();
  84.         if(!Try(n.size() - 1, 0, 0, 0, 0, 0)) {
  85.             cout << -1 << endl;
  86.             continue;
  87.         }
  88.         ll a = 0, b = 0, c = 0;
  89.         for(int i = n.size() * 30; i >= 6; i--)
  90.             if(dp[0][0][i][1][1][1] == 1) {
  91.                 //cout << i << ' ' << trace[0][0][i][1][1][1].a << endl;
  92.                 int ii = 0, carry = 0, S = i, ok = 1, okb = 1, okc = 1;
  93.                 while(ii < n.size() - 1) {
  94.                     //cout << 1 << ' ';
  95.                     //cout << trace[ii][carry][S][ok][okb][okc].a << endl;
  96.                     Trace &cur = trace[ii][carry][S][ok][okb][okc];
  97.                     a = a * 10 + 1ll * cur.a;
  98.                     b = b * 10 + 1ll * cur.b;
  99.                     c = c * 10 + 1ll * cur.c;
  100.                     int nS = cur.s;
  101.                     int nok = cur.ok;
  102.                     int nokb = cur.okb;
  103.                     int nokc = cur.okc;
  104.                     int ncarry = cur.carry;
  105.                     ii++;
  106.                     S = nS; ok = nok; okb = nokb; okc = nokc, carry = ncarry;
  107.                 }
  108.                 break;
  109.             }
  110.         if(a * b * c == 0 || a >= b || a >= c || b >= c) {
  111.             cout << -1 << endl;
  112.             continue;
  113.         }
  114.         vector<ll> va = tach(a), vb = tach(b), vc = tach(c);
  115.         cout << va.size() << ' ' << vb.size() << ' ' << vc.size() << ' ';
  116.         for(auto x : va) cout << x << ' ';
  117.         for(auto x : vb) cout << x << ' ';
  118.         for(auto x : vc) cout << x << ' ';
  119.         cout << endl;
  120.         //cout << a << ' ' << b << ' ' << c << endl;
  121.     }
  122.     //cout << logg3(9);
  123.     //cout << (1 > 2 || 2 < 2);
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0.03s 154728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tLl7vh
language:
C++14 (clang 8.0)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!