As a child, Techno heard a story about Gauss who was able to quickly calculate the sum of numbers from 1 to 100. Gauss' technique was to add 1 to 100, 2 to 99, 3 to 98, and so on until 50 to 51. Thus, the sum would be 101 times the number of pairs: 50.
Mini technoblade not impressed by Gauss idea, written in the white board above Everyone is always impressed by this story, except Techno. He decided to do something more impressive and find the sum of the first $$$n$$$ odd numbers: 1 + 3 + 5 ... + $$$2n-1$$$.
The input consists of a single integer $$$n$$$, $$$1 \leq n \leq 10^7$$$.
Print on a single line the integer representing the sum of the first $$$n$$$ odd numbers: $$$1 + 3 + 5 ... + (2n-1)$$$.
Note that this number does NOT fit in a 32-bit integer. In C/C++, use "long long int" for the answer and for $$$n$$$, or use Python.
1
1
2
4
3
9
10000000
100000000000000
For $$$n = 1$$$, the sum is just 1.
For $$$n = 2$$$, the sum is $$$1 + 3 = 4$$$.
For $$$n = 3$$$, the sum is $$$1 + 3 + 5 = 9$$$.
For $$$n = 4$$$, the sum is $$$1 + 3 + 5 + 7 = 16$$$. And so on.
Technoblade is famous for always taking things to the extreme. One day he was planting potatoes and, after seeing the size of his huge plantation, he became curious to know how long it would take for him to become the person with the most potatoes. After investigation, Techno did the math and saw that he has $$$X_1$$$ potatoes and produces $$$Y_1$$$ potatoes per day, while his biggest competitor, Squid Kid, has $$$X_2$$$ potatoes and produces $$$Y_2$$$ potatoes per day.
He will declare himself victorious of the 1st Potato War if he has a strictly greater number of potatoes than Squid. Help Techno predict the outcome of this battle.
The input is just one line with 4 integers $$$X_1,Y_1,X_2,Y_2$$$ separated by space, in this order. It is guaranteed that all numbers are greater than or equal to 0 and less than or equal to 1000.
If Technoblade is destined for success and victory in the 1st Potato War, print the smallest number of days until he has strictly more potatoes than SquidKid. If he still doesn't have a large enough plantation, and won't win the battle in a finite time, print $$$-1$$$.
1000 0 999 1000
0
0 1 1000 0
1001
100 2 200 1
101
For a company to know if it is doing well or poorly in sales, it is important to analyze the average sales over a period of time.
As a sales analyst, you observe $$$K$$$ consecutive months intervals and find the average. You are interested in the first interval with the lowest average and the first with the highest average.
Formally, we can represent sales as a list $$$v_1,v_2...v_n$$$, where $$$v_i$$$ means how many items were sold in month $$$i$$$. An interval that starts in month $$$i$$$ and has size $$$K$$$ encompasses the elements $$$v_i,v_{i+1}...v_{i+K-1}$$$ and has average $$$\frac{(v_i + v_{i+1}...+v_{i+K-1})}{K}$$$.
For example, if $$$v = \{ 1,\ 1, \ 1,\ 2, \ 3 \}$$$ and $$$K=2$$$, the first interval with the lowest average starts at $$$i=1$$$, $$$\frac{(v_1 + v_2)}{2} = \frac{(1+1)}{2} = 1$$$, and the one with the highest average starts at $$$i=4$$$, $$$\frac{(v_4+v_5)}{2} = \frac{(2+3)}{2} = 2.5$$$. Note that the interval starting at $$$i=2$$$ also has an average of 1, but it is not the first interval with the lowest average. Also note that $$$i=5$$$ does not delimit a valid interval, as we do not yet know the number of sales in month 6.
The first line contains two integers $$$N, K$$$, the number of elements in the sales list and the interval size. It is guaranteed that $$$1 \leq K \leq N \leq 10^5$$$.
The next line contains $$$N$$$ integers $$$v_1, v_2 ... v_N$$$, representing the sales list. It is guaranteed that $$$1 \leq v_i \leq 10^4$$$.
Print a line with two integers: the index of the start of the first interval with the lowest and the highest average.
Due to large constraints, if you are receiving Time Limit Exceeding it may be useful to try another approach.
5 2 1 1 1 2 3
1 4
6 4 1000 1 2 3 4 100
2 1
A Skywars map Skywars is a minigame where each player starts on a flying island and has to be the last survivor. Techno is playing a match, and now only he and 2 enemies remain. A top view of the islands shows empty points and points where island blocks exist, in such a way that the map can be represented as a grid. In order to win, Techno must reach his enemies. Therefore, he wants to know the minimum amount of blocks that must be placed so that his island and the enemies' islands are connected. Here, 2 blocks are considered connected if it is possible to move from one to the other by moving only in adjacent directions on the grid: up, down, left and right.
The first line contains 2 integers, $$$N$$$ and $$$M$$$, representing the number of rows and the number of columns of the grid respectively. It is guaranteed that $$$1 \leq N,M \leq 2\cdot 10^5$$$ and that $$$N \cdot M \leq 2 \cdot 10^5$$$.
Follow $$$N$$$ lines with $$$M$$$ characters $$$c_i$$$ each. It is guaranteed that $$$c_i \in \{ T \ , \ * \ , \ . \ , \ \# \}$$$. 'T' represents where Techno is and '*' the place of the enemies. It is guaranteed that there is exactly 1 'T' and exactly 2 '*'. '.' represents cells without blocks while '$$$\#$$$' cells that have already been occupied.
Print a single integer representing the minimum number of blocks needed to connect Technoblade's island to his enemies' islands.
4 4 T..* .... .... *...
4
4 4 *... .T.. ..*. ....
2
4 4 T#.* ..#. #..# ##.*
2
3 3 .*. T.* ...
1
Note that the cells with Techno or his enemies are not considered empty.
After quintupling the size of his potato plantation, Technoblade got bored of planting potatoes and decided to buy potatoes, for unknown reasons since he already had a lot of potatoes...
Anyway, he made a list of $$$N$$$ potato stores and saw that the $$$i$$$-th store sells potatoes in packages of $$$b_i$$$ potatoes per package. Now Techno wants to know how many ways he can buy exactly $$$B$$$ potatoes.
As he suspects that store number $$$1$$$ belongs to his rival SquidKid, he wants to buy at most $$$t$$$ packages from store $$$1$$$. He can buy any number of packages from the other stores, including $$$0$$$.
In how many ways can he make this purchase? Two ways are considered different if the number of packages of a store bought in an order is different from the other. Since this number is large, print the answer modulo $$$10^9 + 7$$$.
The first line contains two integers $$$N$$$ and $$$B$$$, $$$1 \leq N \leq 100$$$ and $$$1 \leq B \leq 10^{18}$$$. Followed by a line with $$$N$$$ integers $$$1 \leq b_i \leq 500$$$. It is also guaranteed that $$$\sum_{i=1}^{N} b_i \leq 500$$$.
Finally, follows a integer $$$t$$$, $$$0 \leq t \leq 10^{18}$$$.
Print a single line with an integer $$$X$$$, $$$0 \leq X \lt 10^9+7$$$, the number of ways to buy exactly $$$B$$$ potatoes.
1 10 1 9
0
2 3 1 1 1000
4
2 3 1 1 0
1
3 1000000000 1 2 3 1000000000
250000003
Technoblade has finally decided to take a vacation. He has decided to visit an extensive list of cities and has hired you to make a travel plan for him. For this, each city has been given an identifier: an integer from 1 to N, with 1 being Techno's hometown. In addition, you have noted all available trips, which can be represented by 3 integers $$$a_i, b_i, c_i$$$, representing a route from $$$a_i$$$ to $$$b_i$$$ that costs $$$c_i$$$ reais and can be taken in both directions.
Now it's up to you to decide in which order to visit the cities. This plan must start in the hometown (number 1) and end there. In addition, every city must be visited at least once, with repetitions allowed.
As Technoblade is on vacation, he is not so concerned about money, and any plan that has a cost less than or equal to $$$2$$$ times the cost of an optimal plan will be accepted. For example, if we treat this problem as a graph problem, we can have a case like the one below:
Cities are represented by vertices and routes by edges between vertices. The integers on the edges represent the cost of that route. Note that the plan with the lowest cost has a cost of $$$8$$$. $$$1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 5 \rightarrow 1$$$ is an example of a plan.
However, the plan $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6\rightarrow 5 \rightarrow 1$$$ has a cost of $$$16 \leq 2\cdot 8$$$, so it is also a valid plan.
The first line contains 2 integers $$$1 \leq N \leq 3 \cdot 10^5$$$ and $$$1 \leq M \leq 5 \cdot 10^5$$$, representing the number of cities and the number of routes. Followed by $$$M$$$ lines with 3 integers $$$a_i, b_i, c_i$$$ each. It is guaranteed that $$$1 \leq a_i , b_i \leq N$$$, $$$a_i \neq b_i$$$ and $$$1 \leq c_i \leq 10^{12}$$$. It is also guaranteed that it is possible to make a plan that visits every city by using the given routes.
Print on the first line the cost of your found plan. On the second line, print an integer $$$K$$$ representing the number of cities in your plan. Finally, print $$$K$$$ integers $$$1 \leq p_i \leq N$$$ representing the cities to be visited in the order of your plan. You must ensure that $$$p_1 = p_K = 1$$$ and that for every $$$1 \leq i \lt K$$$, there is a route from $$$p_i$$$ to $$$p_{i+1}$$$. Also, you must ensure that $$$K \leq 2 \cdot 10^6$$$. It is guaranteed that there is a valid plan with this many cities.
2 2 1 2 1 1 2 10
2 3 1 2 1
3 3 1 2 100000000000 1 3 100000000000 2 3 1000000000000
400000000000 5 1 2 1 3 1
Technoblade is also famous for having a beautiful crown. Now he wants to make new crowns, one with $$$K$$$ spaces for jewels, where he can place any of the $$$M$$$ types of jewels known to him.
Techno was surprised by the number of options and is now curious to know how many crowns of size $$$K$$$, using $$$M$$$ types of jewels, exist. All jewels of the same type are identical, and two jewels of different types are always distinguishable. Note also that if a crown can be rotated so that it looks the same as another, they are considered identical.
Since Techno has not decided on the value of $$$K$$$, he is interested in the sum of the number of crowns for all $$$K$$$ from $$$1$$$ to $$$N$$$. As this number is large, print modulo $$$10^9+7$$$.
The input consists of only two integers $$$N$$$ and $$$M$$$, $$$1 \leq N, M \leq 10^6$$$.
Print a single line containing the number of possible crowns with size from 1 to $$$N$$$, using $$$M$$$ types of jewels.
1 2
2
2 2
5
10 3
9503
1000 1000000
250445517
Technoblade is organizing a Hunger Games match, a "last survivor wins" type of game. Before the start, players are placed in a circle. Then, they are divided into teams. To facilitate organization, teams must consist of adjacent players in the circle.
Technoblade has already placed the players in a circle and now he just needs to divide them into teams. The players are numbered from $$$1$$$ to $$$n$$$, with player $$$i$$$ next to $$$i+1$$$ for $$$i \lt n$$$ and player $$$1$$$ next to player $$$n$$$. He knows the country of origin of each player $$$p_i$$$ and wants to diversify the teams by having at most $$$k$$$ players from the same country. Remember that players in the same team must be next to each other. For example, if $$$n=5$$$, we can have one team with players $$$1,5$$$ and another with $$$2,3,4$$$, since $$$5$$$ is next to $$$1$$$ and $$$2,3,4$$$ are in sequence. However, the team $$$1,3$$$ would be prohibited. It is worth noting that each player must be in exactly one team. To make the game fast, you want to minimize the number of teams, while ensuring that each team has at most $$$k$$$ players from the same country.
Since Techno has not decided on the value of $$$k$$$ yet, find the answer for all $$$k$$$ from $$$1$$$ to $$$n$$$.
The first line contains a single integer $$$n$$$, $$$1 \leq n \leq 10^5$$$.
Followed by a line with $$$n$$$ integers $$$1 \leq p_i \leq n$$$ as described.
Print $$$n$$$ lines. The $$$k$$$-th line being the smallest number of teams so that each team has at most $$$k$$$ players from the same country.
5 1 2 1 2 1
3 2 1 1 1
6 1 2 2 1 2 1
3 2 1 1 1 1
Be careful with "endl" when printing large outputs.
Minecraft usernames Tiago Domingos wants to create a Minecraft account to play with his friend Tiago Gonçalves. For the choice of the username he wants to be as original as possible.
Domingos' username can be represented by a string $$$D$$$ and Gonçalves' by a string $$$G$$$. Now, to measure how original Domingos was, he finds the smallest continuous subsequence of $$$D$$$ that does not occur as a continuous subsequence of $$$G$$$, that is, the smallest substring of $$$D$$$ that is not a substring of $$$G$$$. Your task is to print the size of the smallest subsequence or warn if all substrings of $$$D$$$ are also substrings of $$$G$$$.
For example, if Tiago Domingos' username is $$$D = tdas$$$ and Gonçalves' is $$$G = tfg$$$, the answer is 1, because $$$a$$$, $$$d$$$, $$$s$$$ do not occur in G.
If $$$D = tdas$$$ and $$$G = tdas$$$, there is no substring that does not appear in $$$G$$$.
If $$$D = td$$$ and $$$G = tudo$$$, the smallest substring is $$$td$$$ of size 2.
The first line has the string $$$D$$$ and the second has $$$G$$$. It is guaranteed that the strings contain only lowercase Latin letters ('a' to 'z') and that their size is at most $$$10^5$$$.
The size of the smallest substring of $$$D$$$ that is not a substring of $$$G$$$. Print $$$-1$$$ if every substring of $$$D$$$ is also a substring of $$$G$$$.
aba abacaba
-1
aaba aabbaa
3
tdas tdas
-1
td tudo
2
Technoblade decided to play a coin game with Skeppy to pass the time. Each of them brought $$$N$$$ coins from home and now they have placed all $$$2N$$$ coins in a row. Each coin has a value that can range from $$$1$$$ real to $$$10^4$$$ reais, the Brazilian currency.
The game consists of taking the leftmost or rightmost coin and taking exactly $$$1$$$ for yourself. In the end, your score is the sum of the values of your coins. Whoever has more is considered the champion.
As Technoblade is the oldest, he starts with a $$$1$$$ real advantage, but in return he must be the first to play.
Skeppy doesn't like to think about strategies, so he just takes the larger of the left and right coins. If both have the same value, he prefers the one on the right.
As a spectator, you want to try to predict the game. You must guess who will win the game, or if Techno can force a tie, assuming that Technoblade, unlike Skeppy, plays optimally.
If Technoblade is the champion, also print his sequence of moves. In case there are many sequences that guarantee victory, print the one with the smallest lexicographic value (see output).
The first line contains an integer $$$N$$$. Followed by a line with $$$2N$$$ integers from $$$1$$$ to $$$10000$$$, representing the coins from left to right, already set up for the start of the game. It is guaranteed that $$$1 \leq N \leq 2500$$$.
If Technoblade is doomed to defeat, print only ":(", without quotes.
If Technoblade cannot win, but can force a tie, print only "tie", without quotes.
If he can win, print "TECHNOBLADE NEVER DIES!" on the first line, without quotes. Then print another line with $$$N$$$ characters "L" or "R". The i-th character determines whether Techno should take the coin from the left or the right in that round. If there are many possible sequences, print the smallest lexicographically.
2 1 10 10 1
TECHNOBLADE NEVER DIES! LL
3 10 1000 1 1 1 1
TECHNOBLADE NEVER DIES! RLL
2 1 10 1 10
TECHNOBLADE NEVER DIES! LL
Now that Technoblade has built his potato empire and taken a vacation to rest, he has decided to just observe the performance of his plantation. Techno has $$$N$$$ plots, numbered from 1 to $$$n$$$. For each plot, its land is worth a price that depends on the weather, type of soil, soil erosion, level of rain, etc.
To stay updated, he first made a list of land values: $$$V_1, V_2... V_n$$$, with $$$V_i$$$ being the price of the $$$i$$$-th plot. After that, he observed that weather effects affect a continuous segment of plots at a time, adding or subtracting from the plot value. Therefore, you must respond to two types of operations:
- Type 1: this is the operation of adding to the plot values. It has the format $$$1\ l\ r\ x$$$. With this operation, $$$V_i := V_i + x$$$ for all $$$l \leq i \leq r$$$. It is guaranteed that $$$-10^6 \leq x \leq 10^6$$$.
- Type 2: It has the format $$$2\ l\ r$$$. This is a query operation, in which you must print the sum of the optimistic values of the plots from index $$$l$$$ to $$$r$$$. The optimistic value of the plot is the highest value it has ever had.
For example, if $$$V = \{ 1,2,3\}$$$ and a type $$$1$$$ operation $$$1\ 2\ 2\ -2$$$ occurs, that is, $$$l=2,r=2$$$ adding $$$x=-2$$$ we have that $$$V = \{1,0,3\}$$$. In addition, $$$V_{optimistic} = \{1,2,3\}$$$ because the highest value that $$$V_2$$$ has ever had is $$$2$$$.
The first line has two integers $$$n$$$ and $$$q$$$, representing the number of plots and the number of operations. It is guaranteed that $$$1 \leq n,q \leq 3 \cdot 10^5$$$.
Followed by a line with $$$n$$$ integers $$$V_i$$$, $$$1 \leq V_i \leq 10^6$$$.
Finally, there are $$$q$$$ lines with type 1 or type 2 operations. Type 1 operations have the format $$$1\ l\ r x$$$ and type 2 operations have the format $$$2\ l\ r$$$. It is guaranteed that $$$1 \leq l \leq r \leq n$$$ and $$$-10^6 \leq x \leq 10^6$$$.
For each type 2 query, print the sum of the optimistic values of the plots from number $$$l$$$ to $$$r$$$.
1 5 1 1 1 1 99 1 1 1 -99 2 1 1 1 1 1 100 2 1 1
100 101
4 8 1 2 3 4 2 1 4 1 1 4 -1 2 1 4 1 1 3 2 2 3 3 1 1 3 5 1 1 3 -100 2 3 3
10 10 4 9
The prices of the plot can become negative, which means that the plot sucks so much he would pay for someone to buy it.
Steve relaxing on his floating block Steve is conducting a physics experiment for the F129 course at UNICAMP. He measured how long it takes for him to fall from a tree and, after adding uncertainties, he has a confidence interval of $$$[l, r]$$$ for the gravity constant. Then, he repeated the experiment by throwing dirt, wood, bricks, and whatever he found on the way. In the end, he obtained $$$n$$$ possible intervals $$$[l_1,r_1], [l_2,r_2]...[l_n, r_n]$$$. However, he noticed that some intervals do not intersect, which would be terrible for his report. Therefore, instead of redoing the experiments and understanding what went wrong, he chose to take the largest number of intervals that have a non-empty intersection and pray that the correct value of the gravity constant is there.
Formally, you must choose the largest number $$$k$$$ of intervals $$$i_1, i_2, ... i_k$$$ such that for any two intervals $$$i_a$$$ and $$$i_b$$$, they have an intersection. Intersection at the endpoints is valid, as the intervals are closed.
The first line of the input contains only one integer $$$1 \leq n \leq 2 \cdot 10^5$$$. The following $$$n$$$ lines each contain two integers, $$$l_i$$$ and $$$r_i$$$, representing the intervals. It is guaranteed that $$$1 \leq l_i \leq r_i \leq 10^9$$$. It is possible for two intervals to be equal.
On the first line, print an integer $$$k$$$, representing the largest number of intervals with a common intersection. Then, print $$$k$$$ distinct integers representing the indices of the used intervals. If there are many answers with maximum $$$k$$$, any one is considered valid.
3 1 3 1 3 1 3
3 3 2 1
5 1 2 1 2 2 4 3 4 4 10
3 2 1 3
4 1 2 2 4 3 4 4 10
3 2 3 4