Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <stack>
- #define task "KMULT"
- using namespace std;
- using ll = long long;
- using ld = long double;
- const int N = 1e4 + 2;
- int n, a[N], k;
- bool dp[N][100];
- int par[N][100];
- char sign[N][100];
- void Read()
- {
- cin >> n >> k;
- for (int i = 1; i <= n; ++i)
- cin >> a[i],
- a[i] %= k;
- }
- void Solve()
- {
- dp[1][(a[1] % k + k) % k] = 1;
- if (a[1] % k == 0)
- dp[1][k] = 1;
- for (int i = 2; i <= n; ++i)
- {
- for (int j = 1; j <= k; ++j)
- {
- int t = j - a[i];
- if (t <= 0)
- t += k;
- if (t > k)
- t -= k;
- if (dp[i - 1][t])
- {
- dp[i][j] = 1;
- par[i][j] = t;
- sign[i][j] = '+';
- }
- t = j + a[i];
- if (t > k)
- t -= k;
- if (t <= 0)
- t += k;
- if (dp[i - 1][t])
- {
- dp[i][j] = 1;
- par[i][j] = t;
- sign[i][j] = '-';
- }
- //cout << dp[i][j] << (j == k ? "\n" : " ");
- }
- }
- cout << dp[n][k] << "\n";
- if (dp[n][k])
- {
- stack<char> s;
- int i = n, j = k;
- do
- {
- s.push(sign[i][j]);
- j = par[i][j];
- --i;
- } while (i > 1);
- while (s.size())
- {
- cout << s.top();
- s.pop();
- }
- }
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- freopen(task ".INP", "r", stdin),
- freopen(task ".OUT", "w", stdout);
- Read();
- Solve();
- }
Add Comment
Please, Sign In to add comment