December Lunchtime 2021 - Chef Loves 1010 solution - CHEF1010

 

Chef Loves 1010 Problem Code: CHEF1010

Chef is given a binary string S$S$ of length N$N$. As Chef loves 1010$1010$ and he is busy in the preparation of Christmas, he asks you to count the maximum number of continuous substrings 1010$1010$, which Chef can get after reordering symbols in the given string.

As a reminder, a binary string is a string consisting only of 0$0$'s ans 1$1$'s.

Input Format

• The first line of the input contains a single integer T$T$ - the number of test cases. The test cases then follow.
• The first line of the test case contains an integer N$N$ - the length of the binary string.
• The second line of each test case contains the binary string S$S$.

Output Format

For each test case, print maximum number of continuous substrings 1010$1010$, which Chef can get after reordering symbols in the string.

Constraints

• 1≤T≤100$1\le T\le 100$
• 2≤N≤100$2\le N\le 100$
• |S|=N$|S|=N$
• S$S$ is a binary string

Subtasks

• Subtask 1$1$ (100 points): Original constraints

Sample Input 1 

3
2
11
8
11000100
10
0100111100

Sample Output 1 

0
2
4

Explanation

• Test case 1$1$: There are no 0$0$s in the string, so a 1010$1010$ substring is not possible.
• Test case 2$2$: We can reorder string into 01010100$01010100$, in which the first 1010$1010$ starts from index 2$2$, and the second 1010$1010$ starts from index 4$4$. It can be proven that there are no orderings that give the answer larger than 2$2$.

Author:3★kp_010

Editorial:https://discuss.codechef.com/problems/CHEF1010

Tags:Tags are hidden. Show temporarily

---

Update this setting in edit profile

Problem level:Cakewalk

Date Added:19-12-2021

Time Limit:1 secs

Source Limit:50000 Bytes

Languages:CPP14, C, JAVA, PYTH 3.6, CPP17, PYTH, PYP3, CS2, ADA, PYPY, TEXT, PAS fpc, NODEJS, RUBY, PHP, GO, HASK, TCL, PERL, SCALA, LUA, kotlin, BASH, JS, LISP sbcl, rust, PAS gpc, BF, CLOJ, R, D, CAML, FORT, ASM, swift, FS, WSPC, LISP clisp, SQL, SCM guile, PERL6, ERL, CLPS, ICK, NICE, PRLG, ICON, COB, SCM chicken, PIKE, SCM qobi, ST, SQLQ, NEM

Solution

#include <iostream>

#include <string>

using namespace std;

int main()

{

    int tc;

    cin >> tc;

    while (tc--)

    {

        int n;

        string s;

        cin>>n>>s;

        int c0 = 0, c1 = 0;

        for (int i = 0; i < n; i++)

        {

            if (s[i]=='1')

                c1++;

            else

                c0++;

        }

        if ((min(c1,c0)-1)<=0)

        {

            cout<<0<<endl;

        }

        else

        {

            cout<<(min(c1,c0)-1)<<endl; 

        }

    }

    return 0;

}