What a day! From reports received by the police department, a strange, triangular shaped object was seen flying and beaming strong light across the sky of Nlogonia for a few minutes this morning. Was it Triangolonian aliens? A secret government project? Someone playing a prank? Either way, you noticed your property now has several triangular patches that are missing its grass... time to buy some grass seeds to fix those.

Grass seeds come in bags of a certain kilogram weight. Each kg of seeds can be used to cover 30$$$m^2$$$ of grass. A local supplier has given you a quote for all $$$B$$$ seed bags it sells. Each bag has a weight of $$$W_i$$$ kg and costs $$$P_i$$$ Nlogonian coins.

You went ahead and measured all the $$$N$$$ triangles missing its grass that you need to cover with seeds. As they have different shapes, you decided to measure their sides ($$$A_i$$$, $$$B_i$$$, $$$C_i$$$) in meters.

Given your local supplier quote, and the measurements of each triangle. Can you find the minimum number of coins you need to buy enough seeds to fix up your property?

In 1734, the great mathematician Leonhard Euler solved the famous Basel Problem, which states that $$$\displaystyle \sum_{k=1}^{\infty} \frac{1}{k^2} = \frac{\pi^2}{6} $$$.

He also provided a generalization: let $$$n$$$ be an even positive integer, then the function $$$\displaystyle \zeta(n) = \sum_{k=1}^{\infty} \frac{1}{k^n}$$$ is always equal to a rational multiple of $$$\pi^n$$$, i.e., $$$\displaystyle \zeta(n) = \frac{p_n}{q_n} \pi^n$$$ for some positive integers $$$p_n$$$ and $$$q_n$$$ with $$$gcd(p_n, q_n) = 1$$$.

Almost 300 years later, another great mathematician insert your name here found a way to compute $$$p_n$$$ and $$$q_n$$$ very fast, but since those numbers can be very large, he really finds $$$p_n \times q_n^{-1}\ mod\ 998244353$$$ only, where $$$q_n^{-1}$$$ is the multiplicative inverse of $$$q_n$$$ in that modulo.

The main enemies of democracy (the anti-democrats) have created a new encryption key for their texts, but it has been cracked! It is based on prime numbers, those that do not have divisors greater than 1.

This new encryption key is based on being able to find the number of primes in an interval of numbers. Anti-Democrats considered that having prime numbers up to one million was going to be enough to confuse the Allies. To prove them wrong, you have been tasked with breaking encrypted messages.

Given two numbers $$$i$$$, $$$j$$$, your task consists to count the number of prime numbers that are in the interval $$$[i, j]$$$ (including the extremes).

Jaime's pizza delivery has been awarded the "Best pizza in town" award. This is because of the care and effort they put for each pizza they make and deliver, always making sure they do not start a pizza until all pizzas before are done. However, a consultant has identified making a pizza at a time delays delivery, and waiting times have been increased considerably since they got the award because more and more people are willing to try this famous pizza.

Pizzas at Jaime's pizzas have at most 4 ingredients, $$$i_1$$$, $$$i_2$$$, $$$i_3$$$, $$$i_4$$$, and they are always done following this order, that is a pizza will never get the ingredient $$$i_3$$$ before ingredient $$$i_2$$$. When a customer orders a pizza, they write a note with the amount of each ingredient they wants in their pizza. If they don't like a specific ingredient from the list, they just write a $$$0$$$ for it. For example, if a customer requested the pizza "1 1 0 2", it means the pizza should have one unit of $$$i_1$$$, one unit of $$$i_2$$$ and two units of $$$i_4$$$. When the kitchen gets this order, Jaime will put $$$i_1$$$ in the pizza, then $$$i_2$$$, and finally $$$i_4$$$, $$$i_3$$$ is not added to the pizza as it was not requested.

To make the process faster, Jaime decided to hire $$$4$$$ people, one to work with each ingredient. These people will put in a pizza only the ingredient they were assigned to. Jaime believes in this way they can deliver pizzas faster, as, in some point, each of the recent hires will be working on a pizza, but they will always make sure to start the orders in the order they were received, and to put the ingredients in the order they should be.

Knowing that an employee takes $$$1$$$ unit of time to put $$$1$$$ unit of ingredient, and the description of the $$$N$$$ orders received in a night, can you determine the minimum amount of time it will take for all the pizzas to be delivered?

A new escape room has opened in the city. In this escape room, a group of at least two people is required to play. At the beginning of the game one person of the group will be selected, this person will enter the room while others stay outside of the room with a map. The one that enters the room has a device and will be blindfolded, so, the person is not aware of the surroundings. The game is as follows, the person inside the room will use the device to tell the others in the group the coordinates $$$(i, j)$$$ the person believes is positioned in the map, the group then will answer with the steps the person should follow in order to escape the room.

The map of the room is represented by a matrix with $$$R$$$ rows and $$$C$$$ columns, each position of the matrix has a character wich means the following:

• '.' means the person can be positioned in that position.
• '#' means there is a wall at that position.
• 'X' means there is an object at that position.
• 'E' represents the position of the exit in the room.

For each coordinate the person in the room sends to the group, the group should answer with a single character:

• 'W' if the coordinate sent has a wall in the map.
• 'X' if the coordinate sent has an object in the map.
• 'E' if the coordinate sent is the exit.
• '?' If the coordinate indicates a place with no way to the exit
• An indication of the path the person should follow to get to the exit if the map has a '.' in that coordinate.

The indications of the path the group will send to the person are always in such way that if the person moves in that direction the person will be closer to the exit than before, the indication should be a character based on the move the person should perform:

• 'L' if the person should move left.
• 'D' if the person should move down.
• 'R' if the person should move right.
• 'U' if the person should move up.

Given the map of the room, and the coordinates sent by the person inside the room, write a program with the answer the group should send to the person.

Jaime is watching a movie, since it's late and all his family is sleeping, he decided to enable subtitles and watch the movie without sound. But, what a surprise, the subtitles are out of sync! He reads the subtitles before some actor in the movie speaks, unacceptable! As the good programmer Jaime is, he decided to look for the file where the subtitles are stored in the movie, he found the file and it's very big! So he will write a program to fix the subtitles and continue watching the movie.

After looking at the file, Jaime found that the subtitles have a well defined structure:

1. A subtitle begins with a line with a number that appears to be a sequence number of the subtitle.
2. The next line contains a string, apparently the time at miliseconds precision where the subtitle should be displayed in the screen and the time when it should be removed from screen separated by the string " –> ", the time is displayed in the format "Hours:Minutes:Seconds,Miliseconds".
3. Finally, one or two lines with the text to be displayed as subtitle. Two subtitles are separated each other with a blank line. And the lines with the subtitle text do not have trailing or leading whitespaces.

The subtitles file looks something like this:

1
00:00:00,498 –> 00:00:02,827
- Here's what I love most
about food and diet.

2
00:00:02,827 –> 00:00:06,383
We all eat several times a day,

3
00:00:06,383 –> 00:00:09,427
of what goes on our plate
and what stays off.

The movie does not last more than 10 hours, and subtitles are at most delayed 10 seconds.

Given the subtitles file and the delay in the subtitles, Can you help Jaime write a program to sync the subtitles of the movie?

Baker invited his friend Amy to get somes snacks at a local shop. But Baker was secretly hoping to get some free snacks from her. He proposed making a game out of eating the snacks, where the loser pays the bill for the snacks.

For each game, the cats will select $$$N$$$ snacks and place them in a pile. Then they will take turns selecting a number of snacks to eat from the pile. Amy will always go first. Each turn consists of the following steps:

1. The active cat chooses a number $$$X$$$ between $$$1$$$ and $$$M$$$ (inclusive). They won't try to eat more snacks that are currently left in the pile.
2. The active cat will eat the chosen X number of snacks from the pile.
3. If the current cat ends up eating all the snacks left in the pile, meaning the pile is empty after they eat, the active cat wins the game.
4. On the other side, if the number of snacks remaining in the pile (counted in binary) contains an odd number of ones, then the active cat loses the game.

Assuming both cats play optimally, can you help figure out whether Baker will get "Free snacks!" or whether he will have to "Pay the bill" for each game.

Juanfra is a professional gamer - he plays videogames consistently every day, and sometimes he also works as a software developer in his free time. Recently, a brand new game got released: "Awesome Mar'ia Sisters" by the Noentiendo company, which some conspiracy-advocate people consider to be a disguised fresh remake of another fairly famous game about a pair of plumber brothers, but who could even believe such a thing when this game is about two construction worker sisters, right?

Anyway, Juanfra, who obviously doesn't even consider that possibility which only some out-of-mind haters can conceive, wants to play this new game, because otherwise what kind of pro gamer would he be? So he decided to upgrade his computer. He's been doing research for a long time and finally arrived to the conclusion that buying parts separately and from different brands is going to give him the best computer quality as possible.

It turned out that the Awesome Mar'ia Sisters game is so CPU demanding that Juanfra's computer started overheating after just a couple of minutes of gameplay - he couldn't even finish the tutorial steps! Unacceptable! He was so mad about it that he ran to the store and bought the first liquid nitrogen cooler he saw there, which proved to be an immediate solution to the problem. Now relaxed and proud of his computer building skills, he kept mastering the game. He was enjoying it so much that he didn't notice the heatwave that started striking the region lately. Unfortunately, the temperatures got so high that not even the cool cooler he installed could help - it got so stressed that it began vibrating due to a poor fixation to the motherboard and got a crack which made it leak nitrogen into the computer case. One night, while he was just warming up doing some blindfold speedruns of the game, the computer started displaying random colors on the screen, which Juanfra didn't notice because he was playing blindfold, so it went on like this for many hours. When he finally finished the blindfold speedrun (which was a new world record by the way), he noticed his huge blunder. However, after investigating for a while he discovered that some transistors melted in his computer components, and with a little help from the spilled nitrogen now he's got a third possible state for a bit!

He immediately figured out that now he can store more games in his computer by compressing them and he's so excited about this fact that he wants to try it right away. The first method he thought of to compress them is to choose a sequence of zeroes and ones (which we'll call $$$w$$$), and then replace it by this new bit state '2' in as many places as he can in the game file. He also needs to be able to decompress the game later in case he wants to install the game in his old conventional computer, so he should be able to replace all the occurrences of '2' with $$$w$$$ in the compressed file and get the exact original one. In addition, Juanfra would like $$$w$$$ to fit into one register of his CPU so he can run this algorithm as fast as possible. This means that $$$w$$$ can be of any length up to the size of one of his CPU registers. The thing is he doesn't remember the exact CPU he's got for his computer and he's very busy playing to look it up, he only remembers it was less than 200 bits, but it can really be any number of bits fewer than 200 because he says it's from an experimental limited-edition release by the Noentiendo company specifically tuned to run their games.

Would you help him implement his idea so he doesn't lose time and can start working on a new world record for blindfold hand-tied speedrun of Awesome Mar'ia Sisters? Juanfra even says he allows you to find out his CPU model so you can make a better work!

Nlogonia is connected to Linealonia by a directed linear highway, this is, vehicles can travel from Nlogonia to Linealonia but not in the other way, and the highway does not have any curves, it is a straight line. The highway has $$$N$$$ cities, there are no two cities in the same place and, they are numbered from $$$1$$$ to $$$N$$$ in such way that if city $$$j$$$ is after city $$$i$$$ when you take the highway if $$$j \gt i$$$ for all $$$i, j \leq N$$$, city $$$N$$$ is Linealonia.

The next year Linealonia will host a programming contest, each city in the highway will send a team to compete in the contest, the cost it takes for a team to go from one city to another is equal to the distance between the two cities. Linealonia has agreed to pay for the travel expenses of all the teams, so they want to find a way to minimize the total cost for all the teams to get to city $$$N$$$. To achieve this, they will build a teleport machine to connect two cities, the only restriction for this machine is that the two cities it connects should be at most at $$$K$$$ Km distance away, and if it connects city $$$i$$$ and $$$j$$$, city $$$j$$$ should be as far as possible from $$$i$$$, considering the $$$K$$$ km restriction. The main advantage of building this machine is that if a team decides to use the machine the cost to travel between the two cities the machine connects will be a constant $$$T$$$, hopefully reducing the total cost for Linealonia.

Can you help Linealonia find what two cities should the machine connect in order to reduce the total cost to gather all the teams for their programming contest?

Bob just joined a software developing company as a Software Engineer. The organization in this company is simple: each employee is identified by a unique integer ID between $$$1$$$ and $$$N$$$. All the employees $$$i$$$, except for the one with ID equal to $$$1$$$, has a manager denoted by $$$m_i$$$. If $$$m_i$$$ is the manager of $$$i$$$, then $$$i$$$ is considered to be a direct report of $$$m_i$$$.

The employees that are managers of any employee usually are busy with meetings providing feedback of their reports, for that reason some tedious tasks are delegated to the employees that do not have any report. One of those tasks is to reply emails of customers that are complaining about bugs in the systems.

The feedback system works in a strange way. When a customer submits a complaint, a random employee receives an email with the content of the complaint. When a employee receives a complaint email, they reply that email if the employee does not have any direct report. Otherwise, the employee resends the email to their manager or to any of their direct reports. The goal is to minimize the number of people that will receive the email before someone replies to it, so an employee will choose resending the email to their manager or their direct report that minimizes this number assuming that they will also do an optimal election.

Bob is responsible of improving the complaining system, for that reason he wants to measure the impact in the performance of the current system. Help Bob find the expected number of people that will receive the email before replying to it, given that all the employees have the same probability of receiving the complaint email when the customer sends it. Note that the first employee and the last employee that receive the email are also counted.

Jaime's birthday will be shortly, and their parents are planning a nice party. They know Jaime loves biscuits, so they will bake some. When they talked to Jaime about their plan, he asked them to tell him how many biscuits there will be in order to decide how many friends he would invite.

First, Jaime's parents found strange their son's petition. They know Jaime has exactly 5 friends, and they assumed he would invite all of them. However, Jaime explained he would love to invite as many friends as possible, but he also wishes all of the children receive the same number of biscuits. When Mother and Father listened to so righteous explanation, they realized there were several other things to consider, such as the amount of cake, the sandwiches, and hundreds of things more.

The family came up with an idea to deal with the situation: They will start by knowing the number of biscuits and, based on that information, they will evaluate how many children –Jaime inclusive– there could be at the party. They will analyze the restrictions that other things state later.

Although Jaime is willing to dispense with many of their friends, he cannot imagine his birthday without his bestie Churro (they are guinea pigs, do not make questions), so, at least, there should be one guest.

Given the number of biscuits Jaime wants in the party, help his parents know the number of children that can be at the party.

Leonel is solving exponentiation problems, he has become really good to calculate powers of two. Several times Leonel has impressed his friends and teacher showing his skills answering what is the value for the $$$k$$$-th power of two ($$$2^k$$$), with really large values for $$$k$$$.

To make things more challenging to Leonel, his teacher has requested to him, instead of calculating the value for $$$2^k$$$, to write the result in the following notation:

• 2 if $$$k = 1$$$
• $$$(2*2^{k-1})$$$ if $$$k$$$ is an odd number
• $$$(2^{\frac{k}{2}})^2$$$ if $$$k$$$ is an even number

Leonel is certain it will take more time for him to write in this notation than calculating the power, that is why he decided to ask for your help to write a computer program so he can copy the notation from the result of your program to his notebook. Given the value of $$$k$$$ write a program that prints $$$2^k$$$ in the notation described by Leonel's teacher.

The moon dancers, as their name suggests, is a group of people who dances to pray the moon. The moon is a goddess for their tribe, they dance every full moon to get the moon blessings and guarantee the tribe another moon cycle of wellness.

Some researchers are very interested in the peculiar dance these moon dancers perform on the full moon. It is marvelous to see how they dance around a circle, each dancer positioned and performing an exact set of moves that have been passed between dancers for generations. At some point of the dance, each of the $$$N$$$ dancers sit at some point in the perimeter of the circle, no two dancers sit in the same place, and they start singing the song of times. Then, suddenly, a set of $$$K$$$ dancers stand up and dance rotating counter clockwise around the circle until each of the $$$K$$$ dancers meet with a dancer that is sitting, making $$$K$$$ pairs of dancers, all of the $$$K$$$ dancers will have rotated the same amount of degrees around the circle. At this point the $$$K$$$ pairs continue with the dance while the $$$N - 2*K$$$ (possibly none) dancers that are not matched continue singing the song of times.

Knowing your programming skills, researchers have come to you and ask for help on a very specific task: given the position of each of the $$$N$$$ dancers when they sit at the perimeter of the circle, can you find the maximum number of pairs that can be matched to continue the dance?