fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. /*
  5. Note: In the output description of the problem, write as follows:
  6. "Output the number of correct sentences that can be made by switching the direction of one parenthesis (without changing any other parenthesis)"
  7.  
  8. -> Because there is only one sample for input/ouput. 
  9. So, to be honest, I don't know exactly what the desired output of the program is in the following cases because it affects the direction of solving the problem
  10.     1. If the input string is can't be fixed, eg.: "(()" 
  11.         -> Case 1: Program need to return 0 because it is incorrect sentences
  12.         -> Case 2: Return number of correct sentences that can be made (in this case: return 1)
  13.     2. If the input string is able to fix, but it need to be fixed at 2 or more positions, eg.: "(()(((()"
  14.         -> I need to fix at 1 point then return output as described in <case 2> OR return 0 because it's still considered invalid ?
  15. -> So I will design as:
  16.     1. Check if the string can be fixed by switching the direction of one parenthesis, return the number of correct sentences that can be made after fix
  17.     2. If the input string is correct, return the number of correct sentences that can be made
  18.     3. If the input string is can't be fixed or string is able to fix, but it need to be fixed at at 2 or more positions -> return 0
  19. */
  20.  
  21. using namespace std;
  22.  
  23. bool IsNeedToFixed(const vector<int>& balance, int pos, bool isOpen) 
  24. {
  25.     if (!isOpen)
  26.         return balance[pos + 1] == -1;
  27.  
  28.     int tmp = 0;
  29.     for (int j = pos + 1; j < balance.size(); ++j)
  30.     {
  31.         tmp = balance[j] - 2;
  32.         if (tmp < 0)
  33.             return false;
  34.     }
  35.  
  36.     return (tmp == 0);
  37. }
  38.  
  39. int CountCorrect(const string& s) 
  40. {
  41.     int n = s.length();
  42.     if (n % 2 != 0) 
  43.         return 0;
  44.  
  45.     vector<int> balance(n + 1, 0);
  46.  
  47.     for (int i = 0; i < n; ++i) 
  48.         balance[i + 1] = balance[i] + (s[i] == '(' ? 1 : -1);
  49.  
  50.     int totalBalance = balance[n];
  51.     if (abs(totalBalance) != 2) 
  52.     {
  53.         if (totalBalance == 0)
  54.             return n / 2;
  55.         return 0;
  56.     }
  57.  
  58.     string tmp = s;
  59.     bool isOpen = (totalBalance == 2) ? true : false;
  60.     char cmp = isOpen ? '(' : ')';
  61.  
  62.     for (int i = 0; i < n; ++i) 
  63.     {
  64.         if (s[i] != cmp)
  65.             continue;
  66.  
  67.         if (IsNeedToFixed(balance, i, isOpen))
  68.         {
  69.             tmp[i] = (isOpen) ? ')' : '(';      // change direction
  70.             break;
  71.         }
  72.     }
  73.  
  74.     // recheck balace for confirm
  75.     for (int i = 0; i < n; ++i)
  76.         balance[i + 1] = balance[i] + (tmp[i] == '(' ? 1 : -1);
  77.  
  78.     return (balance.back() == 0) ? n / 2 : 0;
  79. }
  80.  
  81. int main() {
  82.     string s;
  83.     cin >> s;
  84.  
  85.     cout << CountCorrect(s) << endl;
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
()(())))
stdout 
4
https://ideone.com/8D9Y9R
language:
C++14 (gcc 8.3)
created:
12 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!