Maybe one day, Fahaxiki will go to a city far away to participate in the competition. The inexperienced Fahaxiki hopes that you can help them plan their routes so that they can spend the least RMB and hours to reach their destination.
There are $$$n$$$ cities in the country, connected by $$$m$$$ railways and $$$l$$$ air routes, all of which are regarded as undirected roads. Obviously, schools, train stations, airports and competition sites in a city should be in four different locations. It is known that it takes $$$x$$$ RMB and $$$y$$$ hours to move between any two locations in the same city.
Suppose Fahaxiki is in a school located in city $$$1$$$, and needs to go to the competition site in city $$$n$$$ to participate in the competition. Please find the minimum cost and hours to reach the destination. Prioritize the least cost. If there are multiple paths with the least cost, choose the least hours-consuming solution.
The first line contains one integer $$$T(1 \leq T \leq 10^5)$$$, which represents the number of test case.
For each test case, the first line consists of five integers $$$n, m, l, x, y (1 \leq n \leq 10^5, 0 \leq m, l \leq 10^5, 1 \leq x, y \leq 10^3)$$$, $$$n$$$ cities, $$$m$$$ railways, $$$l$$$ air routes. And it takes $$$x$$$ RMB and $$$y$$$ hours to move between any two locations in the same city.
Each of the next $$$m$$$ lines contains four integers $$$u_i, v_i, a_i, b_i (1 \leq u_i, v_i, \leq n, 1 \leq a_i, b_i \leq 10^3)$$$, indicates that there is a railway connecting city $$$u_i$$$ and city $$$v_i$$$, which costs $$$a_i$$$ RMB and $$$b_i$$$ hours.
Each of the next $$$l$$$ lines contains four integers $$$u_i, v_i, a_i, b_i (1 \leq u_i, v_i, \leq n, 1 \leq a_i, b_i \leq 10^3)$$$, indicates that there is a air route connecting city $$$u_i$$$ and city $$$v_i$$$, which costs $$$a_i$$$ RMB and $$$b_i$$$ hours.
The sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.
The sum of $$$(m + l)$$$ over all test cases doesn't exceed $$$10^6$$$.
For every prediction if there is a route to the destination, output the minimum cost and hours, otherwise output -1.
2 3 2 1 50 1 1 2 300 25 2 3 140 10 1 3 450 3 4 3 2 100 2 1 2 600 20 1 4 1000 40 3 4 700 21 2 4 300 2 1 3 200 2
540 37 1200 28
In the first example, the action route is: city 1 school -> city 1 train station -> city 2 train station -> city 3 train station -> city 3 competition site, it costs 540RMB and 37 hours.
In the second example, the action route is: City 1 School -> City 1 train station -> City 2 train station -> City 2 Airport -> City 3 Airport -> City 3 Competition Site, it costs 1200RMB and 28 hours in total
Hsueh- is about to gradute! Congratulations! Wish all of you a brilliant future like him!
Because of Hsueh-'s active performance in the ACM, his gold medals are too many to take home. So he has to choose some of them.
Hsueh- has only one box. To make it beautiful, he will stack up his gold medals as a tower, which means every gold medal must be putted on another gold medal except the bottom medal, and there will be exactly one gold medal on each layer. In order to make the tower stable, Hsueh- will choose an integer $$$p$$$, then the lower gold medal should be at least $$$p$$$ $$$cm^2$$$ larger than the gold medal right above it. In other words, if the sizes of the tower consists of $$$k$$$ gold medals from top to bottom are $$$s_1$$$, $$$s_2$$$, $$$s_3$$$, $$$\dots$$$, $$$s_k$$$, then $$$s_1 + p \leq s_2$$$, $$$s_2 + p \leq s_3$$$, etc.
Hsueh- has $$$n$$$ gold medals, the sizes are $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n$$$ $$$cm^2$$$, and they have the same height. The box can contain at most $$$m(m \leq n)$$$ gold medals. Now Hsueh- was wondering the maximal integer $$$p$$$ that can fill the box.
The first line contains one integer $$$T(1 \leq T \leq 100)$$$, which represents the number of test case.
For each test case, the first line consists of two integers $$$n$$$, $$$m(2 \leq n \leq 10^3$$$, $$$2 \leq m \leq n)$$$ — the number of gold medals Hsueh- has and the number of gold medals his box can contain.
The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n(1 \leq a_i \leq 10^6)$$$ — the sizes of $$$n$$$ gold medals.
For each test case, print the maximal integer $$$p$$$ that can fill the box.
3 4 2 1 2 3 4 6 3 1 1 2 2 3 3 6 2 1 10 100 10000 100000 1000000
3 1 999999
It's been over 500 years since the human race almost went extinct at the hands of the fearsome and mysterious "Beasts". The surviving races now make their homes, towns, and cities up on floating islands in the sky to keep out of reach of all but the most mobile of Beasts.
Chtholly is on the $$$1$$$-th island now, and she wants to reach the $$$n$$$-th island. Due to her flying abilities (we can think of her flying abilities as an array $$$a$$$), she can fly exactly to the $$$(j + a_i)$$$-th island when she is on the $$$j$$$-th island. For example, if she is on the $$$1$$$-th island now, and her flying ability array $$$a$$$ is $$$[1, 3]$$$, she can only reach the $$$2$$$-th island or the $$$4$$$-th island at this time.
As a clever girl, Chtholly can improve her flying abilities before starting the flight, which means she will add some integers to her ability array $$$a$$$ when she is on the $$$1$$$-th island. For example, if her original flying ability $$$a$$$ is $$$[1, 3]$$$, and she adds $$$[2, 4]$$$ to $$$a$$$. Now her ability array is $$$[1, 2, 3, 4]$$$, she can reach one island from the $$$2$$$-th island to the $$$5$$$-th island at this time. All the abilities Chtholly has and will improve are different. In other words, they are all distinct integers.
Now, Chtholly has known the abilities she can improve. Obviously, the number of ways she can reach the $$$n$$$-th island will be affected by her choice. As a curious girl, Chtholly wants to know in how many different ways she can reach the $$$n$$$-th island if she choose some abilities to improve. She will give you $$$q$$$ choices, and you should tell her the answer to each choice.
The way records the flying abilities Chtholly used in turn. A way $$$x$$$ is different from a way $$$y$$$ if their lengths are different or there exists an index $$$i$$$ such that $$$x_i \neq y_i$$$. You can see a specific example in the notes.
The first line contains three integer $$$n$$$ ($$$1 \leq n \leq 10^4$$$), $$$m$$$ ($$$1 \leq m \leq 10$$$), and $$$k$$$ ($$$1 \leq k \leq 10$$$) — the index of island Chtholly wants to reach, the number of abilities she has and the number of abilities she can improve.
The second line contains $$$m$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_m$$$ $$$(0 \leq a_i \leq 10^4)$$$ — the ability Chtholly has.
The third line contains $$$k$$$ space-separated integers $$$b_1$$$, $$$b_2$$$, $$$\dots$$$, $$$b_k$$$ $$$(0 \leq b_i \leq 10^4)$$$ — the ability Chtholly can improve. It is guaranteed that all integers in $$$a$$$ and $$$b$$$ are different.
The next line contains one integer $$$q$$$ $$$(1 \leq q \leq 10^4)$$$ — the number of choices Chtholly wants to know.
Each of the next $$$q$$$ lines contains an integer $$$c$$$ $$$(0 \leq c \leq k)$$$, followed by $$$c$$$ distinct integers $$$d_1$$$, $$$d_2$$$, $$$\dots$$$, $$$d_c$$$ ($$$1 \leq d_i \leq k$$$)separated by spaces — indexes of abilities Chtholly improve on this choice.
For each choice, print the number of different ways Chtholly can reach the n-th island. Since the answer can be very huge, you have output it modulo $$$10^9 + 7$$$.
4 1 1 2 1 2 0 1 1
0 3
1 1 1 2 3 2 0 1 1
1 1
5 2 2 1 2 3 4 4 0 1 1 1 2 2 1 2
5 7 6 8
In the first example, the situation is as follows:
- In the first choice, Chtholly's ability array is $$$[2]$$$, she can only reach the $$$1$$$-th island and the $$$3$$$-th island in islands with indexes less than or equal to $$$4$$$.
- In the second choice, Chtholly's ability array is $$$[1, 2]$$$, she can reach the $$$4$$$-th island in three ways.$$$[2, 1]$$$, $$$[1, 2]$$$, and $$$[1, 1, 1]$$$.
Do you know why lllllan is called "Su Mama"? If you don't know, I'll tell you now. Because lllllan is very friendly to his friends. Every year when he returns to his hometown after one year's study, he will visit every friend once. It can be seen that he really attaches great importance to the relationship between him and his friends, and when they are in trouble, lllllan will always give a hand. I'm lucky to be one of these friends.
As usual, lllllan is going to visit his friends. But the difference is that lllllan is moveing house this year. Considering that his former house is far away from some friends' houses, so he wanted the new house to be the same distance from all his friends' houses.Now, lllllan wants to visit all his friends from his home.You know, lllllan has a kind of magic, he can change the length of the road he walked to $$$0$$$. Now you need to find the location of lllllan's new house, and the minimum distance after lllan visited all his friends.To simplify this problem, we assume that lllllan's hometown is in a Cartesian coordinate system, and each house is regarded as a point on the plane.
The coordinates of each point (including lllllan's home) are integers.
The first line of input contains one integer $$$n$$$, where $$$n(3 \leq n \leq 10^6)$$$ is number of lllllan's friends.
The next $$$n$$$ lines describe the house of lllllan's friends, the $$$i$$$-th of which contains two integers $$$x_i,y_i (1 \leq x_i, y_i \leq 10^4)$$$, which are the coordinates of the $$$i$$$-th houses.
The testcase ensures that all coordinates are different.
In the first line, output the coordinates of the points meeting the conditions, separated by spaces.
The second line outputs a number, the minimum distance.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. You answer is accepted if and only if $$$\frac{|a-b|}{max(1,|b|)} \leq 10^{-4}$$$.
If there is no coordinate of the point that meets the condition, output "-1"(without quotes) in one line.
4 1 1 1 3 3 1 3 3
2 2 5.6568542495
5 3 1 2 3 3 5 4 4 6 5
-1
The situation in the first example:
During the May Day holiday, Tryna went to visit the dentist. Unfortunately, his dentist was a so beautiful girl that he spent a lot of money in pleasing her. Now he has to have two slices of bread with cheese for breakfast for the rest of the month.
Worse, Tryna went to the supermarket and bought too much cheese. The $$$i$$$-th piece of cheese has the freshness $$$a_i$$$. The freshness of cheese will be reduced by $$$1$$$ every day, and Tryna can eat one piece of cheese at most in a day. Because of Tryna's special hobby, he will only choose the cheese whose freshness can be divided by two to eat.
Now Tryna is wondering how long does it take him to finish all the cheese at least.
The first line contains $$$1$$$ integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the amount of cheese Tryna bought.
The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n$$$ ($$$5 \cdot 10^5\leq a_i \leq 10^6$$$) — the freshness of the cheese.
Print the minimum number of days Tryna need to finish all the cheese at least.
4 500001 500002 500003 500004
4
2 500001 500003
4
2 500004 500002
3
In the first example, one possible situation is as follows:
- In the first day, Tryna take the second piece of cheese, then the freshness array = $$$[500001$$$,$$$500003$$$,$$$500004]$$$.
- In the next day, the array = $$$[500000$$$,$$$500002$$$,$$$500003]$$$. Tryna take the first piece of cheese, then the arrry = $$$[500002$$$,$$$500003]$$$.
- The rest is the same as above.
In the second example, one possible situation is as follows:
- In the first day, Tryna can't take any piece of cheese since no piece of cheese's freshness can be divided by two.
- In the next day, the array = $$$[500000$$$,$$$500002]$$$. Tryna take the first piece of cheese, then the array = $$$[500002]$$$.
- The rest is the same as above.
In 2021, the story of Despicable Me is staged on Sstee1XD. The difference is that due to the mutation of the minion's DNA and the mistakes in population control, the number of minions in the backyard of Sstee1XD has exploded exponentially. No one has a solution, Sstee1XD can only ask you to help count the number of minions.
Suppose that on the first day, the first minion was born in the backyard of Sstee1XD's house. Every day thereafter, each minion will reproduce more minions.The law of reproduction is that each minion will reproduce $$$i$$$ minions on the $$$i$$$-th day after birth.
The first line contains one integer $$$T(1 \leq T \leq 10^5)$$$, which represents the number of test case.
For each test case, the first line consists of one integer $$$n (1 \leq n\leq 10^{18})$$$, The number of days of reproduction of minions.
For each test case, output an integer representing the total number of minions on n-th day.Since the answer can be very large, you have output it modulo $$$10^9+7$$$.
3 1 2 3
1 2 5
1 1000000000000000000
761203726
This picture is an explanation of the first example:
- On the first day, 1-th minion was born, so the total number of minions on the first day was 1.
- On the second day, because 1-th minion had existed for one day, it reproduction 2-th minion, so the total number of minions on the second day was 2.
- On the third day, because 1-th minion had existed for two days, it reproduction 3-th minion and 4-th minion; because 2-th minion had existed for one day, it reproduction 5-th minion, so the total number of minions on the third day was 5.
This is an interactive problem.
$$$Kwords$$$ has a permutation $$$a_1,a_2,...,a_n$$$ of $$$1$$$ to $$$n$$$, now you can ask him no more than $$$10$$$ questions to guess the permutation.
For each query, you can give him a set $$$s$$$ of $$$k(1\leq k\leq n)$$$ indexes, he will give you a sorted array of $$$[a_{s_1}, a_{s_2},...,a_{s_{k}}]$$$.
$$$Kwords$$$ thinks the problem is very interesting and invites you to solve it with him.
The first line contains a single integer $$$n(1\leq n\leq 1000)$$$.
When you are ready to answer, print a single line of the form "! $$$a_1$$$ $$$a_2$$$ $$$…$$$ $$$a_n$$$" $$$(1\leq a_i \leq n)$$$, where $$$a$$$ is a permutation.
When you are ready to query, print a single line of the form "$$$k$$$ $$$s_1$$$ $$$s_2$$$ $$$…$$$ $$$s_k$$$" $$$(1\leq k,s_i\leq n)$$$.
After printing a line, do not forget to flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
You will get Wrong answer if you ask more than $$$10$$$ questions.
4 1 3 2 3
2 1 2 2 1 3 ! 3 1 2 4
When you first joined the ACM Lab, you were full of ambition, but you always lying in bed eating potato chips, watching anime, and planning your future training plan and goals. As a result, an immature ACMer was stumbled by the sluggish life. On this day, Your senior, gold medal player Hsueh can't bear your depraved and degraded life. In order to revive the glory of ACM Lab in HZNU, he decided to hold a temporary meeting to remind everyone.
Due to the prevention and control of the COVID-19, everyone must sit apart when they come to the conference room.In other words, there at least one empty seat between two people. Assuming that there is a large round table in the conference classroom, you are required to judge whether it can accommodate all laboratory members. If so, output the total number of seating plans; otherwise, output $$$0$$$.
Since the answer can be very large, you have output it modulo $$$10^9+7$$$.
The first line contains one integer $$$T(1 \leq T \leq 100)$$$, which represents the number of test case.
For each test case, the first line consists of two integers $$$n,m (1 \leq n,m \leq 10^5)$$$, the number of people in the laboratory and the number of seats in the meeting room. Each person and seat is considered to be different.
For each test case, output an integer representing the total number of different seating plans.
1 2 4
4
Fahaxiki got the opportunity to participate in live competitions through an online competition, and will go to the beautiful Wuhan University to participate in the game. Although they traveled at their own expense on the weekend, they didn't want to miss the opportunity of this trip, so they ask you to help them calculate some problems so that they can get a better travel experience.
In order to simplify the problem, we abstract the developed traffic in Wuhan into some weighted undirected edges, connecting the whole Wuhan into a tree. Find the length of the longest simple path containing k nodes in this tree. A simple path means that the vertices on the path do not overlap with each other.
The first line contains two integers $$$n, k (1 \leq n, k \leq 10^5)$$$, and $$$k$$$ doesn't exceed diameter of the tree.
Then next $$$n - 1$$$ lines, each lines contains three integers $$$a, b, c(1 \leq a, b \leq n, 1 \leq c \leq 10^3)$$$, denote there is an edge between $$$a, b$$$ and length is $$$c$$$.
Output the length of the requested path
4 3 3 4 45 2 3 89 3 1 18
134
As we all know, the 2020-2021 season is a boring season. Because the Fahaxiki team failed to get the spot to participate in the live game, it was tantamount to losing an opportunity to travel at public expense. But Tryna is very much looking forward to a chance to travel at public expense, he thought...
In Tryna's dream, the Fahaxiki team came to Shanghai. They visited the Oriental Pearl Tower, walked through the Bund and even went to Disneyland. However, during this trip to Disney, a little accident happened. Tryna and his teammates are separated, he can only rely on his poor sense of direction to try to find an exit and reconnect with his teammates. It is known that Tryna is a smart person. If there are some simple loads in Disney, he will try his best to walk all the roads to find the exit. At the same time Tryna is also a fool. If some roads in Disney form a ring, he will be trapped in the ring and cannot find an exit. (simple loads , here is a concept relative to ring , all roads that cannot be formed into a ring are collectively referred to as simple loads in this question)
Assuming that Disneyland is a two-dimensional plane, you don't care about the location of Tryna and the location of the exit, you only need to determine whether there is a ring in the plane that can trap Tryna. The smallest unit in the plane is a square surrounded by four sides, and each side represents the barrier from the adjacent unit. If there is no barrier between the two smallest units, it means that the two units are connected to each other. If there is no loop output YES, it means Tryna can find the exit by its own ability. Otherwise, the output NO means that poor Tryna will be trapped in Disney alone.
The first line contains integers $$$n,m(1 \leq n, m, n \cdot m \leq 10^5)$$$, indicating the size of the two-dimensional plane.
Next $$$n+1$$$ lines, each line has $$$2 \cdot m+1$$$ characters. The character '|' or '_' means that there is a wall between the two points and cannot be passed through. On the contrary, a blank space means that two points are connected, representing a road.
output on a separate line:
- YES if Tryna can find an exit by its own ability
- NO otherwise.
You can output YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).
2 3 _ _ _ | | |_| |_ _|_|
YES
2 3 _ _ _ | |_| |_ _|_|
NO
In the first example, (1,1) is connected to (2,1), (2,1) is connected to (2,2), and (2,2) is connected to (1,2). There is no ring in the plane.
In the second example, (1,1) is connected with (2,1), (2,1) is connected with (2,2), (2,2) is connected with (1,2), and (1 ,2) is connected with (1,1). A ring is formed in the plane.