fork(3) download
copy 
  1. using namespace std;
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <set>
  7. #include <cctype>
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <algorithm>
  12. #include <stack>
  13. #include <cctype>
  14. #include <cstring>
  15. #include <string>
  16.  
  17. #define MAX 100100
  18. #define PRIME 31
  19. #define MOD 1000000007
  20. #define PI 3.1415926535897932384
  21. #define F first
  22. #define S second
  23. #define pb push_back
  24. #define mp make_pair
  25. #define pii pair<int, int>
  26. typedef long long ll;
  27.  
  28. int f(){
  29.     string str;
  30.     cin >> str;
  31.  
  32.     int acm[3] = {0, 0, 0}; // available ^ // _ // completed ^_^
  33.     int notUsed = 0; // _ not used
  34.  
  35.     for(int i = 0;i < str.size();i++){
  36.         if(str[i] == '^'){
  37.             if(acm[1]){ acm[1]--; acm[2]++; } // complete ^_^
  38.             else if(notUsed){ acm[1]++; notUsed--; } // Use a ^ already in a ^_^ to pair with _ and current ^ to fill ^_^
  39.             else acm[0]++; // Can't complete any ^_^
  40.         }
  41.         else if(acm[0]) { acm[1]++; acm[0]--; } // Pair ^_
  42.         else notUsed = min(notUsed+1, acm[2]); // Count the ^_^ which can have the second ^ replaced
  43.     }
  44.  
  45.     return acm[2];
  46. }
  47.  
  48. int main(){
  49.     //freopen("in.txt", "r", stdin);
  50.  
  51.     int t;
  52.     cin >> t;
  53.  
  54.     for(int test = 1;test <= t;test++){
  55.         printf("Case %d: %d\n", test, f());
  56.     }
  57.  
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
7
_^^_^^_
^__^__^
______
^^__^^
^_^^_^

^_^_^^^_^
^_^_____^^^^^^^
stdout
copy 
Case 1: 1
Case 2: 1
Case 3: 0
Case 4: 2
Case 5: 2
Case 6: 3
Case 7: 2
https://ideone.com/EEfOWY
language:
C++ (gcc 8.3)
created:
8 years 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!