Little Arjit is the leader of a marvellous fighting army. His team is very good at…
- User
Little Arjit is the leader of a marvellous fighting army. His team is very good at fighting against all their enemies. But like Hound from Game of Thrones, Little Arjit and his entire team is scared of fire. When they see fire, they feel threatened, and scared like a little child, and don’t even mind giving up from a fight.
Now, you’re given the location of the army men of Little Arjit, their enemies, and fire in a pathway. You’ve got to figure out how many enemies will survive after the massacre done by Little Arjit and his army.
Let’s say Little Arjit and his army is denoted by ‘X’, all their enemies are denoted by ‘O’, and fire is denoted as ‘*’
Here’s what happens:
When a X faces an O, i.e., when X is adjacent to O, X kills O. Always. Whenever there will be an O adjacent to X ,X will kill O . The moment X faces a *, he stops, and he cannot move any further.
Given a string containing X, O, * - can you help Little Arjit figure out how many of his enemies will still survive this attack because of fire? Input: First line of input contains a integer T,number of test cases. Next T lines contains a single string S.
Output: For each test case print number of enemies survive after attack.
Constraints: 1 ≤ T ≤ 30 1 ≤ |S| ≤ 100000
SAMPLE INPUT 3 XOOXX XOXXO* XOOOOXOX*
SAMPLE OUTPUT 2 0 4
Assistant
We are given a problem: We have a string S consisting of characters 'X', 'O', and ''. There is a process: X kills adjacent O (i.e., if X and O are next to each other, O gets killed). But when X faces a '' (i.e., if X is adjacent to *?), the description: "The moment X faces a *, he stops, and he cannot move any further." Actually careful: The problem statement: "When a X faces an O, i.e., when X is adjacent to O, X kills O. Always. Whenever there will be an O adjacent to X, X will kill O. The moment X faces a , he stops, and he cannot move any further." There's also mention: "Given a string containing X, O, * - can you help Little Arjit figure out how many of his enemies will still survive this attack because of fire?" So we need to count surviving O's after considering the effect of X's killing adjacent O's but X's are blocked by ''? However it's ambiguous.
We need to interpret the process from typical coding problems. This appears like a variant of "soldiers and enemies" with obstacles. Typically, we have a string; each X kills any O that is either to its left or right unless blocked by a '' or something? The phrasing "The moment X faces a , he stops, and he cannot move any further." suggests that each X has a direction? Or perhaps X kills O's in its line of sight until blocked by ''? Possibly like: X can kill O's on both sides until it hits a fire '' which blocks its range. But the problem says "When a X faces an O, i.e., when X is adjacent to O, X kills O. Always. Whenever there will be an O adjacent to X, X will kill O." That seems like only immediate adjacency matters. But then "The moment X faces a , he stops, and he cannot move any further." This suggests maybe X moves along the path? Or each X has a "facing direction"? Or perhaps it's like: The string is a pathway, and Little Arjit's army (X) is on one side? Actually maybe the problem is: We have a line of positions. X's are soldiers, O's are enemies, * are fire obstacles. When a soldier encounters an enemy adjacent to him, he kills it. But if there's a fire in front of him, he stops moving and doesn't proceed further, so enemies beyond the fire survive. But do X's move? Possibly the scenario: Little Arjit and his army (X) are at some positions, enemies (O) at other positions, and fire () as obstacles. The X's will kill all O's that are adjacent (i.e., immediate neighbors) but also maybe if there is no obstruction, they can kill O's further away? But the problem statement says "adjacent" explicitly: "when X is adjacent to O". So only immediate neighbors. But then why does the fire matter? Because if a fire is adjacent to X, then X stops and cannot move further to kill more enemies, but if X doesn't move, then adjacency is static. So the only O's that get killed are those directly next to an X that are not separated by fire? Actually, adjacency is defined by positions in the string. For two positions i and i+1, they are adjacent. So if X at i, and O at i+1, then X kills that O. That is adjacency, regardless of fire. But fire '*' is a character; if there's a fire at i+1, then X at i is adjacent to fire. According to "The moment X faces a *, he stops, and he cannot move any further." That suggests that maybe X's have a direction of movement: they start from one end and move towards the other? But there is no explicit direction.
Let's examine sample inputs and outputs to infer the rule.
Sample Input: 3 XOOXX XOXXO* XOOOOXOX*
Sample Output: 2 0 4
Test1: S = "XOOXX". Let's list indices: 0:X,1:,2:O,3:O,4:,5:X,6:X.
If we consider only adjacent kills: X at 0 kills any O at adjacent positions (1 and -1, but -1 out of range). Position 1 is *, not O. So no kill from X0. X at 5 kills adjacent positions 4 and 6. Position 4 is *, position 6 is X. So no O killed. X at 6 kills positions 5 and 7 (5 is X, 7 out of range). So no kills. Then all O's survive: positions 2 and 3 = 2 survivors. Output is 2, matches if only adjacency and no kills. But then why include fire? The sample output 2 suggests that these O's survive. But is there any kill? Possibly some O's could be killed if X's can kill beyond adjacency? Let's check: Could X at 0 kill O at 2? That's not adjacent. But maybe if there is no fire in between? Position1 is fire, so blocked, so X cannot kill that O. Similarly, X at 5 could kill O at 3? There is * at 4? Actually positions: X5 at index5, to left index4 is *, so maybe blocked. X6 at index6, left index5 is X, then index4 *, then O at 3. Possibly if X can kill O's to left until encountering fire? But if that were the case, X6 might kill O3? But there is an X at 5, then * at 4, then O at3. The presence of X at 5 might be considered as something? The rule "X stops when faces a " means that if X is trying to move (or its killing range) is blocked by a . So maybe each X can kill O's on both sides until it encounters a fire '', but also any X's themselves may block? But the problem says "The moment X faces a , he stops, and he cannot move any further." It doesn't say X blocks for other X's. So perhaps each X kills all O's on its left side until it hits a '' (fire) or the beginning of string, and similarly on its right side until it hits a ''? But then the sample1: X at index0 can kill O's to its right until it sees a fire. It sees fire at index1, so stops, so cannot kill O at index2. So O2 survives. X at index5: to its left, positions index4 is fire, stops, cannot kill O3. To its right, index6 is X, continues? Actually it might kill O's to right until fire. Index6 is X, not O or fire; it continues scanning? Possibly it can kill O's beyond if not blocked. But index6 is X, but that's another soldier; does it block? The problem doesn't say X blocks; it only says fire stops. So maybe X can see through other X's? But then X5 to right: index6 X, then string ends; no O. So no kills. X6: to left, index5 X, index4 fire stops? Actually if X6 scans left, index5 is X, then index4 is fire; but does the fire stop at index4? If scanning left, it sees index5 (X), then index4 (fire) and stops, so it doesn't see O3. To right, end of string. So no kills. So total kills = 0, survivors=2, matches output 2.
But sample2: S = "XOXXO*". Let's index: 0:X,1:,2:O,3:X,4:,5:X,6:O,7:*.
If we apply rule: each X kills all O's on both sides until fire (but not blocked by X). Let's compute survivors.
X at 0: right side: index1 is *, so stops. left side: none. So kills none. X at 3: left side: index2 is O -> kill it. Continue scanning? After killing O at index2, does it continue? The rule: "When a X faces an O, i.e., when X is adjacent to O, X kills O." It says "adjacent". But if we interpret as "X can kill any O that is reachable without crossing a fire", then it could kill multiple O's. But typical problems: X kills all O's until a * in either direction. But is that consistent? Let's see. X at 3: scanning left, index2 O, kill. Next left index1 is *, so stop. So cannot kill further left. Right side: index4 is *, stop. So from X3, kill O at index2 only. X at 5: left side: index4 is *, stop. So no left kills. Right side: index6 is O, kill it. Next index7 is *, stop. So kill O at index6. Thus all O's (positions 2 and 6) are killed. So survivors=0, matches output 0.
So far consistent with "X kills all O's in both directions until hitting a fire *". But note: X at 0 and X at 5 both didn't kill because fire adjacent blocked them from seeing O's beyond. Also X at 3 killed O at 2, X at 5 killed O at 6.
Now sample3: S = "XOOOOXOX*". Let's write indices and characters:
0:X 1:* 2:O 3:O 4:* 5:O 6:O 7:* 8:X 9:* 10:O 11:X 12:* (since string ends with ? Let's count: "XOOOOXOX". length? Let's compute: characters: X, *, O, O, *, O, O, *, X, *, O, X, * => 13 characters. So indices 0-12.
Let's list: 0: X 1: * 2: O 3: O 4: * 5: O 6: O 7: * 8: X 9: * 10: O 11: X 12: *
Now apply rule: each X kills all O's on both sides until encountering a fire '*' (i.e., when scanning left or right, stop when * is encountered; but do we stop when encountering another X? Probably not; because only fire stops X's "movement". So X can see through other X's.
Now we need to compute which O's survive.
First, note that O's that are not within the "kill zones" of any X (i.e., are separated from an X by a fire) will survive.
We'll simulate kills:
X at index0: left: none. right: index1 is *, stop. So kills none.
X at index8: left: scan indices 7,6,5,4,3,2,1,0. But we stop when we hit a fire. Starting at index8, left neighbor index7 is *, so stop immediately. So left kills none. Right: index9 is *, stop. So kills none. So X8 kills none.
X at index11: left: index10 is O -> kill. Continue left? After index10, next left index9 is *, so stop. So kill O10. Right: index12 is *, stop. So kills none beyond. So X11 kills O10.
But are there any other kills? Possibly X at index0 could kill O's to the right if not blocked? It's blocked by fire at index1, so none. X at index8 blocked by fire both sides. X at index11 killed O10. So surviving O's: indices 2,3,5,6? That's four O's (2,3,5,6). That's 4 survivors. Output is 4. Matches.
Thus the interpretation: For each X, all O's that are on its immediate left or right, and not blocked by any '' (i.e., in the continuous segment of non-'' characters on either side until the first '' or end of string), get killed? Actually from examples, X kills all O's on a side until it sees a ''. But wait: In sample3, X11 kills O10 (immediate left). But also if there were O's further left beyond a fire, they would not be killed. That's consistent.
But there is nuance: In sample2, X3 kills O2 (left), and X5 kills O6 (right). That's also consistent. Also note that X3 and X5 are not blocked by each other; but they don't kill O's beyond because of fire. Also in sample2, X0 didn't kill O2 because there is fire at index1. If the rule was only immediate adjacency, X0 would not kill O2 (since not adjacent). So that is also consistent. Actually if only adjacency, X0 would not kill O2 (since O2 is at distance 2, not adjacent). X3 would kill O2 because adjacent (index2 and 3 are adjacent), and X5 would kill O6 (adjacent). So also only adjacency would give same result for sample2: kills O2 and O6 -> survivors 0. For sample1, adjacency: X0 no kill, X5 no kill, X6 no kill, survivors 2. That also matches. For sample3, adjacency: X0: adjacent to index1 () no; X8: adjacent to index7() and index9() no; X11: adjacent to index10(O) kills O10, adjacent to index12() no; So kills O10, survivors O2,O3,O5,O6 = 4. Also matches. So both the "adjacent only" and the "kill all until fire" interpretations produce the same results for these samples? Let's check: In sample3, X11 is adjacent to O10 and kills it. No other X is adjacent to any O. So indeed adjacency works. In sample2, X3 adjacent to O2, X5 adjacent to O6. X0 adjacent to index1 *, no. So adjacency works. In sample1, no X is adjacent to any O because X0 adjacent to *, X5 adjacent to * and X, X6 adjacent to X. So survivors 2. So both interpretations yield same.
But maybe there are scenarios where X can kill O that is not immediately adjacent but separated by other X or O without fire. For example: "XOO*"? If rule is adjacency only, X at index0 kills only if O at index1; if index1 is O, then kill; O at index2 not killed. If rule is kill all until fire, X0 would kill O at index1 and O at index2 (since no fire until * at index3). That would produce different results. Let's check: Suppose S = "XOO*". According to "adjacent only", X kills O at index1? Actually adjacent means index0 and index1 are adjacent: yes O at index1, kill. O at index2 not adjacent, survive. So survivors = 1 O (at index2). According to "kill all until fire", X0 kills O's on right until fire at index3, so kills O1 and O2 -> survivors = 0. So different. Which one is likely intended? The problem statement: "When a X faces an O, i.e., when X is adjacent to O, X kills O. Always. Whenever there will be an O adjacent to X, X will kill O." That explicitly says adjacent. Then: "The moment X faces a *, he stops, and he cannot move any further." That suggests there is movement, not just adjacency. Perhaps the story: X moves along the path; as he moves, if he meets O, he kills it; but if he meets *, he stops moving and cannot go further. But the problem doesn't specify initial positions or direction of movement. Perhaps it's like: The string represents the pathway. Little Arjit's army (X) are placed somewhere. They will move towards one direction? Or maybe they all move together? Actually the problem might be a known problem: "The New War" or something. Let's think: Possibly the interpretation is: The X's will kill all O's that are to the right of them until they encounter a fire *, but also to the left? Or maybe each X has a direction (say they are all facing right)? But the problem doesn't mention direction. The phrase "faces" may mean "when X is next to an O, i.e., adjacent, X kills O" and "when X faces a *, he stops" meaning if X is adjacent to *, he stops moving further. This indicates X might be moving along the string. Maybe the process: X moves from left to right? But then there are multiple X's. Could be: Starting from the leftmost X, it moves rightwards, killing any O it encounters, until it encounters a * then it stops; but then other X's may also move? This seems complicated.
Let's search memory: This problem might be from hackerearth or similar: "Little Arjit and his army" or "Fight against fire". I recall a problem: Given a string of X, O, *, count surviving O's after the process: Each X kills all O's on its left and right until it hits a *. This is similar to "Bear and Compressing" or "Dragon". Actually I think I've seen a problem: "Little Arjit and his army" where we need to count O's that are not within the range of X's where range is limited by *. That is basically: For each X, all O's in its contiguous segment (delimited by *) are killed. But careful: If there are multiple X's in a segment, they might kill all O's in that segment. The problem: "The moment X faces a *, he stops, and he cannot move any further." That suggests each X's killing range extends until a * in each direction, but he cannot cross a *.
But wait, if there are multiple X's in the same segment, does that cause overkill? But we just need to count survivors, so O's that are not in any X's kill range survive. So the rule: All O's that are in the same "block" (contiguous sequence of characters not containing '') as at least one X, get killed. Because if there is an X in a block, it can move (i.e., kill) throughout that block until it hits a * on either side. So it can kill all O's in that block. That would be a simpler interpretation: Partition the string into segments separated by ''. In each segment, if there is at least one X, then all O's in that segment are killed (since X can move and kill all enemies in that segment). If there is no X in a segment, then all O's survive. Then count total O's in segments with no X. Is this consistent with the samples? Let's test:
Sample1: "XOOXX". Split by '*': segments: "X", "OO", "XX". In segment "X": has X, so any O? none. "OO": has O but no X -> all O's survive (2). "XX": has X but no O. So survivors = 2. Output 2. OK.
Sample2: "XOXXO*". Split: segments: "X", "OX", "XO", ""? Actually trailing *? The string ends with *, so after last *, empty segment maybe ignore. So segments: before first *: "X" (indices 0). Then between * at 1 and * at 4: substring indices 2-3 => "OX". Then between * at 4 and * at 7: substring indices 5-6 => "XO". Then after last *, empty. Now segment "X": has X, no O. Segment "OX": has X and O -> since there is X, all O's killed (so O at index2 killed). Segment "XO": has X and O -> all O's killed (O at index6 killed). Survivors = 0. Output 0. OK.
Sample3: "XOOOOXOX*". Split by '*': segments: 1: before first *: indices0 -> "X". 2: between *1 and *4: indices2-3 -> "OO". 3: between *4 and *7: indices5-6 -> "OO". 4: between *7 and *9: index8 -> "X". 5: between *9 and *12: indices10-11 -> "OX". Actually there is * at index9 and * at index12. So indices 10 and 11: "O" and "X"? But note indices: 10:O, 11:X. So segment "OX". 6: after last *: maybe empty? after *12, end, empty. Segments: "X" (has X, no O), "OO" (no X) -> all O survive (2), "OO" (no X) -> survive (2), "X" (has X, no O), "OX" (has X, so O killed). So total survivors = 2+2=4. Output 4. OK.
This segmentation approach matches all samples perfectly. And it is simpler and aligns with "The moment X faces a *, he stops" i.e., X cannot cross a fire, so its influence is limited to the contiguous block it's in. And "When a X faces an O, i.e., when X is adjacent to O, X kills O. Always." But it also kills O's not adjacent? Actually if X is in the same block, it can move to them? But the problem statement says "adjacent", but in the block interpretation, X kills all O's in the block even if not adjacent. However the statement might be a simplified description; the actual behavior is that X will kill any enemy it can reach without encountering fire, which includes all enemies in the same segment. Since X can move along the segment and kill O's as it encounters them. The phrase "adjacent" might be a misinterpretation; maybe they meant "when X is able to face an O". But given the segmentation approach yields correct sample outputs and is a common type of problem (like count survivors in each segment without X), this is likely the intended solution.
Moreover, the problem constraints: |S| up to 100,000 per test case, and T up to 30. So total length up to 3 million, which is fine. We need an O(n) per test case solution.
Thus solution: For each test case string S, iterate and split by '' into segments. For each segment, count number of O's and check if there is any X. If no X, add count of O's to survivors; else ignore. Or we can simulate in one pass: maintain counters for current segment: countO, hasX. When we see '', we process the current segment: if not hasX, survivors += countO; then reset countO=0, hasX=False. Continue. Also handle segments at start and end (implicitly by resetting at '*' and at end of string). Complexity O(n).
Edge cases: consecutive '*' produce empty segments, which we can ignore because countO=0, hasX=False, survivors unchanged. So fine.
Thus answer is survivors.
But wait, there is nuance: What about scenario where X and O are in same segment, but there is also a '*' within? That would split the segment. So it's okay.
Now, confirm with some extra test cases:
Case: "XOO*". Split: segment1: "XOO" -> has X, so all O's (2) killed. segment2: after *, "" -> empty. So survivors=0. Under segmentation rule, survivors 0. But if only adjacency, survivors would be 1 O at index2? Actually adjacency only: X at 0 kills O at 1, but not O at 2 -> survivors=1. So the problem's intended answer might be 0? I'd need to see if problem statement clarifies. Let's look at the original problem maybe. But I don't have it. However the segmentation interpretation is natural given the mention of fire as blocker. And the phrase "The moment X faces a *, he stops, and he cannot move any further." suggests movement across positions. If X is in a block, it can move until a fire, killing O's it meets. So indeed X kills all O's in its block.
Additionally, consider scenario: "O*X". Under segmentation: segment1: "O" (no X) survive (1). segment2: "X" (has X, no O) survivors=0 total=1. If only adjacency: X kills only if adjacent O: X at index2 is adjacent to index1 , no O. So O at index0 survives. So both give 1. Another scenario: "OXO". Segment1: "OX" (has X) so O at index0 killed; segment2: "O" (no X) survive 1; total 1. Adjacency: X at index1 adjacent to O at index0 kills it; O at index3 not adjacent to any X, survive 1 -> same.
Scenario: "XOX". Segment: "X", "O", "X". "O" segment has no X, so survives 1. Adjacency: X at index0 kills none; O at index2 not adjacent (index1 * between), survive; X at index4 kills none; total 1. Same.
Scenario: "XO*OX". Segment1: "XO" has X -> both killed? Actually O at index1 killed; segment2: "OX" has X -> O at index3 killed; survivors=0. Adjacency: X at index0 kills O at index1 (adjacent). X at index4 kills O at index3 (adjacent). So also 0.
Thus many cases same.
Where they differ: when there is a block with X and multiple O's, and O's not adjacent but separated by other O's or X? For instance "XOO". No fire. Segmentation: entire string is one block with X, so all O's killed. Adjacency: only O at index1 is adjacent, O at index2 not adjacent because adjacent to index1 (O) and not X. So survivors 1. So this would be a distinguishing case. Which output is expected? Let's see if the problem statement gives any additional clue.
Read the problem statement again: "Little Arjit is the leader of a marvellous fighting army. His team is very good at fighting against all their enemies. But like Hound from Game of Thrones, Little Arjit and his entire team is scared of fire. When they see fire, they feel threatened, and scared like a little child, and don’t even mind giving up from a fight.
Now, you’re given the location of the army men of Little Arjit, their enemies, and fire in a pathway. You’ve got to figure out how many enemies will survive after the massacre done by Little Arjit and his army.
Let’s say Little Arjit and his army is denoted by ‘X’, all their enemies are denoted by ‘O’, and fire is denoted as ‘*’
Here’s what happens:
When a X faces an O, i.e., when X is adjacent to O, X kills O. Always. Whenever there will be an O adjacent to X ,X will kill O . The moment X faces a *, he stops, and he cannot move any further."
It says: "When a X faces an O, i.e., when X is adjacent to O, X kills O. Always. Whenever there will be an O adjacent to X, X will kill O ." That is pretty explicit: only adjacent. But then "The moment X faces a *, he stops, and he cannot move any further." This seems to indicate that X might be moving, and when it encounters a * it stops moving further. But if X is moving, it might not be stationary; it might be advancing along the pathway, encountering O's and killing them as it goes. The phrase "faces" could mean "when X is next to an O" (adjacent) and "when X is next to a *" (adjacent). So it might not be about movement; it might be about facing direction. Actually maybe the model is: X are positioned at some points; they can "face" left or right? But not indicated.
Let's think of typical problems: Often there is a problem where you have a string with 'R', 'L', and something else, where R moves right, L moves left, etc. But here it's X, O, . Another known problem: "Little Arjit and his army" is a Hackerearth problem. I recall a Hackerearth problem: "Little Arjit and his fight with monsters" maybe? Let's search memory: Actually I recall a Hackerearth problem named "Little Arjit and his army" where the solution was to count O's not in segments with X. Because I've seen editorial: split by '', count O's in segments without X. Yes, I think that's it.
Let me attempt to recall: There's a problem "Little Arjit and his army" with sample I/O exactly as given. I've definitely seen this problem before. And I remember the solution: For each segment delimited by '*', if there is at least one X, all O's in that segment die; otherwise, they survive. So yes, that is the intended solution.
Thus the correct interpretation: X kills all enemies in its region (until blocked by fire). The "adjacent" wording is perhaps misleading, but the segmentation approach matches samples and is common.
Therefore we should implement the segmentation method.
Now we need to produce solution.
We'll read T, then for each test case, read string S. Then iterate over characters, maintaining count of O's in current segment and a flag if X is present. When we encounter '', we finalize segment: if not hasX, then survivors += countO; reset countO=0, hasX=False. After loop, we need to handle the last segment (if not ended with ''): after loop, we finalize again.
Make sure to handle large input: use sys.stdin.read for speed perhaps.
Now let's test with some custom:
- Input: "XOO" -> survivors? According to segmentation (no *), whole string is one segment, has X, so all O killed, survivors 0. But if we consider adjacency, survivors 1. Which one will be expected? The problem didn't provide such test, but segmentation is likely correct. However let's see if there's any hidden nuance: In the problem, they talk about "adjacent". Could it be that X only kills adjacent O, but if there are multiple X's, they might kill O's that become adjacent after previous kills? But no, O's are static. But maybe X moves? If X moves, it could move into positions and kill O's that become adjacent. But the process isn't described as moving. So segmentation is simpler.
Given the constraints, segmentation solution is O(n) and matches samples.
Another check: If the string is "O*X", segmentation gives survivors 1; if adjacency gives 1. So both same.
What about "XOO"? Segmentation: segments: "X", "O", "O". "O" segments have no X, both survive -> survivors 2. Adjacency: X at index0 kills none; O at index2 and index4 not adjacent to any X -> survivors 2. Same.
What about "XOX": Segmentation (no *): one segment with X, so both O's killed -> survivors 0. Adjacency: X at 0 kills O at 1 (adjacent); X at 2 kills O at 1 also (adjacent). So O at 1 killed; survivors 0. Same.
What about "XOOX": segmentation: one segment with X (since no *), both O's killed -> survivors 0. Adjacency: X at 0 kills O at 1; X at 3 kills O at 2; O at 1 and 2 both killed; survivors 0. Same? Actually X at 0 kills O at 1 (adjacent). X at 3 kills O at 2 (adjacent). So both O's dead. So still 0.
Thus only case where difference occurs is when O's are not adjacent to any X but still in same segment because there are other O's between them? For example "XOOO": adjacency: X kills O at index1 only; O at index2 and 3 survive? Actually check: X at index0 kills O at index1 (adjacent). O at index2 is adjacent to index1 (O) and index3 (O), not X. O at index3 adjacent to index2. So survivors = 2. Segmentation: whole segment "XOOO" has X, so all O's killed -> survivors 0. So difference. Which is correct? Let's see if the problem statement would allow X to kill non-adjacent enemies. It says "When a X faces an O, i.e., when X is adjacent to O, X kills O. Always." That's explicit about adjacent. It doesn't say X can kill enemies further away. So "XOOO" under that rule: X kills only the immediate O, leaving two O's alive. So survivors=2. But segmentation kills all three.
Now, does the problem provide such an example? Not in sample. However, the sample3 includes segments "OO" that have no X, so they survive. If there were "XOO" as a segment, segmentation would kill all O. But does the problem include such scenario? Possibly, but we need to decide.
Let's search online memory: I've seen many problems with similar description: "Little Arjit and his army" with string of X, O, *. The solution is indeed to count O's in segments without X. Actually I recall a problem: "Little Arjit and his army" from Hackerearth. I think the editorial says: "We need to count the number of O's that are not in the same group as any X, where groups are separated by *." Let's confirm by trying to recall the exact problem statement from Hackerearth. It might have been in a contest "Codathon" or "March Circuits". I remember a problem: "Little Arjit and his fight" maybe. But I'm not 100% sure.
Nevertheless, the phrasing "The moment X faces a *, he stops, and he cannot move any further." suggests that X can move along the pathway and kill enemies until encountering a fire. So if X is in a segment without fire, it can move throughout the segment, encountering and killing all enemies there. So it would kill all O's in that segment. That matches segmentation. Also, the phrase "faces" might mean "encounters while moving". But then they also say "When a X faces an O, i.e., when X is adjacent to O". That is confusing: they equate "faces" with "adjacent". So maybe they consider that X can move and when it moves to a cell, it becomes adjacent to the next cell? Hmm.
Alternatively, maybe the process is: X can only kill O if they are immediately next to each other, but X can also move? Actually, perhaps the entire army moves as a group. But the description: "When a X faces an O, i.e., when X is adjacent to O, X kills O. Always. Whenever there will be an O adjacent to X, X will kill O. The moment X faces a *, he stops, and he cannot move any further." This could be interpreted as: X starts at its position and moves in a direction? Or maybe each X can look left and right. When it sees an O adjacent, it kills it; but if there is a * adjacent, it doesn't look further. That would be exactly the "adjacent only" rule. However, the phrase "cannot move any further" suggests movement, not just looking.
Let's read carefully: "The moment X faces a *, he stops, and he cannot move any further." If X is stationary, it doesn't move. So the word "move" indicates that X is moving along the pathway. So likely X is moving along the string (perhaps from left to right) and killing enemies as they come, but stops when encountering fire. But then multiple X's? Actually maybe it's like: The army (all X's) are together; they start from left end? Or maybe each X individually? The problem might be that we have a single entity: "Little Arjit and his army" denoted by X (maybe a single X representing the whole army). But the sample strings have multiple X's. For instance, sample1 has two X's at the end. So it's not a single X; there can be many. So each X might be an individual soldier.
If each X can move both directions? Possibly they can move left or right? The phrase "faces" is ambiguous.
Given the segmentation solution is elegant and fits samples, I'm leaning towards that.
Let's test "XOO" with segmentation: would we expect survivors? Possibly the answer is 0. But does that conflict with the adjacency description? It might be that the problem expects segmentation. However, to be absolutely sure, I'll search for the original problem or think about the name. "Little Arjit" is a character often used in Hackerearth problems. I recall a problem "Little Arjit and his army" where the solution is indeed to split by '*'. I've seen a similar problem: "The New Army" maybe.
I can also derive logically: If X is not blocked by fire, it can continue moving and kill all O's in that continuous section. The phrase "When a X faces an O, i.e., when X is adjacent to O" might be just an example, but they intend that as long as X can reach O without encountering fire, X will kill it, because X will move and become adjacent. But they simplified by saying adjacent because in a continuous segment without fire, X can move step by step, killing each O as it becomes adjacent. So effectively all O's in that segment die. So segmentation is correct.
Thus we will adopt segmentation.
Now, we need to implement solution accordingly.
Edge Cases:
- Empty string? length >=1.
- All '*' => survivors 0.
- No '*' => whole string is one segment. If there is any X, all O's die; else survivors = number of O's.
- Very long strings.
Implementation plan:
Pseudo:
def solve(): import sys data = sys.stdin.read().split() if not data: return t = int(data[0]) out = [] idx = 1 for _ in range(t): s = data[idx] idx += 1 survivors = 0 count_o = 0 has_x = False for ch in s: if ch == '*': if not has_x: survivors += count_o count_o = 0 has_x = False else: if ch == 'O': count_o += 1 elif ch == 'X': has_x = True # after loop, handle last segment if not has_x: survivors += count_o out.append(str(survivors)) sys.stdout.write("\n".join(out))
But careful: The reset on '*' should also reset count_o and has_x. That's done. After loop, we process the trailing segment.
Test with given samples:
Case1: "XOOXX" Iteration: start: count_o=0, has_x=False. ch='X': else, ch=='X' -> has_x=True ch='': at , segment: has_x=True => survivors unchanged (0). Reset count_o=0, has_x=False. ch='O': count_o=1 ch='O': count_o=2 ch='': segment: has_x=False => survivors+=2 => survivors=2. Reset count_o=0, has_x=False. ch='X': has_x=True ch='X': has_x already True (stay True) End: last segment (after last ''): has_x=True => survivors unchanged. Output 2. Good.
Case2: "XOXXO*" Start: ch='X': has_x=True *: segment: has_x True => no add. reset. ch='O': count_o=1 ch='X': has_x=True *: segment: has_x True => no add (count_o=1 ignored). reset. ch='X': has_x=True ch='O': count_o=1 *: segment: has_x True => no add. reset. End: survivors=0. Good.
Case3: "XOOOOXOX*" Processing: X: has_x True *: segment with has_x True -> ignore. reset. O: count_o=1 O: count_o=2 *: segment: has_x False => survivors+=2 (2). reset. O: count_o=1 O: count_o=2 *: segment: has_x False => survivors+=2 (4). reset. X: has_x True *: segment: has_x True -> ignore. reset. O: count_o=1 X: has_x True *: segment: has_x True -> ignore. reset. End: survivors=4. Good.
Thus works.
Complexities: O(n) per test.
Now, possible pitfalls: The input may have spaces? The sample shows each test case string on its own line. Using split() reads them fine. Strings may contain only 'X','O','*'. So okay.
Now, is there any scenario where an O might be killed by multiple X? Not relevant; we just need survivors.
Thus final answer.
But I'll consider alternative solution: If segmentation is not intended, maybe it's more like: For each O, check if there is an X to its left without a * in between, or to its right without a * in between. That would also be O(n) but with scanning left and right. That would be like checking if O is "visible" to an X without fire blocking. That would also kill O if there is an X on either side with no * between. That is essentially the same as: In the same fire-separated segment, if there is at least one X, then all O's are visible (since there is no fire in the segment, any X can see any O? Not necessarily: if there are multiple X's, but if there is an X somewhere in the segment, can it see all O's? If the segment is a contiguous block without , then any X can reach any O by moving stepwise, but for "visibility" without moving, just line-of-sight, does an X kill an O if there is no * between them, even if there are other characters? The problem statement says "adjacent". So maybe the line-of-sight is only immediate adjacency. But if we consider line-of-sight (i.e., X can kill O if there is no * between them), then O would be killed if there exists an X to its left or right such that all characters between them are not ''. But then the condition is: In each segment (block between *), if there is at least one X, then any O in that segment has a clear line-of-sight to some X? Not necessarily: Suppose segment "OXO". The left X? Actually characters: O, X, O. The O at index0: to its right there is X at index1 with no * in between, so O would be killed. The O at index2: left has X at index1, also killed. So all O's killed. Now "XOO": O at index1: adjacent to X, killed. O at index2: is there an X to its left without *? The X at index0 is to its left, and the characters between are index1 (O) which is not *, so there is no * between, so O at index2 would be killed under line-of-sight rule. That yields kill all O's. So line-of-sight without adjacency (i.e., X kills O if there is any X in the same segment, regardless of distance) is exactly the segmentation rule: all O's die if there is at least one X in the segment. But what about segment "OOX"? Similarly, O's killed. So line-of-sight equals segmentation. However, adjacency rule is more restrictive: only if O is next to an X. So the ambiguity is between adjacency and line-of-sight (range until *). Since the problem mentions "The moment X faces a *, he stops, and he cannot move any further." That suggests X can "move" (or "see") until it hits a *; so line-of-sight fits better.
Thus I'm convinced segmentation is correct.
Now, final code. We'll provide explanation.
But before final, consider a test case that might be ambiguous: "OXO". Segmentation: segments "O", "X", "O". "O" without X survive (both O survive) => survivors=2. Under line-of-sight: O at index0: to its right, there is a * at index1, so blocked, no X sees it; left none -> survives. O at index4: left * at index3 blocks, no X sees -> survives. So survivors=2. Same. So fine.
Now what about "XOO*X"? segments: "X", "O", "O", "X". O segments survive -> 2. line-of-sight: each O not adjacent to X because * blocks -> survive. So same.
Now "X O O X" (no fire): segmentation: one segment with X, all O die. line-of-sight: O's are between X's, so each O has X on left or right without fire, so die. So survivors=0. adjacency: X at left kills first O, X at right kills last O, middle O? If more than two O's, some survive. So adjacency differs. So if the problem had a test like "XOOX", both segmentation and line-of-sight give 0, adjacency gives 0 (since O at index1 adjacent to X at index0; O at index2 adjacent to X at index3). Actually "XOOX": indices:0:X,1:O,2:O,3:X. O at index1 adjacent to X0; O at index2 adjacent to X3; so both killed. So survivors=0. So adjacency also gives 0. To differentiate, we need more O's not adjacent to any X, e.g., "XOOO". Adjacent: only one O adjacent (index1) killed, survivors=2. Segmentation: all killed. So that's the key differentiator. So if such test case appears, which output is expected? The problem may include such test. Let's see if there is any clue from the problem title: "Little Arjit and his army" and "fire". Maybe the fire is the only thing that stops them, so without fire they can move freely and kill all enemies. So "XOOO" -> all O's die. That seems plausible.
Also, note the sample output for third test is 4, which is based on segments with O's and no X. In that sample, there were segments "OO" and "OO" without X, so survivors 4. So they explicitly have O's that survive because they are isolated from X by fire. In a scenario without fire, they would not survive. So the idea is that fire protects enemies because it stops X. So if there is no fire, X can kill all enemies in the entire pathway. So the rule that X kills all O's in its block (no fire) makes sense.
Therefore I'll go with segmentation.
Now, I'll write final solution in Python.
But we must be careful: The input may have newline after T, and each string. Using sys.stdin.read().split() is fine.
Time complexity: O(total length) ~ 3e6, fine.
Now, produce final answer.
But I'll also consider an alternative implementation: using split('*') method, but that would create substrings and allocate memory, but it's also O(n) and fine for 1e5. But careful: Python's split on a long string may be okay. However, using manual iteration is efficient and straightforward.
I'll implement manual iteration.
Now, write final solution with explanation.
Edge Cases: Possibly the string can have leading or trailing ''. Our resetting on '' handles leading : at first char if '', we process current segment which is empty (count_o=0, has_x=False) -> survivors unchanged. Similarly multiple '*' produce empty segments. So fine.
Now final code.
But the problem requires to print number of enemies survive after attack for each test case.
Thus final answer.
I'll output code.
Now, to be thorough, let's test with "XOOO": manual: count_o=0,has_x=False. ch='X': has_x=True. ch='O': count_o=1. ch='O': count_o=2. ch='O': count_o=3. End: last segment: has_x=True -> survivors unchanged (0). So output 0. Good.
If adjacency intended would be 2; but segmentation says 0.
Now, is there any official test likely? I'm leaning segmentation.
Thus final answer.
Now, write final solution with proper comments.
--- Let's produce final answer. ```python
import sys
def solve() -> None: data = sys.stdin.read().split() if not data: return t = int(data[0]) out = [] idx = 1 for _ in range(t): s = data[idx] idx += 1
survivors = 0 # answer for this test case cnt_o = 0 # number of 'O' in current segment has_x = False # whether current segment contains an 'X' for ch in s: if ch == '*': # end of a segment: if no X, all O survive if not has_x: survivors += cnt_o # reset for next segment cnt_o = 0 has_x = False else: if ch == 'O': cnt_o += 1 elif ch == 'X': has_x = True # last segment (if the string does not end with '*') if not has_x: survivors += cnt_o out.append(str(survivors)) sys.stdout.write("\n".join(out))if name == "main": solve()