December Lunchtime 2021 Division 3 Solutions
Chef and Vacation Transportation
Vacations have arrived and Chef wants to go to his home in ChefLand. There are two types of routes he can take:
Take a flight from his college to ChefArina which takes X minutes and then take a bus from ChefArina to ChefLand which takes Y minutes.
Take a direct train from his college to ChefLand which takes Z minutes.
Which of these two options is faster?
Input Format
The first line of the input contains a single integer T - the number of test cases. The test cases then follow.
The first line of the test case contains three space-separated integers X, Y, and Z.
Output Format
For each test case, if Chef takes the train output TRAIN, if Chef takes the plane and the bus output PLANEBUS, if both are equal output EQUAL.
You may print each character of the string in uppercase or lowercase (for example, the strings train, tRAiN, TrAin, and TRAIN will all be treated as identical).
Constraints
1≤T≤1000
1≤X,Y,Z≤109
Subtasks
Subtask 1 (100 points): Original constraints
Sample Input 1
3
10 12 11
3 5 15
9 4 13
Sample Output 1
TRAIN
PLANEBUS
EQUAL
Explanation
Test Case 1: It will take 10+12=22 minutes to travel using Plane and Bus. The train journey takes 11 minutes. Since the train is faster, Chef will choose the train.
Test Case 2: It will take 3+5=8 minutes to travel using Plane and Bus. The train journey takes 15 minutes. Since the plane and bus are faster, Chef will choose the plane and bus.
Test Case 3: It will take 9+4=13 minutes to travel using Plane and Bus. The train journey takes 13 minutes. Since they both are equal, Chef can choose either.
Solution in C++:
#include <iostream>
using namespace std;
int main() {
int t,a,b,c;
cin>>t;
while(t--){
cin>>a>>b>>c;
if(a+b>c) cout<<"TRAIN"<<endl;
else if(a+b==c) cout<<"EQUAL"<<endl;
else cout<<"PLANEBUS"<<endl;
}
return 0;
}
Maximum Trio
You are given an array A of N elements. For any ordered triplet (i,j,k) such that i, j, and k are pairwise distinct and 1≤i,j,k≤N, the value of this triplet is (Ai−Aj)⋅Ak. You need to find the maximum value among all possible ordered triplets.
Note: Two ordered triplets (a,b,c) and (d,e,f) are only equal when a=d and b=e and c=f. As an example, (1,2,3) and (2,3,1) are two different ordered triplets.
Input Format
The first line of the input contains a single integer T - the number of test cases. The test cases then follow.
The first line of each test case contains an integer N.
The second line of each test case contains N space-separated integers A1,A2,…,AN.
Output Format
For each test case, output the maximum value among all different ordered triplets.
Constraints
1≤T≤100
3≤N≤3⋅105
1≤Ai≤106
Sum of N over all testcases won't exceed 3⋅105.
Subtasks
Subtask 1 (30 points): Sum of N over all cases won't exceed 2000.
Subtask 2 (70 points): Original constraint
Sample Input 1
3
3
1 1 3
5
3 4 4 1 2
5
23 17 21 18 19
Sample Output 1
2
12
126
Explanation
Test case 1: The desired triplet is (3,2,1), which yields the value of (A3−A2)⋅A1=(3−1)⋅1=2.
Test case 2: The desired triplet is (2,4,3), which yields the value of (A2−A4)⋅A3=(4−1)⋅4=12.
Test case 3: The desired triplet is (1,2,3), which yields the value of (A1−A2)⋅A3=(23−17)⋅21=126.
Solution in Python :
for _ in range(int(input())):
n=int(input())
l = list(map(int,input().split()))
l=sorted(l)
print((l[n-1]-l[0])*l[n-2])
Chef Loves 1010
Chef is given a binary string S of length N. As Chef loves 1010 and he is busy in the preparation of Christmas, he asks you to count the maximum number of continuous substrings 1010, which Chef can get after reordering symbols in the given string.
As a reminder, a binary string is a string consisting only of 0's ans 1's.
Input Format
The first line of the input contains a single integer T - the number of test cases. The test cases then follow.
The first line of the test case contains an integer N - the length of the binary string.
The second line of each test case contains the binary string S.
Output Format
For each test case, print maximum number of continuous substrings 1010, which Chef can get after reordering symbols in the string.
Constraints
1≤T≤100
2≤N≤100
|S|=N
S is a binary string
Subtasks
Subtask 1 (100 points): Original constraints
Sample Input 1
3
2
11
8
11000100
10
0100111100
Sample Output 1
0
2
4
Explanation
Test case 1: There are no 0s in the string, so a 1010 substring is not possible.
Test case 2: We can reorder string into 01010100, in which the first 1010 starts from index 2, and the second 1010 starts from index 4. It can be proven that there are no orderings that give the answer larger than 2.
Solution in Python:
for _ in range(int(input())):
n=int(input())
l=input()
a=l.count('1')
b=l.count('0')
c=0
print(max(c,min(a,b)-1))
Romantic Reversals
Alice initially has a string S of length N, and she decides to modify it! Her modification consists of K steps numbered from 1 to K. In the i-th step, Alice reverses the prefix of length i of S.
For example, suppose Alice starts with S=abferty, and she modifies it via 3 steps, then:
After the first step, abferty→S=abferty
After the second step, abferty→S=baferty
After the third step, baferty→S=faberty So after 3 steps, her string becomes S=faberty.
After performing her K-step modification, Alice ends up with the string S′. Now she challenges you to find the original string S. Can you do it?
Input Format
The first line of the input contains a single integer T - the number of test cases. The test cases then follow.
The first line of the test case contains two space-separated integers N and K - the length of the string and the number of steps in Alice's modification.
The second line of the test case contains S′ - the final string obtained after the modification.
Output Format
For each test case, output the original string S.
Constraints
1≤T≤1000
1≤N≤106
1≤K≤N
|S′|=N
S′ contains only lowercase alphabets
Sum of N overall cases does not exceed 106.
Subtasks
Subtask 1 (30 points): 1≤N⋅K≤2000
Subtask 2 (70 points): Original constraints
Sample Input 1
3
7 3
faberty
7 5
bbaaaba
4 4
zxwy
Sample Output 1
abferty
aababba
wxyz
Explanation
Test case 2: The modification steps from S to S′ is as follow:
1-st step: aababba→S=aababba
2-nd step: aababba→S=aababba
3-rd step: aababba→S=baaabba
4-th step: baaabba→S=aaabbba
5-th step: aaabbba→S=bbaaaba
Test case 3: The modification steps from S to S′ is as follow:
1-st step: wxyz→S=wxyz
2-nd step: wxyz→S=xwyz
3-rd step: xwyz→S=ywxz
4-th step: ywxz→S=zxwy
Solution in Python : ( only 30% marks but you know better than 0%)
for _ in range(int(input())):
n,j = (map(int,input().split()))
l=input()
m=l
while(j>0):
a=(m[:j])[::-1]+m[j:]
j-=1
m=a
print(m)