fork download
copy 
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC target("avx,avx2,fma")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define MOD 1000000007
  9. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  10. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define ii pair<int,int>
  13. #define iii pair<int,pair<int,int>>
  14. //const int MOD = 998244853;
  15. const int MAXN = 1e6 + 7;
  16. ll x,n,a[MAXN],dd;
  17. string s,ans;
  18. ll Try(int id,ll cur){
  19.     dd++;
  20.     if (dd > (int)1e7)return -1e18;
  21.     if (id == n){
  22.         if (cur == x){
  23.             ans = s;
  24.             return cur;
  25.         }
  26.         return -1e18;
  27.     }
  28.     ll res = -1e18;
  29.     ll mul = 1;
  30.     s.push_back('+');
  31.     FOR(i,id + 1,n){
  32.         mul = mul * a[i];
  33.         res = max(res,Try(i,cur + mul));
  34.         s.push_back('*');
  35.     }
  36.     FOR(i,id + 1,n + 1)s.pop_back();
  37.     mul = 1;
  38.     s.push_back('-');
  39.     FOR(i,id + 1,n){
  40.         mul = mul * a[i];
  41.         res = max(res,Try(i,cur - mul));
  42.         s.push_back('*');
  43.     }
  44.     FOR(i,id + 1,n + 1)s.pop_back();
  45.     return res;
  46. }
  47. int main(){
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(0); cout.tie(0);
  50.     //freopen("MENU.inp","r",stdin);
  51.     //freopen("MENU.out","w",stdout);
  52.     int tt;cin >> tt;
  53.     while(tt--){
  54.         cin >> n;
  55.         FOR(i,1,n)cin >> a[i];
  56.         cin >> x;
  57.         bool ok = false;
  58.         s = "";ll st = 1;
  59.         FOR(i,1,n){
  60.             dd = 0;
  61.             st = st * a[i];
  62.             if (Try(i,st) == x){
  63.                 ok = true;
  64.                 break;
  65.             }
  66.             s.push_back('*');
  67.         }
  68.         if (ok)cout << "YES\n" << ans << '\n';
  69.         else cout << "NO\n";
  70.     }
  71.     return 0^0;
  72. }
Success #stdin #stdout 2.05s 5300KB
comments (?)
stdin
copy 
5
17
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8
-23235425
17
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8
-23235425
17
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8
-23235425
17
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8
-23235425
17
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8
-23235425
stdout
copy 
NO
NO
NO
NO
NO
https://ideone.com/y4QNL4
language:
C++ (gcc 8.3)
created:
7 hours 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!