Official

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: