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

Have you ever heard the phrase “Cosmic Twins”? The people who are born on the same day of the year, are called cosmic twins. he problem-setter thinks that the probability of existence of cosmic twins in group of $P$ people is relatively high, based on the number of cosmic twins found in SBU. Your task is to calculate this probability and verify his conjecture.

ورودی🔗

The input contains two space separated integers $P, D$ – the number of people and the number of days in a year respectively.

$1 \leq P, D \leq 400$

خروجی🔗

Print a number in a line indicating the probability of existence of at least one pair of cosmic twins in the group.

The result should be printed with exactly 6 digits after decimal point.

مثال‌ها🔗

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

2 2

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

0.500000

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

22 365

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

0.475695

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

23 365

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

0.507297

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

Farshid loves to write scientific papers, even if there is nothing to write paper about. In one of his latest papers he introduced a new sorting algorithm called FS-Sort. In this sort only one operation is available and that is you can swap two adjacent numbers. If you think for a while, you will see that it is always possible to sort any array of numbers in this way. An array of integers will be given. Now using the above approach he wants to sort the numbers in the ascending order. You have to help him find out the minimum number of operations required. For example, to sort ‘1 2 3’ we need no operation. However sorting ‘2 3 1’ requires at least 2 operations.

ورودی🔗

The first line of the input contains a positive integer $N$. In next line there will be $N$ space separated integers denoting the elements of the array.

$1 \leq N \leq 2000$

خروجی🔗

Print the minimum swap operations required to perform sorting.

مثال‌ها🔗

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

3
1 2 3

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

0

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

3
2 3 1

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

2

• First you should swap 1 with 3.
• Then you should swap 1 with 2.

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

3
2 2 2

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

0

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

Do you know Jack-Jack? He is the youngest child of Parr family. The Parr family consists of Bob, Helen, Violet, Dashiell, and Jack-Jack. They are all characters of the “The Incredibles Movie”. Jack-Jack has many superpowers. Some of them are still not discovered yet. Recently, Helen saw Jack-Jack playing with matrices.

Jack-Jack thinks each cell of a matrix is powerful if it has three neighbors, which sum of their values is a power of two. Two cells are neighbors if and only if they share a side or corner. Jack-Jack is superhero, he is not a programmer. Can you count the number of powerful cells of the matrix for him?

ورودی🔗

The first line of input contains two space separated integers $N$, $M$ – the number of rows and the number of columns of the matrix.

$1 \leq N, M \leq 1000$

In each of the next $N$ lines, there are $M$ space-separated integers each representing a cell of the matrix. The value each cell is a non-negative integer that does not exceed $10^6$.

خروجی🔗

For each test, print a single integer, the number of powerful cells in the matrix.

مثال‌ها🔗

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

4 3
3 3 3
3 3 4
1 1 1
1 1 1

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

3

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

1 1
3

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

0

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

UEFA Champions League is the most prestigious annual sport competition in the world. In this competition, European clubs are divided into 8 groups of 4 teams.

In group stage, teams are ranked according to some specific rules. For example Team A will be ranked above Team B if:

• Team A has more points than Team B.
• If their points are equal, Team A has higher goal difference than Team B.
• In case of tie in all previous cases, Team A has scored more goals than Team B.
• In case of tie in all previous cases, Team A has scored more Away Scored Goals than Team B.

It is guaranteed that there won’t be a tie after these rules.

Your task is to write a program to determine the group leaders (top 2 teams of each group) based on their results.

ورودی🔗

The input is describing 12 games which are played between teams of a group. Each line describes a game and its result. The length of each line doesn’t exceed 25.

The format of each line is: HomeTeamName HomeTeamGoals vs. AwayTeamGoals AwayTeamName

Teams’ names consist of English letters and space character.

The team with more scored goals wins the game and receives 3 points. In case of draw, both teams receive 1 point.

• $GoalDifference = ScoredGoals - RecievedGoals$
• Away Goals = Number of goals scored (being away team)

خروجی🔗

Print the names of first team and the second team in the appropriate order. They must be printed in separate lines.

مثال‌ها🔗

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

Man Utd 8 vs. 2 Arsenal
Lyon 1 vs. 2 Man Utd
FC Barca 0 vs. 0 Lyon
FC Barca 5 vs. 1 Arsenal
Man Utd 3 vs. 1 FC Barca
Arsenal 6 vs. 0 Lyon
Arsenal 0 vs. 0 Man Utd
Man Utd 4 vs. 2 Lyon
Arsenal 2 vs. 2 FC Barca
Lyon 0 vs. 3 FC Barca
Lyon 1 vs. 0 Arsenal
FC Barca 0 vs. 1 Man Utd

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

Man Utd
FC Barca

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

Every contest needs a judge. You are assigned to judge the Tic-Tac-Toe (aka XO) contest in the SBU. Tic-Tac-Toe judges usually have two major responsibilities. Their responsibilities consist of verifying movements’ correction and declaring the result when the game is over.

In this problem you are going to determine the state of a Tic-Tac-Toe game. Player ‘X’ always plays first and the players play in turns.

ورودی🔗

The input consists of three lines. Each line describes a row by 3 characters. The characters can be X, O, and ?. Character ? denotes an empty cell.

خروجی🔗

• Print X if player X has won the game in the given input.
• Print O if player O has won the game in the given input.
• Print Unfinished if the game is not finished yet.
• Print Draw, if the game is finished and none of them won the game.
• Print Invalid if the description is not valid.

مثال‌ها🔗

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

XOX
OXO
??X

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

X

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

O??
???
???

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

Invalid

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

OOO
??X
XX?

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

O

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

???
???
???

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

Unfinished

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

OXO
XXO
XOX

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

Draw

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

There are $N$ circles which their centers lie on the Ox axis. Given the coordinates of their centers and their radius, find the number of regions they create on the plane.

ورودی🔗

The input starts with a line containing a single integer $N$ – the number of circles. Each of the following $N$ lines

$1 \leq N \leq 2000$

consist of two space separated integers $c_i$ and $r_i$ which denote the $i$’th circle’s $x$-coordinate and its radius

$-10^6 \leq c_i \leq 10^6$ $1 \leq r_i \leq 10^6$

respectively.

خروجی🔗

Print a single integer in a line, denoting the number of regions on the plane.

مثال‌ها🔗

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

1
0 3

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

2

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

2
0 3
0 3

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

2

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

2
0 3
2 2

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

4

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

2
-3 3
3 3

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

3

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

SBU Newbies Contest is the oldest annual contest in Computer Science and Engineering department. It is usually held on the second week of “Esfand”. There are many dedicated students who work voluntarily to prepare the contest. These students are divided into 3 groups and they take the tasks based on their group.

The first group of the students are the executive staff. They prepare the contest area, provide meals, do the registration, and many more things!! The second group of the students are the technical staff. They provide a secure network for the contest and setup the online judge. The last group is the scientific group. They write and prepare the problems, generate test cases, and verify the solutions.

This problem is written based on one of the challenges that technical staff faced during the preparation of the contest this year. As you may know, an official contest should strictly prohibit the use of internet during the contest. Trying to solve this problem, the technical staff should gather the cellphones before the contest or use mobile phone jammers in the contest area. Additionally, they should provide a network which restricts contestants’ internet access. After many hours of discussion and crowd-testing, they decided to configure a single router in the SBU and disconnect it from the internet.

The routers structure in the SBU network can be described as a rooted tree. Each router receives the internet from its parent router and will provide the internet for its children. When the technical team configure a router, all the routers in its subtree (including itself) would be disconnected from the internet, but the local connection is still available.

Given the routers which should be disconnected from internet and the structure of the SBU network, find the router which should be configured, in order to disconnect all the given routers from the internet.

If multiple answers exist, print the one which is the farthest from the root of the tree. We don’t want the whole university to lose internet access. You can assume that Router 1 is the root of the network.

ورودی🔗

The first line of the input contains two space-separated integers $N$ and $K$ indicating the number of routers in the network and the number of routers which should be disconnected.

$1 \leq N, K \leq 10^5$

Each of the next $N - 1$ lines describe a connection by giving two space separated integers $u_i, v_i$ – the number of two routers operating as end-points of the connection.

The last line of the input contains $K$ space-separated distinc integer $a_i$ denoting the routers which should be disconnected from the internet.

$1 \leq a_i, u_i, v_i \leq 10^5$

خروجی🔗

Print the lowest router which should be disconnected from the internet in order to avoid internet usage during the contest.

مثال‌ها🔗

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

7 2
1 2
2 7
3 4
2 4
4 5
6 4
6 7

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

2

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

4 1
1 3
2 3
2 4
3

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

3

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

As everybody may know, Reza Shiri is our favorite artist. SBU students love his songs and they share them in their telegram groups all the time. In the Newbies 2018, the hardest problem of the contest was about Reza Shiri’s concert.

This year you are going to help us with purchasing Reza Shiri’s songs. Since we love Reza Shiri and his songs, we never download his songs for free. Reza Shiri’s songs must be purchased from the authorized stores.

Going to the iTunes store, each song can be purchased in one of the following ways:

• Buying the whole album
• Buying a single track

Well, everybody wants to purchase all of the available songs and albums. Unfortunately, having a limited budget, one may not be able to afford buying all of the songs. There are $N$ songs and $M$ albums available. Each song belongs to exactly one Album. Songs are numbered from $1$ to $N$. Albums are numbered from $1$ to $M$.

ورودی🔗

The first line of input contains three space-separated integers $N, M,$ and $P$ – denoting the number of songs, the number of albums, and our budget respectively. The description of songs is given in the following $N$ lines.

$1 \leq N, M, P \leq 1000$

Each line consists of 2 space-separated integers $a_i$ and $p_i$ – indicating the album containing this song and the price of this song.

In the next line of each test, there are $M$ space separated integers $b_1, b_2, \dots, b_m$ – denoting the price of the albums.

$1 \leq b_i, p_i \leq 10^9$ $1 \leq a_i \leq M$

خروجی🔗

Print the maximum number of songs that we can afford to buy.

مثال‌ها🔗

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

5 2 10
1 3
1 4
1 2
2 1
2 2
7 4

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

5

In the first test case, it is the best to buy the first album and two songs from the second album.

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

5 2 10
1 3
1 4
1 2
2 1
2 2
8 4

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

4

In the second test case, it is the best to buy the first album and one song from the second album.

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

5 3 7
1 2
1 2
1 2
1 2
2 2
6 1 3

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

5

In the third test case, it is the best to buy the first and the second album.

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

Everyday Space Runners go to the Enghelab Sports Complex for a morning run in the “Health Road”. They love to exercise and workout. The only thing bothering them is that some people are not punctual and they do not arrive on-time. After days of discussion, they decided to run individually.

They run along on the axis Ox. For every person there are three parameters characterizing their behavior: $t_i, s_i, f_i$ — the moment of time when the $i$-th person starts running, the start point and the end point of the run respectively. Each person moves in a straight line along the road from $s_i$ to $f_i$ with a constant speed of either $1$ or $-1$ depending on the direction.

If two or more persons meet at the health road (they are at the same point at the same time, no matter which directions they are going) they all greet each other. Like in the normal life, every pair of people greet each other at most once.

You task is to calculate for every person how many people she greets while running along the health road. Please, pay attention to the fact that $i$-th person may meet and greet any other person at points $s_i$ and $f_i$.

After a person achieves the destination point $f_i$ she moves out of the road and cannot greet anyone else. The same rule applies to the start of the run: a person cannot greet anyone until she appears on the road.

ورودی🔗

At the first line of the input, integer $N$ is given – number of groups. In the each of next $N$ lines, there are three space-separated integers $t_i, s_i, f_i$.

$1 \leq N \leq 50$ $1 \leq t_i, s_i, f_i \leq 10^9$$s_i \neq t_i$

خروجی🔗

The single line of the output should contain a sequence of $n$ integers $r_1, r_2, \dots, r_n$ separated by a space, where $r_i$ denotes the number of times which the $i$-th person greets other people while running along the health road.

مثال‌ها🔗

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

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

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

2 2 2 0

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

4
10 1 1000000000
10 1000000000 1
5 1 3
8 5 3

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

1 1 0 0

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

Our planet Earth has got two significant movements which are called Earth’s rotation and Earth’s revolution. Earth rotates along its own axis every day, which is why this movement is called the Earth’s Rotation. Furthermore, the movement of earth around the sun is called the Earth’s revolution which takes one year to complete.

The Earth’s movement trajectory around the Sun, which is called orbit, is not a perfect circle. According to the observations, the Earth’s orbit is elliptical which means that our distance from the Sun varies by day.

There is a common misbelief that the seasons appear as a consequence of the Earth’s varying distance from the Sun. This hypothesis can be simply rejected by the fact that we can observe different seasons in different countries at the same time. For example, people in France celebrate the Christmas in the cold and snowy weather, but people in Australia celebrate the Christmas by the beach!

Earth’s rotation movement is the reason to the climate change and the seasons. It will affect the northern and southern hemisphere differently. For example, in Australia spring consists of September, October, and November. Summer which is hottest season of the year includes December, January, and February. Autumn comprises March, April, and May. And finally, winter consists of June, July, and August. In this problem you are asked to write a program to calculate the season in Australia based on the given month.

ورودی🔗

The input contains a string which is the name of the given month written in lowercase English letters.

خروجی🔗

Print the season which contains the given month in lowercase English letters.

مثال‌ها🔗

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

january

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

summer

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

september

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

spring

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

After burning down their own house, Pat & Mat decided to play a game in order to forget their misery. The rules of the game are simple. There are $N$ stones on the table. Pat & Mat play alternatively. Pat plays first. At each turn, they can either remove $1$ or $2$ or $3$ or $4$ or $5$ or $6$ stones from the table. The player who can't perform any legal move in his turn, will lose the game. Given the number $N$, determine which of the brothers will win the game if they play optimally.

ورودی🔗

The input consists of a single integer $N$ denoting the number of stones. $1 \leq N \leq 10^6$

خروجی🔗

Print the name of the winner in a single line.

مثال‌ها🔗

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

6

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

Pat

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

2233

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

Mat

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

A sequence is called $N$-Bonnaci if it is calculated from its previous $N$ elements. An XOR $N$-Bonacci sequence can be formulated in the following format:

$F(K) = F(K - 1) \oplus F(K - 2) \oplus \dots \oplus F(K - N + 1) \oplus F(K - N)$

Here $\oplus$ denotes bitwise XOR operation. Newbies jury have recently found an interesting sequence which is obtained from the XOR operation on the first $K$ elements of the XOR $N$-Bonacci sequence:

$S(K) = F(1) \oplus F(2) \oplus \dots \oplus F(K - 1) \oplus F(K)$

It can be proven that for calculating all of the $N$-Bonacci Numbers, only the first $N$ elements are need to be known. Given the first $N$ numbers of the XOR $N$-Bonacci sequence, your task is to calculate $S(K)$ for $Q$ queries.

ورودی🔗

The first line of the input contains two space separated integers $N$ $Q$. The second line contains $N$ space separated integers denoting $F(1), F(2), \dots , F(N)$ respectively. Each of the next $Q$ lines, describes a query by giving an integer $K$.

$1 \leq N, Q \leq 10^5$

خروجی🔗

For each query, you should print the $S(K)$ in a line.

مثال‌ها🔗

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

3 4
0 1 2
7
2
5
1000000000

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

3
1
0
0