#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL maxprod(vector<LL>& pos, vector<LL>& neg)
{
 if (neg.size() == neg.size() + pos.size() and neg.size() == 1)
  return *(neg.rbegin());
 bool considerneg = false, considerpos = false, negsizeisone = false;
 LL negprod = 1;
 if (neg.size())
 {
  considerneg = true;
  for (int i = 0; i < (int) neg.size(); i++)
   negprod *= neg[i];
  if (neg.size() & 1)
   negprod /= neg[neg.size() - 1];
  if (neg.size() == 1)
   negsizeisone = true;
 }
 //  printf("considerneg: %d, negprod: %lld\n", (int) considerneg, negprod);
 LL posprod = 1;
 if (pos.size())
 {
  considerpos = true;
  for (int i = 0; i < (int) pos.size(); i++)
   if (pos[i])
    posprod *= pos[i];
  if (*(pos.rbegin()) == 0)
   posprod = 0;
  if (pos.size() == pos.size() + neg.size())
   return posprod;
 }
 //  printf("considerpos: %d, posprod: %lld\n", (int) considerpos, posprod);
 if (negsizeisone)
  return posprod;
 if (considerneg and considerpos)
 {
  if (posprod)
   return negprod * posprod;
  else
   return negprod;
 }
 else if (considerneg)
  return negprod;
 else if (considerpos)
  return posprod;
}
LL minprod(vector<LL>& pos, vector<LL>& neg, vector<LL>& v)
{
 if (v[0] >= 0)
  return v[0];
 LL ret = 1;
 for (int i = 0; i < (int) pos.size(); i++)
  if (pos[i])
   ret *= pos[i];
 for (int i = 0; i < (int) neg.size(); i++)
  ret *= neg[i];
 if (not (neg.size() & 1))
  ret /= neg[neg.size() - 1];
 return ret;
}
int main()
{
 int t;
 cin >> t;
 while (t--)
 {
  int n;
  cin >> n;
  vector<LL> pos, neg, v;
  for (int i = 0; i < n; i++)
  {
   LL val;
   cin >> val;
   v.push_back(val);
   if (val < 0)
    neg.push_back(val);
   else
    pos.push_back(val);
  }
  sort(v.begin(), v.end());
  sort(pos.begin(), pos.end());
  sort(neg.begin(), neg.end());
  LL v1 = maxprod(pos, neg);
  LL v2 = minprod(pos, neg, v);
  cout << v1 << ' ' << v2 << '\n';
 }
 return 0;
}
- Problem Description
Tanmay  is a legendary spammer – everyone in the spamming world knows and  admires his abilities to spam anyone, anytime, anywhere. He decided to  guide one of his mentors, named Arjit, as part of the Apex body of  spamming.
Tanmay has no doubts on his skills of teaching and  making his mentor, Arjit, learn about the art of spamming. But, he  surely has serious doubt on Arjit’s skills of learning, implementing and  executing whatever he has decided to teach him as part of the syllabus  of spamming.
Tanmay has sent Arjit to test his skills, but he’s  getting extremely anxious about the performance of his mentee. So, to  calm himself down he asks you to help him find out the maximum and the  minimum productivity attained by Arjit in his travel.
Arjit has  the option to visit N Facebook groups – where every Facebook group has  some potential which can be negative, zero or positive. Now, he can  decide to visit a group if he wants to or not. (Depending on the lessons  taught to him by the great master!) The total productivity attained by  Arjit is the product of all the groups he decides to visit.
Given  the values of all the groups, find out the maximum and minimum spamming  potential he can achieve and let Tanmay know about it, so that he calm  himself down.
Input format:
The first line contains an  integer, T, denoting the number of test cases. Each line of the test  case contains an integer, N, denoting the size of the array. The next  line contains N integers, denoting the value of the numbers in the  array.
Output format:
Print the maximum product you can obtain  followed by the minimum product. A space separates both these outputs.  Answer to each test case is on a new line.
Constraints:
1 T 500
1 N 18
-10 Ni 10 
- Test Case 1
Input (stdin)2
4
1 0 2 10
3
0 0 0
Expected Output20 0
0 0 
- Test Case 2
Input (stdin)5
4
0 0 -1 1
2
0 -1
3
1 1 -1
3
-1 -1 -1
4
1 1 -1 1
Expected Output1 -1
0 -1
1 -1
1 -1
1 -1 
 
No comments:
Post a Comment