Equal Beauty CodeChef SnackDown 2021 Round 1A Question The beauty of an (non-empty) array of integers is defined as the difference between its largest and smallest element. For example, the beauty of the array [2,3,4,4,6] is 6−2=4. An array A is said to be good if it is possible to partition the elements of A into two non-empty arrays B1 and B2 such that B1 and B2 have the same beauty. Each element of array A should be in exactly one array: either in B1 or in B2. For example, the array [6,2,4,4,4] is good because its elements can be partitioned into two arrays B1=[6,4,4] and B2=[2,4], where both B1 and B2 have the same beauty (6−4=4−2=2). You are given an array A of length N. In one move you can: Select an index i (1≤i≤N) and either increase Ai by 1 or decrease Ai by 1. Find the minimum number of moves required to make the array A good. Input Format The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow. Each test
Snake Procession CodeChef SnackDown 2021 Beginner Practice Contest
Question:
The annual snake festival is upon us, and all the snakes of the kingdom have gathered to participate in the procession. Chef has been tasked with reporting on the procession, and for this he decides to first keep track of all the snakes. When he sees a snake first, it'll be its Head, and hence he will mark a 'H'. The snakes are long, and when he sees the snake finally slither away, he'll mark a 'T' to denote its tail. In the time in between, when the snake is moving past him, or the time between one snake and the next snake, he marks with '.'s.
Because the snakes come in a procession, and one by one, a valid report would be something like "..H..T…HTH….T.", or "…", or "HT", whereas "T…H..H.T", "H..T..H", "H..H..T..T" would be invalid reports (See explanations at the bottom).
Formally, a snake is represented by a 'H' followed by some (possibly zero) '.'s, and then a 'T'. A valid report is one such that it begins with a (possibly zero length) string of '.'s, and then some (possibly zero) snakes between which there can be some '.'s, and then finally ends with some (possibly zero) '.'s.
Chef had binged on the festival food and had been very drowsy. So his report might be invalid. You need to help him find out if his report is valid or not.
Input:
- The first line contains a single integer, , which denotes the number of reports to be checked. The description of each report follows after this.
- The first line of each report contains a single integer, , the length of that report.
- The second line of each report contains a string of length . The string contains only the characters '.', 'H', and 'T'.
Output:
- For each report, output the string Valid or Invalid in a new line, depending on whether it was a valid report or not.
Example Input:
1≤R≤500
1≤L≤500
Example Output:
6
18
..H..T...HTH....T.
3
...
10
H..H..T..T
2
HT
11
.T...H..H.T
7
H..T..HExplanation:
Valid
Valid
Invalid
Valid
Invalid
InvalidProgram Code in C++
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
ll t;
cin>>t;
while(t--){
ll n,f=0;
cin>>n;
string s,st;
cin>>s;
for(ll i=0;i<n;i++){
if(s[i]!='.')
st+=s[i];
}
if(st.size()%2!=0)
f=1;
else{
for(ll i=0;i<st.size();i++){
if(i%2==0){
if(st[i]=='T')
f=1;
}
else{
if(st[i]=='H')
f=1;
}
}
}
if(!f)
cout<<"Valid"<<endl;
else
cout<<"Invalid"<<endl;
}
return 0;
}
More Information
CodeChef is one of the largest online coding platform and SnackDown is one of it's of grandest programs held ever year. SnackDown is a global programming event that invites programmers all over the world to participate in India's most prestigious multi-round programming competition. SnackDown is open to everyone who has a knack in programming.
This question that is Snake Procession is of CodeChef SnackDown 2021 Beginner Practice Contest. Here you will get a brief explanation of the problem and after reading the explanation if you are still stuck and have no clue to understand the problem then you can visit the solution of the question given above.
Hope you learnt something from this explanation and solution. Code it guys, practice coding more and more.
Comments
Post a Comment