+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیرحسین اخیراً به شطرنج علاقه‌مند شده است. ریتینگ فعلی او برابر با $a$ است و می‌خواهد آن را به حداقل $b$ برساند. از آنجایی که امیرحسین بازیکن بسیار قدرتمندی است، تمام بازی‌های خود را می‌برد. پس از هر برد، ریتینگ او دقیقاً $x$ واحد افزایش پیدا می‌کند. مشخص کنید امیرحسین حداقل چند بازی باید انجام دهد تا ریتینگش حداقل$b$ شود. # ورودی در تنها خط ورودی، سه عدد صحیح $a$، $b$ و $x$ داده می‌شود. $$1 \leq a \leq b \leq 100$$ $$1 \leq x \leq 100$$ # خروجی در تنها خط خروجی، حداقل تعداد بازی‌های موردنیاز برای رسیدن به ریتینگ حداقل $b$ را چاپ کنید. # مثال ## ورودی نمونه ۱ ```text 10 20 3 ``` ## خروجی نمونه ۱ ```text 4 ``` ## ورودی نمونه ۲ ```text 15 15 7 ``` ## خروجی نمونه ۲ ```text 0 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت -------------------- محمدسام اخیرا مقادیر زیادی (!) کار بر روی سرش ریخته است و نمیتواند تمامی آنها را در یک روز انجام دهد. پس تصمیم میگیرد تا بیشترین تعداد کارمختلفی که میتواند انجام بدهد را انتخاب کند و آنها را انجام بدهد تا حداقل برای روز های آینده زمان آزاد بیشتری داشته باشد. روز او به $n$ واحد زمانی برابر تقسیم شده است و او $m$ کار مختلف برای انجام دادن دارد به طوری که انجام دادن هر کار دقیقا یک واحد زمانی طول میکشد و او باید برای هرکاری که میخواهد انجام دهد ، یک زمان انجام دادن انتخاب کند. همچنین کار $i$ ام باید تا قبل از شروع واحد زمانی $a_i + 1$ تمام شود ( به عبارتی اگر قرار باشد کار $i$ ام انجام شود، این کار باید در یکی از واحد های زمانی $1,2,3,...,a_i $ انجام شود.) علاوه بر اینها ، در یک واحد زمانی محمدسام حداکثر یک کار را میتواند انجام دهد. در صورت انتخاب بهینه کارها و زمان انجام آنها، بیشینه تعداد کار مختلفی که محمدسام در امروز قادر به انجام دادن است چند است ؟ # ورودی در خط اول ورودی به شما اعداد $n$ و $m$ به ترتیب داده میشود. در خط دوم $m$ عدد مختلف در یک خط می آیند که نشان دهنده آرایه $a$ است. $$1 \leq n,m \leq 10^5 $$ $$ 1 \leq a_i \leq n $$ # خروجی ماکسیمم تعداد کار مختفی که محمدسام در صورت انتخاب بهینه کارها و زمان آنها ، میتواند انجام دهد را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 4 3 4 1 1 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 4 6 2 2 3 3 4 4 ``` ## خروجی نمونه ۲ ``` 4 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت -------------------- یک آرایه به نام $a$ و به طول $2n$ را **قشنگ** می‌نامیم اگر به ازای هر $1 \leq i \leq 2n$ مقدار $1 \leq a_i \leq 2n^2$ باشد و همچنین به ازای هر $1 \leq x \leq 2n^2$ حداقل یکی از شروط زیر برقرار باشد: 1. عدد $x$ در آرایه حضور داشته باشد. 2. دو اندیس $ 1 \leq i,j \leq 2n$ وجود داشته باشند که $\ a_i + a_j = x $ باشد. دقت کنید که $i$ و $j$ می‌توانند برابر باشند. 3. دو اندیس $ 1 \leq i,j \leq 2n $ وجود داشته باشند که $ a_i - a_j = x \ $ باشد. بنابراین آرایه $a$ به طول $2n$ قشنگ است اگر و تنها اگر هر عدد $x$ از $1$ تا $2n^2$ یا خود در آرایه باشد، یا بتوان آن را به شکل مجموع یا تفاضل دو عضو آرایه نوشت. حال به شما یک عدد $n$ داده میشود و شما باید یک آرایه قشنگ به طول $2n$ بسازید. تضمین میشود چنین آرایه ای وجود دارد. # ورودی در یک خط به شما عدد $n$ داده شده است. $$1 \leq n \leq 500$$ # خروجی باید $2n$ عدد صحیح خروجی دهید که نشان دهنده اعضای آرایه قشنگ ساخته شده توسط شماست. اگر چند جواب مختلف وجود دارد، یکی را به دلخواه خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` 1 2 ``` ## ورودی نمونه ۲ ``` 2 ``` ## خروجی نمونه ۲ ``` 1 2 4 8 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت --------------------------------- *مرد عنکبوتی بعد از تریلر تبلیغاتی با لیونل مسی ، تصمیم گرفت با چهره های معروف حوزه برنامه نویسی هم تریلر تبلیفاتی درست کند، اما بعد از آشنایی با الگوریتم و برنامه نویسی رقابتی ، او به کلی شیفته این حوزه شد و حالا درحال تفکر بر روی برخی سوالات این حوزه است ...* مرد عنکبوتی یک عدد مورد علاقه دارد و آن را $x$ مینامد. او یک آرایه از اعداد را مستحکم مینامد اگر به ازای هر دو عضو $a$ و $b$ متفاوت از این آرایه داشته باشیم : $$ x \leq (a \oplus b) $$ که $x$ همان عدد مورد علاقه مرد عنکبوتی است. حال به شما یک آرایه از اعداد ورودی داده میشود و شما باید تعداد زیرمجموعه های **ناتهی** مستحکم از اعداد این آرایه را باقیمانده بر $10^9 + 7$ محاسبه کنید. توضیحات : $ a \oplus b $ نشان دهنده حاصل عملیات بیتی XOR بر روی اعداد $a$ و $b$ است. # ورودی در خط اول به شما به ترتیب اعداد $n$ و $x$ ، طول آرایه و عدد مورد علاقه مرد عنکبوتی ورودی داده می‌شود. در خط بعد $n$ عدد به ترتیب آمده اند که نشان دهنده اعضای آرایه مذکور در سوال هستند. **تضمین میشود اعداد موجود در آرایه متمایز هستند.** $$ 1 \leq n \leq 5 \cdot 10^5 $$ $$ 0 \leq a_i , x \leq 10^9 $$ # خروجی در یک خط، تعداد زیرمجموعه های ناتهی مستحکم از آرایه ورودی سوال را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 4 0 0 2 3 4 ``` ## خروجی نمونه ۱ ``` 15 ``` ## ورودی نمونه ۲ ``` 4 8 2 10 5 12 ``` ## خروجی نمونه ۲ ``` 8 ``` ## ورودی نمونه 3 ``` 7 11 10 9 2 1 8 11 15 ``` ## خروجی نمونه 3 ``` 11 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیرحسین و محمدسام درختی پیدا کرده‌اند و به دلیل اعصاب خرابشان دقیقاً نمی‌دانند که چه کاری می‌خواهند با این درخت انجام دهند. ابتدا امیرحسین به رأس $u$ یک مقدار $a_u$ نسبت می‌دهد. می‌دانیم امتیاز $path(u, v)$ برابر است با: \[ \frac{\sum_{w \in \operatorname{path}(u,v)} a_w}{\operatorname{len}(u,v)} \] که در آن $path(u, v)$ کوتاه‌ترین مسیر از رأس $u$ به رأس $v$ است و $len(u, v)$ تعداد رأس‌های موجود در $path(u, v)$ را نشان می‌دهد. در ادامه محمدسام یک عدد $k$ انتخاب می‌کند و سپس در $q$ مرحله مقدار بعضی از رأس‌ها را افزایش می‌دهد. شما باید پس از هر درخواست، در میان تمامی مسیرهایی که حداقل $k$ رأس دارند، بیشترین امتیاز ممکن را پیدا کنید. توجه کنید که هر عملیات روی درختی انجام می‌شود که تمام تغییرات مراحل قبل روی آن اعمال شده است. # ورودی شما باید مسئله را برای $T$ تست‌کیس مستقل حل کنید. در خط اول، عدد $T$ داده می‌شود. برای هر تست‌کیس: - در خط اول دو عدد $n$ و $k$، به‌ترتیب تعداد رأس‌های درخت و عدد انتخابی محمدسام، داده می‌شود. - در خط دوم، $n$ عدد داده می‌شود که مقدار $a_i$ را برای هر رأس مشخص می‌کنند. - در $n-1$ خط بعد، هر خط شامل دو عدد $v_i$ و $u_i$ است که دو سر یال‌های درخت را مشخص می‌کنند. - در خط بعد، عدد $q$ داده می‌شود که تعداد تغییرات را نشان می‌دهد. - در $q$ خط بعد، هر خط شامل دو عدد $v_i$ و $x_i$ است؛ یعنی در این مرحله مقدار رأس $v_i$ به اندازه $x_i$ افزایش می‌یابد. $$1 \leq T \leq 10^5$$ $$1 \leq n \leq 10^5$$ $$1 \leq k \leq 10$$ $$1 \leq q \leq 10^4$$ $$1 \leq a_i, x_i \leq 10^9$$ تضمین می‌شود که مجموع مقادیر $n$ در تمامی تست‌کیس‌ها از $3 \times 10^5$ و مجموع مقادیر $q$ از $3 \times 10^4$ بیشتر نخواهد شد. # خروجی برای هر پرسش، پاسخ را به صورت $A/B$ چاپ کنید، به‌طوری که: $$gcd(A,B)=1$$ # مثال ## ورودی نمونه ۱ ```text 2 6 2 6 16 6 15 5 4 1 2 2 3 2 4 2 5 4 6 2 1 4 3 5 14 1 12 19 9 17 9 10 11 18 9 19 10 14 18 8 1 2 2 3 1 4 1 5 4 6 2 7 7 8 8 9 6 10 6 11 1 12 11 13 3 14 5 10 3 2 8 7 9 5 6 2 1000000000 ``` ## خروجی نمونه ۱ ```text 31/2 31/2 22/1 27/1 27/1 27/1 1000000027/1 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت --------------------------------- محمدسام تصمیم گرفته است یک گراف را به روشی خاص بسازد. او فهرستی از یال‌های پیشنهادی در اختیار دارد، اما تنها زمانی می‌تواند یک یال را به گراف اضافه کند که مجموع وزن دو مؤلفه‌ای که دو سر آن یال در آن‌ها قرار دارند، به اندازه‌ی کافی بزرگ باشد. هر بار که یالی اضافه می‌کند، شماره‌ی آن را در دفترچه‌ی خود یادداشت می‌کند؛ اما پس از پایان کار، دفترچه‌اش گم می‌شود! حالا شما باید این شماره‌ها را بازیابی کنید. در ابتدا یک گراف بدون یال با $n$ رأس داریم. به هر رأس یک وزن (عدد صحیح نامنفی) اختصاص داده شده است. وزن راس $i$ برابر با $w_i$ است. همچنین $m$ سه‌تایی به صورت $(a_i, b_i, s_i)$ داده شده است که کاندید‌های یال‌های گراف است. $a_i$ و $b_i$ دو رأس و $s_i$ یک عدد صحیح نامنفی است. سپس محمدسام فرایند زیر را بارها تکرار می‌کند: + اگر اندیس $i$ ای وجود داشت که رأس‌های $a_i$ و $b_i$ در دو مؤلفه‌ی همبند متفاوت قرار داشته باشند و مجموع وزن رأس‌های دو مؤلفه‌ی آن‌ها حداقل برابر با $s_i$ باشد، **کوچکترین $i$ با این ویژگی** انتخاب می‌شود، سپس محمدسام $i$ را در دفترچه‌ خود یادداشت می‌کند و در نهایت یالی بین $a_i$ و $b_i$ به گراف اضافه‌ می‌کند. + اگر چنین $i$ ای وجود نداشت، فرآیند خاتمه می‌یابد. شما باید شماره‌هایی را که در پایان در دفترچه ثبت شده‌اند، به همان ترتیب بازیابی کنید. # ورودی در خط اول دو عدد صحیح $n$ و $m$ داده می شود که به‌ترتیب تعداد رأس‌های گراف و تعداد یال‌های مدنظر است. در خط دوم $n$ عدد صحیح $w_1, w_2, \ldots, w_n$ داده می‌شود که وزن رأس‌ها را مشخص می‌کنند. در $m$ خط بعد، هر خط شامل سه عدد صحیح $a_i$، $b_i$ و $s_i$ است که یکی از سه‌تایی‌های داده‌شده را توصیف می‌کند. $$1 \leq n, m \leq 2 \times 10^5$$ $$1 \leq a_i, b_i \leq n \ \ (a_i \ne b_i)$$ $$0 \leq w_i, s_i \leq 10^6$$ # خروجی در خط اول، تعداد شماره‌هایی را که در دفترچه نوشته شده‌اند چاپ کنید. در خط دوم، این شماره‌ها را **به همان ترتیبی که نوشته شده‌اند** چاپ کنید. # مثال ## ورودی نمونه ۱ ```text 5 5 1 4 3 4 0 4 5 5 3 1 1 2 5 2 4 3 1 4 1 4 ``` ## خروجی نمونه ۱ ```text 4 2 3 1 4 ``` ## ورودی نمونه ۲ ```text 3 5 3 2 2 1 2 6 1 2 6 1 2 3 1 2 6 2 3 6 ``` ## خروجی نمونه ۲ ```text 2 3 5 ```