Anya has a big problem. Her father's birthday and National Father's Day happen in the same week. Anya loves her father so she bought a large number of gifts to give him. Anya doesn't want to give him all gifts in one day, that's why she will give some gifts to her father on his birthday and the rest of them on father's day. Of course, all gifts must be given and her father must receive at least one gift on each of the two dates.
Anya's father is a very elegant man with refined tastes, so his gifts should be as elegant as possible. At the time of purchasing the gifts, the store owner gave an elegance score to each of the gifts. Anya wants to distribute the gifts in such a way that the sum of the XOR of the elegance score of the gifts she gives on Father's Day and the XOR of the elegance score of the gifts she gives on his birthday is maximum.
Help Anya accomplish this difficult and elegant task.
The first line contains an integer $$$N$$$ ( $$$2 \leq N \leq10^{5}$$$ )indicating the number of gifts Anya bought.
The next line contains $$$N$$$ integers $$$e_{i}$$$ ($$$0 \leq e_{i} \lt 2^{50}$$$) for $$$i = 1,2...N$$$, denoting the score of elegance of each present.
Output a single line with an integer representing the result of this task.
4 1 2 4 8
15
4 10 8 6 17
41
Treeland is a country consisting of $$$n$$$ cities and $$$n-1$$$ bidirectional roads. As you might imagine, Treeland is a tree, which means that there is exactly one simple path between each pair of cities.
The president of Treeland plans to build a 5G network in the country during $$$n$$$ days. Everyday, a 5G antenna tower will be built in a different city according to the following rules:
More formally, let $$$P=[p_1, p_2, \dots, p_n]$$$ be a permutation where $$$p_i$$$ is the city where an antenna is built during day $$$i$$$. For all $$$i \gt 1$$$ there must be a $$$j \lt i$$$ such that $$$dist(p_i, p_j) \leq k$$$, and $$$P$$$ must be the lexicographically smallest possible permutation. Here we define $$$dist(p_i, p_j)$$$ as the number of roads in the simple path from $$$p_i$$$ to $$$p_j$$$.
Find and print $$$P$$$.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$ and $$$1 \leq k \leq 100$$$).
Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$, indicating that there is a road connecting cities $$$u$$$ and $$$v$$$.
Print a single line with $$$n$$$ integers separated by a space $$$-$$$ the answer to the problem.
3 1 1 3 2 3
1 3 2
5 2 1 4 1 5 4 2 5 3
1 2 3 4 5
5 1 1 2 1 5 2 4 3 5
1 2 4 5 3
You are the teacher of a kindergarten classroom and there will be a party in a few days. As expected, you are in charge of bringing all the candies for the kids. You have created $$$q$$$ possible plans over the $$$n$$$ types of candies that exist. For each plan:
First of all, the $$$i$$$-th type of candy has a sweetness level of $$$a_{i}$$$ (this value can be negative, in the case of sour or spicy ones). You have sorted all these values in ascending order ($$$a_{i} \lt a_{i + 1}$$$ for all valid $$$i$$$).
Then, you choose $$$k$$$ tuples $$$(l, r, x)$$$ that mean that you'll buy $$$x$$$ candies of each type with id in the range $$$[l, r]$$$.
The beauty of a plan is the value of the median of all the sweetness levels of the candies you choose. Your task is to compute the beauty of each plan.
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 5 \cdot 10^{5}$$$) — The number of types of candies and the number of plans to analyze.
The second line of input contains $$$n$$$ integers $$$a_{i}$$$ ($$$|a_{i}| \leq 10^{9}$$$, $$$a_{i} \lt a_{i + 1}$$$ for all valid $$$i$$$) — The sweetness level of the types of candy.
The lines describe $$$q$$$ plans.
The first line of a plan contains an integer $$$k_{i}$$$, the number of tuples of the $$$i$$$-th plan.
The following $$$k_{i}$$$ lines contain three integers $$$l_{j}$$$, $$$r_{j}$$$ and $$$x_{j}$$$ ($$$1 \leq l_{j} \leq r_{j} \leq n$$$, $$$1 \leq x_{j} \leq 10^{6}$$$) — The limits of the range of ids to choose and the number of candies to choose from each type, respectively.
It is guaranteed that the sum of $$$k_{i}$$$ among all the plans doesn't exceed $$$5\cdot 10^{5}$$$.
Print $$$q$$$ lines — The $$$i$$$-th line must contain the beauty of the $$$i$$$-th plan. Your answer will be considered correct if its relative or absolute value doesn't exceed $$$10^{-9}$$$.
In other words, let's assume that your answer is $$$a$$$, and the answer of the jury is $$$b$$$. The checker program will consider your answer correct, if $$$\frac{|a-b|}{\max(1, b)} \leq 10^{-9}$$$
7 3 -19 -2 0 9 17 18 20 2 4 6 1 2 6 4 1 3 3 1 2 3 4 2 1 5 1
9 0 0
7 3 -15 -9 -7 0 1 12 15 1 2 7 1 1 7 7 1 4 5 6 1 3 6 5 6 7 4 7 7 2
0.5 15 6.5
Francovich is planning to travel the world via boat, he insists on being via boat because he really loves marine life and marine food.
In each port, he will receive a stamp in his book that keeps track of the arrival for legal purposes.
Because the book has the pages ordered the book will be different depending on the order that he visits the ports, and because he doesn't have a clear destination and want to pass by ports as many times as he can because he doesn't like direct travel. Francovich wonders what is the different numbers of ways his book of stamps can look and is your task to help him!
The ports have predefined travel routes that are bidirectional and Francovich only has enough money to do exactly $$$K$$$ travels and starts in port number 1.
The first line will have three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$2 \leq N \leq 100$$$, $$$1 \leq M \leq 5000$$$, $$$1 \leq K \leq 10^5$$$) that describe the number of ports, the number of travel routes between ports, and the number of travels that Francovich can do.
The next $$$M$$$ lines will have two integers $$$A$$$, $$$B$$$ ($$$1 \leq A,B \leq N$$$) each that describe a direct travel route between the port $$$A$$$ and the port $$$B$$$
A single integer $$$X$$$ that describes the number of ways Francovich's pass-a-port can look after his $$$K$$$ travels. Because this number can be very large print it modulo $$$10^9 + 7$$$.
6 5 1 1 2 1 3 3 6 1 4 1 5
4
6 5 2 1 2 1 3 3 6 1 4 1 5
5
6 5 4 1 2 1 3 3 6 1 4 1 5
22
Ivanovich is highly considered an Erudite of words.
But Ivanovich doesn't know what it means, maybe is about knowing a lot of words, and the ability to use them in the right context is not important.
So Crystalovich wanted to test how good of an Erudite is Ivanovich, so she asked him how many words there are with length $$$N$$$ using an alphabet of $$$M$$$ different letters.
Francovich hearing the problem thought it was very easy, and he doesn't like easy problems, so he added a condition such that each word have to use exactly $$$K$$$ different letters.
Help Ivanovich answer the question, since the answer can be very large print it module $$$10^9 + 7$$$
The first and only one line contains three integers $$$N$$$, $$$M$$$ and $$$K$$$ with ($$$1 \leq N \leq 10^6$$$) ($$$1 \leq K \leq M \leq 5 \times 10^3$$$) representing the length of the word, the size of the alphabet, and the number of different letters that the words should have.
A single number indicating the numbers of words modulo $$$10^9 + 7$$$
3 3 3
6
5 2 2
30
1000 1000 1
1000
Froginald is a very happy frog living in his pond, he got very excited when he knew that the Grand Prix of Mexico is starting again so he decided to go immediately to participate! Even if that means missing an exam, a class, or a day of work.
The road for the Grand Prix is filled with rocks, rocks that we need to overcome to be closer and closer to the Grand Prix.
In the case of Froginald, he can simply jump over them, the road of rocks is a linear path to the Grand Prix, and Froginald can jump to +1 of his position or +2, always ending up closer to the goal. Unfortunate for Froginald some of the rocks are missing being that if he tries to jump to a place with a missing rock he would end up drowning in the lake, so he would definitely try to avoid that.
The road to the Grand Prix is long, and there are many ways to travel it, Froginald is so excited about starting his journey that he wants to know how many ways is for him to reach the goal!
Froginald starts in position 0 which will always have a rock, as well as position $$$N$$$.
The first line has two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^9$$$) ($$$1 \leq M \leq 1000000$$$) indicating how long the road is, and how many holes are in the road. The next line will have $$$M$$$ integers indicating that the position $$$a_i$$$ doesn't have a rock.
A single integer that represents the number of ways that Froginald has to reach the position $$$N$$$, because this number can be very large print it modulo $$$10^9 + 7$$$.
5 1 2
2
The Grand Prix of Mexico wishes to organize its next regional event in the same venue for all the participants, also this year it has a budget to help the participants to move to the venue of the event, so it wants to calculate how much transportation would cost per participant towards headquarters. They also want the process to be as comfortable and easy as possible for the participants, because they want them to stress as little as possible before the day of the regional, so each participant will be picked up at their door.
The organization in Mexico does not have enough vehicles to do this, so it has contacted a transport office to calculate the costs and they have given a cost per kilometer for each participant depending on the location of their home. The transport office ensures it can provide a vehicle for each participant and that will start the travel simultaneously for all participants to the desired venue.
The organization plans to give an equal budget to each participant for logistical reasons when making the final calculation of expenses, so given the cost per kilometer per participant and the exact location of each participant, can you help calculate the minimum cost per participant such that all participants can meet in one place?
For simplicity the distance from a participant to any other location is calculated in Euclidean distance.
In the first line of input a number $$$n(1 \leq n \leq 100)$$$ the number of participants
In the next $$$n$$$ lines three integers $$$x_i(-10^4 \leq x_i \leq 10^4)$$$, $$$y_i(-10^4 \leq y_i \leq 10^4)$$$ and $$$c_i(1 \leq c_i \leq 10^4)$$$ the pair ($$$x_i$$$, $$$y_i$$$) are the coordinates of the participant $$$i$$$ and $$$c_i$$$ is the cost per kilometer that it takes to transport the participant $$$i$$$
In a single line print the minimum budget per participant the organization has to invest to take alll the participants to a single place
Your answer is considered correctly if its absolute or relative error does not exceed $$$10^{-4}$$$
Formally let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{max(1, |b|)} \leq 10^{-4}$$$
2 1 1 1 -1 -1 1
1.414214
4 0 1 1 1 0 1 0 -1 1 -1 0 1
1.000001
Jaime has been successful building fences to keep his sheep safe, the fences he builds are very classic wooden fences forming a rectangle or a square. Seeing the success he has with sheep, he plans on expanding his business and will build fences for hogs. He built the first fence for some hogs and after a couple days, the fence was broken, hogs are really clever to find a way out of the fence.
Jaime has developed a new fence that uses an unbreakable metal wire, he will build a fence and verify the hogs are not able to escape from it, nor break it. To build the fence Jaime has $$$N$$$ units of this metal wire, each unit with a $$$1$$$ meter size. Since the metal wire is unbreakable he has to build each of the $$$4$$$ walls for the fence using complete metal wire units and then join them at their ending points forming the rectangular fence. Note the metal wire units can not be broken, and a wall containing $$$L$$$ metal wire units will have $$$L$$$ meters in length.
Jaime has a lot of hogs now, and no fence ready, this is why he wants to build the fence that encloses the maximum possible area he can using this new metal wire. Jaime is not really good at math, so he asked your help to find the maximum area he can enclose building his fence with the $$$N$$$ units he has.
The first and only line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 1000$$$). The number of metal wire units Jaime has to build the fence.
Print a line with an integer, representing the maximum area Jaime can enclose with a fence built using the $$$N$$$ units.
4
1
15
12
Isabel is a very curious girl. She is learning to count and to divide numbers, as she is a beginner performing divisions she can divide only by a one digit number, for example, she can divide $$$123456$$$ by $$$2$$$ but not by $$$20$$$. To train her division skills she invented a simple game, she writes a number $$$N$$$ of at most $$$8$$$ digits and then she counts how many digits that form $$$N$$$ divide $$$N$$$ without reminder, for example, if $$$N = 111$$$, each of the three $$$1$$$ divide $$$N$$$ and then she counts $$$3$$$. if $$$N=39$$$ the only digit in $$$N$$$ that divides $$$N$$$ is $$$3$$$ and then she counts $$$1$$$.
Isabel wants you to play with her, but you are busy training for the next programming contest, then you decided to make a program that obtains the count Isabel will get for each $$$N$$$. This is your task in this problem.
The input consists of a single line, which contains a positive integer number $$$N$$$ of at most 8 digits.
Your program must output a single line, containing an integer indicating the count Isabel will get for the number N.
111
3
39
1
39333000
4
12345678
4
Jeffrey is the richest man in the world. In fact, he is so rich that he could buy all the major companies himself. Ordinary people don't like this, they wish every rich man was limited to having only one company.
The world council has listened to the requests of the people and has put the most important companies in the world up for sale. Each of the $$$N$$$ rich men in the world have given a list of the companies they would like to buy. The world council will be in charge of deciding which company will sell to each of the richest men.
Unfortunately, by meeting these conditions, it is possible for some companies to become ownerless. Which is terrible, since it is possible that Jeffrey take advantage of it and try to buy them, being thus, owners of more than one company.
People do not want this to happen, that is why the world council has given you the task of deciding which company to sell to each rich man, in such a way that at the end of the sale the minimum number of companies ends up without an owner.
Remember that rich men will only buy companies that are on their list.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 10^4$$$) indicating respectively the number of rich men and the number of major companies. Each of the next $$$N$$$ lines describe each rich man list of companies. Each line starts with an integer $$$K$$$ ($$$0 \leq K \leq M$$$) indicating the number of companies he would like to buy, followed by $$$K$$$ integers $$$c_i$$$ ($$$1 \leq c_i \leq M$$$) for $$$i=1,2..K$$$ indicating the company he would like to buy.
It is guaranteed that the sum of $$$K$$$ does not exceed $$$10^5$$$.
Output a single line with an integer indicating the minimum number of companies that will end up without an owner.
5 6 2 1 2 0 1 3 1 4 2 1 5
2
5 5 1 1 1 2 1 3 1 4 1 5
0
A shelter for homeless people wants to buy $$$n$$$ kilograms of rice for their dinner, but the market only offers bags of rice in predefined weights, making hard for the shelter to buy rice without waste.
For example, if the shelter wanted to buy $$$10$$$ kilos of rice for the dinner and the available presentations at the market have bags of rice with $$$2$$$, $$$15$$$, and $$$7$$$ kilos, the shelter can buy exactly $$$10$$$ kilos buying 5 bags of 2 kilos and no rice will be wasted that night. However, if the shelter wanted to buy $$$5$$$ kilos, there is no way they can buy rice in a way there is no waste, in this case, the minimum waste they can achieve is $$$1$$$ (buying $$$3$$$ bags of $$$2$$$ kilos).
Given a list of rice sales presentations available at the market, and the amount of rice the shelter wants to buy for each of the next $$$k$$$ dinners, find the minimum rice waste the shelter can have for each dinner.
The first line of input contains two integer numbers separated by a space $$$k$$$, and $$$p$$$, ($$$1 \leq k \leq 10^5$$$, $$$1 \leq p \leq 50$$$) representing the number $$$k$$$ of dinners the shelter will make, and the number $$$p$$$ of presentations of rice the market sells. The second line of input contains $$$p$$$ integer numbers separated by space, where the $$$i$$$-th number represents the amount of rice $$$r_i$$$ ($$$1 \leq r_i \leq 100$$$) on the $$$i$$$-th rice presentation available at the market. Each of the next $$$k$$$ lines contains an integer number, where the $$$i$$$-th line represents the amount of rice $$$n_i$$$ ($$$1 \leq n_i \leq 5 \times 10^4$$$) the shelter needs to buy for the $$$i$$$-th dinner.
Print $$$k$$$ lines, where the $$$i$$$-th line contains a single integer number, the minimum rice waste the shelter can have after buying rice for the $$$i$$$-th dinner.
2 3 2 15 7 10 5
0 1
2 3 11 24 35 105 10
0 1
3 2 10 17 1 16 27
9 1 0
The Leones(0,0,0) have finally retired from competition after several years in college and have decided to take a nice vacation at the beach. Although they are a little sad to leave their years of competition in the Grand Prix of Mexico.
They were relaxing in an enramada, ordering some piña coladas and looking at the sea in the distance, when a group of sailboats began to line up on the horizon... it just so happened that the sailboats had numbered sails. After a few minutes the great sage of the Caribbean arrived (also known as the man who sells prepared coconuts) and proposed a riddle in which they would win free coconuts if they solved it correctly. The team could not refuse to do one last problem and they got ready to solve it.
The riddle said the following: Visualize all the sailboats on the horizon as a list of numbers $$$A$$$ then take an element $$$A_i$$$ and calculate the sum of elements for all possible ranges $$$[l, r]$$$ such that $$$A_i $$$ has the maximum value among all elements between $$$A_l$$$ and $$$A_r$$$ inclusive.
This riddle was clearly very simple, so after the team answered it correctly, the wise man from the Caribbean decided to make the riddle even more interesting. Now, for the prize of free coconuts for life, the riddle said: let's say that the previous riddle is the result of $$$ f(i)$$$ for a sailboat at position $$$i$$$, then solve the sum of $$$f(i)$$$ for all existing sailboats
This puzzle has exceeded the capabilities of the participants and now they ask for help from the next generations of ICPC
In the first line a number $$$n(1 \leq n \leq 10^6)$$$ the number of sailboats in the sea.
In the second line $$$n$$$ integers that represents the numbers in the sails of the boats. $$$(-10^9 \leq a_i \leq 10^9)$$$
The first and only line in the output is the answer to the riddle modulo $$$10^9 + 7$$$
4 1 2 5 3
58
7 1 2 3 4 6 5 1
297