Ivanovich is obsessed with a new game, Algorithmic Creed, here you work with your creed trying to give free will to the coders of the world, meanwhile in the other side the managers, also known as "templars" want to take away coders free will and deprive them of their human nature.
An important part of this game is to obtain and update items to be a stronger coder, like a gaming mouse, a new keyboard, a better monitor... because you know that the most important part of coding is the setup.
The game has $$$N$$$ items numbered from $$$1$$$ to $$$N$$$ and the only way to obtain new items is performing a trade. The only item you can buy directly is a pen (for writing pseudocode in paper) which is always represented with the number $$$1$$$, you can always buy it for 1 coin and you can buy it several times. In this game you have the ability to trade items for another one which is always better, the game has a list of item trading rules, each rule describe the item $$$u$$$ as a requirement to obtain item $$$v$$$ and the number of $$$c$$$ coins you have to give to perform the trade. In order to obtain item $$$v$$$ you need to trade all items $$$u$$$ that are a requirement for $$$v$$$ and pay the number of coins associated to trade $$$u$$$ for $$$v$$$, after the trade you will lose the $$$u$$$ items, and the coins, but obtain item $$$v$$$.
Ivanovich has never been good at games, since he always loses focus and begins to think about programming problems. He is wondering how many different setups he can build in the game if he has $$$C$$$ coins to trade. Can you help Ivanovich to solve this weird problem so he can go back to the game?
A setup is different from another one if there is at least one different item. A setup must have at least one item.
The first line of input contains three integers separated by a space $$$N$$$ $$$(1 \leq N \leq 10^5)$$$, $$$M$$$ $$$(1 \leq M \leq 10^5)$$$, $$$C$$$ $$$(1 \leq C \leq 10^2)$$$, representing the number of items in the game, the number of trading rules available and the number of coins available respectively.
Each of the next $$$M$$$ lines contains three integers separated by a space, $$$u_i$$$ $$$(1 \leq u_i \leq N)$$$, $$$v_i$$$ $$$(1 \leq v_i \leq N)$$$, $$$c_i$$$ $$$(1 \leq c_i \leq C)$$$, indicating that in the $$$i$$$-th trading rule the item $$$u_i$$$ is a requirement for $$$v_i$$$ paying $$$c_i$$$ coins.
In the first and only line, print the number of different setups Ivanovich can build. As the answer might be very large, please output the answer modulo $$$10^9 + 7$$$.
3 2 4 1 2 1 2 3 1
10
3 3 4 1 2 1 1 3 1 2 3 1
8
The year 2012 started a trend when everybody tried to predict the end of the world, they always find something peculiar in the number that indicates that it will really be the end of the world.
One famous group was an old Mexican tribe called the Binahuatls, who predicted that the world will be ending in a year where the binary representation it's a palindrome, meaning that the number it's the same if we were to reading forward or backward.
But as you, the person sitting in a chair, reading this problem in a contest or in practice, that is thinking about what the question of this problem is, are a living example that the world hasn't ended yet. The most eager fans of the Binahuatl defend that the world will end in a binary palindromic year for sure.
Given two dates $$$A$$$ and $$$B$$$ help those eager fans to know how many binary palindromic years exists between $$$A$$$ and $$$B$$$ inclusive!
The first line contains a single integer $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$, representing the number of test cases.
Each of the following $$$Q$$$ lines contains two integer numbers separated by a space $$$A$$$ and $$$B$$$ $$$(0 \leq A \leq B \lt 2^{31})$$$.
Print $$$Q$$$ lines, where the $$$i$$$-th line contains a single integer number representing the answer for the $$$i$$$-th test case from the input.
1 1 10
5
3 10 10 4 4 2 2
0 0 0
4 123 1234 2000 2022 10 100 100 1000
47 1 14 42
Planet E-13 orbits around a star in a faraway galaxy named UAZ. In that planet, everyone attends the same super powerful university, which has the capacity to receive up to $$$N$$$ students per semester. Every student gets a school ID, and at the beginning of each semester, each of the students request to enroll in up to eight courses. School enrollment applications are registered by the secretary of the school department, however, given that sometimes she must do it very quickly because the deadlines are very close, students could end up enrolled in courses that they did not request and/or they could have courses they requested to be enrolled in but they were not. Given the list of students with their course requests, and the list of courses in which they actually ended up enrolled in the school system, your job is to provide a list of changes to be made to the school system's records, so that effectively the students end up enrolled in each and every one of the courses they requested, without having missing or unrequested courses.
In the first line of input there will be two integers $$$N$$$ and $$$M$$$ $$$(1 \leq N, M \leq 10^5)$$$, the number of students requesting at least one course enrollment this semester and the number of students that got at least one course enrollment this semester, respectively.
The next $$$N$$$ lines, start with two integers $$$A$$$ $$$(1 \leq A \leq 10^7)$$$ and $$$B$$$ $$$(1 \leq B \leq 8)$$$, the ID of the student and the number of class enrollments student $$$A$$$ is requesting respectively. Then in the same line will be $$$B$$$ integers $$$b_i$$$ $$$(1 \leq b_i \leq 10^4)$$$, this are the enrollment requests by student $$$A$$$.
The next $$$M$$$ lines, start with two integers $$$A$$$ $$$(1 \leq A \leq 10^7)$$$ and $$$C$$$ $$$(1 \leq C \leq 8)$$$, the ID of the student and the number of class enrollments student $$$A$$$ received. Then in the same line will be $$$C$$$ integers $$$c_i$$$ $$$(1 \leq c_i \leq 10^4)$$$, this are the enrollments assigned to the student $$$A$$$ by the school.
note: students and enrollment lists will appear in any order.
If there was no error in enrollments, you should print "GREAT WORK! NO MISTAKES FOUND!" in one line, without quotes.
Otherwise you need to print the changes needed in enrollment such that all students get exactly the courses they requested, not more, not less.
For each student that needs a change in their enrollment there will be a line: the ID of the student followed by a list of corrections separated by spaces, a correction is of type $$$-m$$$ or $$$+m$$$, which are removing a course and adding a course respectively, the list should be printed ordered in ascending order of the absolute value of $$$m$$$. The ID's of students should appear in ascending order, also corrections should be ordered in ascending order for each student. Once all of the changes are listed (ordered by student ID and course ID), you should print the text "MISTAKES IN X STUDENTS: Y NOT REQUESTED, Z MISSED" (without the quotes) replacing X for the number of students that had mistakes in the system, Y for the total number of course enrollments registered in the system that were not requested by the students and Z for the total number of course enrollments that were requested but were not in the system
3 3 1 4 5 4 2 10 4 3 1 2 11 3 2 9 2 4 3 1 2 11 1 4 5 4 2 10 3 2 9 2
GREAT WORK! NO MISTAKES FOUND!
3 5 5 3 9 8 1 9 2 8 7 4 1 10 3 2 1 3 5 4 9 1 4 2 1 4 2 3 1 5 2 3 9 8 2 8 3 2 4 5
1 -1 -2 -3 -5 2 -2 -8 -9 3 -1 -3 4 +10 5 -2 -4 +8 8 -2 -4 -5 9 +7 +8 MISTAKES IN 7 STUDENTS: 14 NOT REQUESTED, 4 MISSED
You are the CEO of a big company that makes roads in the city, one day you are commissioned to make roads in the district capitalism, and of course, the names clearly tell you, that district capitalism is a district where they really love the capital city! You have seen the city and you love the city too so you decided to work for free, it's a normal thing in the capital city that everybody works for free.
There are $$$N$$$ cities numbered from $$$1$$$ to $$$N$$$, you have a list of $$$M$$$ roads that you can make, each road option is represented by three integers $$$A$$$, $$$B$$$, and $$$C$$$ which means that there is an option to connect city $$$A$$$ to city $$$B$$$ with cost $$$C$$$. Since everybody loves the capital city there is a fee for emotional damage that is charged to make a road away from the capital to $$$Y$$$: a road that has a distance $$$X$$$ from the capital will cost $$$X$$$ * $$$C$$$, $$$X$$$ is calculated by the number of roads in a simple path that exists between capital and $$$Y$$$. The capital city has number 1.
Calculate the minimum amount of money you need to spend to connect every city to the capital such that the distance from each city to the capital is minimal.
How can you pay for these roads if you are working for free? Why everybody loves the capital? Those are not the questions in this problem!
The first line, you will have two integers $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$M$$$ ($$$1 \leq M \leq 10^5$$$) representing the number of cities and the number of roads respectively. Each of the next $$$M$$$ lines contains three integers $$$A$$$, $$$B$$$ ($$$1 \leq A, B \leq N$$$)and $$$C$$$ ($$$1 \leq C \leq 10^5$$$) describing each of the road options you can possibly make.
Output a line with a single integer that represents the minimum cost it will take to connect all the cities to the capital, two cities are considered connected if there is a set of roads that you can use to reach from one city to another, it guaranteed that a solution exists.
5 4 1 2 10 1 3 4 1 4 12 1 5 1
27
5 5 1 2 10 1 3 4 2 3 8 5 4 12 1 5 1
39
5 4 1 2 10 2 3 4 3 4 12 4 5 1
58
Jaime's distribution company is getting back to business. In this new distribution task Jaime has to move $$$N$$$ boxes that are stored in his backup warehouse to the main warehouse. In order to do this, Jaime has only one truck, so he will drive to the backup warehouse, then load the truck, and finally drive to the main warehouse and unload the truck, all the previous process is considered a single trip of boxes. Jaime knows if he loads more than $$$M$$$ boxes in the truck it will force the engine and potentially break it, so he will ensure to move the boxes without forcing the engine.
Can you help Jaime determine, how many trips does he has to make in order to move all the boxes from the backup warehouse to the main warehouse?
The first and only line of input contains two integers separated by a space, $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 10^6$$$)
Print a single line with an integer number, the minimum number of trips Jaime has to make to move all the boxes to the warehouse.
10 10
1
1 10
1
11 5
3
You are one of the most famous painters, Vinvent Van Vough and now you are thinking of painting another masterpiece. Everyone knows that your most famous paintings always contain geometric figures, specifically figures with exactly 4 sides, the interpretation of a simple figure in so many colors and in so many contexts is what made you the most famous painter.
Now, you are in front of your canvas painting your soon-to-be-famous starry night. In your canvas, there are already $$$N$$$ stars and you want to connect 4 of these stars to show a quadrilateral constellation. In how many ways you can choose these 4 stars to make a quadrilateral figure?
In the first line, you will have an integer $$$N$$$ ($$$1 \leq N \leq 100$$$) that represents the number of stars on the canvas.
Each of the next $$$N$$$ lines contains two integers $$$X$$$, and $$$Y$$$ separated by a space ($$$-10^6 \leq X, Y \leq 10^6$$$) that represents the coordinates of the $$$a_i$$$ star, no two stars share the same point.
Output a single line with an integer indicating the total ways you can choose 4 stars to draw your quadrilateral figure.
5 10 10 10 20 20 20 20 10 25 15
5
6 1 1 2 2 3 3 5 10 20 10 20 5
12
7 2 8 9 4 3 1 38 43 10 11 49 31 30 20
35
In Guadalajara, the most recent train line is the Pi Line. The name is because it's after the third line and before the fourth line.
This line has two train rails and $$$N$$$ stations, one rail is for a train that goes from station 1 to station $$$N$$$, and the other one is for a train that goes from station $$$N$$$ to station 1. At each station, there is a given time for the train to wait to pick people up that can vary from station to station. Both trains have the same speed (1km/s) and the distance between each station is known. JP began is wondering how long both of the trains will be waiting in the same station?
Knowing the distance between consecutive stations, the time that the trains wait at each station, and the fact that the two trains begin to work at the same time, help JP to answer his question!
The first line contains a single integer $$$N$$$ ($$$2 \leq N \leq 10^6$$$) representing the number of stations in the Pi line. The next line contains be $$$N - 1$$$ integers separated by a space where the $$$a_i$$$ ($$$1 \leq a_i \leq 10^6$$$) integer represents the distance between the station $$$i$$$ and the station $$$i + 1$$$. The third and last line of input contains $$$N$$$ integers separated by a space where the $$$x_i$$$ ($$$1 \leq x_i \leq 10^6$$$) integer represents the time that the train will be waiting at station $$$i$$$.
Print a line with a single integer that indicates the time the two trains are waiting in the same station.
3 1 1 1 10 1
10
3 1 5 1 10 1
6
6 20 13 10 15 20 10 21 5 10 20 7
0
When it comes to numbers there are two rules that are common knowledge:
- Some numbers are really funny.
- Not all people consider the same number as funny.
For example, some people find the number 24 funny, while other people assures the number 25 is even funnier.
As with some other topics there are some funny number jokes that only experts on the topic find entertaining: if your funny number is 25 and your friend says 100, you find it funny as even when 100 is not your funny number, it is disguised! If you divide $$$100$$$ by $$$4$$$ it becomes your funny number!.
You are a funny numbers clown and will be presenting a funny numbers show tonight. This means you want to make people laugh with funny number jokes. As you want to be the best funny numbers clown in the city you do not want to expose yourself trying too hard to make people laugh, so you will not say a number greater than $$$X$$$. You will perform in front of your $$$N$$$ friends, all your friends are funny number experts and find entertaining a funny number joke. Because you are very close to each of your friends you know what is the number each of them finds funny.
Help yourself to know how many different numbers you can say tonight to make at least one of your friends laugh!
The first line of input contains two integers separated by a space $$$N$$$ and $$$X$$$ ($$$1 \leq N \leq 20$$$, $$$1 \leq X \leq 10^9$$$) indicating respectively the number of friends in the show and the maximum number you can say.
The second and last line contains $$$N$$$ numbers separated by a space $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) where the $$$i$$$-th number represent the funny number of your $$$i$$$-th friend.
Output a single line with an integer, indicating how many different numbers you can say tonight to make at least one of your friends laugh.
2 10 2 3
7
3 100 2 3 5
74
1 500 5
100
You have a sequence of $$$N$$$ integers $$$a_i$$$ with elements between $$$1$$$ and $$$K$$$, and you want to calculate the number of inversions. To make it more complicated you get $$$Q$$$ operations $$$i$$$, change all occurrences of $$$i$$$ to $$$i+1$$$, and vice versa.
Each operation changes the original sequence for the following operations.
note: is considered an inversion to a pair of indices ($$$i, j$$$), where $$$i \lt j$$$ and $$$a_i \gt a_j$$$.
The first line contains three integers $$$N$$$, $$$K$$$, $$$Q$$$ ($$$1\le K\le N\le 100\,000$$$, $$$1\le Q\le 1\,000\,000$$$).
The next line contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$1 \le a_i \le K$$$) specifying the sequence.
The following $$$Q$$$ lines each contain an integer $$$i$$$ ($$$1\le i \le K-1$$$), representing the operation of swapping $$$i$$$ elements with $$$i+1$$$, and vice versa.
For each $$$Q$$$ operation, print a single integer, the number of inversions as specified in the statement.
5 4 31 4 2 1 2321
4 2 2
The KAK (Klub Algorithmic Kukei) is a club from the Kukei university which has a peculiar story about how they got their name: One time they made advertisement and some merch that had their name printed, after everything was paid they noticed that they misspelled the word Club as Klub, they find it easier to keep the name rather than making all the advertisement and merch again.
Because of this experience now the KAK focuses a lot on grammar, that is why if you want to join the KAK they will ask something related to strings.
Today you want to join, and in your evaluation for joining the KAK they gave a lot of cards with letters in them, each card has exactly one letter. They ask you to find given a value a $$$k$$$ what would be the $$$k$$$-th string if you sorted lexicographically all the different strings that you can make arranging at least one of the cards and at most all of them? Two arrangements $$$A$$$ and $$$B$$$ are different if they have a different amount of cards or if at some position $$$x$$$ the letters of the cards at position $$$x$$$ differ.
Gain your entry to the "Klub" answering the question!
The first line of input contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N \leq 1000$$$, $$$1 \leq K \leq 10^6$$$) representing the number of cards that the KAK gave you and $$$k$$$. It is guaranteed that at least $$$k$$$ different strings can be made with the given cards.
The next line contains a string of size $$$N$$$ representing the $$$N$$$ pieces. All the letters are lowercase English letters.
Print a line containing a single word, the answer to the problem to join the KAK.
3 2 aaa
aa
3 15 abc
cba
10 120873 abcdefghij
fgdhic
Krystalova is writing trivial problems (as always) but now for some reason (lucky for you) she also wrote a trivial statement.
You have a trivial list of numbers $$$L$$$, and two trivial operations:
1. $$$u$$$ $$$l$$$ $$$r$$$ $$$x$$$: Add $$$x$$$ to the numbers in $$$L$$$ in the range $$$[l, r]$$$.
2. $$$q$$$ $$$l$$$ $$$r$$$: Get the sum of $$$L_i^2$$$ for every $$$i$$$ in the range $$$[l, r]$$$.
In the first line of input two integers $$$N$$$ $$$(1 \leq N \leq 10^5)$$$, $$$Q$$$ $$$(1 \leq Q \leq 10^4)$$$, the size of $$$L$$$ and the number of operations respectively.
The next line contains $$$N$$$ integers $$$L_i$$$ $$$(0 \leq L_i \leq 10^8)$$$, the elements of $$$L$$$.
The next $$$Q$$$ lines contains an operation, that can be one of the two types described before. If the line starts with a letter "$$$u$$$" then will be three integers $$$l$$$ $$$(1 \leq l \leq N)$$$, $$$r$$$ $$$(1 \leq r \leq N)$$$, $$$x$$$ $$$(-10^8 \leq x \leq 10^8)$$$. If the line starts with a letter "$$$q$$$" then will be two integers $$$l$$$ $$$(1 \leq l \leq N)$$$, $$$r$$$ $$$(1 \leq r \leq N)$$$
For every operation of type 2, print in one line the result of the operation. As the answer might be very large, please output the answer modulo $$$10^9 + 7$$$
5 5 1 1 1 1 1 u 1 3 1 q 1 5 u 3 5 1 q 3 3 q 1 5
14 9 25
Krystalova is studying a very particular sequence that she likes very much. Krystalova named the sequence: "Limited Increasing Sequence". A sequence $$$X$$$ of positive integer numbers is a limited increasing sequence if and only if every element $$$X_i$$$ is not greater than the sum of all the items $$$X_j$$$ $$$|$$$ $$$j \lt i$$$. In other words, every element $$$X_i$$$ meets the following condition:
$$$$$$\sum_{j=1}^{i-1}X_{j} \geq X_{i}$$$$$$
Let $$$f(X)$$$ be the sum of all the elements in a limited increasing sequence, it is said the limited increasing sequence $$$X$$$ produces $$$K$$$ if $$$f(X) = K$$$.
Looking at this sequence, Krystalova found that a number $$$K$$$ may be produced as the result of different $$$X$$$. She wants to know how many different limited increasing sequences produces $$$K$$$.
Help Krystalova to solve her problem!
In the first line, you will have a single integer $$$K$$$ ($$$1 \leq K \leq 10^6$$$)
Print a line with a single number with the result. As the answer might be very large, please output the answer modulo $$$10^9 + 7$$$
10
84
2022
904964280
3
1