Since Hasan was too lazy to write a story for this problem, so we'll say it clear:
Given $$$N$$$ Horizontal lines and $$$M$$$ Vertical lines, you need to find the Longest plus sign formed by the intersection of exactly one vertical line with one horizontal line.
The length of the plus sign is defined by the length of its shortest side (the minimum length of the segments $$$[C,L1]$$$, $$$[C,L2]$$$, $$$[C,L3]$$$, $$$[C,L4]$$$.
First line of input will be $$$T$$$ number of test cases.
Each test case will start with two numbers, $$$N$$$ and $$$M$$$ the number of Horizontal lines and the number of vertical lines.
Next $$$N$$$ lines contain three space separated numbers, $$$X_1$$$, $$$X_2$$$ and $$$Y$$$, the starting and ending $$$X$$$ coordinates of the horizontal line, and It's $$$Y$$$ coordinate.
Next $$$M$$$ lines contain three space separated numbers, $$$Y_1$$$, $$$Y_2$$$ and $$$X$$$, the starting and ending $$$Y$$$ coordinates of the horizontal line, and It's $$$X$$$ coordinate.
$$$ 1 \le N, M \le 10^5$$$
$$$ 1 \le coordinates \le 10^5 $$$ and all the coordinates are integers.
For each test case print one line, containing the length of the longest plus sign.
1 3 2 1 5 3 2 4 2 6 12 6 1 5 3 6 9 2
2
Hasan is lazy. He likes to stay asleep in the morning. But the dorm's supervisor always wakes him up. He will try to run from her.
The dorm consists of $$$N$$$ rooms. There are $$$M$$$ portals between these rooms. To catch Hasan, the supervisor will stand at one of these portals. The supervisor can catch Hasan only if she stands in a portal between two rooms such that this portal is the only way to get between these two rooms.
Hasan can add one portal between any two rooms in the dorm; if he added it optimally, what is the minimum number of portals that the supervisor can use to catch him.
First line of the input will be $$$T$$$, the number of test cases.
Each test case starts with a line of two numbers, $$$N$$$, $$$M$$$ ($$$ 1 \le N, M \le 10^5 $$$)the number of rooms and portals.
Next $$$M$$$ lines contain two integers, $$$u$$$ and $$$v$$$ the rooms of the $$$i_{th}$$$ portal($$$ 1 \le u, v \le N $$$).
For each test case, print one line, the minimum number of portals that the supervisor can use to catch him.
2 3 2 1 2 2 3 9 11 3 2 3 8 2 8 1 2 1 5 1 4 5 9 7 5 4 5 6 4 4 7
0 1
Hasan is teaching Dynamic Programming to his students at NCD. However, he feels they aren't studying what he is giving them, so he decided to test them on the NCDPC. He will give them an array of length $$$N$$$, and they must tell him how many Longest Increasing Subsequences are in the array.
For example, if the array is ($$$1$$$ $$$2$$$ $$$1$$$ $$$4$$$ $$$3$$$). The LIS's length is $$$3$$$, and it could be ($$$1$$$ $$$2$$$ $$$4$$$) or ($$$1$$$ $$$2$$$ $$$3$$$), so the answer is $$$2$$$. Note that you can't choose ($$$1$$$ $$$1$$$ $$$3$$$) because it must be a strictly increasing subsequence, and you can't choose ($$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$) because you can't change the order of a subsequence.
First line of the input will be $$$T$$$, number of test cases.
Each test case starts with $$$N$$$, the size of the array, next line contain $$$N$$$ space separated integers, the array.
$$$1\le N \le 1000, 1 \le A_i \le 10^6 $$$
For each test case print one line, the length of the LIS and the number of LISes. As this number may be very large, print it module $$$10^9+7$$$
3 5 1 3 2 3 1 3 1 2 3 7 1 5 6 2 1 4 1
3 1 3 1 3 2
It's the final game in NCD's football cup between Bashar's team and Hamada's team. Everyone is excited for the final. However, not everything was going according to the plan.
Originally, each team had $$$N$$$ players in the field and $$$M$$$ substitutes. But for Bashar's team, Bashar was a little injured, Mahmoud had a broken hand, and Ahmad had had a heavy breakfast. On the other hand, Abdullah from Hamada's team was upset for getting a red card in a previous game, and Karam's hair was red.
But still, the match began. The match consists of $$$K$$$ parts, each lasts $$$30$$$ minutes. And the team who has more goals at the end of the match wins. If at the end both teams have the same goals, Iskandar takes the cup to his office.
At the first few minutes, Majd scored a wonderful goal. But then, after a heroic save, Ghaffar got injured, and Hamada's team scored three goals and was close to winning. Then Bashar got angry and started dribbling everyone. In the meantime, Hadi was drinking yerba mate.
Anyway, the details aren't important for Mr. Tarek, the Sports coach. He just wants to know the result of the match. You are given the number of goals each team scored, print "Bashar" if Bashar's team won, print "Hamada" if Hamada's team won, and print "Iskandar" if there was a draw. (Yes you read all the statement for nothing, I'm sorry).
First line of the input will be $$$T$$$, the number of test cases.
Next $$$T$$$ lines contain two numbers $$$X, Y$$$ $$$( 0 \le X, Y \le 10^{5} )$$$ the number of goals Bashar's team scored, and number of goals Hamada's team scored.
For each test case print one line "Bashar", "Hamada" or "Iskandar".
5 1 5 2 0 0 0 3 3 6 2
Hamada Bashar Iskandar Iskandar Bashar
Adnan is training the ARC team in NCD, but he wants to challenge them, so he started burning their drivers.
The team has $$$N$$$ drivers. Each driver has a lowercase Latin letter written on it. A segment of drivers from $$$L$$$ to $$$R$$$ can be used to move the robot if this segment is palindrome. When Adnan burns a driver, he changes the letter to any other letter he wants.
A segment of letters is considered palindrome if it can be read the same way from right and left. For example, $$$aa$$$, $$$abcba$$$, and $$$mmm$$$ are palindromes. But $$$mma$$$ and $$$aama$$$ aren't.
You will be given $$$E$$$ events in order; these events are of two kinds:
$$$1$$$ $$$i$$$ $$$c$$$: Adnan will burn the $$$i_{th}$$$ driver to change its letter to the char $$$c$$$.
$$$2$$$ $$$l$$$ $$$r$$$: The ARC team will use the segment [$$$l$$$,$$$r$$$], print "Adnan Wins" if this segment is palindrome, and "ARCNCD!" otherwise.
First line of input will be $$$T$$$, number of test cases
Each test case begins with two numbers $$$N, E$$$ the number of drivers, and the number of events.
Followed by a string of length $$$N$$$ consisting of only lowercase Latin letters.
Next $$$E$$$ lines contains $$$3$$$ space separated integers, the queries as described above.
$$$ 1 \le N, E \le 10^5$$$
It's guaranteed there is at least one query of the second type.
For every query of the second type, print "Adnan Wins" or "ARCNCD!"
1 7 5 adaersd 1 5 a 2 3 5 2 1 6 1 1 d 2 1 2
Adnan Wins ARCNCD! Adnan Wins
Each year in NCD, students participate in school research projects. Each project must have a team of at least $$$1$$$ student and at most $$$6$$$ students. And each student can only participate in one project.
However, not all the students found teams to join this year. So the administration will set new projects to accommodate these students. Your job is to find out the minimum number of new projects to accommodate all these students.
In the first line $$$T$$$, the number of test cases.
For each test case you will be given ($$$N$$$, $$$K$$$) the number of students in the NCD and the number of students who have projects.
$$$ 1 \le N, K \le 10^{18} $$$
For each test case print the least number of the new projects.
4 12 7 11 4 3 1 34 4
1 2 1 5
Ali Mansour was having a breakfast with his friends at the dorm. He will pour tea in their cups. He wanted to make the breakfast more exciting, so he decided to throw a drop of tea at their cups.
Ali will throw the drop randomly from point $$$(0, 0)$$$ at a random (formally random) angle between $$$L$$$ and $$$R$$$ with initial speed $$$V$$$.
He has $$$N$$$ friends, and each has a cup of different width. Let's assume that each cup has a $$$0$$$ height and is placed on the ground (The $$$X$$$ Axis). Given each cup's position, for each cup calculate the probability that the drop will fall in this cup. Note: it's possible for two cups to overlap or intersect.
First line of input will be $$$T$$$ the number of test cases.
Each test case is described by $$$4$$$ space separated integers, $$$N, V, L, R$$$ ($$$ 1 \le N \le 1000 $$$), ($$$ 1 \le V \le 10^{9} $$$), ($$$ 0 \le L \le R \le 90 $$$).
Then $$$N$$$ lines, the positions of the cups ($$$X1_{i}$$$, $$$X2_{i}$$$), ($$$ 0 \le X1_{i} \lt X2_{i} \le 10^{9} $$$)
For each test case print $$$N$$$ lines. in the $$$I_{th}$$$ line print the probability that the drop will fall in the $$$I_{th}$$$ cup.
Print the probability rounded to exactly $$$4$$$ digits
1 5 15 30 45 16 21 21 22 22 30 10 15 1 40
0.2987 0.2979 0.4034 0.0000 1.0000
Consider $$$g$$$ = $$$10$$$ $$$m$$$.$$$s^{-2}$$$
Mr. Hamra is preparing a crazy experiment for the next scientific Saturday.
Quantum entanglement is a weird relationship that can occur between two particles. And it has the following feature: if particles $$$A$$$ and $$$B$$$ are in quantum entanglement, and $$$B$$$ and $$$C$$$ are in quantum entanglement, then $$$A$$$ and $$$C$$$ are in quantum entanglement too.
Mr. Hamra has $$$N$$$ particles. He knows $$$M$$$ relationship of quantum entanglement between them. For his magical experiment, he will ask you $$$Q$$$ questions, in each question he will give you two particles and ask whether there is a quantum entanglement between them.
First line of the input will be $$$T$$$, the number of test cases.
Each test case starts with a line of three numbers, $$$N, M, Q$$$ ($$$ 1 \le N, M, Q \le 10^5$$$) the number of particles, quantum entanglement between particles, and the number of questions.
each of the next $$$M$$$ lines contain two integers, $$$u$$$ and $$$v$$$ the particles that are in quantum entanglement.
Next $$$Q$$$ lines contain two integers, $$$X$$$ and $$$Y$$$ the $$$i_{th}$$$ questions.
For each test case, print a binary string of length $$$Q$$$ the $$$i_{th}$$$ char of the string is "1" if there is a quantum entanglement between them or "0" otherwise (Without the quotes).
1 3 1 4 1 2 1 2 2 3 3 1 2 2
1001
Last week, the time was changed so that there will be more daylight time. However students in NCD went insane and didn't know how much to change the time.
There are $$$M$$$ students at NCD. Each student's clock was set on a number between $$$1$$$ and $$$N$$$ before the time change. When the change happened, each student $$$i$$$ changed his clock from its original time $$$A_i$$$ to a new time $$$A_i$$$ + $$$X_i$$$. Bashar wants to restore balance and find the correct time. He realized that the correct time is the most visited hour in all the students' clocks. Because he has exams and he is busy, he asked you to find the correct time.
For example, if $$$N$$$ = $$$3$$$ and there are two students, one at $$$1$$$ o'clock and moved the clock $$$+1$$$ (to $$$2$$$ o'clock) and one at $$$3$$$ o'clock and moved his clock $$$+1$$$ (to $$$1$$$ o'clock) then the correct time is $$$1$$$ o'clock, because it was visited two times.
The first line contains number of test cases $$$T$$$.
Each test case starts with a line containing two integers: $$$N, M$$$ $$$(1 \le M \le N \le 10^5)$$$.
Followed by two lines, first line contains $$$M$$$ space separated integers, Where $$$A_i$$$ is the time that the $$$i_{th}$$$ student has set his clock at.
Second line contain $$$M$$$ space separated integers $$$X_i$$$ the number given in the statement. Negative values of $$$X_i$$$ means you should move counter clockwise, positive values of $$$X_i$$$ means you should move clockwise.
$$$ 1 \le A_i \le N$$$, $$$ -N \le X_i \le N$$$
For each test case, print two space separated integers. The number of the most visited hour and how many students visited it.
If there are multiple answers for the number of the hour, print the smallest one.
1 5 5 1 2 3 4 5 1 1 1 1 2
2 3
Today the dinner in NCD is Pizza. Because the dorm's restaurant is generous, each student will get a number of pizza slices.
Masaoud is no longer a student in NCD, but he is hungry, so he will steal some slices from the students of NCD. But he is on a regime because he wants to become slim. So he wants to eat less than $$$X$$$ slices of pizza.
There are $$$N$$$ students in the restaurant standing in a line. Each student $$$i$$$ has a plate that has $$$A_i$$$ slices of pizza in it. Masaoud will choose a group of students standing directly next to each other and steal all their pizzas.
How many ways can Masaoud choose a group, so that their total number of pizza slices are less than $$$X$$$.
in the first line $$$T$$$, number of test cases.
For each test case, the first line contains $$$N$$$, $$$X$$$ ($$$ 1 \le N \le 10^5 $$$,$$$ 1 \le X \le 10^9 $$$) the number of students and the number given in the problem statement.
the second line contains $$$N$$$ separated integers the number of pizza slices each student has ($$$ 1 \le A_i \le 10^9 $$$).
For each test case output the number of groups of students such that Masaoud can steal their slices.
2 1 4 3 2 4 1 5
1 1
NCD students can make new inventions, discover new theories, and face big challenges, but they can't pass the chemistry test.
In the last test, all the questions were $$$"True"$$$ or $$$"False"$$$ questions. After the exam, it turned out that all the answers were correct.
Each student represents his exam paper as a decimal number, where each bit is an answer to a question. For example, if Hasan's paper was $$$5$$$, which is ($$$101_2$$$) in binary, this means that he answered the $$$1_{st}$$$ and $$$3_{rd}$$$ questions as $$$"True"$$$, and the rest as $$$"False"$$$, and he got $$$2$$$ marks in the exam.
After the test, all the students went insane because the test was very hard. So they asked you to give them their marks.
The first line contains the number of test cases $$$T$$$.
For each test case, the first line contains integer $$$N$$$ ($$$ 1 \le N \le 10^{5} $$$) the number of students.
The next line contains $$$N$$$ space separated integers $$$A_i$$$ ($$$ 1 \le A_i \le 10^{9} $$$) the mark for each student $$$i$$$.
For each test case print $$$N$$$ integers the number of correct questions each student has answered.
2 5 1 2 3 4 5 4 2 4 8 16
1 1 2 1 2 1 1 1 1
Each month, each student in NCD gets a salary of $$$B1^{P1}$$$ Liras. But when Ghaffar went to get his salary this month, he was surprised that he was given $$$B2^{P2}$$$ Liras.
Because he is lazy, he asked you to determine whether the new salary is bigger or smaller than the original salary.
The first line of input will be $$$T$$$, number of test cases.
Each test case is described by four space separated integers, $$$B_1, P_1, B_2, P_2$$$ numbers given in the statement.
$$$ 0 \le B, P \le 10^6 $$$
It's guaranteed that at least one of the $$$B1, P1$$$ and one of the $$$B2, P2$$$ is not equal to zero.
For each test case print "Congrats" if the new salary is bigger, print "HaHa" if it is smaller, and print "Lazy" if it is the same amount.
3 2 3 4 2 2 2 3 1 2 4 4 2
Congrats HaHa Lazy