Official

D - Piano Editorial by en_translator


It is sufficient to exhaustively enumerate a substring of \(S\) of length \((W+B)\), and whether each of them has desired number of w and b. A length-\((W+B)\) substring of \(S\) is represented as \(S_lS_{l+1}\dots S_{l+W+B-1}\) for some positive integer \(l\), but it is impossible to enumerate all possible \(l\). Instead, we use the following property:

  • If \(l_1\) and \(l_2\) are equal modulo \(12\), the length-\((W+B)\) substring of \(S\) starting at its \(l_1\)-th character and another starting at its \(l_2\)-th are equal as strings. (Here, \(12\) originates from the repetition unit wbwbwwbwbwbw of \(S\).)

Thus, it is sufficient to check \(1,2,\dots,12\). Thus, the problem can be solved by about \(12(W+B)\) operations.

Sample code (C++):

#include <bits/stdc++.h>

using namespace std;

const string t = "wbwbwwbwbwbw";

int main() {
    int w, b;
    cin >> w >> b;
    for (int i = 0; i < (int) t.size(); i++) {
        int nw = 0, nb = 0;
        for (int j = 0; j < w + b; j++) {
            if (t[(i + j) % t.size()] == 'w') ++nw;
            else ++nb;
        }
        if (w == nw and b == nb) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Sample code (Python) :

t = "wbwbwwbwbwbw"
w, b = map(int, input().split())
for i in range(len(t)):
    nw = 0
    nb = 0
    for j in range(w + b):
        if t[(i + j) % len(t)] == 'w':
            nw += 1
        else:
            nb += 1
    if w == nw and b == nb:
        print("Yes")
        exit(0)
print("No")

posted:
last update: