A – AbulHassan’s Quest

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Farshad wants to do research on friendship relationships between students of the Shahid Beheshti University, so he has decided to model these relations with a graph. In this graph students are numbered from $1$ to $n$, every student is represented by a single node, and an edge between node $i$ and node $j$ means that student number $i$ and student number $j$ are friends with each other. If $i$ is friend with $j$, then $j$ is also friend with $i$, and of course no student can be friend with himself. Farshad is interested in doing research on friendship groups (two students $i$ and $j$ are in a friendship group if and only if $i$ and $j$ are directly friends with each other or can indirectly connect to each other through friendship links). Farshad wants to count the number of friendship groups and the number of members each group has. Then HP comes and asks him $q$ questions about the number of groups that exist in a particular size range. Each question is of the form $(l, r)$, which means HP wants to know the number of all groups that have size greater or equal to $l$ and less than or equal to $r$. Help Farshad answer these $q$ questions. # ورودی The first line of input contains T, the number of test cases. $$1≤T≤10$$ The first line of each test contains three space separated integers $n, m, q$ where $n$ is the number of students, $m$ is the number of friendship relations and $q$ is the number of questions HP will ask. $$1 \leq n, m, q \leq 10^5$$ Then the next $m$ lines each contain two space separated integers $u, v$. which means student number $u$ and student number $v$ are friends with each other. Then $q$ lines follow, each containing two space separated integers $l$ and $r$ representing the questions HP will ask. $$1 \leq l \leq r \leq n$$ # خروجی The output should consist of $q$ lines where line number $i$ contains the answer to the $i$’th question. # مثال‌ها ## ورودی نمونه ۱ ``` 1 6 4 2 1 2 3 4 4 5 3 5 2 4 3 3 ``` ## خروجی نمونه ۱ ``` 2 1 ```

B – Farshad’s Research

C – Shortest but Hardest

D – Divisible Strings

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *Who do you like more, Colonel or Morteza? She asks.* *Colonel. everybody, but Erfan, replies. (yes, even Morteza)* Erfan is still faithful to Morteza so he decides to be absolutely sure about this matter of life or death. He knows that there’s an upcoming tennis match between Colonel and Morteza. He will therefore choose between them based on the result of the match. Due to the importance of the match, Colonel and Morteza are playing behind closed doors and Erfan is only be able to hear them from behind the walls. The sequence of the sounds that Erfan hears consist of the following: + `G`: Ball hits the ground + `R`: Ball hits a racket + `N`: Ball hits the net + `?`: Unknown. can be `G`, `R`, or `N` Erfan has written down the sequence of the sounds that he has heard. He wants to know who wins more games among all possible valid game sequences. He has seen them play before so he also knows how the game is played. He knows that a valid sequence consists of multiple consecutive valid scores and the player with the most scores wins a sequence. (Morteza wins the sequence in case of a tie in scores) In a valid score: + Always Colonel starts by serving (hits the ball). + ball hitting the net once, or the ground twice in a row ends the score. In the latter case the last player who has just hit the ball scores. It’s the other way around in the former case. This can happen after the serves and after regular hits. (That means in case of `N`, the ball hits the net and simply falls back in the hitter’s side, causing him to lose a point) + a player can hit the ball if it has not yet hit the ground, or if it has hit the ground once. In case of answering a serve, the player can’t hit the ball in the air (this will be an invalid sequence) and will have to let the ball hit the ground once. + The ball will never hit the net right after it has hit the ground. Oh and In case of a tie in the number of possible game sequences won, Dog ate… Let’s say Morteza wins again. It is guaranteed that at least one valid sequence exists. # ورودی The first line of input contains $T$, the number of test cases. $$1 \leq T \leq 50$$ Each of the following $T$ lines contains a single string consisting of `G`, `R`, `N`, and `?`. $$length of each test case \leq 11$$ # خروجی For each test case If Morteza is the winner, output `Morteza to doost dashtani hasti`. Otherwise output `Nasirifar to doost dashtani hasti`. # مثال‌ها ## ورودی نمونه ۱ ``` 2 ??RG??? ??? ``` ## خروجی نمونه ۱ ``` Morteza to doost dashtani hasti Nasirifar to doost dashtani hasti ``` Here are all the valid sequences for the first test case (scores are separated by space for clarity): + `RGRGRGG` + Colonel $1$ : $0$ Morteza + `RNRGRGG` + Colonel $0$ : $2$ Morteza + `RGRGRRN` + Colonel $1$ : $0$ Morteza + `RN RGRRN` + Colonel $0$ : $2$ Morteza + `RGRGG RN` + Colonel $0$ : $2$ Morteza + `RN RGG RN` + Colonel $1$ : $2$ Morteza Morteza Wins in $4$ of the possible valid sequences, Colonel wins in $2$.

E – Tennis

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *Profiling: In software engineering, profiling ("program profiling", "software profiling") is a form of dynamic program analysis that measures, for example, the space (memory) or time complexity of a program, the usage of particular instructions, or the frequency and duration of function calls. Most commonly, profiling information serves to aid program optimization. Wikipedia* Arthur and Jacob are newly introduced to the programming world and they are trying hard for Newbies contest. Yesterday, they learned about recursive functions and Fibonacci sequence. They tried to implement the function themselves so they wrote the following code: ```cpp int fibonacci (int N) { if(N < 2) return N; return fibonacci(N - 1) + fibonacci(N - 2); } ``` But this program works slowly when $N$ is a large number. They traced the program and found the cause of this problem. Take a look at the following picture: ![توضیح تصویر](https://quera.org/qbox/view/Ra9sEDgmRf/F.png) If you want to calculate `Fibonacci(6)`, `Fibonacci(3)` will be calculated multiple times! They want to know how serious this problem can be, so they need a profiler to calculate such a thing for them. Your task is to provide the profiler which receives two integers $N, K$ and tells them if they call `Fibonacci(N)` how many times `Fibonacci(K)` will be calculated (according to their code). # ورودی The first line of input indicates the number of test cases (There will be at most 100 test cases) For each test case, there are two space-separated integers $N$, $K$ in a single line. $$0 \leq N, K \leq 10^5$$ # خروجی For each test case, print the number of times `Fibonacci(K)` will be calculated, if we call `Fibonacci(N)`. Since the result can be very large, print the result modulo $10^9 + 7$. # مثال‌ها ## ورودی نمونه ۱ ``` 5 6 6 6 3 6 2 100000 3 5 10 ``` ## خروجی نمونه ۱ ``` 1 3 5 855252772 0 ```

F – Profiling

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- The **International Mobile Equipment Identity** or **IMEI** /aɪˈmiː/ is a number, usually unique, to identify 3GPP and iDEN mobile phones, as well as some satellite phones. It is usually found printed inside the battery compartment of the phone, but can also be displayed on-screen on most phones by entering *#06# on the dialpad, or alongside other system information in the settings menu on smartphone operating systems. ![توضیح تصویر](https://quera.org/qbox/view/tV9q1q1psq/G_1.png) The IMEI number is used by a GSM network to identify valid devices and therefore can be used for stopping a stolen phone from accessing that network. For example, if a mobile phone is stolen, the owner can call their network provider and instruct them to blacklist the phone using its IMEI number. This renders the phone useless on that network and sometimes other networks too, whether or not the phone's subscriber identity module (SIM) is changed. The IMEI is only used for identifying the device and has no permanent or semi-permanent relation to the subscriber. Instead, the subscriber is identified by transmission of an International mobile subscriber identity (IMSI) number, which is stored on a SIM card that can in theory be transferred to any handset. However, many network and security features are enabled by knowing the current device being used by a subscriber. The IMEI (15 decimal digits: 14 digits plus a check digit) includes information on the origin, model, and serial number of the device. The model and origin comprise the initial 8-digit portion of the IMEI, known as the Type Allocation Code (TAC). The remainder of the IMEI is manufacturer-defined, with a Luhn check digit at the end. ![توضیح تصویر](https://quera.org/qbox/view/loaC5fe6be/G_2.png) New style IMEI code 49-015420-323751 has an 8-digit TAC of 49-015420. The last number of the IMEI is a check digit calculated using the Luhn algorithm, as defined in the IMEI Allocation and Approval Guidelines: + The Check Digit shall be calculated according to Luhn formula. The Check Digit is a function of all other digits in the IMEI. + The purpose of the Check Digit is to help guard against the possibility of incorrect entries to the CEIR and EIR equipment. + The presentation of the Check Digit both electronically and in printed form on the label and packaging is very important. Logistics (using bar-code reader) and EIR/CEIR administration cannot use the Check Digit unless it is printed outside of the packaging, and on the ME IMEI/Type Accreditation label. + The check digit is not transmitted over the radio interface, nor is it stored in the EIR database at any point. Therefore, all references to the last three or six digits of an IMEI refer to the actual IMEI number, to which the check digit does not belong. The check digit (Checksum or Luhn Checksum) is validated in three steps: 1. Starting from the right, double every other digit (e.g., 7 → 14). 2. Sum the digits (e.g., 14 → 1 + 4). 3. Check if the sum is divisible by 10. Conversely, one can calculate the IMEI by choosing the check digit that would give a sum divisible by 10. For the example IMEI 49015420323751? , ![توضیح تصویر](https://quera.org/qbox/view/tCk9YGtMtt/G_3.png) To make the sum divisible by 10, we set x = 8, so the complete IMEI become 490154203237518. Your task is simple, given a 14 digit IMEI, calculate its TAC and its check digit. # ورودی The first line of input indicates the number of test cases (There will be at most 20 test cases) For each test case, there is a 14-digit IMEI in a single line. # خروجی For each test case, print TAC and Checksum of given IMEI respectively in a single line. # مثال‌ها ## ورودی نمونه ۱ ``` 2 49015420323751 01234567890123 ``` ## خروجی نمونه ۱ ``` 49015420 8 01234567 7 ```

G – IMEI

!H – Fall in Love

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- There is an ancient saying that problem I is always one of the hardest problems in programming contests. Colonel believes the above ancient saying, but what are the probabilities that you’re writing the last problem of the problem set, and there is only one problem slot left, and you contact the contest coordinator to see if they can place your problem on slot I, and they respond with “I is the only remaining slot”? Lightning strike. Lightning strike indeed. BUT THIS IS LAST YEAR’S STORY. This time Colonel put the dibs on writing problem I from day 1. Colonel and Erfan were walking in TFB2DW (The Frictionless Bisected 2 Dimensional World), talking about this year’s hardest problem, each of them holding a 2d tennis ball. They suddenly thought whether or not the balls will collide at some point if they were to throw them. What makes the question a little harder though, is that there is an infinite wall in the TFB2DW (hence the name). If any of the 2d balls happen to touch the infinite wall, they will behave in the normal way that 2d balls behave when touching infinite walls. (Really. What else did you expect?) And you know what? We’re asking you to give them the answer. What a surprise. And here’s the “science” if you’re into that kind of stuff. There is no friction in our case, so $\theta_i$ will be equal to $\theta_r$. ![توضیح تصویر](https://quera.org/qbox/view/ZStduqCkHP/I.png) # ورودی There are multiple test cases in the input. The first line contains $T$, the number of test cases. $T$ test cases will then follow, Each of them contains real numbers defining the starting point of each of the balls, it’s moving direction, radius, and velocity(units/second), and two points which uniquely define the infinite wall. Here is the placeholder for one of the test cases in the input: + ball1StartX ball1StartY + ball1DirectionX ball1DirectionY + ball1Velocity ball1Radius + ball2StartX ball2StartY + ball2DirectionX ball2DirectionY + ball2Velocity ball2Radius + wallPoint1X wallPoint1Y + wallPoint2X wallPoint2Y All of the numbers in the input are below $100$. Also it is guaranteed that balls won’t collide anytime after the $10^{12}$ th second, won’t share any point with the infinite wall or each other in the initial position, and won’t be immobile. # خروجی For each test case, if the two balls collide at some point, output a line containing `Lightning strike`, otherwise output `Not even a spark`. # مثال‌ها ## ورودی نمونه ۱ ``` 2 -20 4 1 -1 1 1 10 4 -1 -1 10 1 0 0 10 0 -20 4 1 -1 10 1 10 4 -1 -1 10 1 0 0 10 0 ``` ## خروجی نمونه ۱ ``` Not even a spark Lightning strike ``` In the first case, the second ball having a speed equal to ten times of that of the first ball will leave the scene in a blink of an eye. In the same setup but with equal velocities (second test case), the two balls will collide after hitting the wall.

I – Lightning Strike

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- One of the services that a reliable network provides is Jitter Minimization. Let me explain some more. In network communication, one node is sender and the other one is receiver. Also data is carried in units called packets. So, sender sends (data) packets to receiver. *Jitter Minimization: This service guarantees that the amount of time between the transmission of two successive packets at the sender is equal to the amount of time between their receipt at the destination.* Karen is a network administrator at Computer Science and Engineering Faculty in SBU. She wants to verify whether the network is reliable enough for Newbies2018 or not. So she sent $N$ packets from one node to another one, and wrote down the transmission and receive time for each packet on a single piece of paper. But, she forgot to write whether each entry was transmission time or receive time!! Time to help, you are given a list of transmission and receive time of $N$ packets. Calculate how long did it take for each packet to reach the receiver (from sender), or state that the network isn’t reliable. # ورودی The input file contains multiple test cases. (Number of tests doesn’t exceed $100$) For each test case, first line contains a single integer $N$ – The number of packets. $$1 \leq N \leq 600$$ The second line consists of $2N$ distinct integers $t_i$ – the entries on Karen’s paper $$0 \leq t_i \leq 10^9$$ The input terminates with the $N = 0$, this case should not be processed. # خروجی For each test case print the minimum possible time between send and receive of packets, or print `Unreliable Network` in a single line. # مثال‌ها ## ورودی نمونه ۱ ``` 3 1 3 5 6 4 7 2 1 3 4 6 3 1 2 3 4 12 15 0 ``` ## خروجی نمونه ۱ ``` 2 2 Unreliable Network ``` In the first test case: + Packet $1$ is sent at $t = 1,$ and is received at $t = 3 \to$ Time between send and receive $= 2$ + Packet $2$ is sent at $t = 4,$ and is received at $t = 6 \to$ Time between send and receive $= 2$ + Packet $3$ is sent at $t = 5,$ and is received at $t = 7 \to$ Time between send and receive $= 2$ All transmission times are equal to $2,$ so network is reliable.

J – Jitter Minimization

K – Traffic Lights

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *(Shoma Khoonatoon Moorche Daare?)* A straight tunnel without branches is crowded with busy ants coming and going. Some ants walk left to right and others right to left. All ants walk at a constant speed of $1$ cm/s. When two ants meet, they try to pass each other. However, some sections of the tunnel are narrow and two ants cannot pass each other. When two ants meet at a narrow section, they turn around and start walking in the opposite directions. When an ant reaches either end of the tunnel, it leaves the tunnel. The tunnel has an integer length in centimeters. Every narrow section of the tunnel is integer centimeters distant from the both ends. Except for these sections, the tunnel is wide enough for ants to pass each other. All ants start walking at distinct narrow sections. No ants will newly enter the tunnel. Consequently, all the ants in the tunnel will eventually leave it. Your task is to write a program that calculates the summation of all distances walked by the ants. Figure shows the movements of the ants during the first two seconds in a tunnel $6$ centimeters long. Initially, three ants, numbered $1, 2,$ and $3,$ start walking at narrow sections, $1, 2,$ and $5$ centimeters distant from the left end, respectively. After $0.5$ seconds, the ants $1$ and $2$ meet at a wide section, and they pass each other. Two seconds after the start, the ants $1$ and $3$ meet at a narrow section, and they turn around. Following figure corresponds to the first dataset of the sample input. ![توضیح تصویر](https://quera.org/qbox/view/rwbBtprYqs/L.png) # ورودی The input consists one or more datasets. Integer $t$ at the first line indicates the number of datasets. $$1 \leq t \leq 100$$ There is a string $s$ in each dataset which shows the initial position of ants. $s_i$ indicates the initial state of tunnel at the position $i$. `<` correspond to an ant which is going to left, `>` correspond to an ant which is going to right and `.` means there is no ant at that position. $$1 \leq |s| \leq 1000$$ # خروجی For each dataset, print an integer: the summation of total distance walked by the ants, until they exit. # مثال‌ها ## ورودی نمونه ۱ ``` 5 .><..<. .......> .<...... ..... >< ``` ## خروجی نمونه ۱ ``` 12 0 1 0 2 ```