PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : EASY
PREREQUISITES:
Nill
PROBLEM:
You are given a string of N digits. Place a minimum number of opening and closing brackets into it such that each digit x is enclosed within exactly x pairs of matching brackets.
QUICK EXPLANATION:
Iterate through the string, by keeping the count of the required number of brackets, and add brackets as needed.
EXPLANATION:
Keep a counter, initialised to 0, and iterate through every character. Convert it into int (You can convert by subtracting 48 through ascii) and if the number is greater than the counter, insert an opening bracket before the character and increment the counter. Repeat it until counter = the number and then continue through the rest of the numbers.
If any number is less than the counter, add a closing bracket after the character and decrease the counter by one. Repeat until counter = the number.
SOLUTIONS:
Setter's Solution
#include
#include
#include
#include
#include
using namespace std;
int main() {
int n,t,m;
cin>>n;
for(int i=0;i<n;i++)
{
t=0;
int var;
cin>>var;
string a;
cin>>a;
for(int j=0;j<int(a.length());j++)
{
m=a.at(j)-48;
if(m>t)
{
while(m>t)
{
cout<<“(”;
t++;
}
}
if(m<t)
{
while(m<t)
{
cout<<“)”;
t–;
}
}
cout<<m;
}
while(t>0)
{
cout<<“)”;
t–;
}
cout<<“\n”;
}
return 0;
}
Tester's Solution
Same Person
Editorialist's Solution
Same Person