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: