+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- تیم برگزاری مسابقات دیجی‌کال‍ا کاپ، تصمیم گرفته‌اند تا عل‍اوه بر نفرات برتر هر مسابقه، از بخشی از شرکت‌کنندگان نیز به شکل تصادفی تقدیر کنند و برای این‌کار از اکبر که یکی از مهندسین نرم‌افزار دیجی‌کال‍است، کمک‌ خواسته‌اند. ایده‌ی اولیه‌ی اکبر این بود که به هر یک از شرکت‌کنندگان، یک شناسه‌ی عددی اختصاصی داده شود و سپس با انتخاب تصادفی یکی از این اعداد، یک کارت‌هدیه‌ی خرید از دیجی‌کال‍ا به او هدیه داده شود. بعد از مطرح شدن این ایده‌؛ سارا، از اعضای تیم برند کارفرمایی دیجی‌کال‍ا، پیشنهاد داد تا عل‍اوه بر انتخاب نسبتاً تصادفی برنده‌ی جایزه، جایزه‌ی او هم به شکل خیلی تصادفی از بین کارت‌های هدیه‌ی یک، دو، سه،... و نه میلیون‌تومانی انتخاب شود. اکبر برای پیاده‌سازی این ایده‌، یک راه‌حل عجیب ارائه داده است. او می‌خواهد تا عدد شناسه‌ی اختصاصی انتخاب‌شده را با عدد حاصل از مجموع ارقام آن جایگزین کند و به یک عدد جدید برسد. سپس همین کار را با عدد جدید انجام دهد و تا جایی که به یک عدد تک‌رقمی برسد به این کار ادامه دهد. از آن‌جا که اکبر می‌خواهد جایزه‌ی انتخاب‌شده خیلی تصادفی باشد، با این مسئله که در این راه‌حل به شخص برنده، کارت هدیه‌ی پوچ (صفر میلیون تومانی!) اهدا شود هم مشکلی ندارد. حال اکبر ترجیح داده‌است تا ایده‌ش را به عنوان اولین سوال در مسابقه قرار دهد تا شما در حل این مسئله به او کمک کنید. # ورودی در تنها سطر ورودی عدد $n$ می‌آید که نشان دهنده شناسه‌ی تصادفی انتخاب‌شده و برنده‌ی جایزه‌ی تصادفی دیجی‌کال‍است. $$ 0 \le n \le 10 ^{18} $$ # خروجی در تنها خط خروجی باید عدد تک‌رقمی حاصل از تبدیل $n$ به یک عدد تک‌رقمی چاپ شود که نشان‌دهنده‌ی میزان هدیه‌ی دریافتی شخص برنده‌ است. # مثال ## ورودی نمونه ۱ ``` 17 ``` ## خروجی نمونه ۱ ``` 8 ``` ## ورودی نمونه ۲ ``` 4560 ``` ## خروجی نمونه ۲ ``` 6 ``` در مرحله اول عدد 4560 تبدیل به عدد 0 + 6 + 5 + 4 = 15 می‌شود. در مرحله دوم عدد 15 تبدیل به عدد 5 + 1 = 6 می‌شود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پارمیدا، بعد از شرکت در مسابقه‌ی دیجی‌کال‍ا کاپ، کسب رتبه‌ی نخست، و شروع به هم‌کاری با تیم مهندسی، برای یک جلسه‌ی Onboarding به ساختمان تکنولوژی دیجی‌کال‍ا دعوت شده است. این جلسه، در طبقه‌ی `f` ساختمان `n` طبقه‌ی دیجی‌کال‍ا برگزار می‌شود. پارمیدا بعد از آن‌که چند طبقه را با پله بال‍ا می‌رود، متوجه می‌شود که زمان زیادی تا شروع جلسه نمانده است و ناگهان چشم‌اش به یک آسانسور می‌افتد و بدیهتاً تصمیم می‌گیرد که برای ادامه‌ی مسیر از آسانسور استفاده کند؛ اما پس از سوار شدن به آسانسور متوجه می‌شود که این یک آسانسور معمولی نیست. شیوه‌ی کار این آسانسور این‌گونه است که تنها دو دکمه‌ی `Up u` و `Down d` در آن وجود دارد. با زدن دکمه‌ی `Up` آسانسور به اندازه‌ی `u` طبقه بال‍ا می‌رود و با زدن دکمه‌ی `Down` آسانسور به اندازه‌ی `d` طبقه به پایین خواهد رفت. در صورتی که تعداد طبقات کافی برای بال‍ا رفتن وجود نداشته باشد، دکمه‌ی `Up`کار نخواهد کرد و آسانسور به بال‍ا نمی‌رود. این موضوع در خصوص پایین رفتن نیز صدق می‌کند. حال با درنظر گرفتن این‌که پارمیدا هم‌اکنون در طبقه‌ی `s` ساختمان حضوردارد و ساختمان نیز مجموعاً `n` طبقه است، او کمی کنجکاو شده تا بداند برای رسیدن به محل جلسه، حداقل چندبار باید از دکمه‌های آسانسور استفاده کند. # ورودی ورودی تنها شامل یک خط است که در ان پنج عدد طبیعی **n** (تعداد طبقات ساختمان)، **s** (طبقه‌ای که پارمیدا در آن حضور دارد)، **f** (طبقه‌ای که جلسه در آن برگزار می‌شود)، **u** (تعداد طبقاتی که آسانسور با زدن دکمه‌ی Up بال‍ا می‌رود)، و **d** (تعداد طبقاتی که آسانسور با زدن دکمه‌ی Down به پایین می‌رود) با فاصله از هم آمده‌اند. $$1 \le s, f \le n \le 10^6 $$ $$0 \le u, d \le 10^6 $$ # خروجی خروجی برنامه‌ی شما باید شامل تنها یک خط باشد که آن کمینه‌یتعداد دفعات ل‍ازم برای فشردن دکمه‌های آسانسور برای رسیدن از طبقه‌ی **s** به طبقه‌ی **f** چاپ شده است. در صورتی که با توجه به داده‌های مسئله، امکان استفاده از آسانسور برای رسیدن به طبقه‌ی **f** وجود ندارد، عبارت **Impossible** را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 10 1 10 2 1 ``` ## خروجی نمونه ۱ ``` 6 ``` ## ورودی نمونه ۲ ``` 100 2 1 1 0 ``` ## خروجی نمونه ۲ ``` Impossible ```

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- سل‍ام، من علی‌رضا افشار هستم، تکنیکال لید تیم Shopping-Operation دیجی‌کالا! امسال تصمیم گرفتم پس‌اندازم رو به میزان m تومن افزایش بدم تا چند سال بعد بتونم یه زندگی بهتر داشته‌باشم. برای این کار تصمیم گرفتم تا با گرفتن وام از شرکت، تو چند فرصت سرمایه‌گذاری در بازار رمزارزها (Cryptocurrency) شرکت کنم تا با سودی که از این فرصت‌ها بدست میاد، بتونم وامی که گرفتم رو پس بدم و یک سرمایه‌ای هم برای خودم جمع کنم. البته تو هر فرصت فقط یکبار میشه سرمایه‌گذاری کرد و سودش از روز بعد حساب میشه. تو لیست n فرصتی که پیدا کردم، هزینه فرصت $i$-ام، $c_i$ تومنه و سودی که از این فرصت بدست میاد، $p_i$ تومن. به من کمک کنید تا بتونم محاسبه کنم با سرمایه‌گذاری تو فرصت‌های درست، کمترین تعداد روز ممکن برای پس دادن وام چقدره. دم شما هم گرم :) # ورودی در خط اول ورودی دو عدد طبیعی $n$ و $m$ با فاصله از هم آمده است. $$1 \le n \le 10^5$$ $$1 \le m \le 10^9$$ در $n$ خط بعدی در هر خط دو عدد آمده که به ترتیب $p_i$ و $c_i$ را نشان می‌دهد $$1 \le p_i, c_i \le 10^9$$ # خروجی در تنها خط خروجی کم‌ترین تعداد روزی که لازم است تا من بعد از پس دادن وام شرکت $m$ تومان سرمایه داشته‌باشم را چاپ کنید. ## ورودی نمونه ۱ ``` 2 5 4 10 10 15 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 4 10 1 8 3 12 4 17 10 100 ``` ## خروجی نمونه ۲ ``` 6 ``` ## ورودی نمونه ۳ ``` 3 5 4 1 9 10 6 3 ``` ## خروجی نمونه ۳ ``` 1 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در مراکز پردازش کال‍ای دیجی‌کالا، با توجه به سفارشات، بسته‌ها در جعبه‌هایی قرار می‌گیرند تا به مراکز توزیع ارسال شوند و سپس برای مشتریان فرستاده شوند. بخش نگهداری این جعبه‌ها، یک فضای n در m از قفسه‌هاست که هر قفسه شامل چند جعبه است که بر روی هر قفسه، سود و زیان حاصل از فروش کل جعبه‌های آن قفسه مشخص شده‌است. یک ربات هوشمند، با حرکت از خانه‌ی پایین-چپ این جدول و با **تنها حرکات بالا و راست** و با برداشتن تمام جعبه‌های قفسه‌ای که به آن می‌رسد، جعبه‌ها را جمع‌آوری می‌کند و به دست مسئول ارسال به مرکز توزیع می‌رساند. ما نیاز داریم تا این ربات به بهینه‌ترین حالت کار کند و هر بار، از مسیری حرکت کند که مجموع سود و زیان جعبه‌هایی که به دست مسئول مرکز توزیع می‌رسند، بیشینه باشد. به ما کمک کنید تا با توجه به شرایط، بیشترین سود از جمع‌آوری جعبه‌ها، و همچنین مسیری که باید برای جمع‌آوری این جعبه‌ها طی کند را بدست آوریم. # ورودی در ابتدا دو عدد n و m به شما داده‌ می‌شود. سپس در n خط، در هر خط m عدد ورودی داده‌می‌شود که عدد jام ورودی در خط iام همان، نشان‌دهنده تعداد جعبه در آن قفسه است ($a_{i,j}$​). $$1 \le n,m \le 2000$$ $$-10^9 \le a_{i,j} \le 10^9$$ # خروجی در خط اول یک عدد برابر جمع مسیر با بیشترین وزن را خروجی دهید. سپس در خط بعدی رشته‌ای متشکل از کاراکتر‌های `U` و `R` خروجی دهید که هر کاراکتر به ترتیب حرکت مورد نظر را در مسیر بهینه نشان می‌دهد. `U` به معنای **بالا** و `R` به معنای **راست** است. اگر چندین مسیر مطلوب وجود داشت یک مسیر را به دلخواه خروجی دهید. ## ورودی نمونه ۱ ``` 3 3 1 2 3 10 2 1 11 12 1 ``` ## خروجی نمونه ۱ ``` 30 RUUR ``` بهترین مسیر راست-بالا-بالا-راست است که در این مسیر به ترتیب اعداد `11 12 2 2 3` را می‌بینیم. ## ورودی نمونه ۲ ``` 3 4 2 2 2 2 2 2 2 2 2 2 2 2 ``` ## خروجی نمونه ۲ ``` 12 RRRUU ``` در این نمونه، از هر مسیری که حرکت کنیم، مجموع اعداد خانه‌هایی که طی کرده‌ایم برابر ۱۲ می‌شود. پس می‌توان هر مسیر دیگری را نیز چاپ کرد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یکی از رسم و رسومات تیم مهندسی دیجی‌کال‍ا، خرید پیتزا به بهانه‌های مختلف است. از آن‌جا که تاکنون افراد زیادی با بهانه‌های بسیار متنوعی مجبور به خرید پیتزا برای هم‌تیمی‌های خود شده‌اند، بهانه‌ی موجه جدیدی به ذهن اعضای تیم مهندسی دیجی‌کال‍ا نمی‌رسد. آن‌ها بعد از یک جلسه‌ی Brainstorming، به این نتیجه می‌رسند تا یک بازی طراحی کنند تا در آن، بازنده را مجبور کنند که برای هم‌تیمی‌ها پیتزا سفارش دهد. از آن‌جا که مدت زیادی هست که ناهید و بهرام پیتزا نداده‌اند، برای انجام این بازی انتخاب می‌شوند تا بازنده سفارش پیتزا را به‌عهده بگیرد. بازی به این صورت است که بهرام و ناهید ابتدا یک عدد طبیعی n را انتخاب می‌کنند و در ابتدای هر دست، عدد m = 1 را در نظر می‌گیرند. بهرام و ناهید در هر نوبت، یک عدد از عوامل اول عدد n را انتخاب می‌کنند و آن را در m ضرب می‌کنند. اگر کسی که ضرب را انجام می‌دهد باعث شود که m برابر با n شود، آن دست را برده‌است؛ اما اگر m بزرگ‌تر از n شود بازی مساوی خواهد شد. توجه کنید از ان‌جا که این بازی بر سر چندین پیتزا انجام می‌شود، بهرام و ناهید هر دو به بهترین نحو بازی می‌کنند (همیشه بهترین انتخاب را انجام می‌دهند). با توجه به شرایط این بازی، پیش‌بینی کنید که کدام یک برنده‌ی این بازی خواهد بود. # ورودی در اولین خط، شامل تعداد دست‌های بازی (t) است. در t خط بعد، در هر خط، وضعیت شروع دست آمده است که در آن؛ n نشان‌دهنده‌ی عدد انتخاب شده و s نشان‌دهنده‌ی نام شروع‌کننده‌ی بازی (Nahid یا Bahram) است. $$2 \le n \le 2^{31} - 1 $$ $$1 \le t \le 10^4 $$ # خروجی در هر خط و به ازای هر دست، نام برنده (Nahid یا Bahram) یا در صورت تساوی کلمه‌ی Tie چاپ می‌شود. # مثال ## ورودی نمونه ۱ ``` 10 10 Nahid 20 Bahram 30 Nahid 40 Bahram 50 Nahid 60 Bahram 70 Nahid 80 Bahram 90 Nahid 100 Bahram ``` ## خروجی نمونه ۱ ``` Bahram Bahram Tie Tie Nahid Tie Tie Tie Tie Nahid ``` برای مثال، با در نظر گرفتن n = 12 (که عامل‌های اول‌ آن 3 و 2 هستند) و شروع بازی توسط بهرام، بازی این‌گونه خواهد بود که اگر بهرام 3 را انتخاب کند، ناهید می‌تواند با انتخاب 3 بازی را به تساوی بکشاند؛ در نتیجه بهرام 2 را انتخاب می‌کند و بازی را می‌برد.