A recently founded "NERC" (New Era Russian Coders) company, of course, has an accounting department. And they are very concerned about the budget of the company. In particular, they don't want the company to experience a cash gap — a condition where they need to pay more money than they have in their account now.
At the moment the company has $$$s$$$ euros on its account. The chief accountant has prepared a plan of transactions for $$$m$$$ following days. During this period $$$n$$$ transactions are planned.
For each transaction the change it makes to the company's account is known, but the exact date of the operation is unknown. Money transferred by clients may not be credited to the account immediately, and on the other hand, a claim to pay a bill can suddenly be received. For each transaction, only the range of days the transaction can happen is known in advance. If several transactions would happen on the same day, they can be performed in any order.
Help the accounting department to check if there exists an order of transactions such that the company will experience a cash gap.
The first line contains integers $$$n$$$, $$$m$$$ and $$$s$$$ — the number of payments, the number of days in the plan and the initial amount of money the company has ($$$1 \leqslant n, m \leqslant 1000$$$; $$$1 \leqslant s \leqslant 10^6$$$).
The $$$i$$$-th of the following $$$n$$$ lines contains a description of the $$$i$$$-th payment in the following format: "$$$\mathtt{count}~\mathtt{from}~\mathtt{to}$$$", which means that on any day from $$$\mathtt{from}$$$ to $$$\mathtt{to}$$$, the amount of money will be changed by $$$\mathtt{count}$$$ euros ($$$-10^6 \leqslant \mathtt{count} \leqslant 10^6$$$; $$$1 \leqslant \mathtt{from} \leqslant \mathtt{to} \leqslant m$$$).
Print "YES" if a cash gap can occur, or "NO" if such situation is impossible.
4 3 100 100 1 2 -100 1 2 1 2 3 0 3 3
NO
4 3 100 100 1 2 -100 1 2 1 2 3 -1 2 2
YES
In the first example there is a single transfer from the account, and thus before it there will be at least $$$100$$$ euros available in the account, so the cash gap is impossible.
In the second example, it could happen that both transfers from the account (for $$$100$$$ euros and for $$$1$$$ euro) will be requested on the second day, before all other transactions. In this case by the time the second transaction occurs there will be no money left on the account — it's a cash gap.
Tomorrow Programming School Department of Arithmetics is going to build a new pool in the basement of their building. The pool will serve mainly for testing of innovative floating point arithmetic algorithms, especially their floating properties in different kinds of liquids. Occasionally, the members of the staff will be allowed to the pool as well. To make the pool optimally fit for human needs, the department has to decide on the pool dimensions. The pool will be rectangular, it must not be a square. Its exact surface area $$$C$$$ is predetermined by the choice of the relevant algorithms to be tested there. The company they hired to build the pool offers the list of possible pool side lengths. They have studied the demand in detail and they guarantee that a pool with the given area can be built using the lengths in the list. However, the particular choice is up to the department.
As the presented list is relatively long, the department also hired a junior programmer who is going to find out which lengths from the list can be chosen. Before he started his job, the programmer had made interesting observations. First, all available pool side lengths are primes. Second, the surface area $$$C$$$ of the pool is a product of two distinct primes. He thinks this information may be helpful to find appropriate side lengths reasonably quickly.
Be faster than the hired programmer and solve the problem first.
The first input line contains integer $$$C$$$ ($$$1 \leq C \leq 10^{18}$$$), the area of the pool surface. The second line contains integer $$$M$$$ ($$$1 \leq M \leq 2 \cdot 10^5$$$), the number of pool side lengths offered by the company. The third line contains a list of space-separated unique primes $$$P_1, \ldots , P_M$$$ ($$$1 \lt P_i \lt 10^9$$$), representing the offered pool side lengths.
All measurements are expressed in the same units.
Output a single line with two space-separated pool side lengths from the offered list, which can be used to build the pool. The first side length has to be smaller than the second one.
15 5 7 2 5 11 3
3 5
Alexander and Melina are really good friends. After a long summer of playing games together, they finally had to take the bus back home. Since they had such an active summer, they were getting bored from the bus ride, so Alexander challenged Melina to one final puzzle.
Alexander gave Melina a piece of graph paper $$$W$$$ centimeters wide and $$$H$$$ centimeters tall. The paper was subdivided into $$$1\times1$$$ squares, forming a $$$W\times H$$$ coordinate system. In the paper, Alexander had drawn many colorful points, in such a way that there were exactly two points of each color, all points were at integer coordinates (possibly including the edges and corners of the paper) and there were no two points in the same spot.
Alexander asked Melina to draw a line between each pair of equally colored points, connecting them. The lines connecting the points couldn't touch each other. However, they could assume an arbitrary shape (as long as they remained inside the paper) and they could be considered infinitely thin.
Melina argued with Alexander that the game was unfair since there was no way to satisfy his requirements. Alexander assured her that the game was fair, and she simply had to "get good" to solve the challenge. After much arguing, the friends decided to task you, an unbiased observer, with determining whether the game is fair or not.
 |  |
In the example above, Melina can connect each pair of points without crossing lines, therefore the game is fair. On the contrary, in the example below, Melina can't connect the twos without crossing whichever line connects the ones, therefore the game is not fair.
The first line contains two integers $$$W$$$ and $$$H$$$ ($$$1 \leq W,H \leq 10^9$$$), indicating respectively the width and height of the paper. The second line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of pairs of points drawn in the paper. Each of the next $$$N$$$ lines contains four integers $$$X_1$$$, $$$Y_1$$$, $$$X_2$$$ and $$$Y_2$$$ ($$$0 \leq X_1, X_2 \leq W$$$ and $$$0 \leq Y_1, Y_2 \leq H$$$), representing a pair of points of the same color drawn at coordinates $$$(X_1,Y_1)$$$ and $$$(X_2,Y_2)$$$. No two points have the same location.
Output a single line with the uppercase letter "Y" if the game is fair, and the uppercase letter "N" otherwise.
5 5 3 4 0 2 5 1 0 2 4 4 2 1 2
Y
5 5 2 4 0 3 5 5 3 0 2
N
Meet Carlitos, a spirited adventure enthusiast with an insatiable love for amusement parks. Despite his vibrant passion, Carlitos faces a unique challenge – his height. As he eagerly plans his weekend escapade, he realizes that his vertical limitations might hinder his amusement park experience. It's not just about choosing a park; it's about finding one where he can enjoy the thrill of the rides.
Picture the kaleidoscope of colors, the jubilant laughter, and the heart-pounding rush of the rides. Carlitos has always been drawn to the energy of amusement parks. With the weekend approaching, he pores over park brochures, studying the height requirements of each ride. His goal is to maximize his enjoyment, and that's where you come in.
Your task is to help Carlitos determine the number of rides he can enjoy at a specific park. By considering his height and the minimum height requirements of each ride, guide him in making the most of his amusement park adventure.
The first line contains two integers, $$$N$$$ and $$$H$$$ ($$$1 \leq N \leq 6$$$ and $$$90 \leq H \leq 200$$$), representing the number of rides in a park and Carlitos' height in centimeters, respectively.
The second line contains the minimum heights $$$A_1, \ldots, A_N$$$ ($$$90 \leq A_i \leq 200$$$) of each ride in the park.
Output a single line with an integer indicating the number of rides Carlitos can go on, that is, the number of rides for which Carlitos' height is at least as large as the minimum height required.
1 100 100
1
6 120 200 90 100 123 120 169
3
Fernando is a professional who works in the accounting department of Stark Companies. He is responsible for the control and analysis of the company's daily turnover. Fernando recorded the company's turnovers during $$$N$$$ consecutive days. From this, he generated a list $$$V$$$ of size $$$N$$$ where $$$V_i$$$ represents the amount of money the company earned on the $$$i$$$-th day. Notice that a value $$$V_i \lt 0$$$ indicates that the company lost money that day.
One of Fernando's tasks is to pass on to his superior Tony a list indicating the turnovers during a range of days. But Fernando knows that Tony will be very angry with his subordinates if, in the list he received, there is a day $$$i$$$ such that the sum of the turnovers for the first $$$i$$$ days is negative, indicating that the company lost money. Since Fernando wants his superior to be happy with him, he will modify his list $$$V$$$ a little before sending it to Tony. This modification consists of removing some days from the beginning of the list and some days from the end of the list.
Fernando says that the happiness of the list $$$V$$$ is the number of sublists he can send so that Tony will be happy. Formally, the happiness of $$$V$$$ is the number of integer pairs $$$p,q$$$ ($$$p,q \ge 0$$$ and $$$p + q \lt N$$$) such that if Fernando removes the first $$$p$$$ days and the last $$$q$$$ days from $$$V$$$, for every $$$i$$$ the sum of the first $$$i$$$ values of the resulting list is non-negative.
Fernando was thinking about happiness when an additional problem arose. The company's IT staff reported that there was a glitch in the system that calculates the company's daily turnover. They discovered that for one of the $$$N$$$ days, the system calculated a turnover that differs by $$$X$$$ units from the actual turnover. That is, there is one day $$$i$$$ such that the actual turnover for that day is $$$V_i + X$$$ instead of $$$V_i$$$. Fernando could dig deep and find out exactly which of the days this error happened, but he is too lazy. So he decides that he will add $$$X$$$ on a day in such a way that the happiness of the modified $$$V$$$ is as high as possible.
You, being a friend of Fernando, have decided to help him. Given the glitch $$$X$$$ and the list of turnovers $$$V$$$, you must find the maximum happiness of $$$V$$$ considering that $$$X$$$ must be added to one of the turnovers.
The first line contains two integers $$$X$$$ ($$$-10^9 \leq X \leq 10^9$$$) and $$$N$$$ ($$$1 \leq N \leq 5 \times 10^5$$$), indicating respectively the value of the glitch and the number of days in the list of turnovers. The second line contains $$$N$$$ integers $$${V_1}, {V_2}, \ldots, {V_N}$$$ ($$$-10^9 \leq V_i \leq 10^9$$$ for $$${i}={1}, {2}, \ldots, {N}$$$), describing the list.
Output a single line with an integer indicating the maximum happiness considering that $$$X$$$ must be added to one of the turnovers given by $$$V$$$.
1 6 1 1 -2 1 3 -5
13
-1 6 1 1 -2 1 3 -5
9
The Olympic Games are the most important sporting events in human history. Usually, the Olympic Games are held every four years. However, the 2020 Olympic Games just finished in August 2021 due to the COVID-19 outbreaks.
There are more than 200 nations participating in the Olympic Games. Thousands of athletes around the world compete in various sports. The athletes represent their countries or National Olympic Committees (NOCs) to compete for medals. Therefore, each country or NOC may win medals in the competitions.
There are three types of medals: gold medals, silver medals, and bronze medals. Typically, the gold medals are awarded to the winners of the competitions, and silver medals are awarded to the runner-ups. Most of the bronze medals are awarded to the second runner-ups. However, there can be no second runner-up in some sports. The bronze medals can be awarded in different manners. For example, in a few tournament sports, such as wrestling, boxing, and judo, two bronze medals are awarded to the eliminated semi-finalists.
A country or NOC has a better rank than another country or NOC if one of the following conditions holds.
Please write a program to find the country or NOC which has the best rank among all countries and NOCs.
The first line of the input contains one positive integer $$$n$$$. Then $$$n$$$ lines follow. Each of the following lines contains three non-negative integers $$$g$$$, $$$s$$$, $$$b$$$, and the name of a country or NOC. They are separated by blanks.
Print the name of the country or NOC of the best rank.
4 22 21 22 Great Britain 27 14 17 Japan 39 41 33 United States of America 20 28 23 ROC
United States of America
3 999 999 998 Malaysia 999 999 999 Thailand 999 998 999 Indonesia
Thailand
The year is 3019. By now the humanity is living in cities floating in the atmosphere on air balloons and jet engines. There are $$$n$$$ cities on the planet connected by the jet trains network. If the cities $$$a$$$ and $$$b$$$ are connected by the train route, people can travel between them in any direction. The $$$a$$$-th city can be reached from the $$$b$$$-th city if and only if there is a path between $$$a$$$ and $$$b$$$, where each edge of the path represent a train route.
People of 3019 love to be friends, and it happens so people from the same city have many friends in common. Let us say that the friendship connects not pairs of people, but pairs of cities. The friendship of two cities is mutual.
Sometimes people from a city may decide to organize a celebration and invite all the people from friendly cities. If the celebration is announced to be in city $$$a$$$, all people from the friendly cities of $$$a$$$ try to get to $$$a$$$ using jet trains network. People from all friendly cities of $$$a$$$ that can reach the city $$$a$$$ join the celebration.
It has been decided to create a special system called "Celebration 3019" to evaluate the number of people on a certain celebration. There is information about cities which are friends, and the current state of the jet trains network. The system must handle the following requests: "If the celebration is announced in the city $$$v$$$, people from how many cities will attend it?". Besides, there should be an option to add an information about new pair of friendly cities, and about new jet train route. Fortunately, the train routes never cancel and once friended, the cities remain friends forever.
Please help the mankind to develop such a system.
The first line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ — number of cities, number of pairs of friendly cities and number of jet trains routes ($$$1 \le n \le 10^5$$$, $$$0 \le m, k \le 10^5$$$).
The following $$$m$$$ lines contain two integers $$$a$$$ and $$$b$$$ each ($$$1 \le a, b \le n$$$, $$$a \neq b$$$) — pairs of friendly cities. It is guaranteed that each pair is listed at most once.
The following $$$k$$$ lines contain two integers $$$a$$$, $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$) — pairs of cities connected by the jet train routes. There is at most one route between each pair of cities.
The next line contains the integer $$$q$$$ ($$$0 \le q \le 10^5$$$) — the number of requests to handle, and the following $$$q$$$ lines represent requests.
For each request "? $$$v$$$" print the answer to it on a new line.
4 2 2 1 2 1 3 1 2 1 4 5 ? 1 F 4 1 ? 1 T 4 3 ? 1
1 2 3
The answer to the first request equals one, because only one of the cities $$${2, 3}$$$ has a train route to the city $$$1$$$. The answer to the second request equals two, because before the request cities $$$1$$$ and $$$4$$$ became friends, and they had a train route connecting them. The answer to the third request equals three, because there is now possible to travel from the city $$$3$$$ to the city $$$1$$$ using trains network: first, people can travel to city $$$4$$$, and then to city $$$1$$$.