A devil programmer has developed an AI bot claiming that programmers are going to lose their job to his AI bot. However, programmers are not willing to accept this claim because they know that they are the most intelligent. So, they decided to do a programming battle with that AI. As a programmer, who do you think is going to win this battle?
There will be no input for this problem.
Print who is going to win this war?
Programmer
It is a sample output. Print your own thought.
Assume we have an array $$$a$$$ of size $$$m$$$ indexed from 1 to $$$m$$$ and an integer $$$k$$$. Then we will make the array $$$b$$$ (which is initially empty) by the following procedure:
1. Sort the array $$$a$$$ in non-decreasing order.
2. Append $$$a_{i+1}$$$ - $$$a_i$$$ to $$$b$$$ for each $$$i$$$ from 1 to $$$m$$$-1.
We will call the array $$$\bf{a}$$$ good if the minimum element of the array $$$\bf{b}$$$ is at least $$$k$$$.
Now the actual problem, given an array $$$c$$$ of size $$$n$$$ and the integer $$$k$$$, count the number of good subarrays of $$$c$$$ of size at least 2.
The input consists of multiple test cases. The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^{5})$$$ - the number of test cases. The descriptions of the test cases follow.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq 10^{5}, 1 \leq k \leq 10^{9})$$$.
The following line contains $$$n$$$ space-separated positive integers $$$a_1, a_2, .. , a_n$$$ $$$(1 \leq a_i \leq 10^{9})$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{5}$$$.
For each test case, output the number of good subarrays of $$$c$$$ of size at least 2.
67 37 2 5 3 1 1 53 428 6 282 110 87 215 15 6 11 12 12 115 55 4 1 3 144 49 6 10 12
3 2 1 3 1 1
Tommy went to the jungle. He has found a cave and in the cave, he has found a cage. There is divine water in the cage. The divine water has a special power. Once you drink the water you'll become meritorious. As Tommy is not good at his studies, he wants to drink water to become a meritorious student. But he can't drink the water until he opens the cage. The cage has a display, some buttons, and a lock system. There are twelve buttons. One "Yes" button and one "No" button. The rest of the buttons are digit buttons $$$(0-9)$$$. The cage is locked with a special system.
The display shows three integers $$$x, l, r$$$. The integer $$$x$$$ is good if there exists three integers $$${a, b, c}$$$ such that,
- $$${l \le a \lt b \lt c \le r}$$$ where $$${2 \le r-l \le 100}$$$
- $$${a \times b \times c = x}$$$
To open the cage first he has to determine whether the number $$$x$$$ is good or not. If the number is good then he will press the "Yes" button and then he will type the numbers $$$a, b, c$$$. Otherwise, he will press the "No" button. As mentioned above, he is not good at his studies. So he needs your help. Help him to get the divine water.
Each test consists of multiple test cases. The first line contains a single integer t $$$(1 \le t \le 100)$$$ — the number of test cases. Description of the test cases follows.
Each test case contains three integers $$$x(1 \le x \le 10^{9}), l, r(1 \le l \lt r \le 1000, 2 \le r-l \le 100)$$$ in a line.
For each test case, output $$$−1$$$ if the number is not good.
Otherwise, output three integers $$$a,b,c$$$.
If there are several solutions, output any of them.
5 138 1 53 100 1 100 8 2 6 30 2 10 23 12 19
2 3 23 2 5 10 -1 2 3 5 -1
Oyshee and Farhana bought a pizza which is divided into some equal slices. Here, the number of slices is unknown to us. All we know is the radius, $$$r$$$ of the pizza and the angle, $$$\theta$$$ (in degree) of a slice. See the image below for a better understanding.
Is it possible to distribute all the slices between them equally? Note that, they cannot divide the slices any further.
The input consists of multiple test cases. First line contains an integer $$$t$$$ $$$(1 \leq t \leq 2400)$$$ - the number of test cases. The descriptions of the test cases follow.
The first and only line of each test case contains two integers $$$r$$$ and $$$\theta$$$ $$$(1 \leq r \leq 100,$$$ $$$1 \leq \theta \leq 360)$$$ - the radius of the pizza and the angle of a slice. You can assume that the input will be given in a way that the pizza can be divided into some equal slices.
For each test case, print "YES" (without quotes), if it is possible that both of them get an equal amount of slices, "NO" (without quotes) otherwise.
310 455 408 60
YES NO YES
Hope you have already seen the legendary anime Attack On Titan. Now, I am writing the missing plot of the anime. Inside Wall Maria, there are $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$. They are connected by $$$n-1$$$ bi-directional roads. From each city, it is possible to visit any other city by using some sequence of roads. The path from one city to another city is always unique. Each city $$$i$$$ ($$$1 \leq i \leq n$$$) has $$$a_i$$$ number of titans. One day, Eren told Mikasa "Now I will ask you some questions. In each question, you are given two cities $$$x$$$ and $$$y$$$. You have to tell in the shortest path of the given two cities, if there exists at least one pair of cities $$$i$$$, $$$j$$$ such that GCD of the number of titans of cities $$$i$$$, $$$j$$$ is greater than $$$1$$$". You have to help Mikasa by answering the questions for her. Otherwise, Eren will misbehave with her once again saying "Mikasa, you are an Ackerman".
GCD of two positive integers $$$a$$$ and $$$b$$$ is the biggest integer $$$d$$$ such that both integers $$$a$$$ and $$$b$$$ are divisible by $$$d$$$.
The first line contains one integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the number of cities.
The second line contains n integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$) — number of titans of each city.
Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) denoting the bi-directional road between cities $$$u_i$$$ and $$$v_i$$$.
The next line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of questions.
Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x , y \le n$$$, $$$x \neq y$$$) — the cities for each question.
For each question$$$,$$$ you have to print YES if there exist at least one pair of cities having GCD greater than $$$1$$$ in the shortest path of the given cities. Otherwise, print NO.
You can output YES and NO in any case (for example$$$,$$$ strings yEs$$$,$$$ yes$$$,$$$ Yes and YES will be recognized as a positive response).
7 8 5 6 9 10 3 4 1 2 1 3 2 6 2 7 3 4 3 5 3 5 6 6 1 1 7
YES NO YES
- GCD of the number of titans of cities $$$6$$$ and $$$3$$$ is $$$GCD(a_6, a_3) = GCD(3, 6) =3$$$ which is greater than $$$1$$$.
- GCD of the number of titans of cities $$$3$$$ and $$$5$$$ is $$$GCD(a_3, a_5) = GCD(6, 10) =2$$$ which is greater than $$$1$$$.
- GCD of the number of titans of cities $$$1$$$ and $$$3$$$ is $$$GCD(a_1, a_3) = GCD(8, 6) =2$$$ which is greater than $$$1$$$.
Therefore, the answer to the first question is YES.
For the second question, the GCD of the number of titans of any pair of cities is $$$1$$$.
Therefore, the answer for the second question is NO.
There are $$$n$$$ active coders in RAPL. A few months ago, the RAPL ministry took an initiative to provide daily reward points to all the active coders of RAPL. Initially, the $$$i$$$-th active coder had reward point $$$a_i$$$. From that moment $$$m$$$ days have passed. Each day the reward point of one participant was updated. On the $$$k$$$-th day $$$r_k$$$ point is added to the reward point of of $$$p_k$$$-th $$$(1 \le k \le m)$$$ active coder. These updates are recorded by the information ministry of RAPL.
Now the preservation ministry of RAPL assigned you a task. You have to collect the record of updates from the information ministry of RAPL and write a code to find the number of distinct reward points after the update of the $$$k$$$-th day and submit it to the education ministry of RAPL.
The first line of the input contains a single integer $$$t$$$ $$$(1 \le t \le 10^{5})-$$$ the number of test cases.
The first line of each test case consists of two space separated integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 10^{5}, 1 \le m \le 10^{5})-$$$ the number of active coders, the number of days respectively.
Then $$$m$$$ line contains two space separated integers $$$p_k$$$ and $$$r_k$$$ $$$(1 \le p_k \le n, -10^{9} \le r_k \le 10^{9})$$$.
It is guaranteed that the sum of $$$n$$$, sum of $$$m$$$ over all test cases doesn't exceed $$$2.10^5$$$.
For each testcase print $$$m$$$ lines. The $$$k$$$-th line contains an integer which is the number of distinct reward points after the update of $$$k$$$-th day.
3 5 3 20 10 25 5 3 5 2 2 -5 4 20 1 3 100 1 400 1 1 1 -100 4 5 1000000000 -294967296 705032704 -1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000
4 3 3 1 1 1 4 4 4 4 4
Blank lines in sample input are for demonstration only. Original input file has no blank line.
You are given a grid of size $$$n\times m$$$. Each cell of the grid is either empty or blocked. Tahia wants to put some robots in some of the empty cells. Each empty cell can contain any number of robots at a time. Each robot has a certain direction (left, right, up or down) associated with it.
The robots can only move to the empty cells and they cannot move outside of the grid.
At each second, if the robot can make a move in its associated direction, it changes its position. Otherwise, it changes its direction. At any time t, if the robot is in the cell of row $$$r$$$ and column $$$c$$$, denoted by ($$$r, c$$$) , at time $$$t+1$$$, it moves to one of the cells ($$$r, c-1$$$), ($$$r, c+1$$$), ($$$r-1, c$$$) or ($$$r+1, c$$$) for the directions left, right, up and down respectively. If it cannot change its position, it changes its direction from left to right, from right to left, from up to down or from down to up at that second.
You are given the configuration of the grid and the initial position and direction of all the robots (at time $$$0$$$), you have to output the position and direction of each robot at time $$$k$$$.
The first line of the input contains four integers $$$n$$$, $$$m$$$, $$$x$$$ and $$$k$$$ ($$$1\leq n, m, x, k\leq 100$$$) $$$-$$$ the number of rows, the number of columns, the number of robots and the number of seconds.
The next $$$n$$$ lines contain the configuration of the grid. Each of these $$$n$$$ lines contains $$$m$$$ characters. Each of the characters is either a '$$$\cdot$$$' or a '$$$\#$$$', where '$$$\cdot$$$' denotes an empty cell and '$$$\#$$$' denotes a blocked celll.
Each of the next $$$x$$$ lines contains two integers $$$r_i$$$, $$$c_i$$$ ($$$1\le r_i \le n, 1 \le c_i\le m$$$) followed by a character $$$d_i$$$ ($$$d_i$$$ = $$$L$$$, $$$R$$$, $$$U$$$ or $$$D$$$). Here, $$$r_i$$$ denotes the row number and $$$c_i$$$ denotes the column number of the $$$i$$$-th robot. $$$L$$$, $$$R$$$, $$$U$$$ and $$$D$$$ denotes the robot having directions left, right, up and down respectively.
You have to output the position and direction of each robot at time $$$k$$$ in the given order.
5 5 2 4 ..##. #.... ...## ###.. ....# 2 3 L 2 4 R
2 4 R 2 3 L
10 10 10 10 #......##. #.##.###.. #.#....#.. ......##.. ##.#.#..#. .##...###. #...###..# .##....... ##..#.#.## #...#.#.## 1 3 U 9 6 U 10 2 D 4 9 D 4 9 U 6 1 R 8 1 R 7 2 U 3 4 L 7 4 R
1 3 U 10 6 D 10 2 D 2 9 D 3 9 D 6 1 R 8 1 R 7 2 U 3 5 R 7 2 R
The description of the first sample is given below-
 |  |  |
 |  |
Farha loves to play hopscotch games. But if you do not know how to play, don't worry!
Suppose there is a large $$$10 \times 10$$$ grid, where each cell is numbered from $$$1$$$ to $$$100$$$. Initially, she is in the cell marked $$$1$$$ with a dice (a dice is a cube that has six faces containing distinct integers from $$$1$$$ to $$$6$$$) that she has to throw and move forward in the cells until she reaches $$$100^{th}$$$. But it has some ladders to climb up and some snakes to fall down. It's similar to what we see in a ludo board game!
The game continues in the following way:
Farha throws the dice and gets a number $$$k$$$. If she is at $$$i^{th}$$$ cell, she will reach at $$$(i+k)^{th}$$$ cell. In the continuation, she may catch a ladder top/bottom, be bitten by a snake or she may win reaching $$$100^{th}$$$ cell.
Currently, Farha is at $$$\textbf{94}$$$$$$^{th}$$$ cell. At this point, she'll throw the dice for once. And you'll be given a number $$$k$$$ that she is obtained by throwing the dice. Now, your task is to tell the condition of her after moving $$$k$$$ steps forward.
The first (and only) line contains one integer $$$k$$$ $$$(1 \le k \le 6)$$$.
If she reaches $$$100^{th}$$$, print "Yay! Farha has won the game. She is now at 100."
If she catches a ladder top/bottom, print "Farha is on ladder."
If she is bitten by a snake, print "Alas! Farha is bitten by snake. She is now at X." Here, X is the cell number she belongs to after she has been bitten.
Otherwise, print "Nothing happened to her."
Do not print quotation marks.
1
Alas! Farha is bitten by snake. She is now at 75.
6
Yay! Farha has won the game. She is now at 100.
5
Farha is on ladder.
You are given three integers $$$l$$$, $$$r$$$ and $$$k$$$. Find the number of pairs $$$(a, b)$$$ such that $$$l$$$ $$$\leq$$$ $$$a$$$ $$$\leq$$$ $$$b$$$ $$$\leq$$$ $$$r$$$ and $$$\frac{LCM (a, b) }{GCD (a, b)}$$$ $$$=$$$ $$$k$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1$$$ $$$\leq$$$ $$$t$$$ $$$\leq$$$ $$$100)$$$.
The first (and only) line of each test case contains three integers $$$l$$$, $$$r$$$ and $$$k$$$ $$$(1$$$ $$$\leq$$$ $$$l$$$ $$$\leq$$$ $$$r$$$ $$$\leq$$$ $$$10^9$$$, $$$1$$$ $$$\leq$$$ $$$k$$$ $$$\leq$$$ $$$10^9)$$$.
For each test case, print a single integer — the number of pairs.
51 20 55 15 620 23 311 2022 1811 111 1
4 3 0 321 101
In the second test case, the pairs are (6, 9), (8, 12), (10, 15).
You will be given a number $$$n$$$ $$$(n \lt 10000)$$$. In one move, you must perform the following operation:
1. If $$$n$$$ has less than four digits in its decimal representation, make it a four-digit decimal number by adding leading zeros.
2. Now sort the digits of $$$n$$$ in ascending order and name it $$$p$$$. Then sort the digits of $$$n$$$ in descending order and name it $$$q$$$.
3. Replace $$$n$$$ with $$$\bf{q-p}$$$.
For example, suppose $$$n=523$$$. After the first move, $$$n=5320-0235=5085$$$.
Your task is to output $$$n$$$ after $$$\bf{k}$$$ moves.
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ $$$-$$$ the number of test cases.
Each test case is described by two integers $$$n$$$ $$$(0 \leq n \lt 10000)$$$ and $$$k$$$ $$$(0 \leq k \leq 10^{18})$$$ $$$-$$$ the given number and the number of moves you have to perform respectively.
For each test case, output a single integer $$$-$$$ the value of $$$n$$$ after $$$k$$$ moves.
5523 29365 23333 1351 35231 7
7992 8172 0 5355 6174
For the first test case, $$$5320-0235=5085; 8550-0558=7992.$$$
For the second test case, $$$9653-3569=6084; 8640-0468=8172.$$$
| Are you familiar with Minimum Spanning Tree? - No? Ok. No problem. I'll teach you. Minimum Spanning Tree(MST) is a subgraph in which each node is present and adds the original graph's minimum weight edge to form a tree. More formally, you have to choose such a sub-graph that makes a tree and the sum of all edge weights is minimum.  Figure: Original Graph We can generate a tree from the original graph like this :  Figure: A tree generated from the Original Graph What is the sum of the edge weight in this tree? 5+4 = 9 . right? Obviously yes is your answer. Can we generate another tree? Yes, we can. Here it is.  Figure: Another tree generated from the Original Graph Obviously 3+5 = 8. But is that tree have the minimum sum of edge weight? - No. So what is it? is it a minimum-spanning tree? - No. These are spanning trees but not minimum spanning trees. So what is the minimum spanning tree here? This is the minimum spanning tree given below:  Figure: Minimum Spanning Tree Is it possible to create more than one minimum spanning tree? Obviously possible. See this picture :  Let's dive into the original problem. There is a given graph. Some nodes of the graph are black-colored, some nodes are red-colored and some nodes are white-colored. Now you can do three operations exactly once:
Now you have to calculate how many edges there are in the graph if only red nodes are colored to the black and ignore the other two operations. |
The first line contains $$$n (3 \le n \le 2\cdot10^5)$$$ and $$$m$$$ $$${(n - 1 \le m \le min(2\cdot10^5, \frac{n(n-1)}{2}))}$$$ — the number of vertices in the graph and the number of edges of the graph.
Each of the next $$$m$$$ lines contains three integers $$$v$$$, $$$u$$$ and $$$w$$$ $$${( 1 \le u, v \le n, 1 \le w \le 10^9)}$$$ — the description of an edge and weight of the edge. You can assume that there will be no self-edge or multiple edges between the same nodes and the graph will be connected.
Print the output in a single line.
3 3 1 2 1 2 3 2 3 1 3
3
If you don't understand the minimum spanning tree. See this example .
Read the statement Again and Again.
We all know that the team RUET_Aftermath secured 5th position in ICPC Asia West Continent Final 2021. This is no small feat to achieve and as usual, they got a huge number of fans all over RUET. So, one day they sat at a booth on that "HUGE" road that goes from RUET Gate to Library to give autographs to their fans.
You, being a big fan of theirs, don't want to miss this opportunity. So, you went to the campus as early as possible, but you heard there is already a huge line of fans waiting for the autographs. But you don't know where the line starts or ends and as the road is "HUGE", it's really impossible for you to locate the line without assistance.
Now you asked for help from one random weird guy to find out the length of the line but he will only help you in his weird way. He divided the "HUGE" road into $$$N$$$ equal units numbered from $$$1$$$ to $$$N$$$. The line of fans starts at unit A and ends at unit B where $$${1 \le A \le B \le N}$$$. Now, if you tell the weird guy an integer number from $$$1$$$ to $$$N$$$, he will tell you if the integer is on or before the start, or after the end of the line of fans. And you can ask him at most $$$55$$$ times.
You need to find out the length of the line.
You can assume that the length of the line will not be more than $$$10^{6}$$$.
At first, the weird guy will give you the value of $$$N (1 \le N \le 10^9)$$$. You will take this as an integer input.
After that, you have to give him an integer by printing "? $$$x$$$" in a line. In reply he will give you one of these characters :
- '<' if $$$x$$$ is before the start of the line i.e. $$$x \lt A$$$ .
- '>' if $$$x$$$ is after the end of the line i.e. $$$x \gt B$$$ .
- '=' if $$$x$$$ is on the line i.e $$$A \le x \le B$$$ .
You can ask him for help in this way at most at most $$$55$$$ times.
Finally after figuring out the length, just print "! $$$y$$$" in a line, where $$$y$$$ is the length.
Additionally, you must flush your output each time you print a line. You can use,
- cout.flush() or endl after printing a line in C++
- fflush(stdout) in C
6 < = = = >
? 1 ? 2 ? 3 ? 4 ? 5 ! 3
1000000000
! 1000000
For the first testcase, the weird guy gives 6 as $$$N$$$. After printing $$$1$$$, the guy tells that it is before the start of the line, and after printing $$$5$$$, the guy tells that it is after the end of the line. And, for $$${2, 4}$$$ and $$$6$$$, the guy tells that these integers are on the line. So, the line started at unit $$$2$$$ and ended at unit $$$4$$$. Thus, the length of the line is $$$3$$$. So, you printed "! 3" as final output.
For the second testcase, the weird guy gives 1000000000 as $$$N$$$. And, somehow you have figured out the length without asking for help from the weird guy.
Note that, it's totally up to you how many questions you'll ask the weird guy but you can't ask more than $$$55$$$ times.