Header Ads Widget

Split houses | Practice problem Hackerearth Solution

Rajnish Tripathi 23:30

 Problem:-

You live in a village. The village can be represented as a line that contains n grids. Each grid can be denoted as a house that is marked as H or a blank space that is marked as ..

A person lives in each house. A person can move to a grid if it is adjacent to that person. Therefore, the grid must be present on the left and right side of that person.

Now, you are required to put some fences that can be marked as B on some blank spaces so that the village can be divided into several pieces. A person cannot walk past a fence but can walk through a house. 

You are required to divide the house based on the following rules:

  • A person cannot reach a house that does not belong to that specific person.
  • The number of grids each person can reach is the same and it includes the grid in which the house is situated.
  • In order to show that you are enthusiastic and if there are many answers, then you are required to print the one where most fences are placed.

Your task is to decide whether there is a possible solution. Print the possible solution.

Input format

  • First line: An integer n that represents the number of grids (1≤n≤20)
  • Second line: n characters that indicate the villages that are represented as H or . 

Output format

The output must be printed in the following format:

  • First line: If possible, then print YES. Otherwise, print NO.
  • Second line: If the answer is YES, then print the way to do so.
Sample Input
5
H...H
Sample Output
YES
HBBBH
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Each person can reach 1 grid. Each person can reach his own houses only.

Note that HB.BH also works. Each person can reach only 1 grid.

But H..BH does not work. Because the first person can reach 3 grids but the second one can only reach 1.

H...H does not work either. The first person can reach the second person's house which is bad.

So you need to print HBBBH because it has the most fences.

Code:-

 Here I am going to give you two solutions first one is by using C language and second one is by using c++ which you can submit in c++14 and c++17 also .

Solution 2 (By using C language):- 

#include<stdio.h>
int main()
{
    int n,flag=0;
    scanf("%d",&n);
    char c[n];
    scanf("%s",c);
    for(int i=0;i<strlen(c);i++)
    {
        if(c[i]=='H'&&c[i+1]=='H')
        {
            flag=1;
        }
        else
        {
            if(c[i]=='.')
            c[i]='B';
        }
    }
    if(flag==1)
    {
    printf("NO\n");
    }
    else
{
    printf("YES\n");
    printf("%s",c);
}
}

Solution 2 (By using C++ language):-

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int g,d=0;
    string c;
    //Number of Grids
    cin>>g;
    cin>>c;
    for(int i=0;i<g-1;i++)
    {
        if(c[i]=='H'&&c[i+1]!='.')
        {
            cout<<"NO"<<endl;
            d=1;
            break;
        }
        if(c[i]=='.')
        c[i]='B';
    }
    if(d==0)
    {
        cout<<"YES"<<endl;
        if(c[g-1]=='.')
        c[g-1]='B';
        cout<<c<<endl;
    }
}

Recommended post:-




Tags:

Post a Comment

0 Comments