# PROBLEM LINK:

* Author:* John Zakkam

*Aneesh D H, Suryansh Kumar and Siddharth*

**Testers:***John Zakkam*

**Editorialist:**# DIFFICULTY:

CAKEWALK

# PREREQUISITES:

Basic geometry, Basic math.

# PROBLEM:

Given a binary string S consisting of only 1ās and 0ās where 1 represents a **Square** and 0 represents a **Circle** . The *diameter of the circle* and the *side of the square* must be any *integer* (obviously > 0) . You will have to perfectly inscribe the respective geometric figure at S_{i+1} inside of S_{i} where i Ļµ [0,Nā2], **if it is possible** . Note that, it **will not be possible** to inscribe if the dimension of the geometric figure you are **perfectly inscribing** is **not an integer** and you will discard the rest of the string. Find the maximum number of **circles** we can inscribe in a **square** according to the given string.

# KEY OBSERVATION :

For any circle that is perfectly inscribed in a square of any integer dimension, let the side of the square be a, then the circle which should be perfectly inscribed in this square should have a diameter a and if we now want to perfectly inscribe another square in this circle of diameter a, we need a square of side a/\sqrt{2} so, it is not an integer. But by observation, we can inscribe another circle of the same diameter any number of times.

# EXPLANATION:

We check for the first occurrence of a contiguous substring of 1ās in the string then print the count of the number of zeroes present after it .This is only possible when the first character of the binary string is 1, if the first character is 0, then we can directly print 0.

# SOLUTIONS:

## Setter's Solution in C++

```
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int32_t main()
{
ll n;
cin >> n;
vector<string> s(n);
for (int i = 0; i < n; i++)
cin >> s[i];
for (int i = 0; i < s.size(); i++) {
if (s[i][0] == '0')
cout << 0 << endl;
else {
ll ans = 0, flag0 = 0, flag1 = 0;
for (int j = 0; j < s[i].size(); j++) {
if (s[i][j] == '1')
{
if (ans != 0)
break;
flag1 = 1;
}
else
{
flag0 = 1;
if (flag1 and s[i][j] == '0')
ans++;
}
}
cout << ans << endl;
}
}
return 0;
}
```

## Tester's Solution in Python

```
t = int(input())
for _ in range(t):
s = str(input())
if (s[0] == '0'):
print(0)
else:
i=0
ans=0
while(i < len(s) and s[i]=='1'):
i += 1
while(i < len(s) and s[i]=='0'):
ans += 1
i += 1
print(ans)
```

Time Complexity : O(n*b) where b is the maximum length of the binary string.

PS: I tried to explain it as properly as I could. Please let me know if there are any mistakes or if something is unclear. I hope people enjoyed Code Chronicles 2.0.