A: Challenge Accepted!
After a mind numbing lockdown, you decide to step out of your house and have a jog in the park nearby. After a few laps around the park, you run into your old friend. He challenges you to find if a given string S contains the sub-string baab hidden in it, and wait for it, without using loops, arrays, strings, character pointers and only using recursion. Are you brave enough to accept the challenge?
Input
The first line of input contains a single integer N (1 N 500) denoting the number of characters in the string S. The following line contains a sequence of N lowercase as or bs.
Output
If the given string S contains the sub-string baab, print YES, followed by the index at which it is found. In case, the sub-string is present more than once, print all indices at which it is found, in ascending order, in space separated fashion (see sample case for better clarity). If the sub-string is not found in the given string, just print NO. Note that the indices should be printed in 1-indexed order.
input 10 baababbaab
output
YES 1 7
input 17 baaaaaabbaaaaabaa
output NO
input 12 aabaabaabaab
output
YES 3 6 9
B: Palindrome?
In this problem, you are once again given a string S, and are asked to check if S is a palindrome. A palindrome is a string which reads the same left to right and right to left. The constraint is to solve this using only doubly-linked-lists. Note that, no use of arrays or character pointers must be made to solve this problem and that this is case-sensitive palindrome.
Input
The first line of input contains a single integer N (1 N 1000) denoting the number of characters in the string S. The following line contains a sequence of N lowercase and uppercase alphabets.
Output
Print PALINDROME if given string S is a palindrome or NOT A PALINDROME if it is not.
input 9 MaLaYaLaM
output PALINDROME
input 6 XOFfoX
output NOT A PALINDROME
input 4
KooK
output
PALINDROME
C: Dinner Time
With the advent of the 2020 batch, Mess-1 faces a grave shortage of seats in the mess. At dinner time, every minute a certain number of students either enter the mess or leave it (assume that, in a minute, students do not enter and leave simultaneously). After dinner, the mess manager is curious to know the maximum number of seats that were occupied during dinner time. As he is busy preparing for the upcoming Moonlight dinner, he asks you to help him out. Assume that the students are very lazy and occupy the first unoccupied seat (unoccupied seat with lowest index) they find.
Input
The first line contains a single non-zero integer T (1 T 500) denoting the number of minutes the mess is open for dinner. Each of the following T lines resembles either of the following query:
- E X: This statement denotes that X (0 < X 5000) students enter the mess in that minute.
- L P Y1, Y2, Y3 YP: This statement denotes that P (0 < P 5000) students leave the mess that minute from the seats numbered Y1 to YP. It is guaranteed that the P will be less than or equal to the number of students in the mess at that minute.
Assume that the total number of students in campus are less than or equal to 5000 and seats are 1-indexed (see sample case for better clarity)
Output
Print a single integer N, denoting the maximum number of seats that were occupied during dinner time.
input 6
E 5
E 2
L 3 1 4 5
L 1 2
E 3
E 2
output
8
D: Amazon Shopping
With Amazons yearly sale going on, you wish to buy as many goods as your wish with you limited pocket money you have collected till date. As the sale time is running out, you decide to write a simple program that will help you buy as many goods as possible without exceeding your budget. Hint: Think in terms of subsets and how subsets can visualized with binary numbers.
Input
The first line contains a single integer M (0 M 109) that denotes your pocket money. The following line contains another integer N (1 N 25) denoting the number of goods that are for sale in Amazon. The last line of input contains N space-separated integers (0 Pi 109) denoting the prices of the goods for sale.
Output
Print a single integer X, denoting the maximum number of goods you can buy without exceeding your budget.
input 44
6
14 13 21 8 56 3
output 4
input 70
7
71 101 766 125 908 682 75
output
0
E: Digital Design
In this problem, you will be implementing a simple shift register and some of its functions using a doubly-linked-list. Note: You are not allowed to use any other data structure other than linkedlists for this problem. Further, you are not supposed to convert the given bit string to decimal and perform operations on it.
Input
The first line contains a bit string B (1 |B| 1000) which denotes the initial content of the register. The second line contains a single integer T (1 T 100) denoting the number of queries. Each of the following T queries resemble either of the following:
- LR: This denotes that the content of the register has be left-rotated by one unit.
- RR: This denotes that the content of the register has be right-rotated by one unit.
- LS: This denotes that the content of the register has be left-shifted by one unit. (empty space can be filled with 0)
- RS: This denotes that the content of the register has be right-shifted by one unit. (empty space can be filled with 0)
- INC: This denotes that the content of the register has be incremented by 1.
- DEC: This denotes that the content of the register has be decremented by 1.
Output
Print the content of the register after all operations have been performed. In case any out-carry is generated, you can ignore it.
input 11111001
4
LS
LS
LR INC
output 11001010
F: Koro-sensei and Primes
Koro-sensei has come up with a quite an eerie problem on primes for the students of class 3E. Given two numbers A and B, the students have to find the digit which occurs maximum number of times in the primes from A to B (both inclusive). As the class is getting ready for the annual school festival, they all turn to you, Karuma, for help.
Input
The only line of input contains two space-separated integers A and B (0 A B 1012, 0 B-A 106)
Output
Print two space-separated integers X and Y with X denoting the digit that occurs maximum number of times in the primes from A to B and Y denoting the frequency of X.
input 37 101
output
7 7
input 2692 15859
output
1 1367
F: Tour de Goraq
Ash Ketchum, on his journey to be the Pokemon master, plans to tour the new archipelago Goraq. Goraq is a set of islands with a few of those islands being connected by long bridges. As part of his tour, Ash always starts from island 0, and tours all islands reachable from it before moving on to another cluster of islands. Help Ash figure out how many clusters of islands are present in the Goraq archipelago and along with number of islands per cluster. Note: A cluster of islands is a set of islands that are reachable from one another, i.e. they form a connected component.
Input
The first line of input contains two space-separated integers N (1 N 500) and M (0 M
) denoting the number of islands in the archipelago and the number of bridges between those islands respectively. The following M lines contain two space-separated integers Ui and Vi (0 Ui, Vi N-1) denoting an undirected bridge between islands Ui and Vi.
Output
In the first line, print a single integer X denoting the number of clusters in the archipelago and in the following line, print X space-separated integers denoting the number of islands per cluster (this can be printed in any order).
input 12 12
5 7
7 9
1 7
4 10
3 8
10 8
10 3
2 6
output 3
4 4 4
explanation
As you can observe, there are three clusters wiz. 1-5-7-9, 0-2-6-11, 4-10-8-3
H: Cost Difference
Let us define the cost of an array as the difference of sum of squares of elements at even indices and sum of cubes of elements at odd indices. In this problem, you need to find the array rotations with maximum and minimum cost and report the difference between those costs. Sample array rotation: [7 1 -9 6 0 1] [1 7 1 -9 6 0]
Input
The first line contains a single integer N (1 N 500) denoting the number of elements in the array. The following line contains a sequence of N space-separated integers (103 Ai 103) denoting the array A given you.
Output
Print a single integer S denoting the difference between of costs of the maximum cost rotation and minimum cost rotation.
input 7
6 -1 8 -1 6 8 -4
output 1452
input 10
-5 67 12 -78 5 0 -6 100 6 -37
output 795506
input 5
8 8 8 8 8
output
0
I: Reverse it!
In this problem, you are given a stream of positive numbers. You are expected to generate a singly-linked-list out of them and reverse it. Note: You must not to store the numbers in any array and are supposed to completely reverse the list by reversing all the pointers, i.e. you must not create a new list to store the numbers in reversed order.
Input
The only line of input contains a sequence of numbers A (0 Ai 109). It is assured that the final number in the sequence will be -1 which can be used to as a termination condition and the length of the sequence will be less than 5 105.
Output
Print the linked list after reversing it, in space-separated format. Note that, you need not print the -1 at the end.
input
9 4 67 2 7 1 7 655 8 0 91 -1
output
91 0 8 655 7 1 7 2 67 4 9
input 78 -1
output 78
input
1 78 4 28 9 68 18 19 36 9 -1
output
9 36 19 18 68 9 28 4 78 1
- Rangoli
Roshni has drawn a new rangoli design (which can be visualized as an undirected graph) and wishes to colour it. But unfortunately, she has only two colours Red and Blue. She is very particular about her colouring scheme and wants the colour the vertices in the rangoli in such a way that the two vertices connected by an edge have different colour. As Roshni is still perfecting her rangoli design, help her generate a coloring scheme using only the Red and Blue colours available.
Input
The first line of input contains two space-separated integers N (1 N 500) and M (0 M
) denoting the number of vertices and edges in the rangoli. The following M lines contain two space-separated integers Ui and Vi (0 Ui, Vi N-1) denoting an undirected edge between vertices Ui and Vi in the rangoli.
Output
If coloring the rangoli with just two colours is not possible, print NEED MORE COLOURS else, print a sequence of N characters denoting the colouring scheme for the rangoli. Assume the 0th vertex is always coloured Red, in case a colouring scheme exists. (see sample case for clarity).
input
6 6
0 1
2 3
4 5
0 5
2 1
- 3
output RBRBRB
input
- 6
- 1
- 3
1 5
4 5
2 1
5 0
output
NEED MORE COLOURS
Reviews
There are no reviews yet.