+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
Several balloons are arranged sequentially, each showing one of the letters from `a` to `z`. Amin wants to give a needle to Niloufar and ask her to select **one** or more balloons so that after popping them and joining the remaining balloons (without changing their order), he can reach a state where exactly $4$ balloons remain in sequence, with the letters `acpc` written on them in order.
You need to write a program that, given the initial arrangement of balloons, determines whether this is possible or not.
# ورودی
The first line of input contains a positive integer $t$, representing the number of test cases.
$$1 \leq t \leq 10^4$$
In each test case, there is a single string $s$, consisting of lowercase English letters, showing the sequence of letters written on the balloons.
$$1 \leq |s| \leq 100$$
# خروجی
For each test case, print `YES` if it is possible to form the word `acpc`; otherwise, print `NO`.
# مثال‌ها
## ورودی نمونه ۱
```
2
amirkabirprogrammingcontest
amirkabircollegiateprogramcontest
````
## خروجی نمونه ۱
```
NO
YES
````
A - Balloons
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
We want to engrave the names of several distinguished professors on the wall of Amirkabir University. The name of each professor will be written on a tile $1 \times 1$. We intend to select a rectangle of size $a \times b$ on the wall with $a.b$ tiles and inscribe the professors' names on them.
The university will approve this request if the following conditions are met:
1. First, the names of $n$ faculty members of the Computer Engineering Department must be included in this tribute.
2. Second, the perimeter of this rectangle, that is, $2a + 2b$, must be minimized.
3. Third, the values of $a$ and $b$ must be prime numbers.
Given a natural number $n$, you are asked to calculate the minimum possible perimeter for this tribute.
# ورودی
The first line of input contains a positive integer $t$, representing the number of test cases.
$$1 \leq t \leq 100$$
In the next $t$ lines, each line contains an integer $n$, representing the number of professors for that test case.
$$1 \leq n \leq 10^9$$
# خروجی
For each of the $t$ test cases, print a natural number representing the minimum required perimeter.
# مثال‌ها
## ورودی نمونه ۱
```
3
1
17
10
````
## خروجی نمونه ۱
```
8
20
14
````
B - Memorial
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
Amin and Niloufar are playing Rock-Paper-Scissors together. They are not kids, so instead of playing with their hands, they use actual rocks, papers, and scissors.
Amin has $R_a$ rocks, $P_a$ papers, and $S_a$ scissors. Similarly, Niloufar has $R_n$ rocks, $P_n$ papers, and $S_n$ scissors.
In each round of the game, both players use one of their rocks, papers, or scissors (if a player has no items left, they'll lose that round). According to the traditional rules of this game, paper beats rock, scissors beat paper, and rock beats scissors. If both items are the same, the round is a draw.
Each win earns $3$ points, draw earns $1$ point, and lose earns no points. Your task is to write a program to calculate the maximum score that Amin can achieve among all possible outcomes.
# ورودی
The first line of input contains an integer $t$, representing the number of test cases.
$$1 \leq t \leq 10^5$$
In the first line of each test case, three integers $R_a$, $P_a$, and $S_a$ are given. In the second line of each test case, three integers $R_n$, $P_n$, and $S_n$ are given.
$$0 \leq R_a, P_a, S_a, R_n, P_n, S_n \leq 10^9$$
# خروجی
For each test case, print a single integer representing the maximum score Amin can achieve.
# مثال‌ها
## ورودی نمونه ۱
```
3
1 1 1
1 1 1
3 0 2
0 3 1
8 0 0
8 0 0
````
## خروجی نمونه ۱
```
9
12
8
````
C - Rock-Paper-Scissors
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
The symbol $\oplus$ represents the bitwise XOR operator for integers. For example:
$$9 \oplus 3 = 1001_2 \oplus 11_2 = 1010_2 = 10$$
The \textit{value} of an array such as $a_1, a_2, \dots, a_n$ is defined as:
$$a_1 \oplus a_2 \oplus \dots \oplus a_n$$
You are given two arrays of numbers, $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$.
For each $i$ from $1$ to $n$, you can swap the values of $a_i$ and $b_i$. Write a program to perform these swaps in such a way that the sum of the values of both arrays is maximized.
# ورودی
The first line of input contains a positive integer $n$, representing the length of the arrays.
$$1 \leq n \leq 10^5$$
The second and third lines each contain $n$ positive integers separated by space, with the second line representing the elements of array $a$ and the third line representing the elements of array $b$.
$$0 \leq a_i, b_i \leq 10^{18}$$
# خروجی
Print a single integer, the maximum possible value for the sum of the values of both arrays.
# مثال‌ها
## ورودی نمونه ۱
```
3
1 2 3
3 1 2
````
## خروجی نمونه ۱
```
6
````
D - Array's Value
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
Amin has given an array of $n$ distinct numbers, $a_1, a_2, \dots, a_n$ to Niloufar. She came and calculated the value $\max(a_i, a_j) \times |a_i - a_j|$ for each two-element subset $\{ a_i, a_j \}$ and wrote it on the board. Now Amin wants to calculate the sum of the numbers written on the board. Help him perform this calculation.
# ورودی
The first line of input contains a positive integer $t$, representing the number of test cases.
$$1 \leq t \leq 100$$
In the first line of each test case, there is an integer $n$ indicating the number of elements in the array.
$$2 \leq n \leq 5 \times 10^4$$
The second line of each test case contains $n$ positive integers, representing the elements of the array.
$$1 \leq a_i \leq 5 \times 10^4$$
**Note that the input array is not necessarily sorted.**
# خروجی
For each test case, print a single integer representing the sum of the numbers written on the board.
# مثال‌ها
## ورودی نمونه ۱
```
3
2
1403 9
4
2 1 4 3
7
10 20 3 15 1000 60 16
````
## خروجی نمونه ۱
```
1955782
35
5891525
````
E - Easy Computations
+ محدودیت زمان: ۳ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
Amin and Niloufar need to travel from point $(0, 0)$ to $(3n, 3n)$. In normal terrain, they can travel $1$ km per day. Their path is interrupted by a wide swamp that runs parallel to the $x$-axis. The swamp is $n$ kilometers wide, with boundaries at $y = n$ and $y = 2n$. The map of the area is shown in the diagram below:
The travel speed of Amin and Niloufar through the swamp is $\frac{1}{k}$ kilometers per day. Find the shortest possible time to travel from point $(0, 0)$ to $(3n, 3n)$ and print the result in days.
If the shortest travel time is $d$ days $h$ hours $m$ minutes, and so on, print only the value $d$.
# ورودی
The first line of input contains a positive integer $t$, representing the number of test cases.
$$1 \leq t \leq 10^5$$
For each test case, the only line contains two integers $n$ and $k$.
$$1 \leq n, k \leq 10^7$$
# خروجی
For each test case, print a single integer representing the minimum number of days required to reach the destination.
# مثال‌ها
## ورودی نمونه ۱
```
2
1 1
100 2
````
## خروجی نمونه ۱
```
4
543
````
F - Shortest Path
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
Niloufar wants to give Amin a gift after counting his birth date in calendar from begining. Help Niloufar to solve this problem.
You are given two integers $m$ and $n$ and finds the $n$-th smallest natural number that contains the number $m$ as a subsequence.
We know that the number $m$ consists of distinct digits.
# ورودی
The first line of input contains a positive integer $t$, representing the number of test cases.
$$1 \leq t \leq 100$$
In the first line of each test case, two positive integer $m$ and $n$ is given in order.
$$1 \leq m \leq 5000$$
$$1 \leq n \leq 10^{12}$$
# خروجی
For each test case, print a single integer representing the $n$-th smallest number that contains $m$ as a subsequence.
# مثال‌ها
## ورودی نمونه ۱
```
3
21 14
1403 1
2189 100
````
## خروجی نمونه ۱
```
221
1403
201689
````
G - Birth Date
+ محدودیت زمان: ۵ ثانیه
+ محدودیت حافظه: ۵۱۲ مگابایت
----------
We have a country with $n$ cities. The cities in this country are connected by $n - 1$ two-way roads. We know that from each city, we can reach any other city by traversing some roads, meaning the structure of this country is a tree.
The cities are numbered from $1$ to $n$. We know the population of city $i$ is $w_i$. The \textit{difference} between two cities is defined as the XOR of the populations of the cities along the path between the two cities (including the start and end). The \textit{value} of the country is the sum of the differences between every pair of distinct cities.
Calculating the initial value of the country is not a hard task for the mayor. Therefore, we ask you to design a dynamic system. You will receive $q$ queries.
In each query, the population of city $v$ changes to $x$. We want you to write a program that calculates the initial value of the country and the value of the country after each change.
# ورودی
The first line of input contains an integer $n$, representing the number of cities in the country.
$$1 \leq n\leq 10^5$$
The second line contains $n$ integers $w_1, w_2, \dots, w_n$, representing the initial population of each city.
$$0 \leq w_i \leq 10^8$$
Each of the next $n - 1$ lines contain two integers $u$ and $v$, representing a road between cities $u$ and $v$ in the country.
$$1 \leq u, v\leq n$$
The following line contains an integer $q$, representing the number of queries.
$$1 \leq q \leq 10^5$$
The next $q$ lines each contain two integers $v$ and $x$, representing an operation that changes the population $w_v$ of city $v$ to $x$. It is guarantied that the roads form a tree.
$$0 \leq x \leq 10^8$$
$$1 \leq v\leq n$$
# خروجی
The output consists of $q + 1$ lines, where each line contains an integer representing the current value of the country.
# مثال‌ها
## ورودی نمونه ۱
```
5
10 11 8 3 17
1 2
1 3
2 4
2 5
3
4 16
1 5
5 5
````
## خروجی نمونه ۱
```
123
157
202
170
````
H - Country's Value
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
In hospitals, lines are often drawn on the floor in various directions to help guide visitors to different areas. One day, while Amin was waiting outside the operating room, he started thinking about this:
Suppose there are $n$ departments in a hospital connected by corridors, forming a layout that can be represented as an undirected, connected graph with $n$ vertices and $m$ edges.
Amin wants to color each edge in this graph with one of two colors, red or blue, so that for any two departments (vertices), one can follow a continuous path of edges of same color to travel between them.
This means that if someone wants to travel from department $v$ to department $u$, first we could guide them “follow red” or “follow blue”.
The question Amin faces is: can we color edges of the graph in such a way that any two vertices can be reached using a guide like "follow red/blue"?
# ورودی
The first line of input contains an integer $t$ representing the number of test cases.
$$1 \leq t \leq 10^5$$
For each test case, the first line contains two positive integers $n$ and $m$, representing the number of vertices and edges.
$$2 \leq n \leq 10^5$$
$$1 \leq m \leq 10^5$$
$$ \sum m \leq 10^6$$
In the next $m$ lines, each line contains two integers $u$ and $v$, indicating the existence of an edge $uv$ in the graph.
$$1 \leq u, v \leq n$$
It is guaranteed that the given graphs are simple and connected.
# خروجی
If there is such coloring print `YES`; otherwise print `NO`.
# مثال‌ها
## ورودی نمونه ۱
```
3
4 3
1 2
1 3
1 4
2 1
1 2
3 3
1 2
2 3
1 3
````
## خروجی نمونه ۱
```
NO
YES
NO
````
I - Hospital Lines
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
There are many caves near Tehran, and Amin, after finishing this competition, wants to pick one of them to visit and leave competitions behind. The entrance to this cave looks like the following:
The cave entrance is shaped as an $n$-sided polygon in two dimensions. The entrance consists of two walls, left and right, each forming a concave curve.
The tops of both walls meet at a single point, while the bottoms connect with an straight line.
Amin wants to place a sensor on each vertex of this polygon. Each sensor can detect surroundings unless a wall blocks its view.
The entrance of the cave, as shown in an image, consists of two **concave** walls and a flat floor at the entrance.
There are $n$ sensors installed along the cave entrance, numbered from $1$ to $n$, starting from the bottom left and going to the bottom right.
Two sensors $i$ and $j$ can "see" each other if every point along the line between them lies within the cave space or along the boundary of the walls.
Based on this, we can construct an $n \times n$ table, where we write `1` in row $i$, column $j$ if sensor $i$ can see sensor $j$, and `0` otherwise.
Now, the problem reverses this process. Given an $n \times n$ table of `0`s and `1`s, determine if it's possible to find an arrangement of sensors along the cave entrance that matches the visibility pattern shown in the table.
# ورودی
The first line of input contains a positive integer $t$, representing the number of tables.
$$1 \leq t \leq 10^5$$
For each test case, The first line contains an integer $n$, representing the number of sensors.
$$3 \leq n \leq 100$$
The next $n$ lines each contain a string of length $n$, consisting of `0`s and `1`s, representing the table values.
$$\sum n \leq 10^5$$
# خروجی
For each test case, print `YES` if such an arrangement of sensors is possible, and `NO` otherwise.
# مثال‌ها
## ورودی نمونه ۱
```
5
5
01011
10111
01010
11101
11010
4
0111
1011
1101
1110
3
000
000
000
4
0101
0101
1010
1010
3
111
101
110
````
## خروجی نمونه ۱
```
YES
NO
NO
NO
NO
````
J - Cave's Walls
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
Consider the following algorithm:
```
function gcd(a, b):
if b is 0:
return a
return gcd(b, a % b)
```
We want to create a test to evaluate the performance of this program. For each test, you need to provide two integers $a$ and $b$ such that $1 \le a, b \le n$ and this algorithm has the maximum number of `gcd` function calls.
# ورودی
The first line contains an integer $t$, representing the number of test cases.
$$1 \leq t \leq 10^5$$
In each test case, there is a single integer $n$.
$$1 \leq n \leq 10^{18}$$
# خروجی
For each test case, print the maximum number of function calls.
# مثال‌ها
## ورودی نمونه ۱
```
5
1
2
3
4
5
````
## خروجی نمونه ۱
```
2
3
4
4
5
````
K - Time Complexity
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
Amin hates his chemistry class. Niloufar, who has not finished her chemistry assignments yet, turns to Amin for help with balancing chemical reactions.
Balancing a reaction means adding coefficients in front of the reactants and products so that the number of each element on both sides of the reaction is equal.
Amin has no idea what chemistry is, but he knows that chemical element names start with an uppercase letter, followed by lowercase letters.
Help Amin to check whether the reaction is balanced or not. Note that the coefficients must be integers and should be in their simplest form.
# ورودی
The first line of input contains a positive integer $t$, representing the number of chemical reactions.
$$1 \leq t \leq 100$$
In the next $t$ lines, each line contains a chemical reaction.
$$1 \leq |s| \leq 100 $$
It is guaranteed that the coefficients are less than $100$.
# خروجی
For each test, if the reaction is balanced, print `YES`, otherwise print `NO`
# مثال‌ها
## ورودی نمونه ۱
```
6
3H_2 + N_2 => 2NH_3
6CO_2 + 6H_2O => C_6H_{12}O_6 + 6O_2
3Ca(OH)_2 + 2H_3PO_4 => Ca_3(PO_4)_2 + 6H_2O
4H_2 + N_2 => 2NH_3
3CO_2 + 3H_2O => C_6H_{12}O_6 + O_2
Ca(OH)_2 + 2H_3PO_4 => Ca_3(PO_4)_2 + 2H_2O
````
## خروجی نمونه ۱
```
YES
YES
YES
NO
NO
NO
````