PROBLEM LINK: https://www.codechef.com/TNP32020/problems/TNP302
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : BEGINNER
PREREQUISITES:
Nill
PROBLEM:
There are N buildings placed in a row and numbered from left to right starting from 0 to N-1. Some of the buildings contain bombs. When a bomb explodes it destroys the building in which it is contained along with its neighbouring buildings.
( i’th building’s neighbours will be (i+1) th and (i-1) th building, except for the end buildings, which will be having only one neighbour )
You are given the string S of length N, where Si is B if the i-th building contains bomb, C otherwise. Find the number of buildings that will be destroyed after all bombs explode. Please note that all bombs explode simultaneously.
QUICK EXPLANATION:
We can iterate through the string and for each character, check whether any of its neighbours is ‘B’.
EXPLANATION:
First, we should get the required input from the user and store the characters in a string. Let’s name it S.
Iterate through each character in the string, and its neighbours can be found by using an index greater or lesser by 1. (neighbors of S[i] would be S[i-1] and S[i+1]). For each character if any of its neighbours or that character itself contains a bomb, then that building would be destroyed. So we can find the number of buildings destroyed by using a counter.
While taking neighbours, note that S[i-1] does not exist for the first element (i=0), and S[i+1] does not exist for the last element(i=n-1).
SOLUTIONS:
Setter's Solution
using namespace std;
int main() {
int T;
cin>>T;
while(T>0)
{
int n,ans=0;
cin>>n;
string st;
cin>>st;
if(st[0]==‘B’||st[1]==‘B’) // first element, i==0
ans+=1;
for(int i=1;i<n-1;i++)
{
if(st[i-1]==‘B’||st[i]==‘B’||st[i+1]==‘B’) // middle elements, 0 < i < n-1
ans+=1;
}
if(st[n-1]==‘B’||st[n-2]==‘B’) // last element, i==n-1
ans+=1;
cout<<ans<<“\n”;
T–;
}
return 0;
}
Tester's Solution
Same Person
Editorialist's Solution
Same Person