+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- نوروز که به دلیل قرنطینه کم‌حوصله شده، می‌خواهد به سفری تفریحی برود. (او با استفاده از [اپلیکیشن بانکت](http://www.asredanesh.com/products-services/e-financial/e-banking/bankette/) بلیطی برای سفر تهیه کرده است). وی با استاد خود، آقا فیروز صحبت می‌کند که از او اجازه بگیرد تا بتواند در کلاس‌های آنلاینش شرکت نکند. از آن‌جایی که آقا فیروز به فکر سلامتی شاگردش است، می‌خواهد او را وادار کند تا در خانه بماند. برای این‌کار به او می‌گوید که در امتحان نمره $X$ گرفته است؛ ولی این شرایط برای بهبود نمره‌اش وجود دارد: + در صورتی که **به سفر نرود**، ۲۰ می‌گیرد. + اگر دقیقا **هفت روز** به سفر برود، همان نمره $X$ را می‌گیرد. + در غیر این صورت به ازای **هر یک روز، دقیقا یک نمره** کم می‌شود (اگر نمره او کم‌تر از صفر شود، همان نمره صفر را می‌گیرد). این حالت شامل حالت‌های که نوروز بین ۱ تا ۶ روز به سفر برود هم می‌شود. حال نوروز بلیط سفر خود را از بانکت خریده‌ و می‌داند که دقیقا $N$ روز به سفر می‌رود، اما به‌دلیل افسردگی از قرنطینه، نمره خود را حساب نمی‌کند. به او کمک کنید و بگویید چه نمره‌ای در این درس می‌گیرد. # ورودی در خط اول عدد صحیح $X$ آمده‌است که بیانگر نمره فعلی نوروز در درس بهداشت و سلامت می‌باشد. در خط دوم عدد صحیح $N$ آمده‌است که بیانگر تعداد روز‌هایی می‌باشد که نوروز می‌خواهد به سفر برود. $$ 0 \le X \le 20 $$ $$ 0 \le N \le 100$$ # خروجی در تنها خط خروجی، نمره نهایی‌ که نوروز در درس بهداشت و سلامت می‌گیرد را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 14 0 ``` ## خروجی نمونه ۱ ``` 20 ``` نمره اولیه نوروز ۱۴ است اما چون به مسافرت نمی‌رود، نمره ۲۰ را می‌گیرد. ## ورودی نمونه ۲ ``` 6 7 ``` ## خروجی نمونه ۲ ``` 6 ``` نمره اولیه نوروز ۶ است و به دلیل اینکه دقیقا ۷ روز به مسافرت می‌رود، همان نمره ۶ را می‌گیرد و نمره‌اش تغییری نمی‌کند. ## ورودی نمونه ۳ ``` 13 9 ``` ## خروجی نمونه ۳ ``` 4 ``` نمره اولیه نوروز ۱۳ است و به دلیل اینکه ۹ روز به مسافرت رفته، پس ۹ نمره از او کم می‌شود و نمره‌اش ۴ می‌شود. <details class="blue"> <summary> راهنمایی ۱ </summary> ابتدا حالت‌هایی را که $N$ برابر با ۰ یا ۷ است با استفاده از دو شرط جدا کنید. سپس برای حالت‌هایی که $N\neq7$ و $N\neq0$ است با توجه به این که $X$ بزرگ‌تر از $N$ هست یا نه سوال را حل کنید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> شبه‌کد جواب به شکل زیر می‌شود: ``` if n equals 0 print(20) else if n equals 7 print(x) else print(max(0, x - n)) ``` </details>

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پس از اینکه هر $k$ شاگرد آقا فیروز به‌خاطر او،‌ به مسافرت نرفتند؛ او برای اینکه آن‌ها را تشویق کند، تصمیم گرفت تا به همراه آن‌ها به قنادی کاف برود و برایشان کیک بخرد. پس از اینکه وارد قنادی شدند، آقا فیروز از دیدن قیمت کیک‌ها خیلی جا خورد ولی چون شاگردانش را خیلی دوست داشت، تصمیم گرفت حتما کیک را بخرد. او که معلم ریاضی بود با خود فکری کرد که هم شاگردان خوشحال باشند و هم خودش هزینه کم‌تری کند. در ویترین قنادی $n$ کیک کنار هم چیده شده که قیمت $i$امین آن‌ها $c_i$ است. آقا فیروز تصمیم گرفت تا کیک‌ها را به $k$ بازه **متوالی** تقسیم کند (هر کیک باید در دقیقا یک بازه باشد) و به شاگرد $i$ام بگوید بین کیک‌های بازه $i$ام یکی را که خوش‌مزه‌تر است انتخاب کند(هر کدام از شاگردان، کیکی را به عنوان خوش‌مزه‌ترین انتخاب می‌کند که از همه **گران‌تر** است و در صورتی که چند کیک با گران‌ترین قیمت وجود داشت، به دلخواه یکی از آن‌ها را انتخاب می‌کند). در نهایت او از بین $k$ کیکی که شاگردان انتخاب کردند، یکی از آن‌ها که در واقع **ارزان‌ترینشان** است را انتخاب می‌کند و برای آن‌ها می‌خرد. می‌دانیم در این ایام رعایت بهداشت ضروری است و به همین دلیل، آقا فیروز مشغول نصب [همراه‌بانک مهر ایران](http://www.asredanesh.com/products-services/e-financial/e-banking/gh-mehr-mobile-bank/) برای تلفن همراه خود است تا بتواند پول کیک را به صورت آنلاین و بدون رد و بدل کردن پول نقد پرداخت کند. در این فاصله شما باید شما راهکاری پیدا کنید که آقا فیروز کیک‌ها را دسته‌بندی کند که در نهایت کم‌ترین مقدار پول ممکن را کارت به کارت کند و این مقدار پول لازم را چاپ کنید. در واقع شما باید راهکاری برای دسته‌بندی کیک‌ها پیدا کنید که در آن کم‌ترین مقدار، میان بیشینه این دسته‌ها، کم‌ترین مقدار ممکن باشد و این مقدار را چاپ کنید. # ورودی در خط اول دو عدد $n$ و $k$ آمده است که به ترتیب نمایانگر تعداد کیک‌ها و تعداد شاگرد‌ها می‌باشند. در خط دوم $n$ عدد آمده‌ است که عدد $i$ام نمایانگر $c_i$ است. $$ 1 \le k \le n \le 5\ 000 $$ $$ 1 \le c_i \le 5\ 000$$ # خروجی در تنها خط خروجی، مقدار پولی که آقا فیروز می‌پردازد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 3 2 3 ``` ## خروجی نمونه ۱ ``` 3 ``` در این مثال هر گونه آقا فیروز کیک‌ها را بازه‌بندی کند، یک بازه به طول ۱ و یک بازه به طول ۲ ایجاد می‌شود که در هر دوی آن‌ها قیمت گران‌ترین کیک برابر ۳ است و بنابراین او راهی به جز پرداخت ۳ واحد پول ندارد. ## ورودی نمونه ۲ ``` 5 3 5 4 3 2 2 ``` ## خروجی نمونه ۲ ``` 2 ``` در این مثال آقا فیروز می‌تواند هر کدام از عناصر کناری را یک بازه و سه عنصر وسط را هم یک بازه در نظر بگیرد. در این صورت شاگردها کیک‌هایی با قیمت‌های ۵، ۴ و ۲ را پیشنهاد می‌دهند که او می‌تواند کیک با قیمت ۲ را بخرد و کمترین مقدار ممکن را پرداخت کرده است چون کیکی با قیمت کمتر وجود ندارد. ## ورودی نمونه ۳ ``` 4 1 1 3 4 2 ``` ## خروجی نمونه ۳ ``` 4 ``` در این مثال آقا فیروز تنها یک شاگرد دارد و مجبور است تمامی کیک‌ها را یک بازه در نظر بگیرد و در این صورت شاگردش نیز گران‌ترین کیک یعنی کیک با قیمت ۴ را انتخاب می‌کند. <details class="blue"> <summary> راهنمایی ۱ </summary> مساله را بر حسب $k$ به سه حالت زیر تقسیم کنید: + $k = 1$ + $k = 2$ + $k \ge 3$ سپس برای هر یک از این سه حالت جواب مساله را بر حسب رابطه‌ای از آرایه به دست آورید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> به ازای $k = 1$ تنها به یک حالت می‌توان آرایه را بازه‌بندی کرد و به همین دلیل جواب برابر با عنصر بیشینه آرایه است؛ در حالت $k \ge 3$ هم می‌توان طوری بازه‌بندی را انجام داد که عضو کمینه در یک بازه بیفتد و بنابراین جواب این حالت برابر با عضو کمینه آرایه است. حال تنها حالت $k = 2$ باقی می‌ماند که باید آن را حل کنید. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> در حالت $k = 2$ جواب برابر کمینه عضو اول و آخر آٰرایه است؛ چون می‌توانید آرایه را طوری دسته‌بندی کنید که یکی از این اعضا در یک دسته قرار بگیرد. هم‌چنین در هر حالتی از دسته‌بندی می‌توان این دو را به عنوان کیک خوشمره انتخاب کرد و بنابراین جواب نمی‌تواند کم‌تر شود. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز به تازگی کارهای مدیریت ساختمان خود را با استفاده از [نرم‌افزار سبزپرداز](https://sabzpardaz.org/) انجام می‌دهد؛ این نرم‌افزار به او کمک می‌کند تا کارهایش را خیلی سریع‌تر انجام دهد و وقت بیشتری برای بازی با نوروز داشته باشد. به همین منظور او یک جدول $n \times m$ بر روی زمین کشید و در هر کدام از خانه‌های آن، تعدادی کشمش قرار داد. البته در بعضی از خانه‌های جدول چمن قرار داشت و در آن‌ها کشمش نگذاشت (سطرهای جدول از بالا به پایین از ۱ تا $n$ و ستون‌ها از چپ به راست با ۱ تا $m$ شماره‌گذاری شده‌اند). حال نوبت نوروز است که بازی کند. او ابتدا باید **یکی از خانه‌های سطر پایین جدول** (سطر شماره $n$) را انتخاب کند و بر روی آن برود. سپس طبق گفته آقا فیروز هر بار می‌تواند یکی از دو حرکت زیر را انجام دهد (به شرطی که به خانه‌ای که چمن دارد و یا خارج از جدول است نرود): + یک خانه به چپ برود. + یک حرکت شبیه اسب شطرنج داشته باشد؛ یعنی ابتدا دو سطر به بالا برود و سپس اگر تاکنون زوج بار از این حرکت استفاده کرده بود، یک خانه به سمت چپ و در غیر این صورت یک خانه به سمت راست برود. (توجه کنید که صرفا باید خانه آخر چمن نداشته باشد و اگر خانه دو سطر بالاتر چمن داشته باشد، مشکلی در حرکت به وجود نمی‌آورد) هم‌چنین نوروز زمانی می‌تواند به بازی خاتمه دهد که در **سطر شماره یک** باشد. از آن‌جایی که نوروز خیلی کشمش دوست دارد، هر زمان که وارد یک خانه می‌شود، همه کشمش‌های آن را برای خودش برمی‌دارد. حال او از شما می‌خواهد تا بگویید با شرایط بالا حداکثر چند کشمش می‌تواند به دست آورد. هم‌چنین اگر مسیری با شرایط بالا وجود نداشته باشد، نوروز نمی‌تواند هیچ کشمشی به دست بیاورد و باید صفر چاپ کنید. # ورودی در خط اول دو عدد $n$ و $m$ آمده است که به ترتیب طول و عرض جدول بازی را نشان می‌دهند. تضمین می‌شود که $n$ عددی فرد است. در $i$امین خط از $n$ خط بعدی $m$ عدد آمده است که $j$امین آن‌ها نشان‌دهنده تعداد کشمش‌های خانه واقع در تقاطع سطر $i$ام و ستون $j$ام می‌باشد. این تعداد را با $a_{i, j}$ نشان می‌دهیم. $$ 1 \le n, m \le 1\ 000$$ $$ 0 \le a_{i, j} \le 100\ 000$$ اگر تعداد کشمش‌های واقع در یک خانه صفر باشد، یعنی آن خانه دارای چمن است و نوروز نمی‌تواند بر روی آن برود. # خروجی در تنها خط خروجی، حداکثر تعداد کشمش‌هایی که نوروز می‌تواند بخورد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 5 0 4 2 0 5 ``` ## خروجی نمونه ۱ ``` 6 ``` نوروز می‌تواند از خانه سوم تنها سطر بازی شروع کرده و سپس یک خانه به چپ بیاید و در همان‌جا کار خود را تمام کند که در این صورت ۶ کشمش نصیب او می‌شود. ## ورودی نمونه ۲ ``` 3 4 7 0 6 10 1 8 3 6 7 0 6 10 ``` ## خروجی نمونه ۲ ``` 16 ``` در این‌جا نوروز می‌تواند از خانه چهارم سطر سوم شروع کند و سپس با یک حرکت به خانه سوم سطر اول بیاید و دیگر هم نمی‌تواند حرکتی بکند. در این صورت او ۱۶ کشمش به‌دست می‌آورد که با کمی بررسی معلوم می‌شود این مقدار ماکسیمم است. <details class="blue"> <summary> راهنمایی ۱ </summary> فرض کنید می‌خواهیم به ازای هر خانه از جدول می‌خواهیم به دست آوریم که اگر از این خانه شروع کنیم چند کشمش می‌توانیم به دست آوریم و این مقدار را $dp_{i,j}$ بنامید. حال یک رابطه برای به دست آوردن مقدار $dp$ از روی بقیه مقادیر به دست آورید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> اولا که سطرهایی که شماره زوج دارند، اصلا مهم نیستند چون با توجه به حرکات تعریف شده نمی‌توان به آن‌ها رسید. هم‌چنین به ازای بقیه خانه‌ها، اگر شماره سطر آن‌ها را $x$ بنامیم، درصورتی که $(n - x) / 2$ زوج باشد، حرکت اسبی حتما به سمت چپ و در غیر این صورت به سمت راست است. (یعنی زوجیت تعداد حرکت‌های اسبی تا کنون از روی شماره سطر به دست می‌آید) حال با توجه به این موضوع سعی کنید رابطه‌ای برای محاسبه $dp$ گفته شده در بالا پیدا کنید. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> برای محاسبه $dp$ حرکت‌هایی که نوروز می‌تواند انجام دهد را در نظر می‌گیریم؛ نوروز یک خانه به سمت چپ می‌رود یا همان طور که در بالا گفته شد، حرکت اسبی انجام می‌دهد. حال در صورتی که در خانه $(i, j)$ چمن باشد، مقدار $dp$ آن را منفی بی‌نهایت می‌گذاریم و در غیر این صورت مقدار $dp$ را برابر با بیشینه $dp$ دو خانه‌ای که می‌تواند به آن‌ها برسد (البته توجه کنید که ممکن است یکی از این دو خانه، وجود نداشته باشد و نباید به مقدار آن نگاه کنیم). در آخر هم به مقدار $dp$ تعداد شکلات‌های این خانه را اضافه می‌کنیم. </details> <details class="blue"> <summary> راهنمایی ۴ </summary> در نهایت برای محاسبه کردن جواب، بیشینه مقدار $dp$ را در بین سطر آخر پیدا کنید. اگر آن مقدار آن منفی بود، یعنی هیچ مسیری نداریم و جواب صفر است. در غیر این صورت هم جواب برابر با همین مقدار بیشنیه است. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز که به‌دلیل قیمت بالای کیک، به تنگ آمده بود، تصمیم گرفت تا در شرکت تاکسیرانی تپ‌نپ کار کند. شهری که آقا فیروز در آن زندگی‌ می‌کند شامل $n$ میدان است که در یک خط راست قرار دارند و به ترتیب از چپ به راست با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند و در وسط میدان شماره $i$، مجسمه‌ای با ارتفاع $h_i$ متر وجود دارد. هر مسافر در برنامه تپ‌نپ درخواستی به صورت $(i, j)$ می‌دهد و به این معنی است که می‌خواهد از میدان $i$ به میدان $j$ که $j < i$ است، برود. متاسفانه برنامه‌ی مسیریاب آقا فیروز خراب شده‌ و مسافرین باید به او آدرس بدهند. مسافر در هر مرحله یک عدد $k$ به آقا فیروز می‌گوید و او به سمت چپ حرکت می‌کند تا به **اولین** میدانی برسد که ارتفاع مجسمه‌اش دقیقا $k$ متر باشد. مسافر طوری عدد را می‌گوید که چنین میدانی در سمت چپ میدان فعلی و قبل از میدان $j - 1$ وجود داشته باشد. در نهایت وقتی مسافر به مقصد رسید، آقا فیروز به تعداد عددهایی که مسافر به او گفته‌‌، از او پول می‌گیرد و می‌دانیم مسافر‌ها به گونه‌ای آدرس می‌دهند که **کمترین پول** را به آقا فیروز بدهند. هم‌چنین آقا فیروز تا زمانی که یک مسافر را به مقصد نرسانده، او را پیاده نمی‌کند و در هر زمان **دقیقا یک مسافر** می‌تواند سوار ماشین شود. آقا فیروز که به پول نیاز دارد، می‌خواهد ببیند اگر به ازای هر $i$ و $j$ که $j < i$ است، درخواست $(i, j)$ را قبول کند، در مجموع چقدر پول بدست می‌آورد؛ اما بدلیل اینکه رانندگی انرژی زیادی از وی می‌گیرد، او از شما درخواست کرده‌ تا شما برایش این مقدار را حساب کنید. از آنجایی که ممکن است خروجی عددی بزرگ شود، جواب نهایی را به باقیمانده $10^9 + 7$ خروجی دهید. # ورودی در خط اول ورودی عدد $n$ می‌آید که بیانگر تعداد میدان‌های شهر است. در خط دوم به ترتیب $n$ عدد $h_1, h_2, h_3, \dots, h_n\ $ می‌آیند که $h_i$ برابر با ارتفاع مجسمه‌ای است که در میدان $i$ام قرار دارد. $$ 1 \le n \le 100\ 000 $$ $$ 1 \le h_i \le 100\ 000$$ # خروجی در تنها خط خروجی، مجموع پولی که آقا فیروز می‌تواند کسب کند را بگوید. # مثال ## ورودی نمونه ۱ ``` 3 4 1 2 ``` ## خروجی نمونه ۱ ``` 3 ``` درآمدی که آقا فیروز به ازای هر درخواست $(i, j)$ دارد به این‌صورت است: + (۲, ۱) = ۱ + (۳, ۱) = ۱ + (۳, ۲) = ۱ ## ورودی نمونه ۲ ``` 5 3 3 3 1 2 ``` ## خروجی نمونه ۲ ``` 17 ``` درآمدی که آقا فیروز به ازای هر درخواست $(i, j)$ دارد به این‌صورت است: + (۲, ۱) = ۱ + (۳, ۱) = ۲ + (۴, ۱) = ۳ + (۵, ۱) = ۳ + (۳, ۲) = ۱ + (۴, ۲) = ۲ + (۵, ۲) = ۲ + (۴, ۳) = ۱ + (۵, ۳) = ۱ + (۵, ۴) = ۱ <details class="blue"> <summary> راهنمایی ۱ </summary> مسئله را به شکل زیر به یک گراف $n$ راسی تبدیل می‌کنیم که هر راس نماینده یک میدان است. راس $i$ یالی مستقیم به راس $j$ دارد، اگر و تنها اگر $j<i$ و هیچ $k$ وجود نداشته باشد به صورتی که $j<k<i$ و $h_j=h_k$ باشد. در این صورت جواب مسئله برابر با جمع فاصله هر دو راس است. حال سعی می‌کنیم این مقدار را در گراف ساخته شده محاسبه کنیم. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> یال‌ها را برعکس نگاه می‌کنیم. اگر $k$ کوچک‌ترین عددی باشد که $i<k$ و $h_i=h_k$ راس‌های $i+1$ تا $k$ به راس $i$ یال دارند و اگر $k$ وجود نداشته باشد راس‌های $i+1$ تا $n$ به راس $i$ یال دارند و اگر یال‌ها را برعکس کنیم راس $i$ به همه آن‌ها یال خواهد داشت. پس یعنی راس $i$ به تعدادی از راس‌های جلوی خود یال دارد. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> تعریف می‌کنیم: $r_i$ یعنی جلوترین راسی که راس $i$ به آن یال دارد. در اصل راس $i$ به تمامی راس‌های $i+1$ تا $r_i$ فاصله یک دارد. ادعا می‌کنیم مسیر راس $i$ به راس‌های بزرگ‌تر از $r_i$ از راس $j$ می‌گذرد به صورتی که $i<j \le r_i$ و $r_j$ بیشینه است. </details> <details class="blue"> <summary> راهنمایی ۴ </summary> اولا که $r_i$ ها در واقع اولین مقدار بعد $i$ است که $a_r_i = a_i$ است. بعد از آن طبق ادعای بالا می‌توانیم اندیسی که در بالا گفته شده را با استفاده از سگمنت‌تری به دست آوریم. سپس از روی مجموع فاصله‌های آن اندیس، می‌توان فاصله‌های جدید را هم به دست آورد. </details>

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- گرچه آقا فیروز در تپ‌نپ خیلی اذیت شد ولی توانست پول خوبی به دست آورد. او تصمیم گرفت با این پول یک بازی فکری برای بچه‌هایش بخرد تا هوش ریاضی آن‌ها را پرورش دهد. وقتی آقا فیروز بازی را به پسرش علی داد، او خیلی خوشحال شد و سریع شروع به بازی کرد. بازی از یک صفحه تشکیل شده بود که روی آن دو عدد $n$ و $m$ نوشته شده بود و در زیر آن $n$ نقطه کشیده شده بود که $m$ جفت از آن‌ها با پاره‌خط‌هایی به‌صورت خط‌چین به هم وصل شده بودند. علی باید طوری پاره‌خط‌ها را با رنگ‌های ۱ و ۲ و ۳ رنگ‌آمیزی می‌کرد که در انتها هر پاره‌خطی که رنگ ۱ دارد، حتما حداقل یک پاره‌خط مجاور با رنگ ۲ داشته باشد. دو پاره‌خط مجاور هستند اگر یک سر آن‌ها مشترک باشد. علی که از راحتی این بازی جا خورده بود، تصمیم گرفت تا هوش ریاضی خود را به پدرش ثابت کند و تعداد روش‌های رنگ‌آمیزی صفحه با شرایط را به دست آورد. او که در ابتدا متوجه سختی مسئله نبود، پس از مدتی فکر کردن و ناتوانی در حل آن خیلی ناراحت شد. حال برای این که علی ناراحت نشود شما تعداد روش‌‌های رنگ‌آمیزی را به دست آورید و به او بگویید. همچنین به‌دلیل اینکه ممکن است خروجی بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ چاپ کنید. # ورودی در خط اول دو عدد $n$ و $m$ آمده است که به ترتیب تعداد نقاط و پاره‌خط‌ها را نشان می‌دهد. در $i$امین خط از $m$ خط بعدی دو عدد $v_i$ و $u_i$ آمده است که نشان‌دهنده‌ وجود پاره‌خطی بین دو نقطه با شماره $v_i$ و $u_i$ می‌باشد. تضمین می‌شود همواره $v_i$ و $u_i$ متفاوت هستند و بین هر جفتی حداکثر یک پاره‌خط‌ قرار دارد. $$1 \le n \le 18$$ $$1 \le m \le \frac{n \times (n - 1)}{2}$$ $$1 \le v_i, u_i \le n$$ # خروجی در تنها خط خروجی، تعداد روش‌های رنگ‌آمیزی پاره‌خط‌ها را به باقیمانده $10^9 + 7$ به دست آورید به‌طوری که شرایط بازی رعایت شود. # مثال ## ورودی نمونه ۱ ``` 4 2 1 2 3 4 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 3 3 1 2 2 3 3 1 ``` ## خروجی نمونه ۲ ``` 20 ``` <details class="blue"> <summary> راهنمایی ۱ </summary> تعریف می‌کنیم: $dp_{i, mask}$ تعداد حالات رنگ کردن پاره‌خط‌های ۱ تا $i$ به صورتی که راس‌هایی که در $mask$ هستند، حداقل یک پاره‌خط با رنگ ۲ به آن‌ها متصل باشد چقدر است و از روی این $dp$ جواب مساله را به دست می‌آوریم. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> برای بدست آوردن مقدار $dp_{i, mask}$ روی رنگ پاره‌خط $i$ ام حالت‌بندی می‌کنیم. اگر رنگ پاره‌خط $i$ بخواهد یک باشد، حتما باید یکی از دوسر پاره‌خط $i$ در $mask$ آمده باشد و رنگ کردن بقیه پاره‌خط‌ها $dp_{i-1, mask}$ حالت دارد. اگر رنگ پاره‌خط $i$ بخواهد سه باشد، رنگ کردن بقیه پاره‌خط‌ها $dp_{i-1, mask}$ حالت دارد. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> هم‌چنین اگر رنگ پاره‌خط $i$ بخواهد دو باشد روی $mask$ بدون پاره‌خط $i$ حالت‌بندی می‌کنیم. تعداد پاره‌خط‌هایی که تنها پاره‌خط مجاور آن‌ها با رنگ ۲، یال $i$ است را بدست میاوریم و $dp_{i, mask}$ را با توجه به این مقادیر حساب می‌کنیم. </details> <details class="blue"> <summary> راهنمایی ۴ </summary> حال از روی $dp$ گفته شده در بالا می‌توان جواب مساله را پیدا کرد. </details>

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز که در طی ماه‌های اخیر عملکرد خیره‌کننده‌ای در کار و نظارتش بر دیگران داشت، توسط شرکت عمرانی سرداد به استخدام درآمد. شرکت عصر دانش‌افزار که در زمینه طراحی و ساخت اپلیکیشن‌های بانکی، مالی و خدمات پرداخت فعالیت دارد، کارهای نرم‌افزاری این شرکت عمرانی را انجام می‌دهد. در پروژه‌ای که به آقا فیروز داده‌ شده، $n$ روستا وجود دارد که از $1$ تا $n$ شماره‌گذاری شده‌اند. همچنین یک لیست شامل $n - 1$ جاده به آقا فیروز داده‌ شده که هر جاده دوتا از روستاها را به هم وصل می‌کند. تضمین می‌شود پس از احداث جاده‌ها می‌توان با پیمایش تعدادی جاده از هر روستایی به هر روستای دیگری رفت. همچنین در هر روستا، یک سوله وجود دارد که درون سوله واقع در روستای شماره $i$، دقیقا $i$ تن خاک وجود دارد. همچنین می‌دانیم برای احداث جاده‌ای بین دو روستای $u$ و $v$، باید **دقیقا از یکی از این دو روستا، دقیقا ۱ تن خاک** برداشت. حال آقا فیروز که تازه استخدام شده‌، می‌خواهد خودی نشان دهد. برای همین می‌خواهد تعداد روش‌های مختلف انتخاب سوله‌ها برای برداشتن خاک مورد نیاز جاده‌ها را بشمارد. اما به‌دلیل اینکه درگیر آنالیز کردن پروژه عمرانی‌اش است، از شما می‌خواهد تا به او در این موضوع کمک کنید. توجه کنید از آن‌جا که جواب ممکن است بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ خروجی دهید. # ورودی در خط اول برنامه عدد $n$ به شما داده می‌شود که بیانگر تعداد روستاها می‌باشد. در $n - 1$ خط بعدی، در هر خط دو عدد $u_i$ و $v_i$ می‌آید و بیانگر این است که جاده‌ای بین دو روستا با شماره‌های $u_i$ و $v_i$ باید احداث شود. تضمین می‌شود پس از احداث این $n - 1$ جاده، از هر روستایی با پیمایش جاده‌ها می‌توان به هر روستای دیگری رفت. $$1 \le n \le 1\ 000\ 000$$ $$1 \le u_i, v_i \le n$$ # خروجی در تنها خط خروجی، تعداد روش‌های مختلف انتخاب سوله‌ها برای برداشتن خاک را به باقیمانده $10^9 + 7$ بگویید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 1 3 ``` ## خروجی نمونه ۱ ``` 3 ``` می‌توان برای احداث جاده‌ی اول، از روستای شماره ۲ خاک برداشت، که در این‌صورت برای احداث جاده دوم می‌توان هم از روستای شماره ۱ و هم از روستای شماره ۳ خاک برداشت. همچنین اگر برای احداث جاده‌ی اول، از روستای شماره ۱ خاک برداریم، چون سوله واقع در روستای ۱، دقیقا یک تن خاک داشت، پس دیگر خاکی در آن باقی نمی‌ماند و مجبوریم از سوله واقع در روستای ۳ خاک برداریم. پس در کل به ۳ روش می‌توان سوله‌ها را برای برداشتن خاک انتخاب کرد. ## ورودی نمونه ۲ ``` 4 1 2 2 3 2 4 ``` ## خروجی نمونه ۲ ``` 7 ``` ## ورودی نمونه ۳ ``` 4 2 3 2 1 2 4 ``` ## خروجی نمونه ۳ ``` 7 ``` <details class="blue"> <summary> راهنمایی ۱ </summary> مسئله را به گراف تبدیل می‌کنیم. هم‌چنین به راسی که درجه‌اش بزرگ‌تر از اندیسش باشد، راس حساس می‌گوییم. می‌توانیم ثابت کنیم که تعداد راس‌های حساس از $O(\sqrt{n})$ است. حال اگر برای یک یال نتوانیم سوله‌ای انتخاب کنیم حتما دوسر آن یال، راس حساس هستند. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> درخت را از یک راس دلخواه (مانند راس یک) ریشه‌دار می‌کنیم‌ و جواب را برای هر زیردرخت حساب می‌کنیم. تعریف می‌کنیم: $dp_{1, u}$ یعنی جواب برای زیردرخت $u$، اگر در ابتدا در راس $u$ دقیقن $u$ تن خاک داشته باشیم. به همین طریق $dp_{2, u}$ نیز یعنی جواب برای زیردرخت $u$، اگر در ابتدا در راس $u$ دقیقن $u-1$ تن خاک داشته باشیم. برای راس‌های غیرحساس می‌دانیم $dp_{1, u}$ و $dp_{2, u}$ باهم برابرند و می‌توان به راحتی با مشخص کردن راس انتخاب‌شده روی یال بین بچه‌های $u$ و خودش مقدار آن‌ها را بدست آورد. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> برای حساب کردن $dp_1$ و $dp_2$ برای راس‌های حساس، متغیری کمکی به نام $ans_{u, i}$ را حساب می‌کنیم که مقدار آن برابر با جواب برای زیردرخت راس $u$ بدون درنظر گرفتن بچه‌های غیرحساس آن است که می‌توان آن را با $O({deg_u}^2)$ حساب کرد ($deg_u$ برابر تعداد بچه‌های حساس راس $u$ است). از آنجا که مجموع $deg$ راس‌های حساس از $O(\sqrt{n})$ است، حساب کردن آن با $O(n)$ امکان‌پذیر است. حال با توجه به $ans_u$، می‌توان مقادیر موردنظر را حساب کرد. </details>

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز که پس از انجام پروژه عمرانی حسابی خسته شده بود، به خواب عمیقی فرو رفت. او که روابط اجتماعی قوی دارد، در خواب $n$ دوست فضانورد پیدا کرد که در نقاط مختلف کهکشان قرار داشتند. آن‌ها تصمیم گرفتند تا قراری بگذارند و یکدیگر را در سیاره زمین ملاقات کنند. هر نقطه از کهکشان یک نقطه سه بعدی در نظر گرفته می‌شود و به صورت مختصات $(x, y, z)$ نمایش داده می‌شود. زمین در نقطه $(0, 0, 0)$ قرار دارد. هر فضانورد در فضا می‌تواند در جهت یکی از سه بعد حرکت کند و به ازای هر یک واحد جابه‌جایی در یک بعد، یک واحد اکسیژن نیز مصرف می‌کند. از آ‌ن‌جایی که شارژ کردن کپسول اکسیژن هزینه بالایی دارد، آقا فیروز که دیگر تبدیل به یک مدیر کارکشته شده است، تصمیم می‌گیرد مجموع مصرف اکسیژن دوستان فضانوردش را کمینه کند. برای این‌کار او ایده‌ای را اجرایی می‌کند و بودجه مشخصی به آن اختصاص می‌دهد. آقا فیروز می‌خواهد دقیقا $a$ درگاه در جهت بعد اول مختصات یا همان $x$، $b$ درگاه در جهت بعد دوم یا همان $y$ و همچنین $c$ درگاه در جهت بعد سوم یا همان $z$ راه‌اندازی می‌کند. هر درگاه بدین صورت کار می‌کند که اگر یک فضانورد وارد آن درگاه شود، بدون نیاز به مصرف اکسیژن می‌توان آن را به هر درگاه دیگری در همان بعد ارسال کرد. همچنین هر درگاه بر اساس بعد خود یک مشخصه دارد که نشان‌دهنده مجموعه نقاطی است که شامل می‌شود. اگر یک درگاه در بعد $d$ ام خود دارای مشخصه $w$ باشد، تمام نقاطی که بعد $d$ ام آن‌ها برابر $w$ است را شامل می‌شود. در واقع هر درگاه نقاط یک صفحه در فضا را در بر می‌گیرد. حال آقا فیروز می‌خواهد طوری این درگاه‌ها را راه‌اندازی کند که مجموع اکسیژن مصرفی دوستان فضانوردش کمینه شود ولی مهارت‌های ریاضی او در خواب جوابگو نیستند. به او کمک کند تا خوابش تبدیل به رویا شود. # ورودی در خط اول برنامه عدد $n$ به شما داده می‌شود که بیانگر تعداد فضانوردها می‌شود. در خط دوم، به ترتیب سه عدد $a$، $b$ و $c$ وارد می‌شوند که به ترتیب نمایانگر تعداد درگاه‌های بعد اول و دوم و سوم می‌باشد. در $i$امین خط از $n$ خط بعدی سه عدد $x_i$، $y_i$ و $z_i$ آمده‌اند که نمایانگر مختصات فعلی فضانورد $i$ام می‌باشند. $$1 \le n\le 100\ 000$$ $$0 \le a, b, c\le 100\ 000$$ $$0 \le x_i, y_i, z_i \le 10^9$$ # خروجی در تنها خط خروجی، کمینه اکسیژن مصرفی فضانوردان بعد از نصب درگاه‌ها را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 0 2 2 1 3 3 2 3 4 ``` ## خروجی نمونه ۱ ``` 4 ``` برای بعد دوم دو درگاه در $y=0$ و $y=3$ و برای بعد سوم دو درگاه در $z=0$ و $z=3$ می سازیم. در این حالت با مصرف ۴ اکسیژن همه‌ی فضانورد‌ها می‌توانند به زمین برسند. ## ورودی نمونه ۲ ``` 4 1 2 3 1 2 8 2 18 6 9 15 4 10 10 2 ``` ## خروجی نمونه ۲ ``` 36 ``` برای بعد اول یک درگاه در $x=5$، برای بعد دوم دو درگاه در $y=0$ و $y=15$ و برای بعد سوم سه درگاه در $z=0$ و $z=4$ و $z=6$ می‌سازیم. نفر اول با ۵ واحد اکسیژن از $(1, 2, 8)$ به $(0, 0, 6)$ می‌رود و با استفاده از درگاه $z=6$ بدون مصرف اکسیژن به درگاه $z=0$ می‌رود و به زمین می‌رسد. نفر دوم با ۵ واحد اکسیژن از $(2, 18, 6)$ به $(0, 15, 6)$ می‌رود. سپس با استفاده از درگاه $z=6$ بدون مصرف اکسیژن به درگاه $z=0$ می‌رود (اکنون در مختصات $(0, 15, 0)$ است) و دوباره با استفاده از درگاه $y=15$ بدون مصرف اکسیژن به درگاه $y=0$ می‌رود و به زمین می‌رسد. نفر سوم بدون مصرف اکسیژن از درگاه $y=15$ به درگاه $y=0$ می‌رود. سپس با مصرف ۹ واحد اکسیژن از $(9, 0, 4)$ به $(0, 0, 4)$ می‌رود و سپس با استفاده از درگاه $z=4$ بدون مصرف اکسیژن به درگاه $z=0$ می‌رود و به زمین می‌رسد. نفر چهارم با ۱۷ واحد اکسیژن از $(10, 10, 2)$ به $(0, 15, 0)$ می‌رود و با استفاده از درگاه $y=15$ به درگاه $y=0$ می‌رود و به زمین می‌رسد. ## ورودی نمونه ۳ ``` 3 0 0 0 1 3 1 2 1 3 3 2 2 ``` ## خروجی نمونه ۳ ``` 18 ``` در این حالت هیج ایستگاهی ساخته نمی‌شود و همه باید بدون استفاده از درگاه به زمین برسند. <details class="blue"> <summary> راهنمایی ۱ </summary> سوال را برای تمامی بعد‌ها جداگانه حل می‌کنیم. به جای آنکه بخواهیم دقیقا $a$ تا درگاه بگذاریم فرض می‌کنیم که هزینه ساخت هر‌ درگاه $w$ اکسیژن است و با استفاده از باینری‌سرچ، $w$ را به نحوی مشخص می‌کنیم که حالت بهینه‌ای با $a$ درگاه وجود داشته باشد. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> حال مساله بالا را به این شکل حل می‌کنیم: مختصات‌های افراد را مرتب می‌کنیم و دنباله مرتب شده را $a$ می‌نامیم. تعریف می‌کنیم: $dp_i$ کمترین مقدار اکسیژن مصرفی برای $i$ فضانورد اول به طوری که یک درگاه در نقطه $a_i$ قرار گرفته باشد. به ازای هر‌نقطه $j$ به طوری که $j<i$، $ans_j$ را کمترین مقدار اکسیژن مصرفی تعریف می‌کنیم به طوری که افراد $j+1$ تا $i$ به درگاه واقع در نقطه $a_i$ بروند و افراد ۱ تا $j$ به زمین برسند. به ازای هر‌نقطه $j$ به طوری که $j<i$، $val_j$ را کمترین مقدار اکسیژن مصرفی تعریف می‌کنیم به طوری که دو درگاه بر روی نقطه $a_i$ و $a_j$ باشد و افراد $j+1$ تا $i$ به درگاه واقع در نقطه $a_i$ بروند و افراد ۱ تا $j$ به زمین برسند. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> می‌توان $ans$ و $val$ را با استفاده از $trick$ $hull$ $convex$ بدست آورد. آرایه $dp$ به کمک $ans$ و $val$ حساب می‌شود و کمترین اکسیژن مصرفی را به کمک آرایه $dp$ حساب می‌کنیم. </details>