Alex prepared a report with the help of the generative artificial intelligence CloseLoseShallow (CLS). His report contains $$$n$$$ statements $$$a_1, a_2, \dots, a_n$$$, and he is getting ready to present them to the audience.
Berta believes that most of these statements are false, but she only has evidence for some of them. For each statement, she knows for sure whether it is false or if she does not have enough information to refute it.
Every time Alex reads a statement, Berta will declare it false. If Berta can provide the proof, she will earn a point; if not, Alex will earn a point. If the fact that it is proven false does not prevent Alex from continuing to win, then Alex will not ask for any proof and will simply accept that it is false, giving a point to Berta; otherwise, he will ask for proof and earn a point.
Formally, if Berta has $$$b$$$ points and Alex has $$$a$$$ points, as long as $$$a \gt b + 1$$$, Berta will declare a statement false and her point total will be $$$b + 1$$$ (since Alex will not ask for a reference and both will accept that the statement is false).
Berta wants to ensure that, after her talk with Alex, she has more points than he does to demonstrate that generating reports with generative artificial intelligence is not a good idea. To achieve this, she can choose where to start reading the report and when to stop reading.
Formally, from the $$$n$$$ statements of Alex, Berta can choose a segment defined by the indices $$$l$$$ and $$$r$$$ ($$$l \leq r$$$) and calculate who earns more points in that interval with the statements $$$a_l, a_{l+1}, \dots, a_r$$$.
Berta wants to know how many intervals $$$[l, r]$$$ exist in which she earns more points than Alex. Can you help her calculate it?
The first line of the input contains the number of cases $$$T$$$.
Each case begins with a line containing a single integer, $$$n$$$.
The next line of each case contains $$$n$$$ integers; if Berta has a refutation for the $$$i$$$-th statement, this value will be 1; otherwise, it will be 0.
For each case, print a single line with an integer, the number of intervals in which Berta will earn more points than Alex.
- (13 points) The sum of $$$n$$$ over all cases will be less than 100.
- (9 points) The sum of $$$n$$$ over all cases will be less than 2000.
- (18 points) The statements for which Berta has a refutation and those for which she does not alternate. (There is an example of this subtask explained in the notes of the example cases).
- (26 points) The sum of the number of statements for which Berta has a refutation across all cases is less than or equal to 300.
- (34 points) No additional restrictions.
321 150 1 0 1 061 0 0 1 0 1
3 3 4
$$$1 \le T \le 10^4$$$.
$$$1 \le n \le 10^6$$$.
The sum of $$$n$$$ for all cases is at most $$$10^6$$$.
In a certain region of Galicia, there are $$$n$$$ towns, and there are $$$m$$$ two-way roads connecting some pairs of towns, such that it is possible to travel from any town to another by car.
Due to a change in the law, all roads in the region must become one-way. The Galicians have asked for your help in modifying their road system. For each existing road, the Galicians allow you to decide the direction that the road will take. Additionally, if necessary, you can build new one-way roads.
The Galicians want to ensure that it is still possible to travel by car between any pair of towns, but they ask you to build the minimum number of new roads possible. Furthermore, since you are very skilled, the Galicians want to ask for your help in fixing the road systems of $$$T$$$ different regions. Can you help them?
The first line contains a positive integer $$$T$$$, the number of regions in Galicia to process.
Each case starts with two positive integers $$$n$$$ and $$$m$$$, the number of towns and roads in the region, respectively. The towns are numbered $$$1,2,3,\dots,n$$$.
This is followed by $$$m$$$ lines, each containing two integers $$$1\le u_i, v_i\le n$$$, the towns connected by the $$$i$$$-th road in the region. It is guaranteed that $$$u_i \ne v_i$$$ for all $$$i$$$, and that there are no two roads connecting the same pair of towns.
For each case, you must print the following. The first line should contain the minimum number $$$M$$$ of roads that need to be built.
The following $$$M+m$$$ lines should contain your road project. This includes both the added roads and the already existing roads oriented as you wish. Formally, the $$$i$$$-th line should contain two integers $$$1\le u_i, v_i\le n$$$, representing a one-way road from town $$$u_i$$$ to town $$$v_i$$$.
Note that you are allowed to connect a pair of distinct towns with more than one road.
- (8 points) In each region, there are exactly $$$m = n-1$$$ roads, and there is one town that is the endpoint of all roads.
- (70 points) In each region, there are exactly $$$m = n-1$$$ roads.
- (12 points) The sum of $$$m^2$$$ over all cases does not exceed $$$10^6$$$.
- (10 points) No additional restrictions.
23 31 21 32 33 21 21 3
0 3 1 2 3 1 2 1 1 2 3 1 2 3
$$$1 \le T \le 1000$$$
$$$2 \le n \le 2\cdot 10^5$$$
$$$1 \le m \le 2\cdot 10^5$$$
The sum of $$$m$$$ over all cases does not exceed $$$2\cdot 10^5$$$.
We say that a number is coruñese if, in its decimal representation, there are no two consecutive digits that are the same.
Given $$$n$$$, express $$$n$$$ as the sum of two non-negative coruñese integers.
The first line contains an integer $$$T$$$, the number of cases to process.
This is followed by $$$T$$$ lines, each containing an integer $$$n$$$.
For each case, write a line with two coruñese numbers $$$a$$$ and $$$b$$$, such that $$$a + b = n$$$. The numbers $$$a$$$ and $$$b$$$ must be written in decimal without leading zeros. You can print any valid solution.
- (13 points) The sum of $$$n$$$ for all cases is at most $$$10^6$$$.
- (29 points) $$$n \lt 10^9$$$.
- (25 points) All digits of $$$n$$$ are the same.
- (33 points) No additional restrictions.
5 1 11 2 2025 1337
0 1 6 5 1 1 2020 5 1216 121
$$$1 \leq T \leq 10^4$$$.
$$$1 \leq n \lt 10^{10^5}$$$, and the sum of the number of digits of $$$n$$$ for all cases will be at most $$$10^5$$$.
The OIE arrives, and your family decides to take the opportunity to travel to Coruña with you, enjoying the city while you suffer solving problems. However, this plan will not be easy to carry out, as there are many of you in the family and you have only one car.
In your family, there are $$$n$$$ people, and you have a single car with $$$k$$$ seats. Therefore, to go to Coruña, you will have to make several trips. Initially, the car and the $$$n$$$ family members are in your city. In each trip, the car will move from your city to Coruña or from Coruña to your city, transporting between $$$1$$$ and $$$k$$$ family members, one of whom will be the driver.
Moreover, it would be dangerous for the same person to drive too much. Depending on their situation, some family members can drive more or fewer times (some do not even have a license, so they cannot drive at all). Specifically, the $$$i$$$-th family member can drive at most $$$a_i$$$ times without becoming a danger to road safety.
Determine if the trip your family plans is possible, and if it is, write an itinerary that your family can follow so that everyone arrives in Coruña without anyone driving too much.
The first line contains an integer $$$T$$$, the number of cases. The following $$$T$$$ cases each consist of $$$2$$$ lines:
- The first line contains $$$n$$$ and $$$k$$$, the number of family members and the number of seats in your car.
- The second line contains the $$$n$$$ integers $$$a_1,\ldots,a_n$$$, the number of times each family member can drive.
For each case, you must print on a single line with "SI" or "NO", depending on whether your family's plan is possible.
If it is possible, you must then print a valid itinerary. First, print a single line with an integer $$$m$$$, the number of trips in your itinerary. Since the car alternates its position, odd trips will be from your city to Coruña and even trips will be from Coruña to your city.
For each trip, you must print two lines.
- The first line contains an integer $$$1\le h \le k$$$, the number of occupied seats in the car.
- The second line contains $$$h$$$ integers, the numbers of the family members traveling in that car. The first number you print will be the driver.
- (16 points) $$$k=2$$$.
- (25 points) $$$k=3$$$.
- (14 points) $$$a_i\le 1$$$.
- (23 points) $$$a_i\le 2$$$.
- (22 points) No additional restrictions.
26 32 1 0 3 0 15 20 2 0 1 0
SI 5 3 6 2 5 1 2 3 1 2 3 1 1 2 4 1 NO
- $$$1\le T \le 1000$$$
- $$$2 \le n \le 100$$$
- $$$2\le k \le 100$$$
- $$$0\le a_i \le 200000$$$
- The sum of all $$$a_i$$$ across all cases is at most $$$200000$$$
You and your little brother cannot agree on who has the right to use the home computer.
You want to use it to practice OIE problems, while he thinks he will spend the afternoon playing a video game that is too violent for his age. There is only one way to resolve this family dispute: with a game of tokens.
The game takes place on a board shaped like a regular $$$n$$$-gon. Initially, your brother will place a token on any vertex of the $$$n$$$-gon. From then on, you will play a maximum of $$$k=15$$$ rounds.
In each round, you will first choose and loudly announce an integer $$$d$$$ between $$$1$$$ and $$$n-1$$$. Then, your brother will choose a direction, either clockwise or counterclockwise. He will then place a new token on the vertex that results from moving $$$d$$$ vertices in the direction he has chosen from the last place he placed a token (that is, from the vertex where he placed a token in the previous round, or in the case of the first round, from where he placed a token at the start of the game).
You play with the rule that you cannot place a second token on a square that already has a token. Your brother wins if he survives the $$$k$$$ rounds without placing two tokens in the same spot (that is, if he ends up placing $$$k+1$$$ tokens in different locations, the one he places at the beginning and the ones he places in the $$$k$$$ rounds). You win if in any of the rounds your brother cannot make any legal move. Design a program to win against your brother.
This is an interactive problem. You must refresh the output every time you print data (cout « endl or cout « flush in C++, System.out.flush() in Java, sys.stdout.flush() in Python)
Each input begins with an integer $$$T$$$, the number of cases. Each case is an independent game where the interaction proceeds as follows:
First, you must read a line that will contain the two integers $$$n$$$ and $$$k$$$, the number of sides of the $$$n$$$-gon and the maximum number of turns.
Next, there will be a maximum of $$$k$$$ turns. In the $$$i$$$-th turn, you will first print the integer $$$d$$$ that you have chosen on a single line.
After that, to receive your brother's move, you will need to read a single line, which will contain only one character: > if your brother chooses the clockwise direction, < if your brother chooses the counterclockwise direction, = if your brother has no legal moves (and thus you have won), or - if you wrote an invalid value of $$$d$$$ or it was the $$$k$$$-th round and your brother has any legal moves (and thus you have lost).
If your program reads > or <, it will proceed to the next turn, which will proceed the same way. If it reads =, then you will have won and the case will end. If it is the last case, your program must terminate immediately to be accepted. If not, the next case will start from scratch (that is, you will start by reading $$$n$$$ and $$$k$$$, and then the turns will be played).
If you read -, your program must terminate immediately to receive the verdict "Incorrect answer" in CMS. Otherwise, your program could receive arbitrary verdicts.
- (7 points) $$$n\le 15$$$.
- (12 points) $$$n\le 25$$$.
- (23 points) $$$n\le 55$$$.
- (6 points) $$$n$$$ is even.
- (13 points) $$$n$$$ is neither prime nor the product of two primes.
- (20 points) $$$n$$$ is not prime.
- (19 points) No additional restrictions.
In each subtask, you will receive full points if and only if you win all cases of all tests.
2 5 15 > < = 7 15 < > < =
3 4 6 4 1 3
- $$$1 \le T \le 1000$$$
- $$$3 \le n \le 1000$$$
- $$$k = 15$$$
- The $$$d$$$ you print must be integers between $$$1$$$ and $$$n-1$$$ (both included).