+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت -------------------- امیرحسین به تازگی ورزش جدیدی به نام شوتبال اختراع کرده است. شوتبال همان فوتبال است با این تفاوت که تعداد بازیکنان هر تیم در زمین عددی دلخواه است و حتی لزومی ندارد تعداد بازیکنان دو تیم برابر باشد. می‌دانیم اگر یک تیم $x$ بازیکن در خط دفاعی، $y$ بازیکن در خط میانی و $z$ بازیکن در خط حمله داشته باشد، به دلیل اهمیت خط میانی جهت بازی مالکانه، قدرت تیم برابر با $x + 2y + z$ خواهد بود. از آنجا که این ورزش تازه اختراع شده‌ است، درحال حاضر تنها سه تیم در لیگ شوتبال شرکت می‌کنند، به امیرحسین کمک کنید تا بفهمد کدام یک از این سه تیم از بقیه قوی‌تر است و قهرمان لیگ می‌شود. # ورودی در خط اول ورودی سه عدد طبیعی $a_1$، تعداد بازیکنان تیم اول در خط دفاعی، $a_2$، تعداد بازیکنان تیم اول در خط میانی و $a_3$، تعداد بازیکنان تیم اول در خط حمله می‌آیند. در خط دوم ورودی سه عدد طبیعی $b_1$، تعداد بازیکنان تیم دوم در خط دفاعی، $b_2$، تعداد بازیکنان تیم دوم در خط میانی و $b_3$، تعداد بازیکنان تیم دوم در خط حمله می‌آیند. در خط سوم ورودی سه عدد طبیعی $c_1$، تعداد بازیکنان تیم سوم در خط دفاعی، $c_2$، تعداد بازیکنان تیم سوم در خط میانی و $c_3$، تعداد بازیکنان تیم سوم در خط حمله می‌آیند. $$1 \leq a_1, a_2, a_3, b_1, b_2, b_3, c_1, c_2, c_3 \leq 100$$ # خروجی در تنها خط خروجی، شماره تیمی را چاپ کنید که بیشترین قدرت را دارد. اگر چند تیم بیشترین قدرت یکسان را داشتند، کوچک‌ترین شماره را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 9 2 3 5 4 4 4 2 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 4 3 3 4 7 2 3 5 7 ``` ## خروجی نمونه ۲ ``` 2 ``` در این حالت قدرت تیم دوم و سوم برابر و از تیم اول بیشتر است.

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیرحسین برای انجام کارهای روزانه‌اش $n$ ثانیه زمان در اختیار دارد. او همچنین $c$ واحد پول دارد و می‌تواند حداکثر دمای $h$ درجه را تحمل کند؛ به این معنا که دمای بدن او در هیچ لحظه‌ای نباید از $h$ بیشتر شود، ضمنا می‌دانیم دمای بدن او همواره عددی صحیح و نامنفی خواهد بود. در هر ثانیه، امیرحسین یکی از دو حالت زیر را انتخاب می‌کند: + هدفون روی گوشش باشد: در این حالت می‌تواند کولر را روشن یا خاموش کند. اگر کولر خاموش باشد، هدفون روگوشی او مانند یک پتو عمل کرده و دمای بدن امیرحسین در آن ثانیه یک درجه افزایش می‌یابد و اگر کولر روشن باشد، دمای بدن او تغییری نمی‌کند. روشن بودن کولر در هر ثانیه، هزینه‌ای برابر با یک واحد پول دارد. + هدفون روی گوشش نباشد: در این حالت دمای بدن امیرحسین در آن ثانیه یک درجه کاهش می‌یابد و روشن یا خاموش بودن کولر روی دمای بدن او بی‌تاثیر است؛ با این استثنا که دما هیچ‌گاه از صفر کمتر نمی‌شود. به بیان دقیق‌تر، اگر دما پیش از این ثانیه t باشد، پس از آن برابر $max(0, t - 1)$ خواهد بود. امیرحسین در ابتدا دمای بدن $0$ درجه دارد و نمی‌تواند در هیچ لحظه‌ای دمایی بیشتر از $h$ درجه داشته باشد. همچنین مجموع هزینه‌ی روشن بودن کولر در تمام $n$ ثانیه نباید از $c$ بیشتر شود. لذت امیرحسین از گوش دادن به موسیقی به شکل زیر محاسبه می‌شود: هر **بازه‌ی ماکسیمال** از ثانیه‌های متوالی که در آن‌ها هدفون روی گوش امیرحسین قرار دارد، یک بازه‌ی گوش دادن موسیقی محسوب می‌شود. اگر طول این بازه $l$ ثانیه باشد، مقدار $l^2$ به لذت او اضافه می‌شود. با توجه به مقادیر $n$، $c$ و $h$، **بیشترین مقدار لذتی که امیرحسین می‌تواند به دست آورد را محاسبه کنید.** # ورودی در تنها خط ورودی، سه عدد صحیح $n$، $h$ و $c$ داده می‌شود. $$1 \leq n, h, c \leq 10^9$$ # خروجی در تنها خط خروجی، یک عدد صحیح چاپ کنید که برابر با بیشترین میزان لذتی باشد که امیرحسین می‌تواند به دست آورد. # مثال ## ورودی نمونه ۱ ``` 10 2 2 ``` ## خروجی نمونه ۱ ``` 21 ``` + $2$ ثانیه گوش‌دادن، لذت $4$ + $2$ ثانیه استراحت تا دما صفر شود + $1$ ثانیه گوش‌دادن، لذت $1$ + $1$ ثانیه استراحت + $4$ ثانیه گوش‌دادن با استفاده از $2$ واحد پول برای کولر، لذت $16$ در مجموع: $$4 + 1 + 16 = 21$$

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- تعدادی ماهی در یک صف قرار گرفته‌اند. وزن هر ماهی به جز ماهی اول مشخص است و وزن ماهی $i$م برابر با $a_i$ است. ماهی $i$ می‌تواند ماهی $j$ را بخورد اگر و تنها اگر $a_j \leq a_i \ $، درصورتی که ماهی $i$ ماهی $j$ را بخورد وزن ماهی $i$ در نهایت برابر با مجموع وزن دو ماهی خواهد شد و ماهی $j$ دیگر در صف نخواهد بود. تا زمانی که بیش از یک ماهی در صف باقی مانده باشد، دو مرحلهٔ زیر به‌ترتیب اجرا می‌شوند: + ابتدا ماهی اول تلاش می‌کند تنها ماهی مجاور خود را بخورد. اگر ماهی اول نتواند ماهی جلوی خود را بخورد، بازی به پایان می‌رسد و او بازنده خواهد شد. + امیرحسین که از ماهی اول متنفر است، می‌تواند تعدادی جفت از ماهی‌های باقی‌مانده(شامل ماهی اول) را انتخاب کند (او می‌‌تواند هیچ جفتی انتخاب نکند)، به‌طوری‌که هر ماهی حداکثر در یک جفت قرار بگیرد و دو ماهیی که مجاور یکدیگر نیستند در یک جفت قرار نگیرند. سپس در هر جفت، امیرحسین ماهی سنگین‌تر را مجبور می‌کند جفت سبک‌تر خود را بخورد (اگر وزن دو ماهی برابر باشد یکی از آنها به انتخاب امیرحسین دیگری را می‌خورد). امیرحسین که کمر به نابودی ماهی اول بسته می‌خواهد کمترین عدد طبیعی $x$ را بداند به طوری که اگر وزن ماهی اول $x$ باشد $(a_1=x) \ $، امیرحسین در بازی هرطور جفت ها را انتخاب کند باز تنها ماهی باقی مانده در آخر بازی ماهی اول خواهد بود. # ورودی در خط اول، عدد صحیح $n$، تعداد ماهی‌ها، داده می‌شود. در خط دوم، $n-1$ عدد صحیح داده می‌شود که به‌ترتیب وزن ماهی‌های دوم تا $n$م را نشان می‌دهند. $$ 1 \leq n \leq 3*10^5 $$ $$ 1 \leq a_i \leq 10^9 $$ # خروجی در تنها خط خروجی، کمترین مقدار ممکن برای وزن اولیه‌ی ماهی اول را چاپ کنید؛ به‌طوری‌که ماهی اول در هر صورت توسط ماهی دیگری خورده نشود. # مثال ## ورودی نمونه ۱ ``` 3 3 7 ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 6 7 1 10 6 8 ``` ## خروجی نمونه ۲ ``` 16 ```

+ محدودیت زمان: 3 ثانیه + محدودیت حافظه: ۲۵۶ مگابایت --- محمدسام به تازگی به شرکت در قرعه کشی های مختلف علاقه مند شده است. در آخرین قرعه کشی ای که او شرکت کرده است ، به او یک کد $n$ رقمی با ارقام 1 و 2 و 3 داده میشود. او یک شاخص میزان خوش یُمنی برای خود درنظر میگیرد تا بتواند با استفاده از آن ، حدس بزند که آیا ممکن است در قرعه کشی برنده شود یا خیر. او در یک کد $x$ رقمی به نام $s$ که ارقام آن به ترتیب $s_1$ تا $s_x$ هستند، جذاب بودن آن کد را برابر با تعداد اندیس های $i$ تعریف میکند که $$ 1 \leq i \leq x-1 $$ و $$s_i < s_{i+1} \quad $$ است. و آن را با $G(s) $ نشان میدهد. ( جذاب بودن یک کد 0 رقمی ، برابر با 0 است ) به عبارتی $ G(s) $ نشان دهنده تعداد جایگاه هایی در کد $s$ است که رقم آنها از رقم بعدی خود کوچکتر است. او میزان خوش یُمن بودن یک کد قرعه کشی $n$ رقمی $s$ را ، برابر با جمع $ G(a) ^ k $ به ازای تمامی $2^n $ زیردنباله کد $s$ در نظر میگیرد . به صورتی که $k$ یک عدد ثابت است و به ازای هر تست کیس به شما ورودی داده میشود و $a$ زیردنباله ای از $s$ است . به طور دقیقتر میزان خوش یُمنی یک کد برابر با عبارت زیر است : $$ \sum_{m=0}^{n} \; \sum_{1\le i_1<i_2<\cdots<i_m\le n} G(s_{i_1}s_{i_2}\cdots s_{i_m})^k $$ محمدسام هنوز کد قرعه کشی خود را دریافت نکرده و نمیداند قرار است چقدر این کد خوش یُمن باشد. اما میداند این کد ، یک کد $n$ رقمی با ارقام 1 و 2 و 3 است . او میداند کد قرعه کشی اش ، به صورت تصادفی و با احتمال برابر ، یکی از $3^n$ کد $n$ رقمی موجود ( با ارقام 1 و 2 و 3 ) خواهد بود . حال او از شما میخواهد با توجه به این اطلاعات ، امیدریاضی میزان خوش یُمنی کدی که محمدسام دریافت خواهد کرد را باقیمانده بر $10^9 + 7$ حساب کنید. میتوان نشان داد جواب به صورت کسر ساده نشدنی $ \frac{p}{q} $ است که $p$ و $ q $ اعداد صحیح هستندو $ q \neq 0 $ و شما باید $ p \cdot q^{-1} ( mod \ 10^9 + 7 ) $ را خروجی دهید که $ q^{-1} $ وارون ضربی $ q $ باقیمانده بر $ 10^9 + 7 $ است. **توضیحات :** زیر دنباله ای از یک کد $s$ , دنباله ای است که از پاک کردن برخی اعضای $s$ ( که میتواند تمامی اعضا یا هیچکدام از آنها هم باشد ) به دست می آید . و یک کد $2^n$ زیردنباله دارد. # ورودی ورودی به صورت $T$ تست‌کیس مختلف می‌آید که برای هرکدام باید مسئله را جداگانه حل کنید. در خط اول ابتدا عدد $T$ و سپس در $T$ خط بعد به ترتیب برای هر تست‌کیس عدد $n$ و عدد ثابت $k$ می آید که به ترتیب نشان دهنده طول کد قرعه کشی و عدد ثابت $k$ است. $$ 1 \leq T \leq 50$$ $$ 1 \leq n \leq 10^{18} $$ $$ 1 \leq k \leq 50$$ تضمین می‌شود جمع مقادیر $k$ بر روی همه تست‌کیس‌ها حداکثر $50$ است. # خروجی در یک خط، باید امیدریاضی میزان خوش یُمن بودن کد قرعه کشی محمدسام را حساب کنید ( در حالی که این کد به صورت تصادفی و با احتمال برابر برای او انتخاب خواهد شد ) # مثال ## ورودی نمونه ۱ ``` 3 1 1 5 2 10 10 ``` ## خروجی نمونه ۱ ``` 0 148148169 525754884 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- نلی $n$ تُنگ بلوری دارد که هرکدام دارای میزان مشخصی **شفافیت** هستند. او می‌خواهد همه‌ی تنگ‌ها را در یک ردیف و پشت سر هم قرار دهد. شفافیت تنگ $i$م برابر با $a_i$ است. اما به دلایل نه‌چندان منطقی، قرار گرفتن تنگ‌ها در کنار یکدیگر باعث می‌شود بعضی از آن‌ها ترک بخورند! میزان ترک خوردن هر تنگ به تنگ‌هایی که قبل و بعد از آن قرار گرفته‌اند بستگی دارد. توجه کنید که ترک خوردن یک تنگ باعث تغییر شفافیت آن نمی‌شود. فرض کنید در یک ترتیب، تنگ $i$ در جایگاهی مشخص قرار گرفته است. برای محاسبه‌ی میزان ترک خوردن این تنگ، از میان تمام تنگ‌هایی که **قبل از آن** قرار گرفته‌اند، شفاف‌ترین تنگ را $j$ و به همین شکل، از میان تمام تنگ‌هایی که **بعد از آن** قرار گرفته‌اند نیز شفاف‌ترین تنگ را $k$ در نظر می‌گیریم. سپس میزان ترک خوردن تنگ $i$ به صورت زیر تعیین می‌شود: + در صورتی که $a_i < min(a_j, a_k) \ $، تنگ $i$م به مقدار $min(a_j, a_k) - a_i \ $ ترک می‌خورد. + اگر $a_i > min(a_j, a_k) \ $ و $a_i < max(a_j, a_k) \ $، تنگ $i$م به مقدار $max(a_j, a_k) - a_i \ $ ترک می‌خورد. + اگر $a_i > max(a_j, a_k) \ $، تنگ $i$ ترک نمی‌خورد و میزان ترک خوردگی آن برابر با صفر است. برای اولین تنگ، فقط تنگ‌های بعد از آن را در نظر می‌گیریم و برای آخرین تنگ نیز فقط تنگ‌های قبل از آن را. همچنین، اگر در یک سمت هیچ تنگی وجود نداشته باشد، بیشترین شفافیت آن سمت را برابر با $0$ در نظر می‌گیریم. می‌دانیم شکنندگی یک ترتیب مشخص از تنگ ها برابر با مجموع مقدار ترک خوردگی $n$ تنگ است. نلی تنگ های خود را به امیرحسین داده و از او می‌خواهد تا به او بگوید در نهایت کمترین مقدار ممکن شکنندگی در میان تمام جایگشت‌های این $n$ تنگ چقدر خواهد بود، امیرحسین که ذهنش کمی مشغول است از شما برای یافتن پاسخ کمک می‌‌خواهد. # ورودی در خط اول، عدد صحیح $n$، تعداد تُنگ‌های بلوری، داده می‌شود. $$1 \leq n \leq 3*10^5$$ در خط دوم، $n$ عدد صحیح داده می‌شود که $a_i$ میزان شفافیت تنگ $i$ است، تضمین می‌شود هیچ دو تنگی با شفافیت برابر وجود ندارند. $$1 \leq a_i \leq 10^9$$ # خروجی در تنها خط خروجی، کمترین مقدار ممکن برای شکنندگی یک ترتیب از تنگ ها را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 3 1 4 2 5 ``` ## خروجی نمونه ۱ ``` 6 ``` ## ورودی نمونه ۲ ``` 7 7 1 10 2 6 8 12 ``` ## خروجی نمونه ۲ ``` 20 ```