+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در شکل زیر ۴ تقاطع وجود دارد که با اعداد ۱ تا ۴ شماره‌گذاری شده است.  امین در نقطه شماره‌ی $n$ قرار دارد و می‌خواهد به نقطه شماره‌ی $m$ در یک حرکت می‌تواند یک واحد به سمت راست، چپ، بالا و پایین برود. او می‌داند اگر از یکی از گوشه‌ها خارج شود، از شکل سقوط می‌کند و دیگر نمی‌تواند برگردد. حال می‌خواهیم کمینه تعداد حرکت لازم برای رسیدن از نقطه‌ی شماره‌ی $n$ به $m$ را محاسبه کنید. # ورودی در سطر اول و دوم ورودی، به ترتیب دو عدد صحیح و مثبت $n$ و $m$ داده می‌شود که نشان‌دهنده‌ی شماره‌ی نقطه‌ی شروع و پایان امین است. $$1 \leq n, m \leq 4$$ # خروجی در تنها سطر خروجی، کمینه تعداد حرکت لازم، برای رسیدن از نقطه‌ی شماره‌ی $n$ به نقطه‌ی شماره‌ی $m$ را محاسبه کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 1 2 ``` ## خروجی نمونه ۱ ``` 1 ``` برای رسیدن از ۱ به ۲ کافی است در یک حرکت، یک واحد به راست برویم. ## ورودی نمونه ۲ ``` 2 3 ``` ## خروجی نمونه ۲ ``` 2 ``` برای رسیدن از ۲ به ۳ می‌توانیم یک حرکت به چپ انجام بدهیم و از ۲ به ۱ برویم. سپس یک حرکت پایین انجام دهیم و از ۱ به ۳ برسیم. به این ترتیب پاسخ مسئله برابر ۲ خواهد بود. ## ورودی نمونه ۳ ``` 4 4 ``` ## خروجی نمونه ۳ ``` 0 ``` مبدا و مقصد حرکت یکسان است پس نیازی نیست حرکتی انجام دهیم. بنابراین پاسخ مسئله ۰ است.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- برای دیدن یک بازی فوتبال $n$ نفر پشت دیوار استادیوم صف کشیده‌اند. ارتفاع قد نفر $i$ام در این صف $h_i$ است. برای اینکه همه‌ی این افراد بتوانند نمای بهتری از زمین بازی داشته باشند، می‌خواهیم تعدادی جعبه زیر پای این افراد قرار دهیم تا ارتفاعی که روی آن قرار می‌گیرند بیشتر شود. هر جعبه باعث می‌شود که ارتفاع قد یک نفر ۱ واحد افزایش پیدا کند. زمانی می‌گوییم عدالت برقرار شده که ارتفاعی که هر دو نفر دارند بازی را تماشا می‌کنند حداکثر $d$ واحد اختلاف داشته باشد. از شما می‌خواهیم برنامه‌ای بنویسید که کمترین تعداد جعبه را مشخص کند که با کمک آن می‌توانیم عدالت را برقرار کنیم. # ورودی در سطر اول ورودی، دو عدد صحیح و مثبت $n$ و $d$ که با یک فاصله از هم جدا شده‌اند، آمده است. $$1 \leq n \leq 500 \, 000, \quad\quad 0 \leq d \leq 10^9$$ در $n$ سطر بعدی، اعداد صحیح $h_1, h_2, \dots, h_n\,$ که با یک فاصله از هم جدا شده‌اند آمده است. $$1 \leq h_i \leq 10^9$$ # خروجی در تنها سطر خروجی، کمترین تعداد جعبه لازم برای برقراری عدالت را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 1 1 2 8 ``` ## خروجی نمونه ۱ ``` 11 ``` ## ورودی نمونه ۲ ``` 4 0 1 5 3 6 ``` ## خروجی نمونه ۲ ``` 9 ``` ## ورودی نمونه ۳ ``` 1 3 5 ``` ## خروجی نمونه ۳ ``` 0 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک رشته به طول $n$ از حروف کوچک انگلیسی به نام $s$ داریم. می‌خواهیم در $n$ عملیات این رشته را خالی کنیم. در هر عملیات حرفی را حذف می‌کنیم که رشته فعلی را به رشته الفبایی کوچک‌تری تبدیل کند. اگر چند حرف چنین کاری را انجام می‌دهد با سمت راست ترین حرف این کار را می‌کنیم. جایگشتی از $1$ تا $n$ را ارائه دهید که باید عناصر را به آن ترتیب حذف کرد. # ورودی در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده که تعداد تست‌های آمده در ورودی را نشان می‌دهد. $$1 \leq t \leq 100 \, 000$$ در $t$ سطر بعدی ورودی، در هر سطر رشته $s$ که تنها شامل حروف کوچک انگلیسی است، آمده است. $$1 \leq |s| \leq 100 \, 000$$ تضمین می‌شود مجموع طول این $t$ رشته از $100 \, 000$ بیشتر نشود. # خروجی خروجی در یک سطر جایگشتی را که ترتیب حذف کردن آن در هر مرحله ما را به رشته الفبایی کمینه می‌رساند، چاپ می‌کنیم. # مثال ## ورودی نمونه ۱ ``` 3 abc cba quera ``` ## خروجی نمونه ۱ ``` 3 2 1 1 2 3 2 1 4 3 5 ``` **تست اول.** $$abc \to ab \to a$$ بنابراین جایگشتی که باید به آن ترتیب حذف کنیم، $[3, 2, 1]$ است. **تست دوم.** $$cba \to ba\to a$$ بنابراین جایگشتی که باید به آن ترتیب حذف کنیم، $[1, 2, 3]$ است. **تست سوم.** $$quera \to qera \to era \to ea \to a$$ بنابراین جایگشتی که باید به آن ترتیب حذف کنیم، $[2, 1, 4, 3, 5]$ است.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امین در یک درخت زندگی می‌کند. این درخت $n$ راس دارد. راس‌های این درخت با $n - 1$ یال به هم متصل شده‌اند. طول یال $i$ برابر $\ell_i$ متر است. امین در راس شماره $1$ این درخت زندگی می‌‌کند. او می‌خواهد یک روز برای خرید در این درخت گشتی بزند و سپس به راس $1$ بازگردد. او نمی‌خواهد از یک جاده بیش از دو بار عبور کند. او می‌داند که قصد رفتن به راس‌های $v_1, v_2, \dots, v_k\,$ را دارد و در هرکدام از آن‌ها باید یک خرید $w_1, w_2, \dots, w_k\,$ کیلوگرمی انجام دهد. همچنین به‌ازای هر متر که یک خرید $m$ کیلویی را حمل می‌کند. به اندازه‌ی $m$ خسته می‌شود. حال از شما می‌خواهیم این گشت امین را طوری برنامه‌ریزی کنید که همه‌ی خریدهایش را انجام دهد و به راس شماره‌ی ۱ برساند و کمینه خستگی را تحمل کند. # ورودی در سطر اول ورودی عدد صحیح و مثبت $n$ آمده که تعداد راس‌های درخت را نشان می‌دهد. $$2 \leq n \leq 300 \, 000$$ در $n - 1$ سطر بعدی در هر سطر، سه عدد $u_i, v_i, l_i$ که با یک فاصله از هم جدا شده‌اند می‌آید و به‌ترتیب نشان‌دهنده‌ی وجود یال بین راس‌های $u_i$ و $v_i$ به طول $\ell_i$ متر است. $$1 \leq u_i \neq v_i \leq n, \quad \quad 1 \leq \ell_i \leq 1000$$ تضمین می‌شود که ورودی بالا برای یک درخت باشد. در سطر بعدی عدد $k$ آمده که تعداد راس‌هایی که باید امین در آن‌ها خرید کند را نشان می‌دهد. $$1 \leq k \leq 300\,000$$ در $k$ سطر بعدی، در هر سطر دو عدد $v_j$ و $w_j$ آمده که نشان می‌دهد خریدی در راس $v_j$ دارد که وزن آن برابر $w_j$ است. $$2 \leq v_j \leq n, \quad \quad 1 \leq w_j \leq 1000$$ ممکن است راس‌هایی که در آن خرید داریم یکسان باشد ولی باید هر دو خرید را انجام دهیم. # خروجی در تنها سطر خروجی، کمینه خستگی ممکن برای این گشت را محاسبه کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 5 1 2 1 1 3 2 2 4 1 2 5 2 3 4 10 2 3 3 4 ``` ## خروجی نمونه ۱ ``` 47 ```  دنباله‌ی سفر خود را به این صورت انتخاب می‌کنیم: $$1 \to 3 \to 1 \to 2 \to 4 \to 2 \to 1$$ به این ترتیب «۶ متر خرید ۴ کیلوگرمی»، «۱ متر خرید ۳ کیلوگرمی» و «۲ متر خرید ۱۰ کیلوگرمی» حمل کردیم. بنابراین خستگی این گشت برابر است با: $$6 \times 4 + 1 \times 3 + 2 \times 10 = 24 + 3 + 20 = 47$$ ## ورودی نمونه ۲ ``` 5 1 2 1 2 3 3 3 4 2 4 5 1 1 3 5 ``` ## خروجی نمونه ۲ ``` 20 ```  دنباله‌ی سفر خود را به این صورت انتخاب می‌کنیم: $$1 \to 2 \to 3 \to 2 \to 1$$ به این ترتیب «۴ متر خرید ۵ کیلوگرمی» حمل کردیم. بنابراین خستگی این گشت برابر است با: $$4 \times 5 = 20$$

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امین برای وبسایت خود یک [کپچا](https://en.wikipedia.org/wiki/CAPTCHA) طراحی کرده تا جلوی برخی از حمله‌های سایبری را بگیرد. او برای راحتی حال کاربران فقط تصویر یکی از حروف بزرگ انگلیسی را نشان می‌دهد و از کاربران می‌خواهد که آن حرف را تایپ کنند. میترا بعد از بررسی‌های فراوان، مطمئن شد که: + تصویری که امین نشان می‌دهد همواره یکی از حروف `A`، `B` یا `C` است. + این حروف با فونت *Arial* نوشته شده. + ممکن است تصویر این فونت کوچک یا بزرگ باشد اما همیشه خوانا است. + ممکن است تصویر دورانی از این حروف باشد. + هیچ چیزی به جز این حرف در تصویر وجود ندارد. حال میترا برنامه‌ای نوشته که تصویر نمایش داده شده در وبسایت را به‌صورت جدول $100 \times 100$ از کاراکترهای `.` و `#` نمایش می‌دهد که به ترتیب نشان‌دهنده‌ی سفید و سیاه بودن آن پیکسل در تصویر است. به میترا کمک کنید تا برنامه‌ای بنویسید که با دریافت این جدول، بتواند تشخیص دهد که چه حرفی نوشته شده است. # ورودی ورودی ۱۰۰ سطر دارد و در هر سطر ۱۰۰ کاراکتر قرار داد. هر کدام از این کاراکترها `.` یا `#` هستند. # خروجی در تنها سطر خروجی، یکی از حروف `A`، `B` و `C` که نشان دهنده‌ی کاراکتر ظاهر شده در تصویر است را چاپ کنید. # مثال‌ها **شکل‌های زیر مثال‌های یک پنجم کوچک شده هستند و نیازی نیست برنامه‌ی شما به‌ازای این ورودی‌ها خروجی درستی بدهد.** ## ورودی نمونه ۱ ``` .................... .................... ........####........ .......##..##....... ......##....##...... .....##########..... ....##........##.... ...##..........##... ..##............##.. .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ``` ## خروجی نمونه ۱ ``` A ``` ## ورودی نمونه ۲ ``` .................... .................... .................... .................... .................... .................... .................... .................... .................... .........#######.... .........##....##... .........##....##... .........#######.... .........##....##... .........##....##... .........#######.... .................... .................... .................... .................... ``` ## خروجی نمونه ۲ ``` B ``` ## ورودی نمونه ۳ ``` .................... .................... .................... .................... .................... ........#####....... .......##...##...... ......##.....##..... ......#............. ......#............. ......##.....##..... .......##...##...... ........#####....... .................... .................... .................... .................... .................... .................... .................... ``` ## خروجی نمونه ۳ ``` C ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- می‌خواهیم سامانه‌ای برای مدیریت کالج طراحی کنیم. در یک کالج ۳ نوع کاربر باید قابل تعریف باشد. «عضو»، «مربی» و «مدیر». هر کدام از این افراد یک نام کاربری شناسایی می‌شوند. بالاترین سطح دسترسی به ترتیب متعلق به «مدیر»، «مربی» و «عضو» است. هر حساب کاربری بعد از ثبت نام در حالت «غیرفعال» است. زمانی یک حساب فعال می‌شود که یک «مدیر» آن را فعال کند. همچنین مدیران و مربی‌ها نیاز دارند تا لیست کاربرهایی که «غیر فعال» هستند را داشته باشند. از شما می‌خواهیم برنامه‌ای بنویسید که درخواست‌های زیر را برآورده کند. <details class="blue"> <summary> **عضویت در سامانه** </summary> فرمت کلی این دستورات به صورت زیر است: ``` REGISTER <USERNAME> <ROLE> ``` یعنی کاربری با نام `<USERNAME>` درخواست عضویت با نقش `<ROLE>` را دارد. + اگر کاربری با این نام کاربری **فعال یا غیرفعالی** (با هر نقشی) قبلاً ثبت نام کرده است پیام `INVALID USERNAME` را چاپ کنید. + اگر `<ROLE>`، هیچکدام از مقدارهای `ADMIN`، `MENTOR` یا `MEMBER` نبود، پیام `INVALID ROLE` را چاپ کنید. + در صورتی که هیچ کدام از اتفاقات بالا نیفتاد، `WAITING FOR ACCEPT` را چاپ کنید. همواره کاربرها بعد از اضافه شدن «غیرفعال» هستند و باید منتظر فعال شدن بمانند. </details> <details class="blue"> <summary> **تایید کردن عضویت** </summary> فرمت کلی این دستورات به صورت زیر است: ``` APPROVE <USERNAME1> <USERNAME2> ``` یعنی کاربر `<USERNAME1>` می‌خواهد کاربر `<USERNAME2>` را به حالت فعال تبدیل کند. + اگر کاربری با نام `<USERNAME1>` وجود ندارد، پیام `INVALID USERNAME` را چاپ کنید. + اگر کاربر `<USERNAME1>` فعال نیست، پیام ‍`WAITING FOR ADMIN` را چاپ کنید. + اگر کاربر `<USERNAME1>` نقش `ADMIN` ندارد پیام `<USERNAME1> IS NOT ADMIN` را چاپ کنید. + اگر کاربری با نام `<USERNAME2>` وجود ندارد، پیام `INVALID USERNAME` را اعلام کنید. + اگر کاربر `<USERNAME2>` اکنون فعال است، پیام `<USERNAME2> IS ACTIVE` را چاپ کنید. + در صورتی که هیچ کدام از حالت‌های بالا پیش نیامد کاربر `<USERNAME2>` را فعال کنید و پیام `<USERNAME2> ACTIVATED` را چاپ کنید. </details> <details class="blue"> <summary> **رد کردن عضویت** </summary> ``` REJECT <USERNAME1> <USERNAME2> ``` یعنی کاربر `<USERNAME1>` می‌خواهد کاربر `<USERNAME2>` را فعال نکند و درخواست عضویت او را پاک کند. + اگر کاربری با نام `<USERNAME1>` وجود ندارد، پیام `INVALID USERNAME` را چاپ کنید. + اگر کاربر `<USERNAME1>` فعال نیست، پیام ‍ ‍`WAITING FOR ADMIN` را چاپ کنید. + اگر کاربر `<USERNAME1>` نقش `ADMIN` ندارد، پیام `USERNAME1> IS NOT ADMIN>` را چاپ کنید. + اگر کاربری با نام `<USERNAME2>` وجود ندارد، پیام `INVALID USERNAME` را اعلام کنید. + اگر کاربر `<USERNAME2>` اکنون فعال است، پیام `USERNAME1> IS ACTIVE>` را چاپ کنید. + در صورتی که هیچ کدام از حالت‌های بالا پیش نیامد کاربر `<USERNAME2>` را از لیست انتظار حذف کنید و پیام `<USERNAME2> REJECTED` را چاپ کنید. </details> <details class="blue"> <summary> **صف انتظار تایید** </summary> ``` QUEUE <USERNAME> ``` + اگر کاربری با نام `USERNAME` وجود نداشت، پیام `INVALID USERNAME` را چاپ کنید. + اگر کاربر غیرفعال بود، پیام ‍`WAITING FOR ADMIN` را چاپ کنید. + اگر این کاربر نقش `MEMBER` داشت، پیام `NOT ENOUGH ACCESS` را چاپ کنید. + در صورتی که هیچ کدام از اتفاقات بالا رخ نداد، نام کاربری افرادی که درخواست عضویت دادند و هنوز «غیرفعال» هستند را به **ترتیب لغت‌نامه‌ای** (در مقایسه‌ی رشته‌ها ارزش حروف کوچک و بزرگ را یکسان در نظر بگیرید.) چاپ کنید. اگر هیچ کاربری این وضعیت را نداشت پیام `NO USER` را چاپ کنید. </details> <details class="blue"> <summary> **تغییر نقش** </summary> ``` CHANGEROLE <USERNAME1> <USERNAME2> <ROLE> ``` + اگر کاربری با نام `<USERNAME1>` یا `<USERNAME2>` وجود ندارد، پیام `INVALID USERNAME` را چاپ کنید. + اگر کاربری با نام `<USERNAME1>` یا `<USERNAME2>` غیرفعال است، پیام ‍`WAITING FOR ADMIN` را چاپ کنید. + اگر `<ROLE>` هیچ کدام از سه نقش گفته شده نبود، پیام `INVALID ROLE` را چاپ کنید. + اگر نقش `<USERNAME1>` پایین‌تر از `<USERNAME2>` است یا هردو نقش یکسانی دارند، `NOT ENOUGH ACCESS` را چاپ کنید. + اگر نقشی که `<USERNAME1>` می‌خواهد نقش `<USERNAME2>` را به آن تغییر بدهد، بالاتر از نقش خود اوست (مثلاً خود `MENTOR` است و می‌خواهد `<USERNAME2>` را به `ADMIN` تغییر دهد)، `INVALID CHANGEROLE` را چاپ کنید. (تغییر نقش زمانی مجاز است که `<USERNAME2>` به نقشی پایین‌تر یا هم تراز `<USERNAME1>` تغییر پیدا کند). + اگر نقش کاربر با این دسترسی تغییری نمی‌کند، پیام `ALREADY HAS THIS ROLE` چاپ کنید. + در صورتی که هیچ کدام از تغییرات بالا اتفاق نمی‌افتد، نقش `USERNAME2` را به `ROLE` تغییر دهید و پیام `ROLE CHANGED SUCCESSFULLY` را چاپ کنید. </details> <details class="blue"> <summary> **وضعیت کاربر** </summary> ``` STATUS <USERNAME> ``` نام کاربری، نقش و فعال بودن آن را با این الگو چاپ کنید: اگر کاربری با نام `<USERNAME>` وجود ندارد، پیام `INVALID USERNAME` را چاپ کنید. اگر کاربر فعال است: `username: <USERNAME> role: <ROLE> active` در غیر این صورت: `username: <USERNAME> role: <ROLE> not active` </details> # نکات + توجه کنید در هر دستور باید فقط یک پیام چاپ کنید و اگر چند حالت باهم پیش آمد شرایطی که زودتر بیان شده بود، الویت دارد. + هر رشته‌ای که در ورودی داده می‌شود، شامل حروف کوچک و بزرگ انگلیسی به طول حداقل ۱ و حداکثر ۱۰ کاراکتر است. + در ابتدا یک کاربر با نام کاربری `ADMIN` و نقش `ADMIN` به صورت **فعال** در سامانه وجود دارد. # ورودی در سطر اول ورودی، عدد صحیح و مثبت $n$ داده می‌شود که تعداد دستورها را نشان می‌دهد. $$1 \leq n \leq 10 \, 000$$ در $n$ سطر بعدی، در هر سطر یکی از دستورهایی که در بالا تعریف شده، داده می‌شود. # خروجی برای هر دستور، خروجی مورد نظر را چاپ کنید. تضمین می‌شود ورودی‌ها طوری داده شود که مجموع کاراکتر خروجی‌ها از $10^6$ بیشتر نشود. # مثال ## ورودی نمونه ۱ ``` 21 REGISTER Amin ADMIN REGISTER Mitra MENBER REGISTER Mitra MEMBER REGISTER Amin MEMBER QUEUE ADMIN APPROVE Amin Mitra APPROVE ADMIN Mitra APPROVE Mitra Amin REGISTER Amir MEMBER REJECT Amir Amin APPROVE ADMIN Amin APPROVE Mitra Amir CHANGEROLE Amin Mitra MENTOR STATUS Mitra APPROVE Amin Amir QUEUE Amir REGISTER Mina MENTOR CHANGEROLE Mitra Amir MENTOR QUEUE Mitra CHANGEROLE Mitra Amir MEMBER STATUS Mina ``` ## خروجی نمونه ۱ ``` WAITING FOR ACCEPT INVALID ROLE WAITING FOR ACCEPT INVALID USERNAME Amin Mitra WAITING FOR ADMIN Mitra ACTIVATED Mitra IS NOT ADMIN WAITING FOR ACCEPT WAITING FOR ADMIN Amin ACTIVATED Mitra IS NOT ADMIN ROLE CHANGED SUCCESSFULLY username: Mitra role: MENTOR active Amir ACTIVATED NOT ENOUGH ACCESS WAITING FOR ACCEPT ROLE CHANGED SUCCESSFULLY Mina NOT ENOUGH ACCESS username: Mina role: MENTOR not active ```