+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- حنا وارد مسابقه *هندونه‌خوری* شده است. در این مسابقه $n$ هندوانه وجود دارد که به ترتیب با شماره‌های ۱ تا $n$ نام‌گذاری شده‌اند، ‌هم‌چنین وزن هندوانه $i$ام، $w_i$ است. (وزن هندوانه‌ها متمایز است.) حنا در هر مرحله از این مسابقه دو هندوانه‌ای که کم‌ترین شماره را دارند را انتخاب می‌کند و هندوانه‌ای که سبک‌تر است را می‌خورد. حنا به این کار ادامه می‌دهد تا فقط یک هندوانه باقی بماند. بعد از مسابقه حنا به این فکر رفته که آخرین هندوانه چه شماره‌ای داشت اما از آن‌جا که خیلی هندوانه خورده، فکرش کار نمی‌کند. به حنا کمک کنید و با گرفتن $w_i$ ها شماره آخرین هندوانه را بگویید. # ورودی در سطر اول $n$ تعداد هندوانه‌ها آمده‌ است. در سطر بعدی $w_1, w_2, \ldots, w_n\ $ آمده‌ است. $$ 1 \leq n \leq 100 $$ $$ 1 \leq w_i \leq 100 $$ + تضمین‌ می‌شود که $w_i$ ها متمایز هستند. # خروجی در تنها سطر خروجی شماره هندوانه باقی مانده را چاپ کنید. # مثال # ورودی نمونه ۱ ``` 5 4 3 1 5 2 ``` # خروجی نمونه ۱ ``` 4 ``` در این نمونه به ترتیب اتفاق‌های زیر اتفاق می‌افتد. + هندوانه‌های ۱ و ۲ انتخاب می‌شوند و هندوانه ۲ چون وزن کم‌تری دارد خورده می‌شود. + هندوانه‌های ۱ و ۳ انتخاب می‌شوند و هندوانه ۳ خورده می‌شود. + هندوانه‌های ۱ و ۴ انتخاب می‌شوند و هندوانه ۱ خورده می‌شود. + هندوانه‌های ۴ و ۵ انتخاب می‌شوند و هندوانه ۵ خورده می‌شود. در نهایت هندوانه چهار باقی می‌ماند. # ورودی نمونه ۲ ``` 5 2 4 5 1 3 ``` # خروجی نمونه ۲ ``` 3 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- حنا قهرمان مسابقات *هندونه‌خوری* شده و مقدار زیادی پول جایزه گرفته‌ است. حال حنا می‌خواهد به خانه‌اش برگردد و با پول مسابقات مهمانی بگیرد. شهر محل زندگی حنا، یک خیابان با $n$ خانه است که حنا در خانه‌ی $s$ام زندگی می‌کند و مسابقات *هندونه‌خوری* در خانه $t$ ام برگزار می‌شود. او می‌داند در تعدادی از خانه‌ها زورگیر زندگی می‌کند و اگر از آن‌ها رد شود، زورگیر پول حنا را از او می‌گیرند و حنا نمی‌تواند مهمانی بگیرد. حنا از پلیس کمک می‌خواهد. پلیس‌ها در روز برنامه‌نویس می‌توانند در هر عملیات، یک بازه به طول $2^k$ ($k$ یک عدد حسابی است) را که **همه اعضای** آن زورگیر هستند را انتخاب کنند و آن خانه‌ها را پاکسازی کنند. پلیس‌ها وقت زیادی ندارند. برای همین از شما می‌خواهند کمترین تعداد عملیات برای پاکسازی مسیر بین حنا و مسابقه *هندونه‌خوری* را بگویید. # ورودی در سطر اول عدد $n$ آمده که نشان‌دهنده‌ی طول خیابان است. در سطر دوم یک رشته به طول $n$ آمده‌است. خانه‌هایی که در آن زورگیر وجود دارد حرف `H` و بقیه خانه‌ها حرف `P` هستند. تضمین می‌شود که در خانه‌های $s$ و $t$ زورگیر وجود ندارد. در سطر سوم $s$ و $t$ به ترتیب آمده‌اند. $$ 1 \leq n \leq 1\ 000 $$ $$ 1 \leq s, t \leq n $$ # خروجی در تنها سطر خروجی، کمترین تعداد عملیات برای پاکسازی مسیر حنا از زورگیرها را بگویید. # مثال # ورودی نمونه ۱ ``` 3 PHP 1 3 ``` # خروجی نمونه ۱ ``` 1 ``` در مسیر خانه اول به سوم، تنها در خانه‌ دوم زورگیر وجود دارد که پلیس‌ها طی یک مرحله او را دستگیر می‌کنند. # ورودی نمونه ۲ ``` 9 HPPHHPHPH 8 3 ``` # خروجی نمونه ۲ ``` 2 ``` در مسیر خانه هشتم به سوم تنها در خانه‌های ۴ و ۵ و ۷ زورگیر وجود دارد که پلیس‌ها طی یک مرحله زورگیر خانه‌ی ۴ و ۵ و در مرحله‌ی بعد زورگیر خانه‌ی ۷ را دستگیر می‌کنند. در حرکت اول یک بازه به طول ۲ و در حرکت دوم یک بازه به طول ۱ پاکسازی شد که طول هر دو بازه توانی از ۲ بود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دوستان حنا برای هدیه تولد او $n$ شیرینی خریده‌اند و آن‌ها را پشت سر هم روی میز قرار داده‌اند. آن‌ها به حنا گفته‌اند که وزن شیرینی $i$ ام $w_i$ است (ممکن است وزن یک شیرینی منفی باشد!)‌. حالا حنا می‌خواهد یک بازه پشت سر هم از شیرینی‌ها را انتخاب کند و بخورد. اما از آنجایی که حنا رژیم دارد، مجموع وزن شیرینی‌هایی که می‌خورد، نمی‌تواند بیشتر از $W$ باشد. حنا که گیج شده‌است به شما روی آورده تا به او بیشترین وزن شیرینی که می‌تواند بخورد را بگویید. توجه کنید که حنا همیشه گزینه شیرینی نخوردن را دارد و جواب حداقل صفر هست. # ورودی در سطر اول عدد $n$ و $W$ به ترتیب آمده‌‌است. در سطر بعدی $\, w_1, w_2, \ldots, w_n $ به ترتیب آمده‌‌است. $$1 \leq n \leq 300 \, 000$$ $$ -10^9 \leq w_i\leq 10^9 $$ $$ 1 \leq W \leq 10^9$$ # خروجی بیشینه وزن شیرینی که حنا در مجموع می‌تواند بخورد را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 7 4 5 3 ``` ## خروجی نمونه ۱ ``` 5 ``` حنا تنها می‌تواند بازه $[2,2]$ را انتخاب کند. ## ورودی نمونه ۲ ``` 5 10 1 1 8 3 1 ``` ## خروجی نمونه ۲ ``` 10 ``` در اینجا می‌توانیم بازه $[1,3]$ را انتخاب کنیم. ## ورودی نمونه ۳ ``` 5 10 13 -1 7 -12 19 ``` ## خروجی نمونه ۳ ``` 7 ``` در اینجا می‌توانیم بازه $[1,4]$ را انتخاب کنیم.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پدر حنا برای هدیه تولد او، صندوقچه‌ی پدربزرگش را باز کرده‌است و تکه‌ کد زیر را به او داده‌است. (کد زیر یک شبه‌کد است و می‌توانید درباره شبه‌کد در [این‌جا](https://fa.wikipedia.org/wiki/%D8%B4%D8%A8%D9%87%E2%80%8C%DA%A9%D8%AF) بخوانید.) ``` procedure old_little_code() p := the input array of size n s := an empty stack a := an array of size 2n counter = 1 for i = 1 to n inclusive do: while s is not empty and p[s.top] < p[i] do: a[counter] = s.top counter += 1 s.pop() end while s.push(i) a[counter] = s.top counter += 1 end for while s is not empty do: a[counter] = s.top counter += 1 s.pop() end while return a end procedure ``` در کنار این تکه‌ کد، کاغذی پیدا کرده و آن را نیز به حنا می‌دهد. روی کاغذ نوشته شده "به این تکه کد یک جایگشت از اعداد $1$ تا $n$ را دادم و در خروجی اعداد $a_1, a_2, \ldots, a_{2n}\ $ را گرفتم.". حنا قصد دارد جایگشتی که پدربزرگش به عنوان ورودی به تکه کد داده‌ بود را پیدا کند. به او کمک کنید تا تعداد جایگشت‌های مختلفی که می‌توانند جایگشت پدربزرگش باشند را پیدا کند. # ورودی در سطر اول عدد $n$ آمده‌است. در سطر بعدی، اعداد $a_1, a_2, \ldots, a_{2n}$ به ترتیب آمده‌اند. تضمین می‌شود که به ازای حداقل یک جایگشت، خروجی داده‌شده تولید می‌شود. $$ 1 \leq n \leq 200 \, 000 $$ $$ 1 \leq a_i \leq n $$ # خروجی در تنها سطر خروجی، باقی‌مانده‌ی تعداد جایگشت‌ها بر $10^9 + 7$ را چاپ کنید. # مثال # ورودی نمونه ۱ ``` 2 1 2 2 1 ``` # خروجی نمونه ۱ ``` 1 ``` جایگشت پدربزرگ فقط می‌تواند $\{2, 1\}$ باشد. # ورودی نمونه ۲ ``` 3 1 2 3 3 2 1 ``` # خروجی نمونه ۲ ``` 1 ``` جایگشت پدربزرگ فقط می‌تواند $\{3, 2, 1\}$ باشد. # ورودی نمونه ۳ ``` 4 1 2 2 3 3 1 4 4 ``` # خروجی نمونه ۳ ``` 1 ``` جایگشت پدربزرگ فقط می‌تواند $\{3, 1, 2, 4\}$ باشد. # ورودی نمونه ۴ ``` 5 1 2 2 3 3 4 5 5 4 1 ``` # خروجی نمونه ۴ ``` 3 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همان طور که می‌دانید حنا به ریاضیات علاقه خاصی دارد. او برای این که این علاقه را به دوستانش ثابت کند، آن‌ها را به چالش زیر دعوت می‌کند. هر کدام آن‌ها باید دو عدد $n$ و $k$ را انتخاب کنند و سپس حنا تمام دنباله‌های شامل اعداد طبیعی $a_1, a_2, ..., a_m\ $ را که ویژگی‌های زیر را دارند یادداشت می‌کند. + $1 \le m \le n$ + $1 \le a_i \le k$ + $\sum_{i=1}^{m} a_i = n$ برای مثال اگر $n = 3$ و $k = 2$ باشد، حنا دنباله‌های زیر را یادداشت می‌کند. + $(2, 1)$ + $(1, 2)$ + $(1, 1, 1)$ دوستان حنا که از مهارت حنا شگفت زده می‌شوند از او می‌خواهند تا به ازای هر دنباله حاصل‌ضرب اعضایش را محاسبه کند و در نهایت بگوید که چند مقدار متفاوت در این بین وجود دارد (در نمونه بالا این مقدار برابر با ۲ است)؛ اما چون حنا در ضرب کردن کمی مشکل دارد از شما می‌خواهد تا به او کمک کنید و جواب دوستانش را بدهید. # ورودی در سطر اول $n$ و $k$ به ترتیب آمده‌است. $$1 \leq k \leq n \leq 30 \, 000 $$ # خروجی در تنها سطر خروجی باقیمانده جواب مسئله را بر $10^9 + 7$ چاپ کنید. # مثال # ورودی نمونه ۱ ``` 4 2 ``` # خروجی نمونه ۱ ``` 3 ``` مقادیر مختلف حاصل‌ضرب در این مثال ۱ و ۲ و ۴ هستند. # ورودی نمونه ۲ ``` 5 3 ``` # خروجی نمونه ۲ ``` 5 ```

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- معلم حنا هدیه تولد به او یک درخت ریشه‌دار $n$ راسی داده که ریشه آن راس شماره $1$ است. روی راس شماره $i$ آن عدد $a_i$ نوشته‌ شده‌‌است. حنا بعد از یادگرفتن الگوریتم [جستجوی عمق اول](https://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%A7%D9%88%D9%84_%D8%B9%D9%85%D9%82) تکه کد زیر را نوشته است. ``` b := an array of length n time := 1 procedure DFS(T, a, v): b[time] = a[v] time += 1 label v as visited for u in T.neighbors(v) do: if not visited[u] do: DFS(T, a, u) end if end for end procedure procedure countInversions() DFS(T, a, 1) return number of inversions in the array b /* Number of inversions in the array b is the number of distinct pairs (i, j) such that 1 <= i < j <= n and b[i] > b[j] */ end procedure ``` حنا می‌خواهد تابع `countInversions‍` را فراخوانی کند. او می‌داند که خروجی این تابع به ترتیب همسایه‌های هر راس در تابع `DFS‍` وابسته است. به او کمک کنید، کمینه خروجی ممکن این تابع را پیدا کند. در واقع حنا می‌خواهد طوری ترتیب همسایه‌های رئوس را انتخاب کند که تعداد نابه‌جایی‌های آرایه `b` کمینه بشود. منظور از نابه‌جایی تعداد جفت‌های $1 \le i < j \le n$ است که $a_i > a_j$ باشد. # ورودی در سطر اول ورودی عدد $n$ آمده‌است. در سطر دوم، اعداد $a_1, a_2, ..., a_n$ به ترتیب آمده‌اند. در سطر سوم، اعداد $p_2, p_3, ..., p_n$، به ترتیب آمده‌اند که $p_i$ پدر راس شماره $i$ درخت معلم است. $$ 1 \leq n \leq 1 \, 000 \, 000 $$ $$ 0 \leq a_i \leq 2 $$ $$ 1 \leq p_i < i $$ # خروجی در سطر اول خروجی، کمینه خروجی تابع `countInversions` را چاپ کنید. # مثال # ورودی نمونه ۱ ``` 6 0 0 2 0 0 2 1 2 3 2 2 ``` # خروجی نمونه ۱ ``` 1 ``` # ورودی نمونه ۲ ``` 8 0 1 1 2 1 0 1 2 1 2 2 1 1 2 3 ``` # خروجی نمونه ۲ ``` 0 ``` # ورودی نمونه ۳ ``` 10 2 0 1 1 1 2 1 0 0 0 1 2 2 1 5 5 5 5 5 ``` # خروجی نمونه ۳ ``` 16 ```

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از یک کلاس ریاضیات سخت، حنا برای تفریح به همراه بنا به جنگل رفته است. حنا و بنا هر کدام یک درخت (گراف بدون دور و همبند) ریشه‌دار $n$ راسی انتخاب کرده‌اند. آن‌ها به یک دنباله از اعداد مانند $V_1, V_2, ..., V_K$ *علاقه* دارند اگر هر دو شرط زیر برقرار باشد: + در درخت حنا، به ازای هر $1 \leq i < K$ راس $V_i$ جد راس $V_{i+1}$ است. + در درخت بنا، به ازای هر $1 \leq i < K$ راس $V_{i+1}$ جد راس $V_i$ است. آن‌ها *عاشق* یک دنباله هستند اگر هر دو شرط زیر برقرار باشد: + به این دنباله علاقه داشته باشند. + هیچ دنباله‌ای با طول بیشتر از این دنباله وجود نداشته باشد که به آن علاقه داشته باشند. در یک درخت ریشه‌دار، به راس $v$ *جد* راس $u$ می‌گوییم اگر یکی از دو شرط زیر برقرار باشد: + راس $v$ پدر راس $u$ باشد. + راس $v$ جد پدر راس $u$ باشد. طول بزرگ‌ترین دنباله‌ای که حنا و بنا به آن علاقه دارند، و تعداد دنباله‌هایی که آن‌ها عاشق آن هستند، چقدر است؟ # ورودی در سطر اول ورودی، عدد $n$ آمده‌است. در $n - 1$ سطر بعدی یال‌های درخت حنا آمده‌است. در $i$ امین سطر $v_i$ و $u_i$ دو سر یال $i$ ام در درخت حنا آمده‌است. **ریشه درخت حنا راس شماره $1$ است.** در $n - 1$ سطر بعدی یال‌های درخت بنا آمده‌است. در $i$ امین سطر $v_i$ و $u_i$ دو سر یال $i$ ام در درخت بنا آمده‌است. **ریشه درخت بنا راس شماره $n$ است.** $$ 1 \leq n \leq 200 \, 000 $$ $$ 1 \leq v_i, u_i \leq n $$ # خروجی در تنها سطر خروجی، طول بزرگ‌ترین دنباله‌ای که حنا و بنا به آن علاقه دارند و باقیمانده تعداد دنباله‌هایی که آن‌ها عاشق آن هستند را بر $10^9 + 7$ چاپ کنید. # مثال # ورودی نمونه ``` 5 4 2 3 1 5 4 2 1 4 5 1 5 3 4 2 5 ``` # خروجی نمونه ``` 2 3 ```