UNICAMP Freshman Contest 2025
A. Neymar at Santos
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After a long time abroad, Neymar returns to play in his homeland. What few people know is the small sacrifice that had to be made for this to happen...

Neymar's new contract states that $$$X$$$ reais will be deducted from the salary of each public school teacher in Brazil for every goal Neymar scores while wearing the Santos jersey, and this money will be redirected to Neymar in its entirety. Note that a teacher cannot receive less than $$$0$$$ reais as salary, so there is a limit to how much money can be redirected to Neymar.

Given that there are $$$P$$$ public school teachers, each earning a salary of $$$R$$$, that Neymar scored $$$G$$$ goals in the month, and that the amount deducted from each teacher per goal is $$$X$$$, determine how much money Neymar receives.

Input

The input consists of four lines. Each line contains a single integer:

The first line contains an integer $$$P\;(1 \leq P \leq 10^8)$$$, representing the number of teachers in Brazil.

The second line contains an integer $$$R\;(1 \leq R \leq 3000)$$$, representing how many reais each teacher earns.

The third line contains an integer $$$G\;(1 \leq G \leq 40)$$$, representing how many goals Neymar scored in the month.

The fourth line contains an integer $$$X\;(1 \leq X \leq 2000)$$$, representing how many reais Neymar should receive from each teacher per goal.

Output

Your program should print a single line containing a single integer: the amount of money that Neymar deservedly receives from the Brazilian teachers.

Examples
Input
1861118
1500
10
100
Output
1861118000
Input
1861118
1500
10
200
Output
2791677000
Note

Note that in the second case, the amount that should be deducted from each teacher's salary is greater than their salary. In this case, unfortunately, it is not possible to divert more than the totality of the teachers' salaries to Neymar :(

B. We're Competing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The year is 2077 and you are a renowned archaeologist specializing in ancient texts. Recently, you came across a scroll that appears to be a transcript of an extremely important interview for the course of human civilization. To confirm your suspicions, you ask ChatGPT for help!

You received a transcription of the scroll made by ChatGPT, but it came without spaces and is very hard to read! Furthermore, since you don't have the PRO plan, the AI may have made up to $$$K$$$ mistakes, that is, it may have changed up to $$$K$$$ characters.

All you know about the text you are looking for is that it contains the phrase "tamo competindo", and you are too impatient to ask another AI for a transcription. Therefore, given the factor $$$K$$$ and the transcription from ChatGPT, determine if it is possible that the original scroll matches the text you are looking for, i.e., if it is possible that it originally contained the phrase "tamo competindo".

Input

The first line of input contains a single integer $$$K \; (1 \leq K \leq 14)$$$

The second line of input contains a sequence of characters $$$S \; (1 \leq |S| \leq 5 \cdot 10^4)$$$

Output

If it is possible that the input text is the desired text, print SIM (portuguese for YES). Otherwise, print NAO (portuguese for NO).

Examples
Input
3
tepoassimtamocompetindu
Output
SIM
Input
1
temocompetindu
Output
NAO
Input
14
olaaaa
Output
NAO
Input
3
tamoccompetindo
Output
NAO
Input
10
acreditenosseussonhos
Output
SIM
Note

Explanation of example $$$1$$$: It is possible that the original text was "tipo assim tamo competindo". Since this text contains the phrase "tamo competindo", it is a valid text. To become the version given in the input, ChatGPT could have made mistakes in the second and last letters, making $$$2$$$ of the $$$3$$$ possible mistakes. Thus, the text became "tepo assim tamo competindu". When delivered without spaces, it became "tepoassimtamocompetindu", just like in the input.

Explanation of example $$$2$$$: It is possible to show that it is impossible for this to be the desired text. Note that if $$$K$$$ were greater than or equal to $$$2$$$, the answer would be SIM.

C. Hacking the Matrix
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Cláudia is an outstanding researcher and is always looking for new challenges. Thus, she decides to attack the root of all evil in society: the Matrix.

The Matrix can be seen as an $$$N \times N$$$ binary grid, that is, a table with $$$N$$$ rows and $$$N$$$ columns consisting only of $$$0$$$s and $$$1$$$s.

With all her knowledge, Cláudia can perform two operations on the Matrix:

  1. Choose two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le N$$$ and $$$i \ne j$$$) and swap column $$$i$$$ with column $$$j$$$ of the grid, that is, for all $$$1 \le k \le N$$$, swap the positions $$$(k, i)$$$ and $$$(k, j)$$$ of the grid;
  2. Choose two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le N$$$ and $$$i \ne j$$$) and swap row $$$i$$$ with row $$$j$$$ of the grid, that is, for all $$$1 \le k \le N$$$, swap the positions $$$(i, k)$$$ and $$$(j, k)$$$ of the grid;

Thus, to demonstrate her dominance over the Matrix, Cláudia decides to form a C (for Cláudia) in the cells of the Matrix made up of $$$1$$$s. We say that a C of size $$$x$$$ made up of $$$1$$$s exists in the grid if, for a pair of integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le N$$$), the positions $$$(a + i, b)$$$, $$$(a, b + i)$$$, and $$$(a + x, b + i)$$$ of the grid contain $$$1$$$s for all $$$0 \le i \le x - 1$$$.

Help Cláudia by telling, for a given configuration of the Matrix, what is the largest C she can form using the operations at her disposal.

Due to the time limit of the problem, it is important to submit Python solutions using the PyPy3 compiler.

Input

The first line of the input contains an integer $$$N$$$ ($$$1 \le N \le 500$$$).

There will be $$$N$$$ following lines, where the $$$i$$$-th ($$$1 \le i \le N$$$) contains $$$N$$$ integers, where the $$$j$$$-th ($$$1 \le j \le N$$$) is the value $$$a_{i,j}$$$ ($$$0 \le a_{i,j} \le 1$$$) at position $$$(i, j)$$$ of the Matrix grid.

Output

Print a single integer — the side length of the largest C made up of $$$1$$$s that can be formed by performing any number of operations.

Examples
Input
4
0111
1001
0111
0010
Output
3
Input
5
01101
11001
01111
11101
00010
Output
3
Input
3
000
100
000
Output
1
Note

Explanation of the first example: by swapping the second and fourth columns, we get the following configuration of the Matrix:

0111

0100

0111

0010

The underlined part shows the C of size $$$3$$$ that is formed in the grid after this operation. It can be shown that it is not possible to form a larger C in this case.

D. MA141
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A professor of analytic geometry (MA141) is worried because he can only think of homothety problems to put on his second exam (P2). Therefore, he threatens a turtle from IMECC to get an easy problem.

The turtle, afraid of losing its head by being swallowed, suggests the following problem: "Given four points in the Cartesian plane $$$A, B, C, D$$$. The task is to determine whether these four points form a square with sides $$$AB$$$, $$$BC$$$, $$$CD$$$, and $$$DA$$$."

The professor gladly accepted the turtle's suggestion, and everyone lived happily ever after.

Input

The input consists of four lines, each containing two integers separated by a space $$$x$$$ and $$$y\;(-10^4 \leq x, y \leq 10^4)$$$, representing the coordinates of points $$$A, B, C$$$, and $$$D$$$. It is guaranteed that there are no coincident points among $$$A$$$, $$$B$$$, $$$C$$$, and $$$D$$$.

Output

Print "SIM" (portuguese for YES) if the four points form a square with sides $$$AB$$$, $$$BC$$$, $$$CD$$$, and $$$DA$$$, and "NAO" (portuguese for NO) otherwise.

Examples
Input
0 0
0 1
1 1
1 0
Output
SIM
Input
1 0
1 1
0 1
0 0
Output
SIM
Input
0 0
0 1
1 2
1 1
Output
NAO
Input
1 0
2 1
1 2
0 1
Output
SIM
Input
1 0
1 2
2 1
0 1
Output
NAO
Note

Note that the sides of the square do not need to be parallel to the axes, as shown in the fourth example.

Hint: Floating point operations may cause precision errors. Try to do everything with integers.

E. Esteche vs Yvens
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yvens and Esteche play the following game with a pile of $$$n$$$ stones.

They take turns, starting with Yvens, and on each turn, the current player must make one of two moves:

  • Remove one stone from the pile.
  • Remove two stones from the pile.

The player who removes the last stone loses the game.

Given the initial number of stones $$$n$$$, determine who has a winning strategy, assuming both play perfectly.

Input

The input consists of a single line containing an integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$), the initial number of stones in the pile.

Output

Print Yvens if Yvens has a winning strategy, or Esteche otherwise.

Examples
Input
1
Output
Esteche
Input
2
Output
Yvens

F. F128
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Passinho is having an existential crisis. After yet another tough F128 class at Unicamp, he wonders, indignantly, why computer science students need to study physics. "All I wanted was to dance and code... and now I'm stuck with this problem!" he laments.

This time, Passinho needs to understand the motion of a particle confined in a straight, closed corridor.

Consider a particle moving in a straight corridor of total length $$$d$$$ meters, with perfectly rigid walls at both ends. We define the position $$$x$$$ of the particle as the distance in meters from the leftmost wall of the corridor. The particle starts from an initial point at a distance $$$k$$$ meters from this wall, with an initial velocity of $$$v$$$ meters per second (positive, i.e., directed to the right), and moves for a total time of $$$t$$$ seconds.

Whenever the particle collides with one of the ends of the corridor (at positions $$$x = 0$$$ and $$$x = d$$$), it reverses its direction of motion and loses kinetic energy. This causes its velocity to be multiplied by a loss factor $$$\lambda$$$, where $$$0 \lt \lambda \lt 1$$$. That is, after the first collision, its velocity becomes $$$v \cdot \lambda$$$; after the second, $$$v \cdot \lambda^2$$$; and so on.

Since Passinho only wants to code, help him by writing a program that calculates the exact position of the particle after $$$t$$$ seconds. Do this before he decides to drop the course for good!

Input

The first line of input contains four integers $$$d$$$, $$$t$$$, $$$k$$$, and $$$v$$$, representing, respectively, the length of the corridor, the total time of the experiment, the initial position of the particle, and its initial velocity.

  • $$$1 \leq d \leq 10^4$$$
  • $$$0 \leq t \leq 10^4$$$
  • $$$0 \leq k \lt d$$$
  • $$$0 \leq v \leq 10^4$$$

The second line contains a single real number $$$\lambda$$$ ($$$0 \lt \lambda \lt 1$$$), with exactly 4 decimal places, representing the velocity loss factor at each collision.

Output

Print a single real number $$$X$$$, representing the final position of the particle after $$$t$$$ seconds of movement.

Your answer will be considered correct if the absolute or relative error does not exceed $$$10^{-6}$$$.

More formally, your answer $$$a$$$ will be accepted if and only if $$$\frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}$$$, where $$$b$$$ is the jury's correct answer.

Examples
Input
8 4 2 1
0.0010
Output
6.000000
Input
8 10 1 1
0.5
Output
6.500000
Input
10 40 5 3
0.3
Output
7.350000
Note

Hint: To avoid numerical precision issues, you can configure your program's output to print more decimal places:

  • In C++: use cout « fixed « setprecision(10);
  • In C: use printf("%.10lf", x);
  • In Python: use print(f"{x:.10f}")

G. GPT in Fury
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have discovered that the scroll in your hands contains the legendary interview of Versteppen with Pó de Pá, with the help of ChatGPT. However, the data from your interaction with the AI has gone to OpenAI's servers, and they do not want you to acquire the burst of knowledge from the interview. Therefore, the next time you request the transcription of the scroll, ChatGPT will choose some words from the text and encrypt them, replacing all the letters of the chosen words with random letters.

For example, if a part of the text says "tipo assim tamo competindo", ChatGPT might say that the transcription is "tipo lkopn zyre competindo", encrypting the second and third words and replacing their letters with random characters.

When you request a new transcription (since you forgot to save the previous one), you notice that something is strange, but you are not sure which words were faithfully transcribed and which had their characters replaced. Your task is, given the transcription, to identify which words were encrypted by ChatGPT. Since nobody is perfect, your efforts will be considered acceptable if you can identify at least 70% of the words.

Note: Pay attention to the input and output format of the problem, as well as the notes at the end of the statement.

Input

The input consists of a single line with 7502 words, containing the interview in question, with potentially encrypted words.

To make reading easier, the original text was transcribed to only contain characters from a to z, normalizing the text so that it does not contain uppercase letters, accents, or numbers. For example, if a part of the original text was "Mas você já tá 300 por hora meu Deus do Céu" and none of the words in this part were encrypted by ChatGPT, this part would appear as "mas voce ja ta trezentos por hora meu deus do ceu".

If a word was encrypted by ChatGPT, it is guaranteed that all its characters will be generated randomly following a uniform distribution, that is, every character has the same chance of appearing. If a word was not encrypted, all its characters will appear as in the original transcription.

There will be $$$10$$$ test cases. In all of them, the original text is the same, and the only change will be the words that ChatGPT chooses to encrypt and the seed of the random generator used to generate the random characters.

Output

Print a single line with 7502 numbers separated by spaces. If you think the $$$i$$$-th word was encrypted by ChatGPT, the $$$i$$$-th number should be $$$1$$$. Otherwise, it should be $$$0$$$. If your solution correctly identifies whether the word was encrypted or not at least $$$70\%$$$ of the time, it will be accepted.

For technical reasons, you must flush the standard output after printing your solution.

In python, this can be done by importing the sys library and using the command sys.stdout.flush().

In C++, this can be done via cout « flush;

In C, this can be done via fflush(stdout);

Note

A snippet of the interview containing $$$403$$$ words will be provided at this link: https://pastebin.com/SFZnYeW8. Note that the interview is entirely in portuguese.

You can use this snippet to test your code before submitting, as well as to get an idea of the nature of the text.

H. La Vaca Saturno Saturnino
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

La Vaca Saturno Saturnino, the owner of Saturnino's Restaurant (RS), is tired of seeing students cutting in line at her restaurant. Because of this, she has decided to cancel the academic registration (RA) of all students who cut in line at tonight's dinner.

Through the RS cameras, she has records of the students in the queue at different moments, in order. These records are in increasing order of time.

She asks you to, given these records, print for each student whether they cut in line or not.

It is guaranteed that once a student enters the queue, whether at the end or not, they do not change their position relative to the other students already in the queue. Therefore, it is only possible for a student to cut in line when entering the queue, by joining before the end of the queue. It is also guaranteed that no student enters the queue more than once, and that no student leaves the queue before all those in front of them have left. It is possible that a student never enters the queue.

Input

The first line of input contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 10^5$$$) — the number of queue records and the number of students.

Then follow $$$2N$$$ lines, where each pair of lines describes a queue record.

The first line of the $$$i$$$-th pair contains an integer $$$K_i$$$ ($$$1 \leq K_i \leq 10^5$$$), the number of people in the queue in this record.

The second line of the $$$i$$$-th pair contains $$$K_i$$$ integers $$$A_{ij}$$$ ($$$1 \leq A_{ij} \leq M$$$), representing the students in the queue in this record, in order from the first to the last in the queue.

It is guaranteed that the sum of all $$$K_i$$$ does not exceed $$$10^5$$$.

Output

Print a line with $$$M$$$ integers separated by spaces, where the $$$i$$$-th integer is 1 if the $$$i$$$-th student cut in line, and 0 otherwise.

Examples
Input
2 5
3
1 3 5
5
1 2 3 4 5
Output
0 1 0 1 0
Input
3 10
3
1 3 5
4
3 5 7 9
4
7 8 9 10
Output
0 0 0 0 0 0 0 1 0 0
Input
2 8
3
5 4 3
3
8 2 6
Output
0 0 0 0 0 0 0 0

I. Aura Farming
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Beraldo is studying hard for the ICPC, the International Collegiate Programming Contest, and as a good competitor, he knows that the dominance of his aura compared to that of his opponents is the only factor that determines his final performance in the competition. Due to his true stoic sigma mindset, he is not concerned with the aura values of his opponents at the moment. His focus is on raising his own aura as much as possible before the day of the competition.

His only way to increase his aura is by solving programming problems listed by the ICPC. There are $$$N$$$ problems available for him to practice. To solve the $$$i$$$-th problem, he needs to have at least $$$A_i$$$ aura points. If he manages to solve it, his aura increases by $$$B_i$$$.

Beraldo starts with $$$K$$$ aura points and can attempt the problems in any order, each at most once. He needs your help to calculate the maximum aura he can reach.

Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$0 \le K \le 10^5$$$) — the number of available problems and Beraldo's initial aura.

Each of the next $$$N$$$ lines contains two integers $$$A_i$$$ and $$$B_i$$$ ($$$0 \le A_i \le 10^5$$$, $$$1 \le B_i \le 10^4$$$) — the minimum aura required to solve the problem and the amount of aura gained by solving it.

Output

Print a single integer: the maximum aura value that Beraldo can reach.

Examples
Input
3 5
2 1
4 2
10 100
Output
8
Input
5 5
6 10
2 3
10 100
20 1
25 1
Output
120
Input
2 7
7 2
10 1
Output
9

J. Tigrinho
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After much thought, Po decided to leave his position as Dragon Warrior to study Computer Science at Unicamp. However, since the trip from China to Campinas is not cheap, he started to invest in the Tigrinho Game.

Po plays a simplified version of the Tigrinho Game, developed by Tigress's family. In this version, the player pays 5 reais to Tigrinho, who reveals a $$$3 \times 3$$$ matrix consisting of integers from 1 to 9 and possibly some wildcards. For each of the 3 rows and the 2 diagonals of the matrix, if the row or diagonal contains all equal numbers, the player gets 1 real back. Since wildcards are not numbers, they can be ignored, so, for example, a row with 2 equal numbers and a wildcard also pays 1 real back to the player.

At first, it may seem that the game depends purely on luck, but Po discovered that if he plays with strategy, he can predict the number of wildcards that will appear in the matrix. But since Po also doesn't want to take risks, he wants to know, given the number of wildcards in the matrix, what possible matrix will give him the lowest profit.

Input

The input consists of a single integer $$$K$$$ ($$$0 \leq K \leq 9$$$) — the number of wildcards in the matrix.

Output

Print 3 lines, each with 3 characters and a line break, representing the matrix with $$$K$$$ wildcards that gives the lowest profit. Use the character * (asterisk) to represent a wildcard and the digits 1 to 9 to represent the numbers in the matrix.

If there is more than one matrix with $$$K$$$ wildcards that gives the lowest profit, print any one of them.

Do not print spaces between the elements of the matrix.

Example
Input
1
Output
*29
239
179
Note

The matrix shown in the example does not pay any money back to Po. Note that, although the third column has $$$3$$$ equal numbers, only rows and diagonals give money.

K. Rofofo's Test
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rofofo is a renowned professor who teaches at one of the largest universities in Brazil. In his most recent classes, Rofofo talked about computer cache, and for this, he invented a new processor model, the RodolfEx $$$2000$$$.

The RodolfEx $$$2000$$$ has $$$N$$$ cachelines, each with $$$M$$$ variables. A variable in the RodolfEx $$$2000$$$ has $$$8$$$ bits of memory, that is, it can store integers from $$$0$$$ to $$$255$$$. Therefore, when adding variables, overflow may occur. Thus, we interpret the sum of two integers $$$x$$$ and $$$y$$$ in the RodolfEx $$$2000$$$ as $$$(x+y)\%256$$$, that is, the remainder of the division of $$$x + y$$$ by $$$256$$$.

Moreover, the processor has only $$$2$$$ relevant instructions for the test:

  1. Add $$$1$$$ to a specific variable in $$$A$$$ clock cycles.
  2. Add $$$1$$$ to all variables in a cacheline in $$$B$$$ clock cycles.

Note that when adding $$$1$$$ to a variable with value $$$255$$$, it overflows and returns to $$$0$$$.

In his test, Rofofo gives the initial value of each variable in the RodolfEx $$$2000$$$, as well as the factors $$$A$$$ and $$$B$$$, and wants to know the minimum number of clock cycles needed so that all variables become equal. Write a program that solves Rofofo's test and scores $$$10$$$!

Due to the time limit of the problem, it is important to submit using the PyPy3 compiler for Python solutions.

Input

The first line of input contains two integers, $$$A$$$, $$$B$$$ $$$\;(1 \leq A, B\leq 10)$$$, the number of clock cycles for each operation.

The second line of input contains two integers, $$$N$$$ and $$$M$$$ $$$\;(1 \leq N \leq 10; 1 \leq M \leq 10^4)$$$, the number of cachelines and variables per cacheline in the RodolfEx $$$2000$$$.

The next $$$N$$$ lines of input each contain $$$M$$$ integers $$$v_1, v_2, \dots, v_M \; (0 \leq v_i \leq 255)$$$, the initial values of the corresponding cacheline.

Hint: Note that in this problem $$$N$$$ is much smaller than $$$M$$$. Try to design an algorithm where the slowest part depends on $$$N$$$, not $$$M$$$!

Output

Print a single integer: the minimum number of clock cycles needed to complete Rofofo's test.

Examples
Input
1 2
2 3
1 2 1
1 1 1
Output
4
Input
1 2
2 3
1 2 1
254 253 255
Output
11
Input
8 3
2 2
109 114
164 109
Output
630
Note

Explanation of example 1: We can perform a type $$$1$$$ operation on the first and last variable of the first cacheline, and then perform a type $$$2$$$ operation on the second cacheline. In total, the number of clock cycles for this solution is $$$(1+1) \cdot 1 + 1 \cdot 2 = 4$$$

Explanation of example 1: We can perform a type $$$1$$$ operation on the first and last variable of the first cacheline, two type $$$1$$$ operations on the first variable of the second cacheline, and one type $$$1$$$ operation on the second variable of the second cacheline. After these operations, the $$$3$$$ variables of the first cacheline are all equal to $$$2$$$, while the $$$3$$$ variables of the second cacheline are all equal to $$$255$$$. By performing a type $$$2$$$ operation on the second cacheline, an overflow occurs and the $$$3$$$ variables of the second cacheline become $$$(255+1)\%256 = 0$$$. After that, just perform two more type $$$2$$$ operations on the second cacheline.

In total, there were $$$(1+1+2+1) \cdot 1 + 3 \cdot 2 = 11$$$ clock cycles.