Villages and Tribes
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
There are n villages in a line in an area. There are two kinds of tribes A and B that reside there. A village can be either empty or occupied by one of the tribes. An empty village is said to be controlled by a tribe of village A if it is surrounded by villages of tribes A from the left and from the right. Same goes for the tribe B.
Find out the number of villages that are either occupied by or controlled by tribes A and B, respectively.
The first line of the input contains an integer T denoting the number of test cases.
The first line of the input contains a string s denoting the configuration of the villages, each character of which can be 'A', 'B' or '.'.
For each test case, output two space-separated integers denoting the number of villages either occupied by or controlled by tribe A and B, respectively.
- 1 ≤ T ≤ 20
- 1 ≤ |s| ≤ 105
- Subtask #1 (40 points): 1 ≤ |s| ≤ 103
- Subtask #2 (60 points): Original constraints
Input 4 A..A..B...B ..A.. A....A ..B..B..B.. Output 4 5 1 0 6 0 0 7
|Tags||admin2, cakewalk, nov17|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.