https://www.codechef.com/TNP32020/problems/TNP302

PROBLEM LINK: https://www.codechef.com/TNP32020/problems/TNP302

Practice

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

#include

#include

#include

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