• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• Hey good-hearted professor, come to my office please.
• Hello evil professor, what can I do for you?
• Look at the questions I’ve prepared for the final exam.
• Oh professor, it’s pretty difficult. No calculator can save such a big number.
• Yes, I know. I gave this question, so hens of the sky will cry for them.

Hearing this conversation, roosters of the sky became angry with the evil professor. They don’t want hens to be crying, so they tried to solve evil professor’s problem, and give the answer to students.

The problem is given two numbers $n$ and $m$. calculate $n \times {245}^m$ then print the least significant digit.

ورودی🔗

The first line contains single integer $t$ — the number of tests. $1 \leq t \leq 100$

Each test contains two numbers, $n$ and $m$ respectively. $0 \leq n, m \leq 10^9$

خروجی🔗

For each test, print one integer in one line — the answer to the problem.

مثال‌ها🔗

ورودی نمونه ۱🔗

3
1 1
2 1
2 2

خروجی نمونه ۱🔗

5
0
0

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• Dad, I don’t have any T-shirts!
• Don’t worry son! I’m going to take a contest soon. I will bring you one.

Reza loves to participate in contests all over the country. He registers into contests for the living and not only makes his wife happy with the prize but also brings the T-shirts to his son. Obviously, Reza only participates in the contests which their transportation costs are not higher than their prize. In such cases, he will travel from Tehran to the city, takes the contest and travels back to Tehran to reward the prize and the T-shirt to his wife and son immediately. Reza’s wife wants to go shopping for the New Year soon, but she is not sure if Reza can afford the money. Help her to calculate the total money that Reza is able to earn from the contests. (Reza is an expert in ACM contests and he will win the prize in any contest he participates in)

ورودی🔗

In the first line there will be an integer $T$ indicating the number of test cases. $1 \leq T \leq 100$

Each test case begins with two integer $N$ and $M$ the number of cities hosting the contests and the number of roads between them respectively. $1 \leq N \leq 10^3$ $1 \leq M \leq \frac{N(N - 1)}{2}$

In the following $N$ lines, comes an integer $P_i$ indicating the prize of city $i$. $1 \leq P_i \leq 10^9$

The next following $M$ lines contain three integers $u, v$ and $w$ which means the cities $u$ and $v$ are connected to each other and the transportation cost between them is $w$.

$1 \leq w \leq 100$

Assume that Reza begins from Tehran (city $0$) and comes back to Tehran after each contest.

خروجی🔗

For each test case print the maximum money that Reza can earn from participating in the contest in a line

مثال‌ها🔗

ورودی نمونه ۱🔗

2

3 4
7 10 25
0 3 11
0 2 5
1 3 8
1 2 16

3 3
10 20 30
0 1 4
1 2 6
2 3 10

خروجی نمونه ۱🔗

35
30

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

Mammad owns a small woodcraft manufactory in a very humid city near the coastline. He needs to buy raw wood cubes to build customer orders. Since the transportation is a difficult procedure, he prefers to buy a certain amount of wood once a year and store them in the inventory. But as the raw wood gets cropped during the time in humid climates, he has to use some special spray to protect them which is pretty expensive. So he wants to stack them in the inventory in such a way that the total spray he needs to use becomes minimal. He wants only make one stack and for ease of finding different sizes, he does not want to put more than one piece directly on top of the other. Having the size of the cubes, calculate the minimum outer surface of the stack which he should the spray on. (The surface hidden between the woods or between the floor and the woods does not need to be sprayed)

ورودی🔗

In the first line there will be an integer $T$ indicating the number of test cases.

$1 \leq T \leq 100$

Each test case begins with an integer $N$, indicating the number of cubes following $N$ lines containing an integer $d_i$ indicating the dimensions of each cube.

$1 \leq N \leq 10^7$ $0 \leq d_i \leq 10^9$

خروجی🔗

For each test case, print an integer indicating the minimum exposed surface when the cubes are stacked in an efficient way.

مثال‌ها🔗

ورودی نمونه ۱🔗

2

3
5
3
5

7
10
3
1
7
3
6
9

خروجی نمونه ۱🔗

261
1240

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• I’m sorry madam, but your son is abnormal.
• (She cries out loud) but why?
• He has a strange habit of storing a rooted tree, in a simple array.
• OMG!!! How did this happen to us? What should we do now?
• Well, you should find him a problem-solver. Maybe you can find one in newbies contest!!

mrm_196 always rewrites the rooted trees in a simple array, but the array holds four conditions:

1. If the tree has $N$ vertices, the array has length $2N$.
2. Each vertex has a number (from $1$ to $N$) which is written twice (but they may not be necessarily beside each other).
3. Between the numbers of each vertex, the numbers in its subtree are written.
4. Vertex 1 is always the root of the tree.

For example, he may store the following tree in one of these six ways:

Your task is pretty simple, find what he always wanted, THE DEGREE OF THE TREE!!!! Degree of a tree is the maximum degree of all its vertices.

ورودی🔗

The first line of the input contains an integer $T$ — the number tests to answer. $1 \leq T \leq 20$

The first line of each test contains an integer $N$ — the number of vertices in the tree. $1 \leq N \leq 100\, 000$

The second line of each test contains $2N$ integers $a_1, a_2, \dots, a_{2N}$ — the elements of his array. $1 \leq a_i \leq N$

It’s guaranteed that the given array always forms at least one valid tree.

خروجی🔗

For each test, print a single integer in one line — the degree of the tree.

مثال‌ها🔗

ورودی نمونه ۱🔗

2
1
1 1
5
1 3 2 2 4 4 5 5 3 1

خروجی نمونه ۱🔗

0
4

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

In the dormitory, people will take turns to buy dinner or stuff for dinner. Each night one person goes out to buy and writes details of it on the “Detail Paper”. Details include name of the buyer, amount of money he/she paid and name of the people ate that night. Image below shows a Detail Paper.

At the end of each month everybody have to pay their debts, But everyone get’s so creepy when it comes to money. So they all decided to hire a team from ACM(Abdominal Control Market) of the SBU University.

you are one of the teams participating in ACM Newbies Contest so you have to help them. They only have two rules:

1. Only people that ate, should pay (name of them is written in Detail Paper)
2. The money paid by everyone on each night must be equal.

ورودی🔗

First line of input contains an integer $T$ indicating number of test cases. Each test case contains an integer $L$, number of lines to follow. $L \leq 50$

Each line of test case is as following: A string $S$ name of the buyer followed by an integer $C$ cost of things bought followed by an integer $N$, indicating how many people ate that specific night, Following N space separated strings indicating name of the people that ate that night. It’s guaranteed that C is divisible by N and Each line contains no more than 250 characters.

$0 \lt C \lt 100\, 000$ $N \leq 10$

Each Name contains “A-Z” and “a-z” characters. Names are NOT case-sensitive and length of each name is at most 20 characters.

خروجی🔗

For each test case output “Case #X:” (quotations for clarify) which X is the number of test case.

Then print “Debtors:” (quotations for clarify) and in each line print name of debtors and their liability as following sorted by debtors name in alphabetical order: “S owes D Tomans.” (quotations for clarify)

First alphabetical character of S must be uppercase and rest of alphabetical characters must be lowercase, D is an integer number (money person S must pay).

Then print “Creditors:” (quotations for clarify) and in each line print name of creditors and their credit as following sorted by creditors name in alphabetical order: “S paid D Tomans.” (quotations for clarify)

First alphabetical character of S must be uppercase and rest of alphabetical characters must be lowercase, D is an integer number (money person S must get).

People who don’t have to pay or receive any money are neither Debtor nor Creditor, so their name should not appear in output.

مثال‌ها🔗

ورودی نمونه ۱🔗

2
10
Michel 9200 4 Aden John David Michel
Ashley 8700 3 Ashley Aden John
Ashley 6000 3 Michel John Ashley
Aden 15000 3 Ashley John Aden
Michel 1800 4 Aden David Michel Ashley
David 2200 4 Aden John David Ashley
Aden 29400 3 Aden David Ashley
Aden 8500 4 Aden David Ashley John
John 21000 3 Aden Michel John
Aden 3100 2 Aden Michel
1
Ehsan 4500 1 ehsan

خروجی نمونه ۱🔗

Case #1:
Debtors:
Ashley owes 8125 Tomans.
David owes 13025 Tomans.
John owes 875 Tomans.
Michel owes 2300 Tomans.
Creditors:
Aden paid 24325 Tomans.
Case #2:
Debtors:
Creditors:

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• Saman: yo! let me send you this awesome track!
• Erfan: thanks man, I’m at work now. I’ll listen to it when I get home.

Erfan is going to a trip for Norooz holidays and wants to enjoy some music of a genre named “Khaltoor” on his way. He wants to ask his friend Saman to make a CD for him containing this type of music. The CD has maximum capacity of $M$ minutes. Saman has $N$ music tracks and needs your help to write maximum number of tracks into the CD.

ورودی🔗

In the first line there will be an integer $T$ indicating the number of test cases. $1 \leq T \leq 100$

Each test case begins with two integers $N$ and $M$ indicating the number of tracks and the capacity of the CD. $1 \leq N \leq 10^5$ $1 \leq M \leq 10^9$

The following $N$ lines containing an integer $t_i$ indicating the length of each track. $1 \leq t_i \leq 10^9$

خروجی🔗

For each test case, print an integer indicating the maximum number of tracks that Saman can write on the CD.

مثال‌ها🔗

ورودی نمونه ۱🔗

1

6 12
13 5 10 3 4 11

خروجی نمونه ۱🔗

3

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

There is company producing random sized triangular shaped biscuits. Since the technique of making such biscuits is very complicated, the minimum size of produced biscuits is out of control. The owners know that it’s annoying for the customers to find lots of tiny pieces in their biscuit packs, so, they want to add a filtering module in their production line. In the filtering module, there is a rolling belt which all the biscuits are put there and scanned by a camera before being redirected to the filtering grid. In this stage, the camera detects the number of triangles and dimension of each. The filtering grid has an adjustment system which can change the size of the squares of the grid filter.

For more accuracy in filtering, the grid has a harsh vibrating motion causing the biscuits being popped up and rotate in all possible directions. This will happen long enough and you can be sure the triangles will fall on the grid in almost all possible orientations.

The owners want you to write a program in order to adjust the grid size in such a way that for a threshold percentage of $P$ and acceptable error of $E$, only $P±E$ percent of the biscuit pieces remain on the grid to be packed and the others fall through the grid holes to be recycled.

ورودی🔗

First line of input begins what in integer $T$ indicating number of test cases to follow.

$1 \leq T \leq 20$

Each test case begins with three space separated integers $N, P$ and $E$ representing number of biscuits, threshold, and acceptable error respectively.

$1 \leq N \leq 10^5$ $0 \lt P, E \lt 100, \quad \quad 100 \gt P ± E \gt 0$

Following $N$ lines each contain $3$ space separated real numbers $a, b$ and $c$ indicating dimensions of each triangle.

$0 \lt a, b, c \lt 10^9$.

خروجی🔗

For each test case, print out the minimum size of square edges to be set in such a way that $P±E$ percent of the biscuits remain on the filter rounded in $2$ digits after floating point. Note that if a range of size satisfies the condition, print the minimum and assume that a biscuit having an exact match dimensions with the squares will fall. If the condition can’t be satisfied print IMPOSSIBLE.

مثال‌ها🔗

ورودی نمونه ۱🔗

2
5 70 10
1.5 2 2.5
2 2 2
7.5 8 10
5 6 7
3 3 3
3 50 20
5.5 5.5 5.5
5.5 5.5 5.5
5.5 5.5 5.5

خروجی نمونه ۱🔗

1.22
IMPOSSIBLE

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

Roosters of the sky (as discussed previously) moved to help the students. But nothing went out as expected. Since roosters can’t fly, they had to move on land. They wanted to come to SBU, but most of the highways were on “Tarhe zowj o fard”. So they had to come from Sadr highway to avoid cameras. But unfortunately, they got stuck in traffic and got there late. The evil professor was successful. Most of the students failed.

Roosters didn’t want to come back home ashamed. They planned to attack university in the middle of the night! This way, they could change the grades, so that most of the students could pass the exam and hens of the sky were relieved.

Now, it’s midnight and they are in the SBU and logged into evil professor’s “Golestan” account. If they add more than K units to the grades in total, evil professor will understand and changes the grades. Each student will become happy hi units if he/she was failed and then passes the course. Help the roosters change the grades, so that increased happiness between students is maximum, and evil professor doesn’t understand. Student with at least 10 grades is passed.

ورودی🔗

First line of the input contains an integer $t$ — number of tests to answer.

$1 \leq t \leq 60$

First line of each test contains two integer $N, K$ — the number of students.

$1 \leq N \leq 100$$0 \leq K \leq 10^9$

Second line of each test contains $N$ integers $a_1, a_2, \dots, a_N$ — the grades of students.

$0 \leq a_i \leq 20$

Second line of each test contains $N$ integers $h_1, h_2, \dots, h_N$ — increase of happiness in each failed student if he/she suddenly passes.

$0 \leq h_i \leq 100$

خروجی🔗

For each test, print a single integer in one line — Maximum amount of increase in the happiness.

مثال‌ها🔗

ورودی نمونه ۱🔗

5
4 20
0 0 0 10
1 2 3 4
4 15
0 0 0 0
4 3 2 1
4 9
0 0 0 0
100 100 100 100
3 9
1 6 5
8 6 3
2 4
8 7
2 4

خروجی نمونه ۱🔗

5
4
0
9
4

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت

Get your beAr, there is nothing to fear, Colonel’s heavy trace, is again here.

There is an ancient saying that problem I is always one of the hardest problems in programming contests. There is also another not-very-ancient saying that Colonel is still pissed about the fact that the solution to problem F in Tehran Regionals required big integers. Colonel believes the above ancient saying, but what are the probabilities that you’re writing the last problem of the problem set, and there is only one problem slot left, and you contact the contest coordinator to see if they can place your problem on slot I, and they respond with “I is the only remaining slot”?

Lightning strike. Lightning strike indeed. Would’ve been a Full-house if this was a probability problem, but nah we’re not that lucky.

ورودی🔗

In the first line you’ll have $n$ and $m$ .

$1 \leq n \leq 1000\,000, \quad \quad 1 \leq m \leq 1000\,000$ In the next line there will be $n$ numbers forming an array of size $n$.

In each of the next $m$ lines there will a single query of one of the following types: $1\,\, a\,\, b\,\, k$

Which updates all the elements in range $a$ to $b$ inclusive, raises each of them individually to the power $k$.

$42\,\,a\,\,b$

Which asks for the product of all the array elements between $a$ and $b$ inclusive.

خروجی🔗

For each query of type $42$, output a number, the answer to the product of the numbers in the specified range. Since the answer can be very large, print answer modulo $10^9 + 7$.

مثال‌ها🔗

ورودی نمونه ۱🔗

5 5
1 2 3 4 1000
1 2 3 2
1 1 4 4
42 1 1
42 1 2
42 2 5

خروجی نمونه ۱🔗

1
256
981692997

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

Ant and Ant-eater have got two arrays, each consisting of $1$ to $N$’s permutation. They want to play a game, the goal of the game is making the arrays similar. In each turn one can remove a single integer from his array. If both play optimally, find out the minimum number of turns it takes to finish the game.

ورودی🔗

The first line of input shows the number of test cases $T$. Each test case will contain 3 lines. The first line contains a single integer $N$ indicating the length of permutations.

$1 \leq N \leq 100 \, 000$

Second and third line each will contain $N$ space separated integers indicating the numbers in permutations A and B respectively.

خروجی🔗

For each test case, print a single integer in a line, the minimal number of turns to finish the game.

مثال‌ها🔗

ورودی نمونه ۱🔗

3
4
1 2 3 4
4 3 2 1
4
1 2 3 4
1 2 4 3
5
4 2 3 5 1
4 5 1 3 2

خروجی نمونه ۱🔗

6
2
4

First test case:

• Ant’s: $\{1, 2, 3, 4\} \to \{1, 3, 4\} \to \{1, 4\} \to \{4\}$
• Ant-eater’s: $\{4, 3, 2, 1\} \to \{4, 3, 1\} \to \{4, 1\} \to \{4\}$