---------- A rectangular cake is transported via a truck to a restaurant. On the way to the destination, the truck hits a pothole, which shatters the cake in $N$ perfectly rectangular pieces of width $w_i$ and length $l_i$, for $1 \le i \le N$. At the destination, the damage is assessed, and the customer decides to order a replacement cake of the same dimensions. Unfortunately, the original order form was incompletely filled and only the width $W$ of the cake is known. The restaurant asks for your help to find out the length $L$ of the cake. Fortunately, all pieces of the cake have been kept. # Input The input consists of the following integers: - on the first line, the width $W$ of the cake; - on the second line, the number $N$ of shattered pieces; - on each of the next $N$ lines, the width $w_i$ and length $l_i$ of each piece. $$1 \le N \le 5000000$$ $$1 \le W, L \le 10000$$ $$1 \le w_i, l_i \le 10000$$ # Output The output should be the integer $L$. ## Sample Input ``` 4 7 2 3 1 4 1 2 1 2 2 2 2 2 2 1 ``` ## Sample Output ``` 6 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> برای حل این سوال از مساحت کیک‌های خورد شده استفاده می‌کنیم. به وضوح مساحت کیک بزرگتر برابر است با مجموع مساحت‌های کیک‌های خرد شده. حال می‌توانیم از جمع مساحت مستطیل‌های ورودی، مساحت مستطیل بزرگتر را به دست آورده و با تقسیم آن بر $W$ که یکی از ابعاد مسطیل است، مقدار $L$ که همان بعد دیگر مستطیل است، به دست می‌آید. </details>

---------- Spike is a bounty hunter and he is currently tracking a criminal! To investigate he uses his spaceship, the Swordfish II, and travels to $N$ different places on 2D Euclidean space before returning to his crew at the starting location with all the information he has gathered. The starting location is the leftmost place (with the lowest $x$-coordinate) and Spike wants to travel to every other place before returning. However space fuel costs a lot of Woolongs and Spike would rather spend his money on special beef with bell peppers. Therefore he wants to travel the minimum possible distance. On top of that he is being chased by the Red Dragon crime syndicate. To make sure they don’t catch him he can only visit places in increasing order of their $x$-coordinate until he reaches the rightmost place (with the largest $x$-coordinate), then he can turn around and visit places in decreasing order of their $x$-coordinate until he reaches his starting location again. # Input The input starts with an integer $T$ ($1 \le T \le 100$) specifying the number of test cases that follow. Each test case consists of an integer $N$ ($2 \le N \le 512$) specifying the number of places in the tour. The coordinates of these places are given as integers in the next $N$ lines, $x$-coordinate first, $y$-coordinate second ($0 \le x, y \le 5000$). The places are given in ascending order of the $x$-coordinate. Every place has a unique $x$-coordinate. # Output For each test case, output on a single line the minimum travel distance needed to complete the tour. Your output should have an absolute or relative error of at most $10^{-2}$. ## Sample Input ``` 2 5 0 1 1 2 2 0 3 2 4 1 3 100 1 200 1 300 1 ``` ## Sample Output ``` 9.300563079746 400 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> در واقع سوال از ما می‌خواهد که به غیر از عنصر اول و آخر بقیه را به دو زیر دنباله افراز کنیم،‌ سپس هر دو عنصر اول و آخر به اول و آخر هر دو دنباله اضافه کنیم و در نهایت طولی که برای پیمودن این دو دنباله نیاز است را با هم جمع بزنیم. به طور مشخص تعداد حالت‌های افراز دنباله‌ی اصلی به دو دنباله بسیار زیاد است و نمی‌توان روی همه‌ی حالات رفت ولی اگر یک ترتیب نظام‌مند برای حرکت روی دنباله‌ و افراز آن به دو دنباله‌ی مشخص داشته باشیم، می‌توانیم از برنامه‌نویسی پویا برای به دست‌ آوردن پاسخ استفاده کنیم. </details> ---------------------------------- <details class="blue"> <summary> راهنمایی ۲ </summary> از پایین به بالا (به صورت صعودی بر حسب $x$) حرکت می‌کنیم و اندیس آخرین نقطه‌ی هر دو دنباله را در استیت $dp$ ذخیره کرده و عنصر جدید را به یکی از آن‌ها اضافه می‌کنیم. به طور دقیق‌تر، $dp[i][j]$ که در آن $j < i$ است را بدین صورت تعریف می‌کنیم: کل $i$ نقطه‌ی اول را در نظر گرفته و می‌دانیم که دنباله‌ای که با شروع از نقطه‌ی اول به نقطه‌ی آخر می‌رسد از ما عبور می‌کند و همچنین آخرین نقطه‌ای (نقطه‌ای که بزرگترین $x$ را دارد) که در مسیر برگشت قرار دارد، $j$ می‌باشد. حال با رعایت تمام این شرایط، حداقل هزینه‌ی رسیدن از نقطه‌ی شروع به راس $i$ام به علاوه‌ی حداقل هزینه برای رسیدن از نقطه‌ی $j$ام به نقطه‌ی شروع را داخل $dp[i][j]$ می‌ریزیم. استیت‌های $dp$ از $O({n^2})$ است و از هر استیت هم دقیقا دو نفر مشخص اپدیت می‌شوند. به طور دقیق‌تر، $dp[i][j]$ پس از اضافه کردن یک عنصر به آن، یا به استیت $dp[i + 1][j]$ می‌رود و یا به $dp[i + 1][i]$ (می‌توانیم جای دو دنباله را عوض کنیم چون طول را چه از اول به آخر و چه برعکس به دست بیاوریم با هم برابر است). بنابراین در مجموع الگوریتم ما از $O({n^2})$ می‌باشد. در نهایت نیز برای به دست‌آوردن به ازای همه‌ی $1 <= j <= n$ مقدار جواب را با مقدار $dp[n][j] + dis(n, j)$ مینیمم می‌گیریم که در آن $dis(i, j)$ نمایانگر فاصله‌ی اقلیدسی نقطه‌ی $i$ام و نقطه‌ی $j$ام می‌باشد. </details>

---------- To guard the art jewelry exhibition at night, the security agency has decided to use a new laser beam system, consisting of sender-receiver pairs. Each pair generates a strip of light of one unit width and guards all objects located inside the strip. Your task is to help the agency and to compute for each exhibition room the minimum number of sender-receiver pairs which are sufficient to protect all exhibits inside the room. Any room has a rectangle shape, so we describe it as an $[0, N] × [0, M]$ rectangle in the plane. The objects we need to guard are represented as points inside that rectangle. Each sender is mounted on a wall and the corresponding receiver on the opposite wall in such a way that the generated strip is a rectangle of unit width and length either $N$ or $M$. Since the new laser beam system is still not perfect, each sender-receiver pair can only be mounted to generate strips the corners of which have integer coordinates. An additional drawback is that the sender-receiver pairs can protect only items inside the strips, but not those lying on their borders. Thus, the security agency arranged the exhibits in such a way that both coordinates of any point representing an exhibit are non-integers. The figure below (left) illustrates eight items arranged in $[0, 4] × [0, 4]$ (the second sample input). In the room, up to eight sender-receiver pairs can be mounted. The figure to the right shows an area protected by three sender-receiver pairs.  # Input The input starts with the number of exhibition rooms $R \le 10$. Then the descriptions of the $R$ rooms follow. A single description starts with a single line, containing three integers: $0 < N \le 100$, $0 < M \le 100$, specifying the size of the current room and $0 < K \le 104$, for the number of exhibits. Next $K$ lines follow, each of which consists of two real numbers $x, y$ describing the exhibit coordinates. You can assume that $0 < x < N$, $0 < y < M$ and that $x$ and $y$ are non-integer. # Output For every room output one line containing one integer, that is the minimum number of sender-receiver pairs sufficient to protect all exhibits inside the room. ## Sample Input ``` 2 1 5 3 0.2 1.5 0.3 4.8 0.4 3.5 4 4 8 0.7 0.5 1.7 0.5 2.8 1.5 3.7 0.5 2.2 3.6 2.7 2.7 1.2 2.2 1.2 2.7 ``` ## Sample Output ``` 1 3 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> در ابتدا گرافی دو بخشی تشکیل می‌دهیم که در یک بخش رئوس متناظر آن سطرها و در بخش دیگر رئوس متناظر ستون‌ها قرار دارند. حال بین راس $x$ از بخش سطرها و راس $y$ از بخش ستون‌ها یال می‌گذاریم اگر و تنها اگر در خانه‌ی تقاطع سطر $x$ام و ستون $y$ام جواهری ظاهر شده باشد. اکنون مسئله معادل این است که در گراف فعلی اندازه‌ی پوشش راسی کمینه را در بیاوریم. برای آشنایی با پوشش راسی می‌توانید از [این لینک](https://en.wikipedia.org/wiki/Vertex_cover) استفاده کنید. </details> ---------------------------------- <details class="blue"> <summary> راهنمایی ۲ </summary> طبق قضیه‌ی konig-egervary در نظریه‌ی گراف‌، می‌دانیم که اندازه کوچک‌ترین پوشش راسی با اندازه بزرگ‌ترین تطابق در گراف دو بخشی برابر است. در [این لینک](https://en.wikipedia.org/wiki/Matching_(graph_theory) می‌توانید بیشتر با تطابق آشنا شوید. بنابراین از آن‌جایی که گرافی که ما تشکیل دادیم دو بخشی است،‌ می‌توانیم با یافتن اندازه‌ی تطابق بیشینه به جواب مسئله دست پیدا کنیم. </details>

---------- Gunnar and Emma play a lot of board games at home, so they own many dice that are not normal 6-sided dice. For example they own a die that has $10$ sides with numbers $47, 48, ..., 56$ on it. There has been a big storm in Stockholm, so Gunnar and Emma have been stuck at home without electricity for a couple of hours. They have finished playing all the games they have, so they came up with a new one. Each player has $2$ dice which he or she rolls. The player with a bigger sum wins. If both sums are the same, the game ends in a tie. Given the description of Gunnar’s and Emma’s dice, which player has higher chances of winning? All of their dice have the following property: each die contains numbers $a, a + 1, ..., b$, where $a$ and $b$ are the lowest and highest numbers respectively on the die. Each number appears exactly on one side, so the die has $b - a + 1$ sides. # Input The first line contains four integers $a_1, b_1, a_2, b_2$ that describe Gunnar’s dice. Dice number $i$ contains numbers $a_i, a_i + 1, ..., b_i$ on its sides. You may assume that $1 \le ai \le bi \le 100$ . You can further assume that each die has at least four sides, so $a_i + 3 \le b_i$ . The second line contains the description of Emma’s dice in the same format. # Output Output the name of the player that has higher probability of winning. Output "Tie" if both players have same probability of winning. ## Sample Input 1 ``` 1 4 1 4 1 6 1 6 ``` ## Sample Output 1 ``` Emma ``` ## Sample Input 2 ``` 1 8 1 8 1 10 2 5 ``` ## Sample Output 2 ``` Tie ``` ## Sample Input 3 ``` 2 5 2 7 1 5 2 5 ``` ## Sample Output 3 ``` Gunnar ``` <details class="blue"> <summary> راهنمایی ۱ </summary> برای اینکه بتوانیم بفهمیم که شانس کدام یک از طرفین برای برد بیشتر است، باید امید ریاضی جمع اعداد ظاهر شده بر روی تاس‌های آن‌ها را پس از پرتاب به دست بیاوریم. (برای آشنایی با مفهوم امید ریاضی به [این لینک](https://en.wikipedia.org/wiki/Expected_value) مراجعه نمایید) </details> ---------------------------------- <details class="blue"> <summary> راهنمایی ۲ </summary> می‌دانیم که امید ریاضی جمع اعداد ظاهر شده بر روی تاس‌ها برابر است با جمع امید ریاضی اعداد ظاهر شده بر روی تاس‌ها. بنابر این حال کافی است به ازای هر تاس مستقلا امید ریاضی عدد ظاهر شده بر روی آن را به دست آورده و سپس این دو مقدار را با جمع کنیم تا امید ریاضی امتیاز یک نفر به دست بیاید. (منظور از امتیاز همان مقداری است که در نهایت بین دو نفر با هم مقایسه می‌شود) حال می‌خواهیم برای یک تاس که عددی رندوم از $a$ تا $b$ به ما می‌دهد،‌ امید ریاضی عدد ظاهر شده بر روی آن‌ را به دست آوریم. مقدار $s$ را برابر تعداد اعداد بر روی تاس (همان $b - a + 1$) قرار دهید. حال هر کدام از اعداد روی تاس به احتمال $\frac{1}{s}$ ظاهر می‌شوند. پس امید ریاضی من برابر است با حاصل ضرب $\frac{1}{s}$ در جمع اعداد موجود بر روی تاس. می‌دانیم فرمول جمع اعداد $a$ تا $b$ در ریاضیات برابر است با $\frac{(b + a) s}{2}$ که اگر این عبارت را در $\frac{1}{s}$ ضرب کنیم، حاصل که همان امید ریاضی مد نظر ماست، برابر $\frac{b + a}{2}$ می‌شود. بنابر این امید ریاضی امتیاز یک نفر برابر است با جمع $\frac{b + a}{2}$ به ازای هر دو تاس آن. در نهایت نیز کسی که امید ریاضی امتیازش بیشتر باشد، برنده‌ی بازی‌ است و اگر این مقدار مساوی بود، احتمال مساوی این دو نفر بیشتر از احتمال برد آن‌هاست. </details>

---------- Per is repairing roads. The job is concentrated on roads with one lane in each direction. Thus, when Per closes down the lane in one direction, all traffic has to go through the other lane. This is done by allowing only one direction of travel at any time. Per is often assigned the task of directing the traffic through this lane. No car drives before being given a “go” signal from Per, and all the cars drive through the maintained segment at the same speed. Because there is only one lane, cars in one direction must leave the segment before cars in the other direction can enter. For safety reasons, cars driving in the same direction have to keep a distance of at least $3$ seconds between each other. For example, if cars $A$ and $B$ arrive at the west endpoint at second $10$, Per can let them go at earliest second $10$ and $13$ in the order they arrived. If it, in this example, takes $8$ seconds to pass and car $C$ arrives at the east endpoint at second $17$, then car $C$ has to wait $4$ seconds until Per lets it go at second $21$. There is a problem of drivers getting irritated with Per; they think they have to stop for too long. Per has been logging how long they can bear to wait before they get irritated. One day, to be able to evaluate his work, Per noted down when the cars arrived at the two endpoints of the segment. Per’s question is the following: what is the least number of drivers that can be irritated? We assume that a driver gets irritated if the time between the moment he arrives at the maintained segment and the moment he is actually given the “go” exceeds his irritation time limit. # Input The first line of the input contains two integers $t$ and $n$ ($4 \le t \le 180, 1 \le n \le 250$), where $t$ is the time in seconds needed for a car to pass the segment under maintenance, and $n$ is the total number of cars arriving at the segment. The following $n$ lines describe the cars. The $i$-th line contains the description of the $i$-th car in the following format: - one character $d$, being $W$ for cars arriving at the west endpoint of the segment, and $E$ for the ones that arrive at the east endpoint; - two integers $a$ and $r$ ($0 \le a < 86 400, 0 \le r \le 3 600$), where $a$ denotes the arrival time in seconds after midnight, and $r$ denotes the time in seconds it takes for the driver to get irritated. The cars arrive in the order specified in the input and they cannot overtake each other. In particular, a car whose driver is already irritated has to stay in the queue until eventually receiving the “go” and passing the maintained segment. # Output Output one line with the least possible number of irritated drivers. ## Sample Input 1 ``` 8 3 W 10 0 W 10 3 E 17 4 ``` ## Sample Output 1 ``` 0 ``` ## Sample Input 2 ``` 100 5 W 0 200 W 5 201 E 95 1111 E 95 1 E 95 11 ``` ## Sample Output 2 ``` 1 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> مهم‌ترین نکته‌ای که باید به آن توجه کرد این داشت این است که اتومبیل‌ها به همان ترتیبی که وارد صف می‌شوند، از گذرگاه اصلی عبور می‌کنند. این باعث می‌شود که ما بتوانیم کل اتومبیل‌های یک سمت گذرگاه را بلوک‌بندی کنیم و بگوییم که پس از اینکه یک بلوک از سمت شرق رفت، نوبت بلوک سمت غرب خواهد شد. (منظور از بلوک تعدادی اتومبیل پشت سر هم در صف می‌باشد) گرچه تعداد بلوک‌های بندی‌های ما زیاد است اما با استفاده از برنامه‌نویسی پویا می‌توان روشی برای حرکت نظام‌مند بر روی کلیه‌ی حالت پیدا کرد و به پاسخ مسئله دست یافت. </details> ---------------------------------- <details class="blue"> <summary> راهنمایی ۲ </summary> حال زمان آن است که تعریف $dp$ را دقیق کنیم. $dp[i][j][{0,1}]$ را تعریف می‌کنیم حداقل تعداد رانندگانی باید عصبانی شوند تا $i$ ماشین اول صف غرب و $j$ ماشین اول صف شرق از گذرگاه عبور کنند و ۰ یا ۱ بودن بعد سوم نیز نمایانگر این است که در این مرحله نوبت عبور یک بلوک ماشین از شرق گذرگاه به غرب آن است یا باالعکس. تعداد استیت‌های $dp$ که از $O({n^2})$ است و هر استیت را با فیکس کردن طول بلوک عبوری، می‌توانیم $O(n)$ اپدیت کنیم. بنابراین در اوردر زمانی ${n^3}$ می‌توانیم مسئله را حل کنیم. </details>

---------- André Claude Marzipan is the head chef at the French restaurant Le Chaud Chien. He owns a vast number of baking trays, which come in two sizes: $1$ foot by $1$ foot, and $1$ foot by $2$ feet. He stores them along $3$-foot deep shelves of various lengths. For example, on a shelf that is $5$ feet long, he might store baking trays in either of the two ways shown below:  Of course, there are many more than just these two ways, and in his off hours André often wonders how many different ways he can place trays on a given shelf. André is a bit of un maniaque du rangement (neat freak), so he insists that the trays are always aligned along the two axes defined by the shelf edges, that the edges of the trays are always $1$ foot multiples away from any edge, and that no portion of a tray extends beyond the shelf. The matter is complicated by the fact that often there are locations on the shelf where he does not want to put any baking trays, due to leaks above the shelf, dents in the shelf’s surface, etc. Since André is more adept at cuisine than counting, he needs a little help. # Input The input consists of two lines: the first line will contain two integers $m, n$, where $1 \le m \le 24$ indicates the length of the shelf (which is always $3$-feet deep) and $n$ indicates the number of bad locations on the shelf. The next line will contain $n$ coordinate pairs $x y$ indicating the locations where trays should not be placed, where $0 < x < m$ and $0 < y < 3$. No location will have integer coordinates and coordinates are specified to the nearest hundredth. If $n = 0$, this second line will be blank. # Output Output the number of ways that trays could be placed on the shelf. ## Sample Input 1 ``` 4 0 ``` ## Sample Output 1 ``` 823 ``` ## Sample Input 2 ``` 4 2 0.29 2.44 2.73 1.8 ``` ## Sample Output 2 ``` 149 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> ابتدا فرض کنید مکان بد نداریم و سینی‌ها را در همه‌جای جدول $3 * m$ (همان تاقچه‌ی گفته شده در مسئله)‌ می‌توان قرار داد. حال فرض کنید می‌خواهیم از چپ به راست حرکت کنیم و با استفاده از برنامه‌نویسی پویا، مقدار فعلی مورد نظر را از مقادیر قبلی به دست آوریم. بدین منظور $dp[i]$ را تعریف می‌کنیم، تعداد روش‌های گذاشتن سینی‌ها در یک جدول $3 * i$. با اندکی تفکر در می‌یابیم که رابطه‌ی بازگشتی که این $dp$ را اپدیت می‌کند،‌ خیلی سخت و طولانی است و بنابراین می‌توان نتیجه گرفت که راه مناسبی برای حل مسئله نیست. پس چه کنیم ؟!!! برای اینکه $dp$ ما از مقادیر قبلی قابل اپدیت شدن باشد،‌ میاییم به آن یک بعد اضافه می‌کنیم که بعد جدید نشان‌دهنده‌ی وضعیت دو ستون آخر می‌باشد که آیا ۶ خانه‌ی این دو ستون تاکنون پر شده‌اند یا نه. حال می‌توانیم با گذاشتن یک دومینو به وضعیت جدیدی برویم و مقدار آن وضعیت جدید را از مقدار خود اپدیت کنیم. حال کمی تعریف را دقیق کنیم. $dp[i][mask]$ را تعریف می‌کنیم تعداد روش‌های گذاشتن سینی در $i$ ستون اول به طوری که ستون‌های ‍۱ تا $i - 2$ به صورت کامل با سینی پر شده باشند و $mask$ هم نشان‌دهنده‌ی وضعیت دو ستون آخر باشد. توجه داشته باشید که $mask$ عددی از ۰ تا ۶۳ است که اگر آن را به چشم یک عدد ۶ بیتی در مبنای دو نگاه کنیم، بیت‌های آن نشان‌دهنده‌ی وضعیت دو ستون آخر ما هستند. علت اینکه $mask$ را وضعیت دو ستون آخر گرفتیم این بود که ما اکنون می‌خواهیم سینی‌هایی را قرار دهیم که حتما در ستون $i$ ام خانه‌ای را اشغال می‌کنند و به وضوح این سینی‌ها با ستون‌های ۱ تا $i - 2$ اشتراکی ندارند. </details> ---------------------------------- <details class="blue"> <summary> راهنمایی ۲ </summary> اکنون فرض کن خانه‌های بد نیز وجود دارند و ما نمی‌توانیم داخل این خانه‌ها سینی قرار دهیم. تنها تفاوتی که این مسئله با حالت قبل دارد، این است که ما هیچ‌گاه $dp[i][mask]$هایی که در $mask$ وضعیت یک خانه‌ی بد خالی نشان داده‌ می‌شود را اپدیت نمی‌کنیم. در واقع می‌توانیم فرض کنیم که خانه‌های بد از ابتدا پر بوده‌اند و لذا مقدار تعدادی از استیت‌های $dp$ برابر صفر خواهند شد. این تنها تفاوت این قسمت و حالت قبل است. </details>

---------- In the wizarding world of security, there are two kinds of researcher: the idealist arranging hat and the mercenary deranging hat. As we learned last year, an arranging hat carefully sorts out any list of letters given to it into ascending order. However, a deranging hat performs the exact opposite function: putting a sorted string of letters back into its original order. The tool of choice for today’s discerning headwear is a sorting network: a sequence of instructions represented by a list of pairs of numbers $A_i$ and $B_i$, meaning that if at step $i$ the $A$-th item in the string is not already smaller than the $B$-th item, they should be swapped immediately. Given a specific word $W$, output a sorting network that the deranging hat can use to form the word from its original sorted letters. # Input One line containing one string of lowercase Latin letters (`‘a’-‘z’`), $S$, containing at most $1000$ characters. # Output Output at most 10000 lines, each containing two integers $A_i$ and $B_i$ ($1 \le A_i, B_i \le |S|$ ) giving the $i$-th operation to perform. ## Sample Input 1 ``` bab ``` ## Sample Output 1 ``` 2 1 ``` ## Sample Input 2 ``` dude ``` ## Sample Output 2 ``` 4 3 3 2 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> اگر دنباله‌ی خروجی را از آخر به اول نگاه کنیم معادل این است که در ابتدا آرایه فعلی را داریم و در هر مرحله اگر $A_i$ کوچکتر از $B_i$ بود، جای آن دو را با هم عوض کن. حال با این مدل نگاه کردن می‌توانیم بر روی رشته‌ی فعلی مراحل را پیاده کنیم. هر دفعه کوچک‌ترین حرفی (از نظر الفبایی) که سر جایش نیست را در نظر گرفته و آن را با یک جا به جایی به سر جایش بیاوریم. این‌گونه مرحله به مرحله در حال ساختن رشته‌ی صعودی از چپ به راست هستیم. در نهایت نیز جفت‌های همه‌ی مراحلمان را به ترتیب برعکس اجرا شدن خروجی می‌دهیم و طبق بند فوق، این همان دنباله‌ي خواسته شده‌ی مسئله است. اگر اندازه‌ی رشته‌ی ورودی را $l$ در نظر بگیریم، حداکثر $l$ مرحله کار بالا را انجام می‌دهیم و تایم برنامه نیز از $O({l^2})$ می‌باشد چرا که برای پیدا کردن جفت مورد نظر در هر مرحله حداکثر $l$ کاراکتر را چک می‌کنیم. </details>

---------- Times are hard at the Association of Chartered Mountaineers. The growth of their pedestrian sport has slowed to a crawl. Instead of taking up mountaineering, younger potentials are gravitating towards warmer indoor activities such as snooker, musical chairs, and programming contests. To win over more members, the Association is going to organise a series of new time trial orienteering events next year. The route for the first race will be a short run through the Cairngorms, with every contestant following the same route designated by marker points but all starting at different times. Because hiking can be dangerous, and many of the contestants will be inexperienced, the competition committee drew up two rules: - Every contestant needs to keep a specific maximum distance away from the next-closest contestant, in either direction, at all times. - Every contestant should be given personal space. If a contestant needs a personal space of $D$ metres, nobody else should ever come closer than that at any time. This distance varies according to level of experience. The hardest part of orienteering is the pathfinding; once a contestant knows where to go next, they can get there in almost no time (for the purposes of this problem, instantaneously). In fact, while the inaugural ACM "Icy-Cold Peak Contest" is already underway, pathfinding is turning out to be a problem: nobody is sure whether they can move next without breaking any of the conditions on minimum and maximum distance. Help the runners reach the end of their route by computing a list of who should move to the next goal point, and at what time. # Input - One line containing an integer $B$ ($1 \le B \le 50000$), the maximum separation allowed between any two runners. - One line containing an integer $P$ ($3 \le P \le 1000$), the number of marker points along the route. - One line containing $P$ unique space-separated integers $d_1 ... d_P$ ($0 \le d_i \le 10^6$), with $d_i$ being the distance of the $i$-th vertex from the starting point $d_1 = 0$. - One line containing an integer $K$ ($2 \le K \le 1000$), the number of hikers on the landscape. - $K$ further lines, each containing the pair of space-separated integers $A_i$ and $V_i$ ($1 \le A_i \le 10^6; 1 \le V_i \le P$), the minimum separation distance and current marker position respectively for the $i$-th person. The initial configuration of hikers will be legal according to the minimum and maximum distance rules. The hikers will be given in increasing order of distance from the start. # Output If it is not possible to get everyone to the end of the route without breaking minimum or maximum distance requirements, output impossible. Otherwise, output a space-separated list of moves on one line, each describing which person should make the next move. If anyone falls off the landscape, your answer will not be judged as correct. However, once someone has arrived at the end of their journey they cease to count towards any rule violations. ## Sample Input 1 ``` 3 8 0 1 2 3 4 5 6 7 2 2 1 2 4 ``` ## Sample Output 1 ``` 1 2 1 2 1 2 1 2 1 1 1 ``` ## Sample Input 2 ``` 10 10 0 1 3 6 10 14 17 19 20 21 3 3 1 1 3 3 5 ``` ## Sample Output 2 ``` 2 1 1 3 2 1 3 2 1 3 3 2 1 3 2 2 1 2 1 1 1 ``` ## Sample Input 3 ``` 5 5 0 2 5 9 14 2 2 1 2 2 ``` ## Sample Output 3 ``` impossible ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> حل این مسئله به ایده‌ی تئوری سختی نیاز ندارد و صرفا حریصانه عمل می‌کنیم. در هر مرحله همه‌ی افراد را چک می‌کنیم و اگر کسی بود که می‌توانستیم او را یک ایستگاه به جلو ببریم، این کار را انجام می‌دهیم و افراد دیگر را چک نمی‌کنیم. تعداد بارهایی که ما یک نفر را جلو می‌بریم حداکثر ${p^2}$ مرحله است و هر دفعه هم برای پیدا کردن فردا داریم یک فور $O(p)$ می‌زنیم. تا این‌جا تایم برنامه خیلی بد نیست چون احتمالا برای جلو بردن یک فرد نباید در هر مرحله هر $p$ نفر را چک نخواهیم کرد ولی خب در صورت پیاده‌سازی بد ممکن است این راه تایم شود. ایده‌ای می‌زنیم تا تایم برنامه‌ را بهبود بخشیم. به این صورت عمل می‌کنیم که در هر مرحله همه‌ی افراد را چک می‌کنیم و هر کسی که می‌توانست جلو برود را جلو می‌بریم. در واقع در هر مرحله دقیقا هر $p$ نفر را چک می‌کنیم ولی احتمالا به جای یک نفر چند نفر به جلو خواهند رفت. اثبات خوب بودن این بهینه‌سازی در تئوری ممکن نیست یا خیلی سخت است اما همه‌ی ما شهود داریم که در هر مرحله واقعا ممکن است تعداد بیشتر از یک نفر بتوانند یک ایستگاه به جلو بروند و این موضوع در عمل هم مشاهده می‌شود (اگر به اندازه‌ي کافی شهود ندارید برای خود چند مثال بزنید تا متوجه خوب بودن الگوریتممان شوید). بنابراین قسمت اصلی این سوال پیاده‌سازی کد آن است ولی این ایده که در هر مرحله هر چند نفری که می‌توانستند را به جلو حرکت دهید، تایم برنامه‌ی شما را بسیار بهبود خواهد بخشید. </details>

---------- Following tremendous advances in space flight control software and equally impressive innovations in reality TV crowdfunding, humans have successfully settled a number of planets, moons, asteroids, and various other kinds of funny-shaped rocks across our solar system. To celebrate, the Galactic President has elected to create a new holiday called "Solar Night". At the crux of the event, she decrees, every settlement will simultaneously launch colourful fireworks into the darkness of night. Night, like most things, is a difficult problem in space. Every spacebound object has its own day length and period of rotation. Thankfully all of the settlements did, at least, start their clocks at the same moment. Settlements may have started in daylight or darkness and so it is possible that the first recorded sunrise can be either before or after the first hour of sunset. By convention, the President’s term lasts for exactly $1825$ days as measured by the planet with the longest period of rotation. The celebration needs to happen within that time or it will not serve its intended purpose. Determine how many hours must pass for us to find a suitable time to celebrate Solar Night. # Input - One line containing the integer $N$ ($1 \le N \le 20$), the number of settlements. - $N$ lines, each containing three integers: - $H$ ($2 \le H \le 100$), the number of hours in this settlement’s solar day. - $R$ and $T$ ($0 \le R, T \le H - 1, R \neq T$), the hours of sunrise and sunset respectively. At sunrise and sunset, a settlement is in darkness. At times strictly in between sunrise and sunset, a settlment is in daylight. # Output Output the number of hours that must pass from when the settlement clocks began until each settlement is in darkness. If no suitable time occurs in the first $1825$ days, output impossible. ## Sample Input 1 ``` 2 24 7 19 24 18 6 ``` ## Sample Output 1 ``` 6 ``` ## Sample Input 2 ``` 3 10 8 2 15 5 10 20 15 10 ``` ## Sample Output 2 ``` 12 ``` ## Sample Input 3 ``` 2 6 4 2 12 7 5 ``` ## Sample Output 3 ``` impossible ``` ## Sample Input 4 ``` 2 10 5 6 10 6 5 ``` ## Sample Output 4 ``` 5 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> برای یافتن پاسخ مسئله به ترتیب روی همه‌ی روزها (از ۱ تا $1825$) حرکت می‌کنیم و متغیر $cnt$ را برابر تعداد شهرک‌هایی تعریف می‌کنیم که اکنون در آن‌ها شب است. حال در هر مرحله، همه‌ی شهرک‌ها را چک می‌کنیم و در صورت تغییر وضعیت آن‌ها مقدار متغیر $cnt$ را اپدیت می‌کنیم. اگر در روزی، مقدار $cnt$ برابر $n$ شد، که آن روز جواب ماست و اگر هیچ‌گاه اتفاق نیفتاد، پاسخ $impossible$ است. </details>

---------- For the grand opening of the algorithmic games in NlogNsglow, a row of tower blocks is set to be demolished in a grand demonstration of renewal. Originally the plan was to accomplish this with controlled explosions, one for each tower block, but time constraints now require a hastier solution. To help you remove the blocks more rapidly you have been given the use of a Universal Kinetic / Incandescent Energy Particle Cannon (UKIEPC). On a single charge, this cutting-edge contraption can remove either all of the floors in a single tower block, or all the $x$-th floors in all the blocks simultaneously, for user’s choice of the floor number $x$. In the latter case, the blocks that are less than $x$ floors high are left untouched, while for blocks having more than $x$ floors, all the floors above the removed $x$-th one fall down by one level. Given the number of floors of all towers, output the minimum number of charges needed to eliminate all floors of all blocks. # Input The first line of input contains the number of blocks $n$, where $2 \le n \le 100 000$. The second line contains $n$ consecutive block heights $h_i$ for $i = 1, 2, ..., n$, where $1 \le h_i \le 1 000 000$. # Output Output one line containing one integer: the minimum number of charges needed to tear down all the blocks. ## Sample Input 1 ``` 6 2 1 8 8 2 3 ``` ## Sample Output 1 ``` 5 ``` ## Sample Input 2 ``` 5 1 1 1 1 10 ``` ## Sample Output 2 ``` 2 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> فرض کنید ما فقط می‌توانیم تعدادی طبقه حذف کنیم. در این صورت با کمی بررسی در می‌یابیم که حداقل تعداد حرکت لازم برای از بین بردن کل بلوک‌ها، برابر با ارتفاع بلند‌ترین برج ماست. </details> ---------------------------------- <details class="blue"> <summary> راهنمایی ۲ </summary> حال به حل مسئله می‌پردازیم. بدون لطمه خوردن به کلیت مسئله فرض کنید اول تمام ستون‌ها و سپس تمام طبقات موردنظر را حذف می‌کنید. در این صورت پس از حذف ستون‌ها، طبق راهنمایی یک تعداد حرکات شما برابر با ارتفاع بلندترین برج است. بنابراین بهینه‌ترین حالت ممکن این است که اگر می‌خواهیم دقیقا $k$ ستون حذف کنیم،‌ آن $k$ ستونی را حذف کنیم که بیشترین ارتفاع را دارند. در این حالت تعداد حرکات ما برابر است با $k$ + ارتفاع $k + 1$ امین بلندترین برج. ($k$ حرکت برای حذف کردن $k$ تا بلندترین برج و ارتفاع $k+1$ امین برج برای حذف گردن بقیه) به دست آوردن مقادیر بالا به ازای هر $k$، پس از مرتب‌سازی برج‌ها بر اساس ارتفاعشان به سادگی امکان‌پذیر است. </details>