Jaime's delivery package organization is growing, the number of employees is getting bigger every month, and they bill and have earnings never seen before. Jaime decided it's time to have some hierarchy in the organization, therefore, he worked arranging the $$$N$$$ employees of his company identified with the numbers from $$$1$$$ to $$$N$$$, in such way that each employee has a manager who supervises the employee's work, the only employee who will not have a manager is Jaime. In this hierarchy, it is said that an employee $$$A$$$ reports to another employee $$$B$$$ if you can reach $$$A$$$ following the hierarchy moving through the managers starting from $$$B$$$. The reporting unit of an employee $$$A$$$ consists of all the employees $$$B$$$ such that $$$B$$$ reports to $$$A$$$, including also the employee $$$A$$$. The reporting unit of Jaime will always be the entire company (all the employees).
An organization growing is good news, and it does not mean only good news for Jaime, but for all the employees, during the last year Jaime hired a software company to develop an employee recognition program. This recognition program gives points to employees who have excelled in their work, and also it can give points to all the managerial chain of an employee if the employee has contributed significantly to the company, this is, in some cases the recognition points are earned only to an employee, in other cases the same amount of recognition points will be earned to the employee, the employee's manager, the employee's manager's manager, and so on until they reach Jaime.
Jaime has recorded all the $$$M$$$ recognition prizes the company has granted to the employees during the year, and now, he wants to answer some queries that the software he has is incapable to answer: how many recognition points employee $$$A$$$ has earned, and how many recognition points have been distributed to the entire reporting units of employee $$$B$$$. Since you have helped Jaime before, he came to you asking for help. Your task is to write a program, knowing who is the manager of each employee and the $$$M$$$ recognition prizes, to answer all of Jaime's queries.
he first line of input contains three integer numbers separated by a space, $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$1 \leq N, M, Q \leq 10^6$$$), representing the number of employees in Jaime's company, the number of recognition prizes, and the number of queries Jaime wants to answer. The next line contains $$$N$$$ integer numbers separated by a space, where the $$$i$$$-th number in the line represents the id of the employee who is the manager of employee $$$i$$$, since Jaime does not have a manager, his manager in the input will have the id $$$0$$$.
The next $$$M$$$ lines contains three integer numbers separated by a space $$$m_i$$$ ($$$1 \leq m_i \leq 2$$$), $$$e_i$$$ ($$$1 \leq e_i \leq N$$$), $$$v_i$$$ ($$$1 \leq v_i \leq 10$$$), describing the $$$i$$$-th recognition prize. If $$$m_i = 1$$$, then the recognition prize of $$$v_i$$$ points was earned by the individual employee $$$e_i$$$, if $$$m_i = 2$$$ then the recognition prize of $$$v_i$$$ points was earned to the managerial chain of employee $$$e_i$$$.
The next $$$Q$$$ lines contains two integer numbers separated by a space $$$t_i$$$ ($$$1 \leq t_i \leq 2$$$) and $$$e_i$$$ ($$$1 \leq e_i \leq N$$$), each describing one of Jaimes queries. If $$$t_i = 1$$$, Jaime wants to know how many recognition points employee $$$e_i$$$ earned. If $$$t_i = 2$$$, Jaime wants to know how many recognition points were distributed to the reporting unit of employee $$$e_i$$$.
For each of Jaime's queries print a line with a single integer number, where the $$$i$$$-th line contains the answer to the $$$i$$$-th query Jaime made.
5 5 7 2 3 0 2 3 1 1 1 1 2 1 1 4 1 2 5 3 2 1 2 1 1 1 2 1 3 1 4 1 5 2 2 2 3
3 3 5 1 3 7 15
Atsa just bought Super Mario Maker and wants to test your skills for an analysis with a level that he prepared.
That level consists of a platform with some Goombas in it. As you know, Goombas are characters with the following behavior:
- Initially, they point in one direction, (left: 0, right: 1).
- They move in the direction they are currently facing, as long as there are no obstacles.
- If two Goombas collide, they will flip their direction inmediately.
- When a Goomba reaches one end of the platform, it falls.
The platform is $$$L$$$ blocks long, extending from the coordinate $$$0$$$, to $$$L$$$. Above it, there will be $$$G$$$ Goombas. The $$$i-th$$$ Goomba will be located at $$$p_i$$$ facing to the direction $$$d_i$$$. All Goombas will advance with a speed of $$$1$$$ block per second.
Atsa wants you to tell him how many seconds it will take for the platform to be empty.
For this problem purposes, consider the size of a Goomba to be a single point. No two Goombas will share the same initial $$$x$$$ coordinate.
The first line of the input contains two integers $$$L$$$ $$$\left(2\leq L \leq 10^{16}\right)$$$ and $$$G$$$ $$$\left(1 \leq G \leq 10^4 \right)$$$.
Each of the following $$$G$$$ lines contains two integers $$$p_i$$$ $$$\left(0 \lt p_i \lt L\right)$$$ and $$$d_i$$$ $$$\left(d_i \in \{0, 1\}\right)$$$.
The time in seconds that must pass for the platform to be empty.
3 2 1 1 2 0
2
5 2 1 0 2 1
3
Bella is a simple girl with a simple life: wake up, go to work, work, go home, rest, sleep, and repeat. Bella commutes via bus, and it rains often in her city, so sometimes she needs an umbrella. However, the local weather forecast is unreliable, so Bella can't be sure if it's going to rain or not until right before she begins a trip. To avoid getting caught unprepared, Bella created a system.
She owns one or more umbrellas, keeping them at home or her workplace. Before any trip (from home to work, or vice versa), Bella looks outside to decide whether to bring an umbrella on that trip:
- if it's raining, she brings an umbrella;
- otherwise, if there are currently no umbrellas at her destination (either work or home), she still brings an umbrella, just in case;
- otherwise, she doesn't bring an umbrella.
The second rule above is meant to prevent a situation where Bella needs an umbrella but has none at her current location (a bad memory she will talk about to anyone who asks). This guarantees that Bella will never catch rain and get sick.
Now we need you to simulate Bella's method for a certain period. The simulation starts with Bella at home. Each day she takes two bus trips: to and back from work. Given the starting numbers of umbrellas at her home and workplace, and the weather reports during $$$N$$$ consecutive days, find out whether or not Bella brought an umbrella on each of her $$$2 N$$$ bus trips.
The first line contains three integers $$$N$$$ ($$$1 \leq N \leq 10^4$$$), $$$H$$$ ($$$1 \leq H \leq 100$$$), and $$$W$$$ ($$$0 \leq W \leq 100$$$), indicating respectively the duration of the simulation period in days, and the starting numbers of umbrellas at Bella's home and workplace. For $$${i}={1}, {2}, \ldots, {N}$$$, the $$$i$$$-th of the next $$$N$$$ lines contains two characters representing whether it rained on each trip of the $$$i$$$-th day. The first character refers to the first trip of the day (from home to work), while the second character refers to the second trip of the day (from work to home). Each character is the uppercase letter "Y" if it rained, and the uppercase letter "N" otherwise.
Output $$$N$$$ lines. For $$${i}={1}, {2}, \ldots, {N}$$$, the $$$i$$$-th line must contain two characters indicating whether Bella brought an umbrella on each trip of the $$$i$$$-th day. The first character refers to the first trip while the second character refers to the second trip. Each character must be the uppercase letter "Y" if Bella brought an umbrella, and the uppercase letter "N" otherwise.
5 2 1 Y N N N Y N N Y Y Y
Y N N N Y Y N Y Y Y
Students aren't allowed to leave the Institute of Magic and Embarrassment (IME), so they get very hungry for candy. Camelo realized this opportunity and decided to open a candy store inside IME (no one knows how he got permission to do such an absurd thing).
There are $$$n$$$ students in IME, and every day student $$$i$$$ orders $$$c_i$$$ candies. Camelo does not care about money, he only wants to be liked by the maximum number of people at IME. A student likes Camelo if at the moment he receives his order, he has more candies than everyone else together.
Can you help Camelo find the maximum number of people he can make like him, and the minimum number of candies to do so? He can attend the orders in any order he wants (he may also choose to ignore some orders).
The first line contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$ — the number of test cases.
Each test case is two lines and the first line contains an integer $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ indicating the number of students at IME.
The second line contains $$$N$$$ integers $$$x_i$$$ $$$(1 \leq x_i \leq 10^9)$$$, indicating how many candies student $$$i$$$ orders.
It is guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$3 \times 10^5$$$.
For each test case, output two integers — the maximum number of people Camelo can make like him and the minimum number of candies to do so.
433 4 251 8 4 2 1011052 2 2 2 2
2 5 4 15 1 10 1 2
In the first case, we can at most make two people happy, and the way of doing so that minimizes the number of candy is attending the third person and then the first, requiring $$$2 + 3 = 5$$$ candies.
Every seven years, in Marshaland, there is an exciting team-contest among the most daring marshmallows of the place. It consists of finding balls that were previously hidden. But the most appealing thing of this event is the reward.
The fee for enrolling in the contest is one marsh-coin, and that is the initial prize. For every ball a marshmallow team finds, the number of coins to earn doubles. So, after finding the first ball, the competitors are promised to earn 2 coins, after the second, their prize will be 4 coins, and so on. When the time is up, the judges announce exactly one winner team, that is, of course, the group with the greatest number of balls. Then, besides the coins the champion team acquired, the governor adds a bonus of $$$K$$$ coins to the prize.
The oracle of Marshaland, who never fails in her predictions, announced to the local government that she could not foresee the winner, but she had a vision: the number of members of the winner team will be the same as the number of balls they will attain to gather. Besides, this number is certainly a prime number greater than 2.
In prior years, there have been violent incidents within the first-place teams because they do not find a fair way to distribute the money. Thinking of it, the government wants to ensure that teams are shaped by exactly $$$p_1, p_2, \dots, p_j$$$ marshmallows, where the $$$p_i$$$ values are primes that meet the features stated by the oracle. That is why they have come to you; they know about your outstanding programming skills and they are asking you to find all the different $$$p_i$$$, knowing only the bonus the governor will add to the prize.
The first line of input contains a single integer number $$$T$$$ ($$$1 \leq T \leq 1000$$$), representing the number of cases. Each of the next $$$T$$$ lines contains a single integer, $$$K$$$ ($$$0 \lt K \leq 10^6$$$), representing the bonus coins the governor will add to the prize.
For each case in the input, print a line with all the primes in ascending order that fulfill the oracle's omens. If there are no primes with the requiered conditions, print -1.
3 2 8 345678
-1 5 5 29 149
Polygonia (a country where everything has to be a polygon) has a scientific conflict, the progressive side, that wants to legalize circles against the conservatives, that want to keep circles illegal in order to keep their traditions.
In order to proof their advantage, the circle lovers have design a motorbyke that use circular-shaped wheels, as an attempt to replace the polygon-shaped ones, but in order to disguise the circle-ban, they have painted the wheels as if they have a regular polygon. You can see an example of them in the next image.
The motorbike has always two wheels, but in some cases, they do not represent the same polygon, for example, the front wheel is square-shaped and the back one is hexagon-shaped. In order to keep the disguise, the motorbike has to stop exactly when both wheels have one side of the polygon parallel to the ground (so it seems that it is a polygon-shaped wheel).
It is guaranteed that both wheels, despite having different polygons, are the same size. A turn is the energy needed to roll a wheel 30 degrees, it is always the same, regardless the wheel's size. It is safe to assume that when one wheel is rolled by $$$x$$$ angle, the other one, moves $$$x$$$ angle too.
So, given the wheel's circumference, the number of the simulated sides of the back and the front wheel, and a distance (in the same unit as the circumference), your task is to compute the minimum integer number of turns that are necessary to cover that distance and that guarantees that in both wheels, there is one side parallel to the ground. When the bike starts its journey, this condition is guaranteed.
The input consist on an integer number $$$T$$$ ($$$1\leq T \leq 10^5$$$) that denotates the number of test cases. The next $$$T$$$ lines have four positive integer numbers separated by space:
- $$$C$$$ ($$$1\leq C \leq 10^3$$$) The circunference of the wheel.
- $$$F$$$ ($$$3\leq F \leq 233$$$) The number of sides of the front wheel.
- $$$B$$$ ($$$3\leq B \leq 233$$$) The number of sides of the back wheel.
- $$$S$$$ ($$$1\leq S \leq 10^9$$$) The distance that must be covered by a bike's journey.
For each test case, print on a single line an integer that represents the minimum number of turns required.
1 2 8 4 10
60
Atsa is constantly looking for new ways to have fun during this quarantine, she used to play checkers against her friends but, after winning against each of them, no one wants to play checkers against her anymore. Atsa now considers to play checkers alone, but found a more interesting way to challenge herself.
A checkers board is represented by a rectangular grid with $$$N$$$ rows and $$$M$$$ columns, with a total of $$$N$$$x$$$M$$$ cells. Each cell has a light color, or a dark color, in such way that no adjacent cells have the same color, the figure below shows a checkers board with $$$8$$$ rows and $$$8$$$ columns:
Since Atsa has a lot of checkers boards, she also has a lot of stones to play checkers, she has enough stones to place at least one stone on each cell of any of her checkers boards. Similar to the cells in the board, each stone is either light colored or dark colored. Atsa found that if she places a light colored stone on each light colored cell of the board, and a dark colored stone on each dark colored cell, then all squares of $$$2$$$x$$$2$$$ cells in the board will have two dark colored stones, and two light colored stones, she defined this configuration as a "pairable" stones configurations. Atsa believes this is not the only "pairable" stones configuration in the board and decided to find all of them on each of the boards she has. Are you be able to find how many distinct "pairable" stones configurations can be placed in a checkers board?
The first and only line of input contains two integer numbers separated by a space, representing respectively, the number $$$N$$$ of rows in the board, and the number $$$M$$$ of columns in the board ($$$1 \leq N, M \leq 60$$$).
Output a single line with a single number, representing, the number of distinct "pairable" stones configurations that Atsa can place in the checkers board given in the input.
2 2
6
2 3
10