B - Split? Editorial by en_translator
We mainly explain using C++ codes, but we also have a sample code in Python at the last.
If the first character of \(S\) is 1
, then the answer is No
. We will consider the cases where the first character of \(S\) is 0
.
First, for every column, we find there is a standing pin in the column. Here is an implementation in C++:
string s;
cin >> s;
array<bool, 7> column = {};
column[0] = (s[6] == '1');
column[1] = (s[3] == '1');
column[2] = (s[1] == '1') or (s[7] == '1');
column[3] = (s[0] == '1') or (s[4] == '1');
column[4] = (s[2] == '1') or (s[8] == '1');
column[5] = (s[5] == '1');
column[6] = (s[9] == '1');
You may be confused because the Problem Statement uses 0-based indexing, while the code above uses 1-based. In this case, you may avoid mistakes by writing as follows:
string s;
cin >> s;
s = '$' + s // prepend an arbitrary character to s
array<bool, 7> column = {};
column[0] = (s[7] == '1');
column[1] = (s[4] == '1');
column[2] = (s[2] == '1') or (s[8] == '1');
column[3] = (s[1] == '1') or (s[5] == '1');
column[4] = (s[3] == '1') or (s[9] == '1');
column[5] = (s[6] == '1');
column[6] = (s[10] == '1');
Then, we exhaustively search for every pair of columns satisfying the conditions.
This can be written by the following double for loops:
for (int i = 0; i < 7; ++i) {
for (int j = 0; j < i; ++j) {
if (column[i] and column[j]) {
// If each column has a standing pin,
// check if there is a column where all pins are knocked down
}
}
}
In order to check if there is a column where all the pins are knocked down, we add the third for statement in the if block.
for (int k = j + 1; k < i; ++k) {
if (!column[k]) {
cout << "Yes\n";
return 0;
}
}
In C++, return 0;
means it terminates the process in the main()
function and returns 0
. Thus, we can output Yes
and terminate the execution once a pair of columns satisfying the conditions is found. Otherwise, Yes
may be printed multiple times.
Finally, add a code to output No
when a pair of such columns is not found. Overall, the code becomes as follows:
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
s = '$' + s;
if (s[1] == '1') {
cout << "No\n";
} else {
array<bool, 7> column = {};
column[0] = (s[7] == '1');
column[1] = (s[4] == '1');
column[2] = (s[2] == '1') or (s[8] == '1');
column[3] = (s[1] == '1') or (s[5] == '1');
column[4] = (s[3] == '1') or (s[9] == '1');
column[5] = (s[6] == '1');
column[6] = (s[10] == '1');
for (int i = 0; i < 7; ++i) {
for (int j = 0; j < i; ++j) {
if (column[i] and column[j]) {
for (int k = j + 1; k < i; ++k) {
if (!column[k]) {
cout << "Yes\n";
return 0;
}
}
}
}
}
cout << "No\n";
}
return 0;
}
Sample code (Python) :
def search(column):
for i in range(7):
for j in range(i):
if column[i] and column[j] :
for k in range(j + 1, i):
if not column[k]:
return 'Yes'
return 'No'
s = input()
s = '$' + s
if s[1] == '1':
print('No')
else:
column = [False] * 7
column[0] = (s[7] == '1');
column[1] = (s[4] == '1');
column[2] = (s[2] == '1') or (s[8] == '1');
column[3] = (s[1] == '1') or (s[5] == '1');
column[4] = (s[3] == '1') or (s[9] == '1');
column[5] = (s[6] == '1');
column[6] = (s[10] == '1');
print(search(column))
posted:
last update: