fork download
copy 
  1. //                                                           .=*#=
  2. //                                                        .=*=+* -#:
  3. //                                                      -*+. +=   .#=
  4. //                                                    -*=   *-     .#=
  5. //                                                  :*=    *#++#*   .%:
  6. //                                                 ++.    *-  =+     -#
  7. //                                               :*-     *-  *=       %-
  8. // .------::.                                   -*.     +=   -+++-.   *#
  9. // -*:-=+*#%#*++-.                             =+      -+        :+*- +@.
  10. // :*      .-++-:=++:                         ++      .#          .*: +%-
  11. // .#        .:+#- .=*=.                     =+       *:        :++.  *+=
  12. //  %       -%*=-=*.  :*+.                  -*       :*      :++=.    #-+
  13. //  #:       .=*- .*:   :*=         .:==++++*        +-     -**+:    :*:+
  14. //  +=         -#:  *-    :*-   :=++=-:.             =*-   :+++-     *-:+
  15. //  -#      .=*-     *-     =*+*=:                     -*= ==       .# -#++++++++=-:
  16. //   @:    =*:        #:     ..                          -*-#       *: ==        .:-+++:
  17. //   **   :#:         .#.                                 .*@.     =+  +:             .-*+:
  18. //   :@:   .=++=:.     -*                                   +.    :#   #.                .+*:
  19. //    ##       :-*@*   +-                                        .#.  .#                   .++=-.
  20. //    :@+       =#*++-.#                                         *:   -+                      .-+++-
  21. //     *%-           #+-                                              *.                          .-*+.
  22. //     .##-          +@                                           -. .#                              .++.
  23. //      :*++         :%                                  .=+.     :*:*:                                :*-
  24. //       =+-*:        -                                :++.        .**                    =.             +=
  25. //        =+.++:                                     .++.            #.                   ==              +=
  26. //         =+ .=*=.                                 .*:              *:                   *:               *:
  27. //          -*.  :++=:                             .#.               #.                .-*-                .#
  28. //           :*:    .=:                            *:               +=   .-=+++++==++++=:                   *:
  29. //            .*=               ...                .               += -++=:.                                :+
  30. //              -*:   ..    =++++==++++=:                        :*+++-                                      #
  31. //               .++. ==    .          .==                     .+%*=.                                        %
  32. //                 .*+==                                      =#%=                                           %
  33. //                   :#*                         .:.        -***..::.                                        %
  34. //                     #:                      +%@@:      -*-+%++=--*-                                      .#
  35. //                     .*-                     :=*=     -*- =%-     *:                                      -=
  36. //                       =*=.                         =*-  -*       # .-.                                   #.
  37. //                         :=#*++++++++++++++++-:::-+*-    #.      .*+=#.                                  ==
  38. //                           *:   .*-         #----:      ==           %+++++++++:                        -*
  39. //                           %    -*+-       .#:          #.                    +-                       -*
  40. //                           %      ##:+**. =*%.         -%                    -+                       ++
  41. //                           *:     #:+: :**-+=         .##                   :*                      :*-
  42. //                           :#=- +-#      :*:         .#:#                  :#.                    :*+.
  43. //                            .*#+*+.     :*.         .*: %                 .#*+=:                :*+.
  44. //                                        #..+       :*:  #.                    .++            :+*-
  45. //                                        :**=  #  :++.   ==                   .*+.       .:=++=.
  46. //                                          :=++*++=.     .#                   .+%+==++++++-.
  47. //                                                         *:           .-+++++=-::..
  48. //                                                         :*       .=++=:.
  49. //                                                          +-    -*+:
  50. //                                                          .#..=*-
  51. //                                                           =#*:
  52. //                                                           .-
  53.  
  54. #include <bits/stdc++.h>
  55. #define prob ""
  56. #define int long long
  57. using namespace std;
  58. void file(){
  59.     freopen(prob".INP", "r", stdin);
  60.     freopen(prob".OUT", "w", stdout);
  61. }
  62. void Init() {
  63.     ios_base::sync_with_stdio(false);
  64.     cin.tie(nullptr);
  65.     cout.tie(nullptr);
  66.     //file();
  67. }
  68. void Sol() {
  69.     int q;
  70.     cin>>q;
  71.     while(q--){
  72.         int n;
  73.         cin>>n;
  74.         string s;
  75.         cin>>s;
  76.         vector<int>p;
  77.         for(int i=0;i<n;i++){
  78.             if(s[i]=='1'){
  79.                 p.push_back(i);
  80.             }
  81.         }
  82.         if(p.empty()){
  83.             cout<<(n+2)/3<<'\n';
  84.             continue;
  85.         }
  86.         int t=p[0], res = p.size();
  87.         if(p[0]>=2){
  88.             res+=(p[0]+1)/3;
  89.         }
  90.         t=n-p.back()-1;
  91.         if(t>=2){
  92.             res+=(t+1)/3;
  93.         }
  94.         for(int i=0;i<p.size()-1;i++){
  95.             int temp=p[i+1]-p[i]-1;
  96.             res+=temp/3;
  97.         }
  98.         cout<<res<<'\n';
  99.     }
  100. }
  101. signed main(){
  102.     Init();
  103.     Sol();
  104.     return 0;
  105. }
  106.  
  107.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5RQU1x
language:
C++ (gcc 8.3)
created:
3 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!