+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- The ministry of health in Neverland has recently published a colorcoded chart to help people better understand the level of *Covid-19* risk in different cities, and take appropriate actions and precautions based on the risk level. ![توضیح تصویر](https://quera.org/qbox/download/lO9rlF9z8S/A.png) In this chart, each city is colored either red, yellow, or white, based on some indicators showing the coronavirus risk level at that city. After exploring several models, the ministry has reached the following criteria for classifying the cities. For a given city, if the average number of new cases per day over the past two weeks is at most $50$ per one million population, and the average number of new hospitalizations per day over the past two weeks is at most $10$ in every one million population, then the city is marked as white, meaning that the city is in a low-risk zone. On the other hand, if the average number of new hospitalizations per day in a city over the past two weeks is more than $30$ per one million population, then the city is categorized as high-risk and is color-coded red. All other cities are colored yellow. While the data for new cases and hospitalizations are publicly available, the ministry does not update its colorcoded chart very frequently. Hana, a curious student, likes to know the risk level of her city at any point of time, before the ministry publishes its updated chart. She can obtain the average number of new cases and new hospitalizations from the Internet, but she needs your help to convert this data to a color code that better demonstrates the risk level at her city. # ورودی The input consists of two lines. The first line contains an integer $p$ ($0 \leq p \leq1000$), showing the average number of new cases per day in every one million population in Hana’s city over the past two weeks. The second line contains an integer $q$ ($0 \leq q \leq 500$), showing the average number of new hospitalizations per day in every one million population over the past two weeks in that city. Note that $q \leq p$. # خروجی In the output, print the color-code of Hana’s city. It must be either White, Yellow, or Red. ## ورودی نمونه ۱ ``` 50 7 ```` ## خروجی نمونه ۱ ``` White ```` ## ورودی نمونه ۲ ``` 60 40 ```` ## خروجی نمونه ۲ ``` Red ```` ## ورودی نمونه ۳ ``` 15 12 ```` ## خروجی نمونه ۳ ``` Yellow ````

A - Covid-19

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

The ministry of health in Neverland has recently published a colorcoded chart to help people better understand the level of Covid-19 risk in different cities, and take appropriate actions and precautions based on the risk level.

توضیح تصویر

In this chart, each city is colored either red, yellow, or white, based on some indicators showing the coronavirus risk level at that city. After exploring several models, the ministry has reached the following criteria for classifying the cities. For a given city, if the average number of new cases per day over the past two weeks is at most $50$ per one million population, and the average number of new hospitalizations per day over the past two weeks is at most $10$ in every one million population, then the city is marked as white, meaning that the city is in a low-risk zone. On the other hand, if the average number of new hospitalizations per day in a city over the past two weeks is more than $30$ per one million population, then the city is categorized as high-risk and is color-coded red. All other cities are colored yellow.

While the data for new cases and hospitalizations are publicly available, the ministry does not update its colorcoded chart very frequently. Hana, a curious student, likes to know the risk level of her city at any point of time, before the ministry publishes its updated chart. She can obtain the average number of new cases and new hospitalizations from the Internet, but she needs your help to convert this data to a color code that better demonstrates the risk level at her city.

ورودی🔗

The input consists of two lines. The first line contains an integer $p$ ( $0 \leq p \leq1000$ ), showing the average number of new cases per day in every one million population in Hana’s city over the past two weeks. The second line contains an integer $q$ ( $0 \leq q \leq 500$ ), showing the average number of new hospitalizations per day in every one million population over the past two weeks in that city. Note that $q \leq p$ .

خروجی🔗

In the output, print the color-code of Hana’s city. It must be either White, Yellow, or Red.

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

50
7

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

White

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

60
40

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

Red

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

15
12

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

Yellow

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Coronavirus cases are now rising very fast in Neverland. The rise is mainly caused by a new variant of the virus which is spreading more rapidly than the original version. People are frustrated by seeing another pick in the statistics, while at the same time, there is no clear estimate on when vaccination will be available in the country. Although the new variant of coronavirus is not believed to be more deadly, the rise in the new case statistics has made people panicked and afraid. Therefore, the government of Neverland has decided to manipulate the new case statistics slightly to reduce people’s anxiety. The goal of the manipulation is to show that the new cases are not rising in the coming few days. More precisely, the number of new cases announced in each of the coming days must be equal or lower than the number announced in its preceding day. Due to investigations, the only way to change the statistics is to throw away some test results. Therefore, the announced numbers must be always less than or equal to the real numbers. As the manipulation is not free, the government is going to hire a computer scientist to calculate the minimum total amount by which the real numbers must be changed in order to achieve the above goal. Due to your experience in the ICPC programming contests, the government has selected you for this critical mission. # ورودی The first line of the input consists of $n$ ($1 \leq n \leq 10000$), the number of the coming days. Each of the next $n$ lines contains an integer $p_i$ ($0 \leq p_i \leq 1000$), indicating the real number of new cases at the $i-th$ day. # خروجی In the output, print the minimum total amount by which the real numbers must be changed in order to have new cases not to be rising in the coming days. ## ورودی نمونه ۱ ``` 3 100 150 200 ```` ## خروجی نمونه ۱ ``` 150 ```` ## ورودی نمونه ۲ ``` 2 5 4 ```` ## خروجی نمونه ۲ ``` 0 ```` ## ورودی نمونه ۳ ``` 4 10 0 9 8 ```` ## خروجی نمونه ۳ ``` 17 ````

B - Statistics

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

Coronavirus cases are now rising very fast in Neverland. The rise is mainly caused by a new variant of the virus which is spreading more rapidly than the original version. People are frustrated by seeing another pick in the statistics, while at the same time, there is no clear estimate on when vaccination will be available in the country.

Although the new variant of coronavirus is not believed to be more deadly, the rise in the new case statistics has made people panicked and afraid. Therefore, the government of Neverland has decided to manipulate the new case statistics slightly to reduce people’s anxiety. The goal of the manipulation is to show that the new cases are not rising in the coming few days. More precisely, the number of new cases announced in each of the coming days must be equal or lower than the number announced in its preceding day. Due to investigations, the only way to change the statistics is to throw away some test results. Therefore, the announced numbers must be always less than or equal to the real numbers.

As the manipulation is not free, the government is going to hire a computer scientist to calculate the minimum total amount by which the real numbers must be changed in order to achieve the above goal. Due to your experience in the ICPC programming contests, the government has selected you for this critical mission.

ورودی🔗

The first line of the input consists of $n$ ( $1 \leq n \leq 10000$ ), the number of the coming days. Each of the next $n$ lines contains an integer $p_i$ ( $0 \leq p_i \leq 1000$ ), indicating the real number of new cases at the $i-th$ day.

خروجی🔗

In the output, print the minimum total amount by which the real numbers must be changed in order to have new cases not to be rising in the coming days.

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

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

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

2
5
4

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

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Arts and literature have always been influenced by science. This appears, for example, in Christopher Nolan movies. But, there is a scientist who is doing his research on a hypothesis based on fictional novels. Dr. Khosro, a theoretical physicist, does research on parallel worlds with high-dimensions, inspired by Isaac Asimov’s novels. During his research, he needs a method of sorting in his imaginary high-dimension network of planets. In Dr. Khosro’s imaginary n-dimensional world, there are $2^n$ planets and a wormhole network connecting them. The network is like an $n$-dimensional hypercube. The planets are numbered with non-negative integers less than $2^n$, and there is a wormhole from planet a to planet b if and only if the n-bit binary representations of $a$ and $b$ differ in exactly one bit-position. In Dr. Khosro’s model, there is a number written on each planet and we can swap the numbers of two planets only if there is a direct wormhole between them. You are given the numbers written on each planet, construct a valid sequence of swaps that makes the numbers sequence sorted from smallest to largest. Formally, if the number written on the planet number $i$ ($0 \leq i \lt 2^n$) is denoted by $a_i$, you have to construct a sequence of valid pairwise swaps that makes the sequence $a = \langle a_0, a_1, \dots, a_{2^{n-1}} \rangle$ in increasing order. # ورودی The first line of input consists of $n$ ($1 \leq n \leq 10$), the dimension of Dr. Khosro’s imaginary world. The next line contains $2^n$ **distinct** integers, indicating $a_0, a_1, \dots, a_{2^{n-1}} \; (0 \leq a_i \leq 10^6)$. # خروجی Print the numbers of your swaps in the first line. Your answer will be considered correct if this number is nonnegative and less than $12,000$. Then in the following lines, print the sequence of swaps. In your solution, every swap must be between two planets with a direct wormhole between them. # مثال‌‌ها ## ورودی نمونه ۱ ``` 2 3 2 10 4 ```` ## خروجی نمونه ۱ ``` 2 1 0 3 2 ```` ## ورودی نمونه ۲ ``` 1 10 100 ```` ## خروجی نمونه ۲ ``` 0 ````

C - Science Fiction

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

Arts and literature have always been influenced by science. This appears, for example, in Christopher Nolan movies. But, there is a scientist who is doing his research on a hypothesis based on fictional novels.

Dr. Khosro, a theoretical physicist, does research on parallel worlds with high-dimensions, inspired by Isaac Asimov’s novels. During his research, he needs a method of sorting in his imaginary high-dimension network of planets. In Dr. Khosro’s imaginary n-dimensional world, there are $2^n$ planets and a wormhole network connecting them. The network is like an $n$ -dimensional hypercube. The planets are numbered with non-negative integers less than $2^n$ , and there is a wormhole from planet a to planet b if and only if the n-bit binary representations of $a$ and $b$ differ in exactly one bit-position. In Dr. Khosro’s model, there is a number written on each planet and we can swap the numbers of two planets only if there is a direct wormhole between them. You are given the numbers written on each planet, construct a valid sequence of swaps that makes the numbers sequence sorted from smallest to largest. Formally, if the number written on the planet number $i$ ( $0 \leq i \lt 2^n$ ) is denoted by $a_i$ , you have to construct a sequence of valid pairwise swaps that makes the sequence $a = \langle a_0, a_1, \dots, a_{2^{n-1}} \rangle$ in increasing order.

ورودی🔗

The first line of input consists of $n$ ( $1 \leq n \leq 10$ ), the dimension of Dr. Khosro’s imaginary world. The next line contains $2^n$ distinct integers, indicating $a_0, a_1, \dots, a_{2^{n-1}} \; (0 \leq a_i \leq 10^6)$ .

خروجی🔗

Print the numbers of your swaps in the first line. Your answer will be considered correct if this number is nonnegative and less than $12,000$ . Then in the following lines, print the sequence of swaps. In your solution, every swap must be between two planets with a direct wormhole between them.

مثال‌‌ها🔗

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

2
3 2 10 4

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

2
1 0
3 2

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

1
10 100

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Yalda wants to give a brilliant gift to Bahar for her birthday. She has drawn the sketch of a necklace consisting of $n$ beads of different colors on paper. The necklace is illustrated by a string of length $n$ which is made up of lowercase English letters that indicate the colors of the beads. Each of the $26$ English letters represents a distinct color. Yalda is going to make the necklace using the infinite number of beads in different colors she has. However, as Bahar’s birthday is approaching, she has a little time and wants to make the necklace in the fewest steps possible. Yalda has two empty necklaces initially. One of the necklaces is going to be the final gift, and the other one is a buffer necklace that helps her during the construction. At each step she can do one of the followings: + Add a bead of the desired color at an arbitrary place in the buffer necklace, + Remove a bead at an arbitrary place from the buffer necklace, + Substitute a bead of the buffer necklace with a bead of the desired color, or + Append a string of beads to the end of the main necklace, copying the buffer necklace. The added string will be exactly the same as thebuffer necklace. However, the order of the beads in the buffer necklace will get reversed during the copying procedure (for example, if the main necklace equals `pq` and the buffer necklace equals `abc` before this procedure, the main necklace becomes `pqabc` and the buffer necklaces becomes `cba` after the procedure). Yalda would really appreciate it if you could tell her the minimum number of steps required for making the necklace. # ورودی The only line of the input consists of a non-empty string of lowercase English letters with at most $300$ letters. The string indicates the sketch of the desired necklace. # خروجی In the only line of output, print a single number indicating the minimum number of steps that are required to make the necklace. # مثال‌‌ها ## ورودی نمونه ۱ ``` abaadbcceaaefc ```` ## خروجی نمونه ۱ ``` 12 ```` ## ورودی نمونه ۲ ``` abaddbeageabdkpkdbeqg ```` ## خروجی نمونه ۲ ``` 16 ````

D - Necklace Construction

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

Yalda wants to give a brilliant gift to Bahar for her birthday. She has drawn the sketch of a necklace consisting of $n$ beads of different colors on paper. The necklace is illustrated by a string of length $n$ which is made up of lowercase English letters that indicate the colors of the beads. Each of the $26$ English letters represents a distinct color. Yalda is going to make the necklace using the infinite number of beads in different colors she has. However, as Bahar’s birthday is approaching, she has a little time and wants to make the necklace in the fewest steps possible. Yalda has two empty necklaces initially. One of the necklaces is going to be the final gift, and the other one is a buffer necklace that helps her during the construction. At each step she can do one of the followings:

Add a bead of the desired color at an arbitrary place in the buffer necklace,
Remove a bead at an arbitrary place from the buffer necklace,
Substitute a bead of the buffer necklace with a bead of the desired color, or
Append a string of beads to the end of the main necklace, copying the buffer necklace. The added string will be exactly the same as thebuffer necklace. However, the order of the beads in the buffer necklace will get reversed during the copying procedure (for example, if the main necklace equals pq and the buffer necklace equals abc before this procedure, the main necklace becomes pqabc and the buffer necklaces becomes cba after the procedure).

Yalda would really appreciate it if you could tell her the minimum number of steps required for making the necklace.

ورودی🔗

The only line of the input consists of a non-empty string of lowercase English letters with at most $300$ letters. The string indicates the sketch of the desired necklace.

خروجی🔗

In the only line of output, print a single number indicating the minimum number of steps that are required to make the necklace.

مثال‌‌ها🔗

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

abaadbcceaaefc

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

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

abaddbeageabdkpkdbeqg

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Leila is a surgeon in a high-quality hospital. To reach the operating room, she has to pass through a waiting saloon, where some patients with Coronavirus symptoms are waiting to get tested. To avoid the infection, Leila wants to pass through the saloon in such a way that she keeps the maximum distance from the patients. Your task is to help her find the maximum possible distance from any patient while passing through the waiting saloon. You are given the map of the saloon as a matrix, in which the locations of the patients and the free seats (where she can not pass through!) are marked. The distance of two cells $(x_1, y_1)$ and $(x_2,y_2)$ in the matrix is defined as $\max(|x_1-x_2|, |y_1-y_2|)$. Seats do not block corona from spreading. Thus, in the definition of the distance between two cells, we do not consider the places of the seats. In each step, Leila can go from one cell in the matrix to one of its four neighbors: up, down, right, and left in the saloon, if no seats and patients are there. # ورودی The first line of the input consists of two integers $m$ ($1 \leq m \leq 500$) and $n$ ($1 \leq n \leq 500$) separated by a space, which is the number of rows and the number of columns, respectively. Then, the map of the waiting saloon is given in m following lines; each line represents a row of the matrix and contains n characters, `*` is for a patient, `#` for an empty seat, and `.` for free space where Leila can walk through. The starting point of Leila is represented by an `S` character, and the endpoint of her path is represented by an `E` character in the matrix. Note that Leila cannot go out of the saloon (which is represented as the matrix) in her path. # خروجی Print the maximum possible distance which Leila can maintain from the patients in her path. If it is not possible for Leila to reach the operating room at all, print a `-1` in the output. Otherwise, if no patient is present in the saloon, print “safe” in the output. # مثال‌ها ## ورودی نمونه ۱ ``` 4 5 .*#.. .*..E ..##. S.... ```` ## خروجی نمونه ۱ ``` 2 ```` ## ورودی نمونه ۲ ``` 6 8 .......E ........ ........ .....**. ........ S....... ```` ## خروجی نمونه ۲ ``` 3 ```` ## ورودی نمونه ۳ ``` 3 3 #E# ### #S# ```` ## خروجی نمونه ۳ ``` -1 ```` ## ورودی نمونه ۴ ``` 3 3 .S. *** .E. ```` ## خروجی نمونه ۴ ``` -1 ```` ## ورودی نمونه ۵ ``` 3 3 S.. ... ..E ```` ## خروجی نمونه ۵ ``` safe ````

E - Social Distancing

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

Leila is a surgeon in a high-quality hospital. To reach the operating room, she has to pass through a waiting saloon, where some patients with Coronavirus symptoms are waiting to get tested. To avoid the infection, Leila wants to pass through the saloon in such a way that she keeps the maximum distance from the patients. Your task is to help her find the maximum possible distance from any patient while passing through the waiting saloon. You are given the map of the saloon as a matrix, in which the locations of the patients and the free seats (where she can not pass through!) are marked. The distance of two cells $(x_1, y_1)$ and $(x_2,y_2)$ in the matrix is defined as $\max(|x_1-x_2|, |y_1-y_2|)$ . Seats do not block corona from spreading. Thus, in the definition of the distance between two cells, we do not consider the places of the seats. In each step, Leila can go from one cell in the matrix to one of its four neighbors: up, down, right, and left in the saloon, if no seats and patients are there.

ورودی🔗

The first line of the input consists of two integers $m$ ( $1 \leq m \leq 500$ ) and $n$ ( $1 \leq n \leq 500$ ) separated by a space, which is the number of rows and the number of columns, respectively. Then, the map of the waiting saloon is given in m following lines; each line represents a row of the matrix and contains n characters, * is for a patient, # for an empty seat, and . for free space where Leila can walk through. The starting point of Leila is represented by an S character, and the endpoint of her path is represented by an E character in the matrix. Note that Leila cannot go out of the saloon (which is represented as the matrix) in her path.

خروجی🔗

Print the maximum possible distance which Leila can maintain from the patients in her path. If it is not possible for Leila to reach the operating room at all, print a -1 in the output. Otherwise, if no patient is present in the saloon, print “safe” in the output.

مثال‌ها🔗

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

4 5
.*#..
.*..E
..##.
S....

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

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

6 8
.......E
........
........
.....**.
........
S.......

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

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

3 3
#E#
###
#S#

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

-1

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

3 3
.S.
***
.E.

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

-1

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

3 3
S..
...
..E

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

safe

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Hezardastan, a leading information technology development group in Iran, has launched a new project: a private space telescope with a monetized service for taking photos from all known astronomical objects (stars, planets, galaxies, constellations, ...). For special research, we need to use this service. The research must be done in $k$ consecutive days, numbered $1$ through $k$. Let $S_i$ denote the set of astronomical objects whose photo should be taken on the $i-th$ day ($1 \leq i \leq k$). We have to specify the set $S_i$ separately for each day on the photography website. ![توضیح تصویر](https://quera.org/qbox/download/AjgB74u8df/F.png) In order to specify a set of astronomical objects, we should enter the name of its members. The name of each astronomical object is a non-empty string of at most $10$ characters. The characters can be the hyphen (`-`), digits (`0` to `9`), or capital letters (`A` to `Z`). The website provides limited support of wildcards for entering a set of astronomical object names. More specifically, each entered string on the website can refer to multiple astronomical objects by having at most one asterisk (`*`), either in its beginning or its end (but not both). The asterisk matches any string (including the empty string). For example, `A*` refers to all known objects whose name starts with `A`, while `*99` refers to all objects whose name ends with `99` (including the name `99` itself if there is an astronomical object with this name). We have to pay $1000$ dollars for each photo. In order to reduce the load on the service website, Hezardastan has put an additional tax on the data entry: we have to pay $1$ extra dollar for each string entered to specify a set of astronomical objects. So for example, we have to pay $5002$ dollars by entering the set `A*`, `*B` if there are $5$ astronomical objects whose name starts with `A` or ends with `B`. Given the name of all the known astronomical objects and the sets $S_1, \dots, S_k$, your task is to find a minimum cost representation for each $S_i$. # ورودی The input starts with a line containing two space-separated integers $n$ ($1 \leq n \leq 1000$) and $k$ ($1 \leq k \leq 100$). The second line contains $n$ space-separated unique strings, as the names of all known astronomical objects. The objects are numbered $1$ through n in the same order. The next $k$ lines specify $S_1$,...,$S_k$, one set per line. Each line starts with $S_i$ (size of $S_i$) followed by $S_i$ integers, the numbers of the objects in $S_i$. # خروجی Print a single line for each day in the output. The $i-th$ line must start with the minimum possible cost to take the photos of the $i-th$ day. It should then contain a representation of $S_i$ for such a minimum cost method. If the representation contains $m$ elements, print the integer $m$, followed by the m elements. All the numbers and strings in the line should be separated by single space characters. If there are multiple optimum representations for a set, you can print any one of them. ## ورودی نمونه ۱ ``` 8 7 K-PAX SIRIUS REGULUS ARCTURUS BELLATRIX ANDROMEDA CYGNUS SCORPIUS 8 1 2 3 4 5 6 8 7 6 2 3 4 7 8 6 5 1 2 3 5 8 3 5 6 7 2 2 8 0 1 1 ```` ## خروجی نمونه ۱ ``` 8001 1 * 6002 2 A* *S 5003 3 *X R* S* 3003 3 AN* B* C* 2001 1 S* 0 0 1001 1 K* ````

F - Hezardastan

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

Hezardastan, a leading information technology development group in Iran, has launched a new project: a private space telescope with a monetized service for taking photos from all known astronomical objects (stars, planets, galaxies, constellations, ...). For special research, we need to use this service. The research must be done in $k$ consecutive days, numbered $1$ through $k$ . Let $S_i$ denote the set of astronomical objects whose photo should be taken on the $i-th$ day ( $1 \leq i \leq k$ ). We have to specify the set $S_i$ separately for each day on the photography website.

توضیح تصویر

In order to specify a set of astronomical objects, we should enter the name of its members. The name of each astronomical object is a non-empty string of at most $10$ characters. The characters can be the hyphen (-), digits (0 to 9), or capital letters (A to Z). The website provides limited support of wildcards for entering a set of astronomical object names. More specifically, each entered string on the website can refer to multiple astronomical objects by having at most one asterisk (*), either in its beginning or its end (but not both). The asterisk matches any string (including the empty string). For example, A* refers to all known objects whose name starts with A, while *99 refers to all objects whose name ends with 99 (including the name 99 itself if there is an astronomical object with this name).

We have to pay $1000$ dollars for each photo. In order to reduce the load on the service website, Hezardastan has put an additional tax on the data entry: we have to pay $1$ extra dollar for each string entered to specify a set of astronomical objects. So for example, we have to pay $5002$ dollars by entering the set A*, *B if there are $5$ astronomical objects whose name starts with A or ends with B.

Given the name of all the known astronomical objects and the sets $S_1, \dots, S_k$ , your task is to find a minimum cost representation for each $S_i$ .

ورودی🔗

The input starts with a line containing two space-separated integers $n$ ( $1 \leq n \leq 1000$ ) and $k$ ( $1 \leq k \leq 100$ ). The second line contains $n$ space-separated unique strings, as the names of all known astronomical objects. The objects are numbered $1$ through n in the same order. The next $k$ lines specify $S_1$ ,..., $S_k$ , one set per line. Each line starts with $S_i$ (size of $S_i$ ) followed by $S_i$ integers, the numbers of the objects in $S_i$ .

خروجی🔗

Print a single line for each day in the output. The $i-th$ line must start with the minimum possible cost to take the photos of the $i-th$ day. It should then contain a representation of $S_i$ for such a minimum cost method. If the representation contains $m$ elements, print the integer $m$ , followed by the m elements. All the numbers and strings in the line should be separated by single space characters. If there are multiple optimum representations for a set, you can print any one of them.

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

8 7
K-PAX SIRIUS REGULUS ARCTURUS BELLATRIX ANDROMEDA CYGNUS SCORPIUS
8 1 2 3 4 5 6 8 7
6 2 3 4 7 8 6
5 1 2 3 5 8
3 5 6 7
2 2 8
0
1 1

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

8001 1 *
6002 2 A* *S
5003 3 *X R* S*
3003 3 AN* B* C*
2001 1 S*
0 0
1001 1 K*

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- The downtown is very busy this weekend. Javad and Jalal are each organizing a race, namely Javad Rally and Jalal Rally. They have located the start and final intersections for each race and are now negotiating with the local police to finalize the route of each race. The police will close the intersections of each route on the race day, so **there are no shared intersections in the routes**. Moreover, since the race routes are closed by the local police on the race day which makes more traffic congestion in the downtown, each route must be the shortest path from the start to its final intersections. They have trouble figuring out the proper conflict-free routes, so they asked you for help to count the number of different ways to organize the races. Two races are different if the pair of their routes are different. The map of the city is given as $n$ intersections numbered $1$ to $n$, and $m$ roads connecting those intersections. Each road has a specified length. Moreover, for each rally, the start and the final intersections are given. You should calculate the number of the different conflict-free shortest path races. # ورودی The first line of the input contains two integers $n$ ($4 \leq n \leq 24$) and $m$ ($1 \leq m \leq \frac{n(n - 1)}{2}$). The following $m$ lines are the road descriptions. The $i-th$ road has three integers: $u_i$ ($1 \leq u_i \leq n$), $v_i$ ($1 \leq v_i \leq n$), and $w_i$ ($1 \leq w_i \leq 1000$) denoting its two end-vertices and its length. There are no self-loops and multiple edges in the given map and all roads are bidirectional. The last line contains $4$ integer: $s_1$,$t_1$, $s_2$, and $t_2$ ($1 \leq s_1, t_1, s_2, t_2 \leq n$); the numbers of the start and the final intersections of Javad’s route and Jalal’s route, respectively. It is guaranteed that all these numbers are distinct. It is guaranteed that the given map is connected, i.e., there is a path between any two intersections. # خروجی Print the number of different ways to organize both races. # مثال‌ها ## ورودی نمونه ۱ ``` 4 4 1 2 2 2 3 1 1 3 1 3 4 1 1 2 3 4 ```` ## خروجی نمونه ۱ ``` 1 ```` ## ورودی نمونه ۲ ``` 4 3 1 2 1 2 3 1 3 4 1 1 3 2 4 ```` ## خروجی نمونه ۲ ``` 0 ```` ## ورودی نمونه ۳ ``` 6 8 1 4 1 1 3 1 4 2 1 3 2 1 1 2 2 1 5 1 5 2 1 5 6 2 1 2 6 5 ```` ## خروجی نمونه ۳ ``` 3 ````

G - JJ Rally

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

The downtown is very busy this weekend. Javad and Jalal are each organizing a race, namely Javad Rally and Jalal Rally. They have located the start and final intersections for each race and are now negotiating with the local police to finalize the route of each race. The police will close the intersections of each route on the race day, so there are no shared intersections in the routes. Moreover, since the race routes are closed by the local police on the race day which makes more traffic congestion in the downtown, each route must be the shortest path from the start to its final intersections. They have trouble figuring out the proper conflict-free routes, so they asked you for help to count the number of different ways to organize the races. Two races are different if the pair of their routes are different.

The map of the city is given as $n$ intersections numbered $1$ to $n$ , and $m$ roads connecting those intersections. Each road has a specified length. Moreover, for each rally, the start and the final intersections are given. You should calculate the number of the different conflict-free shortest path races.

ورودی🔗

The first line of the input contains two integers $n$ ( $4 \leq n \leq 24$ ) and $m$ ( $1 \leq m \leq \frac{n(n - 1)}{2}$ ). The following $m$ lines are the road descriptions. The $i-th$ road has three integers: $u_i$ ( $1 \leq u_i \leq n$ ), $v_i$ ( $1 \leq v_i \leq n$ ), and $w_i$ ( $1 \leq w_i \leq 1000$ ) denoting its two end-vertices and its length. There are no self-loops and multiple edges in the given map and all roads are bidirectional. The last line contains $4$ integer: $s_1$ , $t_1$ , $s_2$ , and $t_2$ ( $1 \leq s_1, t_1, s_2, t_2 \leq n$ ); the numbers of the start and the final intersections of Javad’s route and Jalal’s route, respectively. It is guaranteed that all these numbers are distinct. It is guaranteed that the given map is connected, i.e., there is a path between any two intersections.

خروجی🔗

Print the number of different ways to organize both races.

مثال‌ها🔗

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

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

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

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

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Birds are stupendous animals. Many species of them perform different rituals throughout their life; from courtship dances of peacocks to moon walking of red-capped manakins. Among all, we are studying the permutation dance in this problem. This ritual is performed by a group of birds sitting in a row on a wire or tree branch, as shown in the figure. ![توضیح تصویر](https://quera.org/qbox/download/cykgYbOpMb/H.png) The ritual can be simplified to a performance based on a sequence of actions of these types: + insertion: A new bird joins the group and inserts herself somewhere in the row of the birds. + departure: A bird in the row leaves the group for rest of the ritual and flies away. + relocation: A bird in the row flies from her position and sits (inserts herself) somewhere else in the row. Given the initial position of the birds in the row and the sequence of actions, your task is to compute the final position of the birds in the ritual. # ورودی The input starts with a line containing two space-separated integers $n$ ($1 \leq n \leq 1000$) and $s$ ($1 \leq s \leq 5000$). The second line contains $n$ space-separated bird names, as the initial configuration of the ritual (positioning of the birds in the row, from left to right). Each bird name is a non-empty string of at most $10$ (lowercase) alphanumeric characters ($a$ to $z$, and $0$ to $9$). The sequence of actions is provided in the next s lines, one action per line. Each line is in one of the following formats based on the action type. The bird-name parameter in the actions has the similar format as the second line of the input. + insertion: `insert bird-name position` The `position` parameter is an integer showing the number of birds to the left of the insertion position. This parameter is in the range $[0,M]$ where $M$ is the total number of birds in the row before the insertion. Position $0$ puts the bird in the beginning (leftmost position) of the row, and position $M$ puts the bird in the end (rightmost position). + departure: `depart bird-name` + relocation: `relocate bird-name displacement` The `displacement` parameter is an integer that can be positive, negative, or zero. The bird flies to her own position if the displacement is $0$. Otherwise, the bird flies over k birds on his right (left) if displacement is positive(negative),where $k$ is the absolute value of displacement. This parameter is in the range $[ L,+R]$ where $L$ and $R$ are respectively the numbers of birds to the left and to the right of the moving bird in the row before the relocation. Displacement $L$ puts the bird in the beginning(left most position) of the row,and displacement $+R$ puts the bird in the end (right most position). No two participating birds share the same name.Moreover,it is guaranteed that all the actions are meaningful at the moment of execution and there is always at least one bird on the branch throughout the ritual. # خروجی Print a single line in the output containing the final configuration of the ritual. The line should contain the space-separated list of the bird names in the row(from left to the right). ## ورودی نمونه ۱ ``` 3 1 juju ashi mashi insert fifi 1 ```` ## خروجی نمونه ۱ ``` juju fifi ashi mashi ```` ## ورودی نمونه ۲ ``` 3 15 m1 m2 f insert m3 0 relocate m2 -2 relocate m1 -2 relocate m3 -2 relocate m2 -2 relocate m1 -2 relocate m3 -2 depart m2 relocate m1 1 relocate f 0 relocate m3 0 relocate f -1 relocate m3 -1 relocate m1 -2 relocate f -1 ```` ## خروجی نمونه ۲ ``` m1 f m3 ```` ## ورودی نمونه ۳ ``` 4 5 hedwig hermes fawkes errol insert pigwidgeon 1 relocate hermes 2 depart fawkes insert buckbeak 0 depart hedwig ```` ## خروجی نمونه ۳ ``` buckbeak pigwidgeon errol hermes ```` A video of the first two sample inputs is provided in the attachment package. Copyright notice: the images and videos of this problem are taken from the following addresses: + Animation “For the Birds”, Pixar Animation Studios + [https://www.instagram.com/p/BpBshBghJ54/](https://www.instagram.com/p/BpBshBghJ54/) + [https://www.instagram.com/p/B1XWKQXgGKe/](https://www.instagram.com/p/B1XWKQXgGKe/)

H - Birds Rituals

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

Birds are stupendous animals. Many species of them perform different rituals throughout their life; from courtship dances of peacocks to moon walking of red-capped manakins. Among all, we are studying the permutation dance in this problem. This ritual is performed by a group of birds sitting in a row on a wire or tree branch, as shown in the figure.

توضیح تصویر

The ritual can be simplified to a performance based on a sequence of actions of these types:

insertion: A new bird joins the group and inserts herself somewhere in the row of the birds.
departure: A bird in the row leaves the group for rest of the ritual and flies away.
relocation: A bird in the row flies from her position and sits (inserts herself) somewhere else in the row.

Given the initial position of the birds in the row and the sequence of actions, your task is to compute the final position of the birds in the ritual.

ورودی🔗

The input starts with a line containing two space-separated integers $n$ ( $1 \leq n \leq 1000$ ) and $s$ ( $1 \leq s \leq 5000$ ). The second line contains $n$ space-separated bird names, as the initial configuration of the ritual (positioning of the birds in the row, from left to right). Each bird name is a non-empty string of at most $10$ (lowercase) alphanumeric characters ( $a$ to $z$ , and $0$ to $9$ ).

The sequence of actions is provided in the next s lines, one action per line. Each line is in one of the following formats based on the action type. The bird-name parameter in the actions has the similar format as the second line of the input.

insertion: insert bird-name position

The position parameter is an integer showing the number of birds to the left of the insertion position. This parameter is in the range $[0,M]$ where $M$ is the total number of birds in the row before the insertion. Position $0$ puts the bird in the beginning (leftmost position) of the row, and position $M$ puts the bird in the end (rightmost position).

departure: depart bird-name
relocation: relocate bird-name displacement

The displacement parameter is an integer that can be positive, negative, or zero. The bird flies to her own position if the displacement is $0$ . Otherwise, the bird flies over k birds on his right (left) if displacement is positive(negative),where $k$ is the absolute value of displacement. This parameter is in the range $[ L,+R]$ where $L$ and $R$ are respectively the numbers of birds to the left and to the right of the moving bird in the row before the relocation. Displacement $L$ puts the bird in the beginning(left most position) of the row,and displacement $+R$ puts the bird in the end (right most position).

No two participating birds share the same name.Moreover,it is guaranteed that all the actions are meaningful at the moment of execution and there is always at least one bird on the branch throughout the ritual.

خروجی🔗

Print a single line in the output containing the final configuration of the ritual. The line should contain the space-separated list of the bird names in the row(from left to the right).

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

3 1
juju ashi mashi
insert fifi 1

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

juju fifi ashi mashi

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

3 15
m1 m2 f
insert m3 0
relocate m2 -2
relocate m1 -2
relocate m3 -2
relocate m2 -2
relocate m1 -2
relocate m3 -2
depart m2
relocate m1 1
relocate f 0
relocate m3 0
relocate f -1
relocate m3 -1
relocate m1 -2
relocate f -1

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

m1 f m3

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

4 5
hedwig hermes fawkes errol
insert pigwidgeon 1
relocate hermes 2
depart fawkes
insert buckbeak 0
depart hedwig

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

buckbeak pigwidgeon errol hermes

A video of the first two sample inputs is provided in the attachment package. Copyright notice: the images and videos of this problem are taken from the following addresses:

Animation “For the Birds”, Pixar Animation Studios
https://www.instagram.com/p/BpBshBghJ54/
https://www.instagram.com/p/B1XWKQXgGKe/

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- A Time-Turner is a magical device used to travel back in time, spend some time there, and then get back to the current time. Rose Granger has found a Time-Turner in the libraries of Hogwarts and took it upon herself to go back in time and take out some members of the Black family, in order to save the lives of muggles (humans without any magical ability). The Black family has $n$ members, numbered $1$ to $n$ in order of being born. Member $1$ is the first member of the Black family with a recorded history. For each $i$ ($2 \leq i \leq n$), member i is a direct descendant of member $p_i$ ($1 \leq p_i$ < $i$). i.e., member $p_i$ and all of his/her ancestors are an ancestor of member $i$. It is also written in the books that the $i-th$ member of the Black family is responsible for the death of $c_i$ muggles. Now Rose has q options. The $j-th$ option is to use the Time-Turner to go back in time and take out all the members from $a_j$ to $b_j$ ($a_j \leq b_j$) and then come back to the current time. As a consequence of this action, any member of the Black family who has an ancestor among members $a_j$ to $b_j$ will never be born. For any member i who is among members $a_j$ to $b_j$ (i.e. $a_j \leq i \leq b_j$), or has an ancestor among members $a_j$ to $b_j$, Rose will save $c_i$ lives. For each option, help Rose to find out how many lives she will save if she takes that option. # ورودی The first line of the input contains two integers $n$ and $q$ ($2 \leq n \leq 10^5$, $1 \leq q \leq 10^5$). The second line contains $n$ space-separated integers $c_1$ to $c_n$ ($0 \leq c_i \leq 10^4$). The third line contains $n-1$ integers $p_2$ to $p_n$ ($1 \leq p_i < i$). Each of the next q lines contains one option; The $j-th$ line contains two integers $a_j$ and $b_j$ ($1 \leq a_j \leq b_j \leq n$). # خروجی For each $j$ ($1 \leq j \leq q$), output the number of lives Rose will save if she takes the $j-th$ option. # مثال ## ورودی نمونه ۱ ``` 6 5 1 2 4 8 16 32 1 2 2 1 5 1 1 2 3 4 5 2 6 6 6 ```` ## خروجی نمونه ۱ ``` 63 14 56 62 32 ````

I - Black Family Tree

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

A Time-Turner is a magical device used to travel back in time, spend some time there, and then get back to the current time.

Rose Granger has found a Time-Turner in the libraries of Hogwarts and took it upon herself to go back in time and take out some members of the Black family, in order to save the lives of muggles (humans without any magical ability).

The Black family has $n$ members, numbered $1$ to $n$ in order of being born. Member $1$ is the first member of the Black family with a recorded history. For each $i$ ( $2 \leq i \leq n$ ), member i is a direct descendant of member $p_i$ ( $1 \leq p_i$ < $i$ ). i.e., member $p_i$ and all of his/her ancestors are an ancestor of member $i$ . It is also written in the books that the $i-th$ member of the Black family is responsible for the death of $c_i$ muggles.

Now Rose has q options. The $j-th$ option is to use the Time-Turner to go back in time and take out all the members from $a_j$ to $b_j$ ( $a_j \leq b_j$ ) and then come back to the current time. As a consequence of this action, any member of the Black family who has an ancestor among members $a_j$ to $b_j$ will never be born. For any member i who is among members $a_j$ to $b_j$ (i.e. $a_j \leq i \leq b_j$ ), or has an ancestor among members $a_j$ to $b_j$ , Rose will save $c_i$ lives.

For each option, help Rose to find out how many lives she will save if she takes that option.

ورودی🔗

The first line of the input contains two integers $n$ and $q$ ( $2 \leq n \leq 10^5$ , $1 \leq q \leq 10^5$ ). The second line contains $n$ space-separated integers $c_1$ to $c_n$ ( $0 \leq c_i \leq 10^4$ ). The third line contains $n-1$ integers $p_2$ to $p_n$ ( $1 \leq p_i < i$ ). Each of the next q lines contains one option; The $j-th$ line contains two integers $a_j$ and $b_j$ ( $1 \leq a_j \leq b_j \leq n$ ).

خروجی🔗

For each $j$ ( $1 \leq j \leq q$ ), output the number of lives Rose will save if she takes the $j-th$ option.

مثال🔗

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

6 5
1 2 4 8 16 32
1 2 2 1 5
1 1
2 3
4 5
2 6
6 6

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Whenever a baby is born in Neverland, a place on the main road of Neverland is assigned to her/him. In every traditional activity, such as morning exercises, the citizens of Neverland take place on their own assigned place on the main road. Unfortunately, during the corona pandemic, all out-door traditional activities of Neverland are canceled. After the approval of the corona vaccine, Neverland’s council has decided to reopen the activities, but of course with a corona-secure regulation. Neverland’s council has assumed that a vaccinated person is safe both in getting infected or in the transmission of the infection. On the other hand for non-vaccinated persons, there is a corona-safe distance that keeping this distance between every two persons keeps them safe. Thus, a safe situation is a situation in which every two non-vaccinated persons keep the corona-safe physical distance. Knowing assigned places to the citizens participating in traditional activities, Neveland’s council has decided to vaccinate a minimum number of citizens to make their activity safe. # ورودی The input consists of two lines. The first line contains two integers separated by a space $n$ ($1$ ⩽ $n$ ⩽ $10^5$), the number of Neverland’s citizens participating in the activities, and the corona-safe distance $L$ ($1$ ⩽ $L$ ⩽ $10^5$), i.e. two persons will not get the virus from each other if their distance is at least L. The next line consists of n integer numbers in the range $[10^5,10^5]$, where the $i-th$ number represents the location of the $i-th$ participating citizen. The location is calculated as the distance in meters from the beginning of the main road of Neverland. # خروجی Print the minimum number of citizens that should be vaccinated to have a safe activity in Neverland. # مثال ## ورودی نمونه ۱ ``` 5 2 -1 0 1 2 3 ```` ## خروجی نمونه ۱ ``` 2 ```` ## ورودی نمونه ۲ ``` 5 4 1 2 4 6 8 ```` ## خروجی نمونه ۲ ``` 3 ````

J - Vaccination Against Corona

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

Whenever a baby is born in Neverland, a place on the main road of Neverland is assigned to her/him. In every traditional activity, such as morning exercises, the citizens of Neverland take place on their own assigned place on the main road. Unfortunately, during the corona pandemic, all out-door traditional activities of Neverland are canceled. After the approval of the corona vaccine, Neverland’s council has decided to reopen the activities, but of course with a corona-secure regulation. Neverland’s council has assumed that a vaccinated person is safe both in getting infected or in the transmission of the infection. On the other hand for non-vaccinated persons, there is a corona-safe distance that keeping this distance between every two persons keeps them safe. Thus, a safe situation is a situation in which every two non-vaccinated persons keep the corona-safe physical distance. Knowing assigned places to the citizens participating in traditional activities, Neveland’s council has decided to vaccinate a minimum number of citizens to make their activity safe.

ورودی🔗

The input consists of two lines. The first line contains two integers separated by a space $n$ ( $1$ ⩽ $n$ ⩽ $10^5$ ), the number of Neverland’s citizens participating in the activities, and the corona-safe distance $L$ ( $1$ ⩽ $L$ ⩽ $10^5$ ), i.e. two persons will not get the virus from each other if their distance is at least L. The next line consists of n integer numbers in the range $[10^5,10^5]$ , where the $i-th$ number represents the location of the $i-th$ participating citizen. The location is calculated as the distance in meters from the beginning of the main road of Neverland.

خروجی🔗

Print the minimum number of citizens that should be vaccinated to have a safe activity in Neverland.

مثال🔗

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

5 2
-1 0 1 2 3

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

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

5 4
1 2 4 6 8

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- A fly named McFly is going to a party tonight. Unfortunately for him, it’s a party for humans, not flies. There is going to be a $10^9$ meter long table at the party, where humans put down their cookies for a while before they pick them up again later. That’s when McFly can buzz in and taste the cookie while the human is leaving his/her cookie unattended. Tasting cookies is McFly’s favorite thing to do. He doesn’t want to eat them, he just wants to enjoy tasting as many cookies as possible. He’ll enjoy tasting a cookie if it is different from the previous cookie he tasted, or if it is the first cookie he tastes at the party. That means he can enjoy tasting the same cookie multiple times, as long as he tastes at least one other cookie between every two tastings of the same cookie. But McFly is prepared. He went to see a fortune-teller to know what is going to happen at the party. The fortune-teller told him about $n$ cookies, which are going to be put down on the table. The $i-th$ cookie is going to be at position $x_i$ (i.e. $x_i$ meters from start of the table), from time $s_i$ to $f_i$ (Times are measured in seconds, from the start of the party). It is guaranteed that no two cookies will be at the same position, at the same time; i.e., for every $i$ and $j$ where $i = j$ and $x_i = x_j$, either $f_i \leq s_j$ or $f_j \leq s_i$. More specifically, the table can be considered as a horizontal line on which McFly and the cookies are seen as points. McFly can be present at any position before the start of the party. At any time afterward, he can fly at the speed of $1$ meter per second along with the table, or stay in place. McFly can taste cookie $i$ if he is at position $x_i$ at some time $t$ where $s_i \leq t < f_i$. Tasting cookies take no time. Help McFly to enjoy as many tastes as possible. # ورودی The first line of the input contains the integer $n$ ($1 \leq n \leq 100\,000 $). The $i$-th line of the next $n$ lines contains three integers $x_i$, $s_i$, and $f_i$ ($0 \leq x_i \leq 10^9$, $0 \leq s_i < f_i \leq 10^9$). The total time of cookies being on the table is at most $10^5 \left( \sum_{i=1}^n f_i - s_i \leq 10^5 \right)$. # خروجی Output the maximum number of new tastes McFly can enjoy. ## ورودی نمونه ۱ ``` 4 7 2 5 1 2 4 4 1 6 2 9 10 ```` ## خروجی نمونه ۱ ``` 3 ```` ## ورودی نمونه ۲ ``` 3 0 0 11 2 0 11 3 4 9 ```` ## خروجی نمونه ۲ ``` 8 ````

K - McFly

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

A fly named McFly is going to a party tonight. Unfortunately for him, it’s a party for humans, not flies.

There is going to be a $10^9$ meter long table at the party, where humans put down their cookies for a while before they pick them up again later. That’s when McFly can buzz in and taste the cookie while the human is leaving his/her cookie unattended. Tasting cookies is McFly’s favorite thing to do. He doesn’t want to eat them, he just wants to enjoy tasting as many cookies as possible. He’ll enjoy tasting a cookie if it is different from the previous cookie he tasted, or if it is the first cookie he tastes at the party. That means he can enjoy tasting the same cookie multiple times, as long as he tastes at least one other cookie between every two tastings of the same cookie.

But McFly is prepared. He went to see a fortune-teller to know what is going to happen at the party. The fortune-teller told him about $n$ cookies, which are going to be put down on the table. The $i-th$ cookie is going to be at position $x_i$ (i.e. $x_i$ meters from start of the table), from time $s_i$ to $f_i$ (Times are measured in seconds, from the start of the party). It is guaranteed that no two cookies will be at the same position, at the same time; i.e., for every $i$ and $j$ where $i = j$ and $x_i = x_j$ , either $f_i \leq s_j$ or $f_j \leq s_i$ . More specifically, the table can be considered as a horizontal line on which McFly and the cookies are seen as points. McFly can be present at any position before the start of the party. At any time afterward, he can fly at the speed of $1$ meter per second along with the table, or stay in place. McFly can taste cookie $i$ if he is at position $x_i$ at some time $t$ where $s_i \leq t < f_i$ . Tasting cookies take no time. Help McFly to enjoy as many tastes as possible.

ورودی🔗

The first line of the input contains the integer $n$ ( $1 \leq n \leq 100\,000$ ). The $i$ -th line of the next $n$ lines contains three integers $x_i$ , $s_i$ , and $f_i$ ( $0 \leq x_i \leq 10^9$ , $0 \leq s_i < f_i \leq 10^9$ ). The total time of cookies being on the table is at most $10^5 \left( \sum_{i=1}^n f_i - s_i \leq 10^5 \right)$ .

خروجی🔗

Output the maximum number of new tastes McFly can enjoy.

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

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

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Keivan will leave the country to study abroad. He invited all his friends to a restaurant for his goodby party. He asked them to stay home for two weeks before the party night, to be sure that none of them has contracted the coronavirus. ![توضیح تصویر](https://quera.org/qbox/download/JDz4zpbcvT/L.png) Tomaketheparty short, Keivan reserved a round table, specified each person’s seat, and put his guests’ order in front of their seats. The party was over, and everyone enjoyed the food. Unfortunately, some guests had fevers right after the party. Therefore, Keivan asked them all to take the PCR tests again. The results of the tests were not as all hoped for. Coronavirus had affected some of his friends. We know that a PCR test could have a false negative. But, it never has a false positive. This means that if a person has a negative result, he may be healthy or has contracted the coronavirus. But, people with positive results have definitely contracted the virus. Now, Keivan is confused. He does not know how his friends got sick. The restaurant manager told him that exactly one of his friends ordered a bat soup. He is determined to find those who may have ordered this soup. Thus he asked for the video check. Unfortunately, the video captured by the restaurant’s CCTV has a low quality, making it hard to see their orders. However, he could see their activities and their timings. From these activities, he wants to find those who may have ordered the bat soup and spread the coronavirus. Keivan wrote down his friends’ activities in chronologically ascending order. Each activity tells that a person talks to one of his adjacent neighbors. We know that the person who ate the bat soup got affected by the virus immediately. After that, if a sick person talks to his neighbor, the second person gets sick. There are no other ways for virus transmission. # ورودی The first line of the input has three positive integers: $n$, $m$ and $q$ ($1 \leq m \leq n \leq 10^5$, $1 \leq q \leq 10^5$) which are the number of guests, the number of sick guests, and the total number of guests activities, respectively. Guests are numbered from $1$ to $n$ in clockwise order. It means that the guest $i + 1$ is the left neighbor of guest $i$ (guest $1$ seats in the left chair of $n$). The next line contains exactly $m$ distinct integers $a_i$ ($1 \leq a_i \leq n$); each denotes one of guests who are affected by the coronavirus. The next $q$ lines are guests’ activities in the chronologically ascending order of time. Each line contains an integer $b_i$ ($1 \leq b_i \leq n$) following by a character $c_i$ ($c_i$ $L$,$R$). This indicates that the guest $b_i$, talks to his left ($L$) or his right ($R$) person. # خروجی Print all the guests who might have ordered the bat soap, in the ascending order, in one line. # مثال‌ها ## ورودی نمونه ۱ ``` 3 1 3 2 1 L 2 L 3 L ```` ## خروجی نمونه ۱ ``` 1 2 ```` ## ورودی نمونه ۲ ``` 3 2 2 2 3 1 R 3 R ```` ## خروجی نمونه ۲ ``` 1 3 ````

L - The Last Supper

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

Keivan will leave the country to study abroad. He invited all his friends to a restaurant for his goodby party. He asked them to stay home for two weeks before the party night, to be sure that none of them has contracted the coronavirus.

توضیح تصویر

Tomaketheparty short, Keivan reserved a round table, specified each person’s seat, and put his guests’ order in front of their seats. The party was over, and everyone enjoyed the food. Unfortunately, some guests had fevers right after the party. Therefore, Keivan asked them all to take the PCR tests again. The results of the tests were not as all hoped for. Coronavirus had affected some of his friends. We know that a PCR test could have a false negative. But, it never has a false positive. This means that if a person has a negative result, he may be healthy or has contracted the coronavirus. But, people with positive results have definitely contracted the virus.

Now, Keivan is confused. He does not know how his friends got sick. The restaurant manager told him that exactly one of his friends ordered a bat soup. He is determined to find those who may have ordered this soup. Thus he asked for the video check. Unfortunately, the video captured by the restaurant’s CCTV has a low quality, making it hard to see their orders. However, he could see their activities and their timings. From these activities, he wants to find those who may have ordered the bat soup and spread the coronavirus.

Keivan wrote down his friends’ activities in chronologically ascending order. Each activity tells that a person talks to one of his adjacent neighbors. We know that the person who ate the bat soup got affected by the virus immediately. After that, if a sick person talks to his neighbor, the second person gets sick. There are no other ways for virus transmission.

ورودی🔗

The first line of the input has three positive integers: $n$ , $m$ and $q$ ( $1 \leq m \leq n \leq 10^5$ , $1 \leq q \leq 10^5$ ) which are the number of guests, the number of sick guests, and the total number of guests activities, respectively. Guests are numbered from $1$ to $n$ in clockwise order. It means that the guest $i + 1$ is the left neighbor of guest $i$ (guest $1$ seats in the left chair of $n$ ). The next line contains exactly $m$ distinct integers $a_i$ ( $1 \leq a_i \leq n$ ); each denotes one of guests who are affected by the coronavirus.

The next $q$ lines are guests’ activities in the chronologically ascending order of time. Each line contains an integer $b_i$ ( $1 \leq b_i \leq n$ ) following by a character $c_i$ ( $c_i$ $L$ , $R$ ). This indicates that the guest $b_i$ , talks to his left ( $L$ ) or his right ( $R$ ) person.

خروجی🔗

Print all the guests who might have ordered the bat soap, in the ascending order, in one line.

مثال‌ها🔗

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

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

1 2

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

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

1 3

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Ahistogram is a simple rectilinear polygon $H$ (i.e. the interior angle at each vertex is either $90$° or $270$°) that has a horizontal edge seeing every point $q$ inside (i.e. the interior or the boundary of) $H$. Here, we say that an edge sees a point $q \in H$ if there is a vertical segment $s$ connecting $e$ to $q$ that is lying inside $H$. Let $H$ be a histogram with $n$ vertices, and consider a decomposition $R$ of $H$ into rectangles whose sides are vertical or horizontal. The vertices of the rectangles need not all be vertices of $H$: it is allowed to introduce additional vertices, on the boundary of $H$ and/or in its interior. The stabbing number of a horizontal or vertical segment $s$ inside $H$ with respect to such a decomposition $R$ is the number of rectangles from $R$ whose interior (not just their boundaries) are intersected by $s$. The stabbing number of $R$ is the maximum stabbing number of any horizontal or vertical segment $s$ that lies inside $H$. The goal is to compute a decomposition $R$ with the minimum stabbing number. # ورودی The first line of the input contains two positive integers $m$ and $n$ ($1 \leq m,n \leq 50$) denoting the number of rows and the number of columns of the table illustrating the histogram, respectively. The next $m$ lines, each contains exactly n characters. `*`s denote the boundary of the histogram. The rest is filled with dots (`.`). Each edge of the histogram contains at least three `*`s. You can assume the given histogram has at least four and at most 16 edges, and edges do not overlap, intersect or touch each other; i.e. each `*` is adjacent to exactly two other `*` characters. # خروجی Print the stabbing number of the given histogram in one line. # مثال‌ها ## ورودی نمونه ۱ ``` 10 13 .....****.... .....*..*.... .....*..***.. .....*....*.. .....*....*** ...***......* ...*........* ****........* *...........* ************* ```` ## خروجی نمونه ۱ ``` 2 ```` ## ورودی نمونه ۲ ``` 8 15 ............... .........*****. ....***..*...*. ....*.*..*...*. .****.****...*. .*...........*. .*************. ............... ```` ## خروجی نمونه ۲ ``` 2 ````

M - Stabbing Number

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

Ahistogram is a simple rectilinear polygon $H$ (i.e. the interior angle at each vertex is either $90$ ° or $270$ °) that has a horizontal edge seeing every point $q$ inside (i.e. the interior or the boundary of) $H$ . Here, we say that an edge sees a point $q \in H$ if there is a vertical segment $s$ connecting $e$ to $q$ that is lying inside $H$ .

Let $H$ be a histogram with $n$ vertices, and consider a decomposition $R$ of $H$ into rectangles whose sides are vertical or horizontal. The vertices of the rectangles need not all be vertices of $H$ : it is allowed to introduce additional vertices, on the boundary of $H$ and/or in its interior. The stabbing number of a horizontal or vertical segment $s$ inside $H$ with respect to such a decomposition $R$ is the number of rectangles from $R$ whose interior (not just their boundaries) are intersected by $s$ . The stabbing number of $R$ is the maximum stabbing number of any horizontal or vertical segment $s$ that lies inside $H$ . The goal is to compute a decomposition $R$ with the minimum stabbing number.

ورودی🔗

The first line of the input contains two positive integers $m$ and $n$ ( $1 \leq m,n \leq 50$ ) denoting the number of rows and the number of columns of the table illustrating the histogram, respectively. The next $m$ lines, each contains exactly n characters. *s denote the boundary of the histogram. The rest is filled with dots (.). Each edge of the histogram contains at least three *s. You can assume the given histogram has at least four and at most 16 edges, and edges do not overlap, intersect or touch each other; i.e. each * is adjacent to exactly two other * characters.

خروجی🔗

Print the stabbing number of the given histogram in one line.

مثال‌ها🔗

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

10 13
.....****....
.....*..*....
.....*..***..
.....*....*..
.....*....***
...***......*
...*........*
****........*
*...........*
*************

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

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

8 15
...............
.........*****.
....***..*...*.
....*.*..*...*.
.****.****...*.
.*...........*.
.*************.
...............