Dang_Quan_10_Tin

KMULT

Aug 27th, 2020
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <stack>
  4. #define task "KMULT"
  5. using namespace std;
  6. using ll = long long;
  7. using ld = long double;
  8.  
  9. const int N = 1e4 + 2;
  10. int n, a[N], k;
  11. bool dp[N][100];
  12. int par[N][100];
  13. char sign[N][100];
  14.  
  15. void Read()
  16. {
  17.     cin >> n >> k;
  18.     for (int i = 1; i <= n; ++i)
  19.         cin >> a[i],
  20.             a[i] %= k;
  21. }
  22.  
  23. void Solve()
  24. {
  25.     dp[1][(a[1] % k + k) % k] = 1;
  26.     if (a[1] % k == 0)
  27.         dp[1][k] = 1;
  28.     for (int i = 2; i <= n; ++i)
  29.     {
  30.         for (int j = 1; j <= k; ++j)
  31.         {
  32.             int t = j - a[i];
  33.             if (t <= 0)
  34.                 t += k;
  35.             if (t > k)
  36.                 t -= k;
  37.             if (dp[i - 1][t])
  38.             {
  39.                 dp[i][j] = 1;
  40.                 par[i][j] = t;
  41.                 sign[i][j] = '+';
  42.             }
  43.             t = j + a[i];
  44.             if (t > k)
  45.                 t -= k;
  46.             if (t <= 0)
  47.                 t += k;
  48.             if (dp[i - 1][t])
  49.             {
  50.                 dp[i][j] = 1;
  51.                 par[i][j] = t;
  52.                 sign[i][j] = '-';
  53.             }
  54.             //cout << dp[i][j] << (j == k ? "\n" : " ");
  55.         }
  56.     }
  57.     cout << dp[n][k] << "\n";
  58.     if (dp[n][k])
  59.     {
  60.         stack<char> s;
  61.         int i = n, j = k;
  62.         do
  63.         {
  64.             s.push(sign[i][j]);
  65.             j = par[i][j];
  66.             --i;
  67.         } while (i > 1);
  68.         while (s.size())
  69.         {
  70.             cout << s.top();
  71.             s.pop();
  72.         }
  73.     }
  74. }
  75.  
  76. int32_t main()
  77. {
  78.     ios::sync_with_stdio(0);
  79.     cin.tie(0);
  80.     cout.tie(0);
  81.     if (fopen(task ".INP", "r"))
  82.         freopen(task ".INP", "r", stdin),
  83.             freopen(task ".OUT", "w", stdout);
  84.     Read();
  85.     Solve();
  86. }
Add Comment
Please, Sign In to add comment