Haneen and Reem are working on their graduation project. The deadline for submitting the final project is after d hours. They need at least w hours of work to finish it. So now they are thinking of skipping PSUT Coding Marathon V. Yaslo7oon? La yaslo7oon.
The Marathon will consume m hours of their time.
They will participate in the marathon if any of the two following cases can happen: first, if the time they have is enough for them to participate and finish the project in time, second, if they won't finish the project anyway even if they didn't participate.
Determine whether they should participate in the marathon or not.
The input contains three integers d, w and m (1 ≤ d, w, m ≤ 1000), the number of hours before the deadline, the number of working hours needed to finish the project, and the number of hours the marathon takes.
Print "good luck" if they should participate, and "see you next semester" if they should not.
All letters in the output must be in lowercase. Do not print extra characters.
48 879 7
good luck
48 41 8
see you next semester
A string is a palindrome if it can be read the same in both directions. For example, "madam" is a palindrome while "sir" is not.
Given two strings, each of which is a palindrome. Find if it is possible to merge all the letters of the two string in one palindrome string. That is, you need to find if it is possible to put all letters of the two strings together in one string and order them in some way to get a palindrome.
For example, if we have the two strings "abba" and "qq", we can merge them to "aqbbqa", which is a palindrome. Note that you can merge the two strings in any way, but you are not allowed to remove any of the characters.
The input consists of two lines, each contains a non-empty string of no more than 100 lowercase English letters.
It is guaranteed that each of the given strings is a palindrome.
Print a single line with YES if it is possible to merge the two strings into a palindrome. Otherwise, print NO.
You can print each letter in any case (upper or lower).
abba
YES
a
c
NO
bab
weew
YES
The memory limit for this problem is 4 MB.
In computer science, a tree is a connected graph with no cycles. Each node in a tree has exactly one parent, except for the root, which doesn't have a parent.
A forest is a graph that consists of one or more trees.
We introduce the following method to generate a forest of n nodes:
- The input for the method is an array A of n distinct integers.
- Edges are generated in the following way: the parent of node i is j, where j is the maximum index such that j < i and Aj > Ai. If such index doesn't exist, then node i has no parent.
Note that the generated trees are rooted.
Given an array of n distinct integers, find the number of trees in the forest generated using this array.
The first line of input contains a single integer n (1 ≤ n ≤ 2 × 106), the size of the array.
The second line contains n distinct integers A1, A2, ..., An (1 ≤ Ai ≤ n), representing the values of the array.
As the memory limit for this problem is 4 MB, you need to solve it without storing the array.
Print a single integer that represents the number of trees in the generated forest.
3
2 1 3
2
5
5 4 3 2 1
1
1
1
1
Given a forest of n nodes, find an array of n distinct integers such that if we apply the method mentioned in the previous problem, it will generate the given forest.
Please check the previous problem for the details on how the method works.
We care only about the structure of the forest, that is, the labels of the nodes are not important. In other words, the forest generated using the array in your output is considered to match the given forest if it is possible to re-label its nodes such that the set of edges matches the given edges.
Note that trees in the forest are rooted (edges are directed from the parent to the node).
The first line of input contains a single integer n (1 ≤ n ≤ 105), the number of nodes in the forest.
The second line contains n integers p1, p2, ..., pn (0 ≤ pi < i), where pi is the parent of node i, or 0 if node i doesn't have a parent.
Print n distinct space-separated integers, each between 1 and n, representing the array that can be used to generate the structure of the given forest.
If there is more than one solution, you can print any of them.
5
0 1 1 3 4
5 2 4 3 1
5
0 1 0 3 4
4 2 1 5 3
Note that in the second example, the generated forest will not be exactly the same as the given one, but it is possible to re-label the nodes so that it matches the given forest. The structure is the same, both forests consist of a chain of length 2 and a chain of length 3.
You have an array A of n distinct integers. You used the method for generating forests but you didn't like the number of trees generated. You want to remove at most one element to maximize the number of trees in the generated forest. What is the maximum number of trees you can achieve?
Solve the problem for each subarray, that is, for each pair of integers (l, r) such that (1 ≤ l ≤ r ≤ ), find the maximum number of trees in a forest that can be generated if we use only the values in the range [l, r] in their order, given that you are allowed to remove at most one element from the range.
Instead of printing too many numbers, print the sum of the answers for all subarrays.
The first line of input contains a single integer n (1 ≤ n ≤ 5000), the size of the array.
The second line contains n distinct integers A1, A2, ..., An (1 ≤ Ai ≤ n), representing the values of the array.
Print a single integer that represents the sum of the answers for all subarrays.
3
3 1 2
8
We have 6 subarrays:
- Three subarrays of size one, the answer for each of them is 1 as we can't get more trees by removing an element.
- Subarray [3, 1], number of generated trees is 1, and if we remove any of the two elements it won't change.
- Subarray [1, 2], number of generated trees is 2 (each of a single node), and if we remove any of the two elements it will become 1, so it is better not to remove any element.
- Subarray [3, 1, 2], number of generated trees is 1, but if we remove the first element, we will get a forest of two trees. So the answer for this subarray is 2.
Total answer is 8 = 1 + 1 + 1 + 1 + 2 + 2.
The 2018 WIFA World Mug is around the corner.
The tournament consists of n teams. In each round of the tournament, each team plays against another team. A team that loses a match exits the tournament, while a team that wins a match progresses to the next round. The tournament finishes when one team wins the final match.
In the first round, team 1 plays against team 2, team 3 plays against team 4, and so on. In the second round, the winner of the first match plays against the winner of the second match, and so on as shown in the picture.
Each team has a certain unique strength si. Team i will win a match against team j if its strength si is greater than team j's strength sj. The number of goals scored in that match equals |si - sj|.
Given the tournament format, can you calculate the number of goals scored throughout the tournament?
The first line of input contains one integer n (2 ≤ n ≤ 218), the number of teams participating in the tournament. It is guaranteed that the number of teams is a power of two (i.e., 2, 4, 8, 16, ...).
The second line contains n distinct integers, the ith integer is si (1 ≤ si ≤ 109), the strength of the ith team.
On a single line, print the number of goals that will be scored in the tournament.
8
100 200 300 400 800 700 600 500
1200
The organizers of the tournament wish to ensure a great amount of fun for the fans, for that, they have decided to rearrange the teams such that more goals in the tournament are scored.
Can you help out by calculating the maximum number of goals that could be scored if the teams were rearranged optimally?
The first line of input contains one integer n (2 ≤ n ≤ 218), the number of teams participating in the tournament. It is guaranteed that the number of teams is a power of two (i.e., 2, 4, 8, 16, ...).
The second line contains n distinct integers, the ith integer is si (1 ≤ si ≤ 109), the strength of the ith team.
On a single line, print the maximum number of goals that could be scored in the tournament if the teams were rearranged to maximize that number.
8
100 200 300 400 800 700 600 500
2100
An undirected graph is cylindrical if it can be split it into two disjoint simple cycles of equal length such that the ith node in the first cycle is connected to the ith node in the second cycle.
Given an undirected graph of even number of nodes n and 
edges, determine whether it is cylindrical or not, and if it is, print the two cycles that forms it (check the output section for the exact requirements).
The first line of input contains an even integer n (6 ≤ n ≤ 105), the number of nodes in the graph.
Each of the following lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), representing an edge connecting the nodes u and v. Each pair of nodes is connected by at most one edge.
Print "NO" if the given graph is not cylindrical. Otherwise, print "YES" followed by two lines, each containing the nodes of one cycle in following format:
c1 c2 ... 
- Each consecutive nodes in a cycle must be connected by an edge in the input. Also the first and the last nodes in the cycle must be connected.
- The ith node in the first cycle must be connected to the ith node in the second cycle.
- Each of the n nodes must belong to exactly one of the cycles.
If there is more than one solution, you can print any of them.
6
1 2
2 3
3 1
4 5
4 6
5 6
1 5
2 6
3 4
YES
1 3 2
5 4 6
6
2 6
3 6
1 3
2 1
3 4
4 2
4 5
5 6
1 5
NO
A Tree Generator is a balanced string of parentheses, like (()()). Generators are executed character by character from left to right, where '(' means add a new child to the selected node, and select the new node. While ')' means select the parent of the currently selected node.
Initially, there is a tree with one node (1), and this node is selected.
Selecting a new node will deselect any other node.
Newly created nodes take the first unused positive integer as an ID (2, 3, ...).
You are given n generators and will generate a tree using k operations of the following format:
- Select node x. It is guaranteed that node x exists in the tree before this operation.
- Activate generator number i (1 ≤ i ≤ n) at the selected node. Note that the selected node will remain the same after the process (as the given generators are balanced).
Finally, you have to answer q queries on the generated tree, each query has the following format:
- Find the length of the shortest path between node u and v.
The first line of input contains three integers n, k and q (1 ≤ n, k, q ≤ 105), the number of generators, the number of operations, and the number of queries, respectively.
Each of the following n lines contains a non-empty string of parentheses. It is guaranteed that the given string is balanced.
Total number of characters over all generators will not exceed 2 × 105.
Each of the following k lines is in one of the following formats:
- s x, select node x.
- a i, activate generator i (1 ≤ i ≤ n).
Each of the following q lines contains two integers u and v, representing a query. It is guaranteed that u and v exist in the generated tree.
For each query in the given order, print the length of the shortest path between the given nodes.
3 3 2
()
(()())
(())
a 2
s 3
a 3
6 4
2 5
4
2
3 9 5
(()())
()()
(())
s 1
s 1
s 1
a 1
a 2
s 4
a 3
a 3
a 1
3 3
1 3
11 3
8 2
4 8
0
2
3
3
2
Complete the Square is a two-player game played on a grid of R rows, each containing C dots.
In one turn, a player draws a vertical or a horizontal segment between two adjacent dots. This segment has to be new (not drawn before).
A square is completed if its four sides are drawn. When a player completes a square, they write the first letter of their name in that square and receive one point. After completing a square, the same player has to draw another segment unless the grid is completed.
As shown in the image, in one turn, player B completed 5 squares and drew an extra segment. The numbers written in the squares are for clarifying the order in which the squares were completed. Note that it is possible that a player completes two squares at the same moment.
Given a state of the game, find the maximum number of squares you can complete in one turn.
The first line of input contains two integers R and C (2 ≤ R, C ≤ 1000), the number of rows and columns of the grid.
Each of the following 2R - 1 rows contains 2C - 1 characters representing the state of the game. Since the letter in each square is irrelevant for solving the problem, a completed square will contain the lowercase English letter 'x'.
A vertical segment is represented with a vertical bar '|', a horizontal segment is represented with a dash '-'. Dots are represented with the lowercase English letter 'o'. Edges that are not drawn or squares that are not completed will be represented with a dot '.'.
It is guaranteed that the input is valid in a way that every completed square is filled with an 'x', and every uncompleted square is filled with a dot '.'. No character will appear in an invalid place (for example, no '|' will appear in the place of a horizontal segment).
The given state of the game is not necessarily reachable through valid sequence of turns. However, consider it as an initial state for the game and solve the problem.
Print the maximum number of squares you can complete in one turn.
5 6
o-o.o.o.o.o
......|.|..
o.o.o-o.o.o
........|.|
o.o-o.o.o.o
..|...|....
o.o.o-o-o.o
|.|.....|..
o.o-o-o-o.o
5
2 3
o.o-o
|.|x|
o.o-o
0
The first example represents the grid in the middle of the picture.