+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در این سوال به شما دو عدد صحیح مثل $a$ و $b$ داده می‌شود. از شما می‌خواهیم برنامه‌ای بنویسید که مقدار $a$ و $b$ را دریافت کند و $a + b$ را چاپ کند. # ورودی در تنها سطر ورودی، دو عدد صحیح $a$ و $b$ که با یک فاصله از هم جدا شده‌اند، داده می‌شود. $$1 \leq a, b \leq 100$$ # خروجی در تنها سطر خروجی، مقدار $a + b$ را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 5 ``` ## خروجی نمونه ۱ ``` 8 ``` ## ورودی نمونه ۲ ``` 1 1 ``` ## خروجی نمونه ۲ ``` 2 ``` <details class="red"> <summary> **اگر نمره‌ی کامل این سوال را نگرفتید، اینجا را بخوانید.** </summary> ---------- به احتمال زیاد، شما با سیستم داوری مسابقات برنامه‌نویسی آشنایی ندارید. بنابراین ابتدا [**اینجا**](https://quera.org/course/assignments/2693/problems/8774) را بخوانید و اگر بازهم مشکل شما حل نشد به [**ما**](https://quera.org/contest/clarification/64031/) پیام دهید. </details> <details class="blue"> <summary> **راهنمایی اول** </summary> ---------- مسئله را به سه قسمت تقسیم کنید: + دریافت دو عدد از ورودی + محاسبه‌ی جمع آن دو عدد + چاپ کردن حاصل در خروجی برای آشنایی بیشتر درباره‌ی نحوه‌ی دریافت ورودی این [لینک](https://quera.org/course/assignments/2693/problems/8774) را مطالعه کنید. </details> <details class="blue"> <summary> **راهنمایی دوم** </summary> ---------- از چاپ کردن موارد اضافه هنگام دریافت ورودی مثل `please enter a number:` و چیزهای مشابه آن پرهیز کنید. </details> <details class="blue"> <summary> **راهنمایی سوم** </summary> ---------- توجه کنید ورودی در یک خط داده می‌شود. بنابراین اگر از زبان‌هایی مثل پایتون برای برنامه‌نویسی استفاده می‌کنید، باید یکبار با کمک `input` ورودی بگیرید و سپس رشته بدست آمده را دو قسمت کنید. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امین وارد یک آب‌میوه فروشی می‌شود. معده امین $V$ لیتر ظرفیت آب‌میوه دارد! در این آب‌میوه فروشی $n$ نوع آب‌میوه وجود دارد. انواع آب‌میوه را با اعداد $1$ تا $n$ شماره‌گذاری می‌کنیم. از آب‌میوه‌ی نوع $i$ام ($1 \leq i \leq n$) به اندازه‌ی $v_i$ لیتر در مخزن آن وجود دارد. امین می‌داند که اگر همه‌ی ظرف آب‌میوه‌ی موجود در مخزن $i$ام را بنوشد، به اندازه‌ی $h_i$ خوشحال می‌شود. همچنین اگر هر کسری از این ظرف را بخورد به همان نسبت خوشحالی بدست می‌آورد. (برای مثال اگر $\frac{1}{3} v_i$ لیتر بنوشد به‌اندازه‌ی $\frac{1}{3} h_i$ خوشحالی بدست می‌آورد.) حال امین می‌خواهد از هر نوع آب‌میوه مقداری بنوشد. (این مقدار می‌تواند هر عدد حقیقی نامنفی باشد!) به طوری که مجموع خوشحالی او بیشینه باشد. از شما می‌خواهیم برنامه‌ای بنویسید که این مقدار بیشینه را محاسبه و چاپ کند. # ورودی در سطر اول ورودی، عدد صحیح و مثبت $n$ و $V$ داده می‌شود. $$1 \leq n \leq 100 \, 000$$ $$1 \leq V \leq 10^9 $$ در $n$ سطر بعدی، در هر سطر، دو عدد $h_i$ و $v_i$ که با یک فاصله از هم جدا شده‌اند. $$1 \leq h_i, v_i \leq 10^9$$ # خروجی در تنها سطر خروجی، حداکثر مجموع خوشحالی که امین می‌تواند بدست بیاورد را چاپ کنید. **خروجی برنامه را با دقت دقیقاً یک رقم بعد از اعشار چاپ کنید.** # مثال‌ها ## ورودی نمونه ۱ ``` 3 400 100 200 150 140 100 300 ``` ## خروجی نمونه ۱ ``` 270.0 ``` ## ورودی نمونه ۲ ``` 1 10 500 30 ``` ## خروجی نمونه ۲ ``` 166.7 ``` <details class="blue"> <summary> **راهنمایی اول** </summary> ---------- ابتدا مسئله را برای حالت $n = 2$ حل کنید. </details> <details class="blue"> <summary> **راهنمایی دوم** </summary> ---------- اکنون که می‌توانید تصمیم بگیرد بین دو آبمیوه کدامیک الویت دارد. سعی کنید با همین روش همه‌ی آبمیوه‌ها را مرتب کنید. </details> <details class="blue"> <summary> **راهنمایی سوم** </summary> ---------- برای اینکه این مرتب‌سازی سریع باشد، سعی کنید از روش‌های مرتب‌سازی مقایسه‌ای مثل *merge sort* یا *quick sort* استفاده کنید تا به‌اندازه‌ی کافی راه‌حل شما سریع باشد. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- به شما عدد صحیح $n$ و عدد اعشاری $x$ داده می‌شود. از شما می‌خواهیم برنامه‌ای بنویسید تا حاصل عبارت زیر را محاسبه کند. $$\left[x\right] + \left[x + \frac{1}{n}\right] + \left[x + \frac{2}{n}\right] + \dots + \left[x + \frac{n-1}{n}\right]$$ که در این‌جا $\left[x\right]$ به معنای براکت $x$ است و مقدار آن بزرگ‌ترین عدد صحیح کم‌‌تر یا مساوی $x$ است. # ورودی در سطر اول تعداد سناریوها داده می‌شود. $$1 \leq t \leq 100$$ در سطر اول هر سناریو، عدد صحیح و مثبت $n$ داده می‌شود. $$1 \leq n \leq 10^9$$ در سطر دوم هر سناریو، عدد اعشاری $x$ داده می‌شود. $$-100 \lt x \lt 100$$ عدد اعشاری $x$ دقیقاً با دقت حداکثر ۷ رقم بعد از اعشار داده می‌شود. # خروجی در تنها سطر خروجی، یک عدد صحیح که برابر پاسخ مسئله است را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 2 7.1561 3 2.71 1 3.14 ``` ## خروجی نمونه ۱ ``` 14 8 3 ``` سناریو اول. $$[7.1561] + [7.1561 + 0.5] = 7 + 7 = 14$$ سناریو دوم. $$[2.71] + [2.71 + 0.333...] + [2.71 + 0.666...] = 2 + 3 + 3 = 8$$ سناریو سوم. $$[3.14] = 3$$ <details class="blue"> <summary> **راهنمایی اول** </summary> ---------- توجه کنید مقدار هر براکت $[x]$ یا $[x] + 1$ است. </details> <details class="blue"> <summary> **راهنمایی دوم** </summary> ---------- مقدار $n$ براکت داده شده، به ترتیب صعودی است. پس می‌توانید با استفاده *binary search* آخرین براکتی که $[x]$ است را پیدا کنید. </details> <details class="blue"> <summary> **راهنمایی سوم** </summary> ---------- با همان استدلال می‌توان ثابت کرد پاسخ مسئله برابر $[nx]$ است. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک گراف ساده به نام $G$ با $n$ راس و $m$ یال داریم. راس‌های این گراف با اعداد $1$ تا $n$ شماره‌گذاری شده‌اند. در هر عملیات می‌توانیم یکی از دو عدد صحیح و مثبت مثل $u$ و $v$ را انتخاب کنیم به طوری که $1 \leq u \neq v \leq n$ و یکی از دو عملیات زیر را انجام دهیم اگر یال $uv$ در $G$ موجود است، آن را حذف کنیم. اگر یال $uv$ در $G$ موجود نیست، آن را به $G$ اضافه کنیم. می‌خواهیم با این عملیات‌ها $G$ را به یک درخت، تبدیل کنیم. به شما گراف $G$ داده می‌شود و از شما می‌خواهیم کمترین تعداد عملیات لازم برای تبدیل $G$ به یک درخت را محاسبه کنید. # ورودی در سطر اول ورودی، دو عدد صحیح $n$ و $m$ که با یک فاصله از هم جدا شده‌اند، داده می‌شود. $$1 \leq n \leq 100 \, 000$$ $$0 \leq m \leq 500 \, 000$$ در $m$ سطر بعدی،‌ در هر سطر، دو عدد صحیح $u$ و $v$ که با یک فاصله از هم جدا شده‌اند داده می‌شود. $uv$ یک یال از $G$ است. $$1 \leq u \lt v \leq n$$ # خروجی کمترین تعداد عملیات لازم برای تبدیل $G$ به یک درخت. # مثال‌ها ## ورودی نمونه ۱ ``` 5 4 1 2 1 3 2 3 4 5 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 3 2 1 2 1 3 ``` ## خروجی نمونه ۲ ``` 0 ``` <details class="blue"> <summary> **راهنمایی اول** </summary> ---------- گراف $G$ درخت است اگر و تنها اگر همبند باشد و هیچ دوری نداشته باشد. </details> <details class="blue"> <summary> **راهنمایی دوم** </summary> ---------- اگر $G$ دارای $c$ مولفه‌ی همبندی باشد، به حداقل $c - 1$ یال نیاز داریم که آن را همبند کنیم. اگر یک مولفه‌ی همبندی $G$ دارای $n_i$ راس و $m_i$ یال باشد، باید یک زیردرخت فراگیر آن که شامل $n_i - 1$ یال است را نگه‌داریم و $m_i - n_i + 1$ یال دیگر را از آن مولفه‌همبندی حذف کنیم. (با وجود این یال‌ها دور گراف به‌وجود می‌آید.) </details> <details class="blue"> <summary> **راهنمایی سوم** </summary> ---------- اگر مجموع یال‌های مورد نیاز برای حذف را محاسبه کنید،‌ می‌بیند که فقط به مقدار $c$ نیاز دارید و می‌توانید آن را با استفاده از الگوریتم‌های مثل *dfs، bfs* یا *dsu* بدست آورید. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک آرایه از اعداد صحیح مثل $a_1, a_2, \dots, a_n\,$ داریم. در $q$ مرحله یک عملیات مثل زیر روی آن انجام می‌دهیم. دو عدد صحیح مثل $\ell$ و $r$ انتخاب می‌کنیم که $1 \leq \ell \leq r \leq n$ باشد و سپس مقدار + $a_{\ell} = a_{\ell} + fib_1$ + $a_{\ell + 1} = a_{\ell + 1} + fib_2$ + $\dots$ + $a_r = a_r + fib_{r-\ell + 1}$ می‌شود که منظور از $fib_i$ جمله‌ی $i$ام دنباله فیبوناچی است. دنباله فیبوناچی به صورت زیر تعریف می‌شود: $$ fib_n = \begin{cases} 1 & n = 1 \\ 1 & n = 2 \\ fib_{n - 1} + fib_{n - 2} & n > 2 \end{cases} $$ از شما می‌خواهیم بعد از پایان این عملیات‌ها، مقدار نهایی اعضای آرایه را چاپ کنید. چون این مقدار می‌تواند خیلی بزرگ باشد. صرفاً باقی‌مانده هر عدد آرایه را بر $10^9 + 7$ چاپ کنید. # ورودی در سطر اول ورودی، دو عدد صحیح و مثبت $n$ و $q$ که با یک فاصله از هم جدا شده‌اند، داده می‌شود. $$1 \leq n, q \leq 100 \, 000$$ در سطر دوم ورودی، $n$ عدد صحیح $a_1, a_2, \dots, a_n\,$ که با یک فاصله از هم جدا شده‌اند داده می‌شود. $$1 \leq a_i \leq 10^9$$ در $q$ سطر بعدی، در هر سطر دو عدد صحیح $\ell$ و $r$ داده می‌شود که نشان‌دهنده‌ی بازه‌ی عملیات است. $$1 \leq \ell \leq r \leq n$$ # خروجی در تنها سطر خروجی، $n$ عدد صحیح که با یک فاصله از هم جدا شده‌اند را چاپ کنید که وضعیت نهایی آرایه‌ی $a$ را نشان می‌دهد. چون ممکن است مقدار اعداد آرایه خیلی بزرگ شود، باقی‌مانده‌ی این اعداد را بر $10^9 + 7$ چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 5 3 1 2 3 4 5 2 4 1 3 5 5 ``` ## خروجی نمونه ۱ ``` 2 4 6 6 6 ``` ## ورودی نمونه ۲ ``` 3 2 2 4 1 1 3 2 3 ``` ## خروجی نمونه ۲ ``` 3 6 4 ``` <details class="blue"> <summary> **راهنمایی اول** </summary> ---------- نیازی نیست همه‌ی تغییرات را در لحظه روی آرایه اعمال کنیم. می‌توانیم همه را دریافت کنیم و با ترتیبی مناسب آن‌ها را روی آرایه اعمال کنیم. </details> <details class="blue"> <summary> **راهنمایی دوم** </summary> ---------- اگر لحظه‌ی شروع و پایان هر بازه که باید تغییر کند را روی آرایه در نظر بگیریم و به ترتیب از چپ آرایه (اندیس ۰) شروع کنیم و به سمت راست (اندیس $n - 1$) حرکت کنیم و همه‌ی تغییرات را به همین ترتیب روی آرایه اعمال کنیم. به این ایده *sweep line* می‌گویند. </details> <details class="blue"> <summary> **راهنمایی سوم** </summary> ---------- با توجه به رابطه بازگشتی فیبوناچی که برای همه یکی هست می‌توان اتفاق این تغییرات را جمع کرد. یعنی اگر چند تغییر روی یک خانه اتفاق می‌افتد می‌توان همه‌ی آن‌ها را باهم جمع کرد. </details>