+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ" برای مثال، وقتی کوئرا تصمیم گرفت که دیوار رنگ و رو رفته‌ی شرکت را دوباره رنگ کند، قبل از اینکه نقاش کارش را شروع کند، بچه‌ها به این نتیجه رسیدند که می‌توانند قبل از اینکه نقاش دیوار را دوباره سفید کند روی آن نقاشی کنند! از این رو مهدی در حالی که این شعر را میخواند روی دیوار یک مربع کشید: یه خونه می‌کشم... بعد از کشیدن مربع، پارسا تصمیم گرفت که یک لیوان را به سمت مربع پرت کند؛ او فکر می‌کرد که توی تغییر دکوراسیون شرکت قرار است شرکت را با وسایلش خراب کنند و طرحی نو دراندازند!! برای همین به نظرش آمد که در این وضعیت خراب کردن هر چیزی به شرکت کمک می‌کند.(او حتی این کار را جزو ساعت کاری‌اش هم حساب می‌کرد!) علی‌رقم هشدار‌های صاحب لیوان، پارسا این کار را کرد و دقیقاً قبل از اینکه لیوان به دیوار برسد و بترکد، نقاش رنگ سفید را روی دیوار ریخت تا شروع به رنگ زدن کند که این کار باعث پاک شدن مربع مهدی شد. حالا مهدی جای مربع و پارسا نقطه‌ی ترکیدن لیوان را می‌داند ولی نمی‌دانند که لیوان داخل یا روی مربع ترکید یا بیرون آن؛ چرا که اگر داخل یا روی مربع ترکیده باشد، مهدی وگرنه پارسا باید خرده‌لیوان‌ها را جمع کند! حال شما با گرفتن اطلاعات از این دو، بازنده را مشخص کنید. # ورودی در سطر اول ورودی دو عدد صحیح $x$ و $y$ می‌آید که نمایانگر مختصات گوشه‌ی بالا چپ مربع می‌باشد. در سطر دوم یک عدد صحیح $r$ می‌آید که نمایانگر طول ضلع مربع می‌باشد. در سطر سوم دو عدد صحیح $dx$ و $dy$ می‌آید که نمایانگر مختصات جایی است که لیوان ترکیده است. $$ -100 \le x, y, dx, dy \le 100 $$ $$ 1 \le r \le 1000 $$ دقت کنید که مختصات دکارتی می‌باشد؛ یعنی زمانی لیوان داخل یا روی مربع است که شروط زیر برقرار باشد: $$ x \le dx \le x + r $$ $$ y - r \le dy \le y $$ # خروجی در یک سطر کسی که باید خرده‌لیوان‌ها را جمع کند چاپ کنید. اگر این شخص پارسا بود "Parsa" و اگر مهدی بود "Mahdi" چاپ کنید. . # مثال ## ورودی نمونه ۱ ``` 0 5 5 0 0 ``` ## خروجی نمونه ۱ ``` Mahdi ``` ## ورودی نمونه ۲ ``` 0 5 5 5 6 ``` ## خروجی نمونه ۲ ``` Parsa ``` ## ورودی نمونه ۳ ``` 0 5 5 -5 3 ``` ## خروجی نمونه ۳ ``` Parsa ``` ## ورودی نمونه ۴ ``` 0 5 5 3 3 ``` ## خروجی نمونه ۴ ``` Mahdi ```

تعمیر دیوار

محدودیت زمان: ۰.۵ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ"

برای مثال، وقتی کوئرا تصمیم گرفت که دیوار رنگ و رو رفته‌ی شرکت را دوباره رنگ کند، قبل از اینکه نقاش کارش را شروع کند، بچه‌ها به این نتیجه رسیدند که می‌توانند قبل از اینکه نقاش دیوار را دوباره سفید کند روی آن نقاشی کنند! از این رو مهدی در حالی که این شعر را میخواند روی دیوار یک مربع کشید: یه خونه می‌کشم...

بعد از کشیدن مربع، پارسا تصمیم گرفت که یک لیوان را به سمت مربع پرت کند؛ او فکر می‌کرد که توی تغییر دکوراسیون شرکت قرار است شرکت را با وسایلش خراب کنند و طرحی نو دراندازند!! برای همین به نظرش آمد که در این وضعیت خراب کردن هر چیزی به شرکت کمک می‌کند.(او حتی این کار را جزو ساعت کاری‌اش هم حساب می‌کرد!) علی‌رقم هشدار‌های صاحب لیوان، پارسا این کار را کرد و دقیقاً قبل از اینکه لیوان به دیوار برسد و بترکد، نقاش رنگ سفید را روی دیوار ریخت تا شروع به رنگ زدن کند که این کار باعث پاک شدن مربع مهدی شد.

حالا مهدی جای مربع و پارسا نقطه‌ی ترکیدن لیوان را می‌داند ولی نمی‌دانند که لیوان داخل یا روی مربع ترکید یا بیرون آن؛ چرا که اگر داخل یا روی مربع ترکیده باشد، مهدی وگرنه پارسا باید خرده‌لیوان‌ها را جمع کند!

حال شما با گرفتن اطلاعات از این دو، بازنده را مشخص کنید.

ورودی🔗

در سطر اول ورودی دو عدد صحیح $x$ و $y$ می‌آید که نمایانگر مختصات گوشه‌ی بالا چپ مربع می‌باشد.

در سطر دوم یک عدد صحیح $r$ می‌آید که نمایانگر طول ضلع مربع می‌باشد.

در سطر سوم دو عدد صحیح $dx$ و $dy$ می‌آید که نمایانگر مختصات جایی است که لیوان ترکیده است.

$-100 \le x, y, dx, dy \le 100$

$1 \le r \le 1000$

دقت کنید که مختصات دکارتی می‌باشد؛ یعنی زمانی لیوان داخل یا روی مربع است که شروط زیر برقرار باشد:

$x \le dx \le x + r$ $y - r \le dy \le y$

خروجی🔗

در یک سطر کسی که باید خرده‌لیوان‌ها را جمع کند چاپ کنید. اگر این شخص پارسا بود "Parsa" و اگر مهدی بود "Mahdi" چاپ کنید. .

مثال🔗

ورودی نمونه ۱🔗

0 5
5
0 0

خروجی نمونه ۱🔗

Mahdi

ورودی نمونه ۲🔗

0 5
5
5 6

خروجی نمونه ۲🔗

Parsa

ورودی نمونه ۳🔗

0 5
5
-5 3

خروجی نمونه ۳🔗

Parsa

ورودی نمونه ۴🔗

0 5
5
3 3

خروجی نمونه ۴🔗

Mahdi

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ" برای مثال، بعد از اینکه کوئرا تصمیم گرفت که دکوراسیون خود را تغییر دهد، از آنجایی که دیگر نمی‌شد در مکان فعلی شرکت کار کرد، اعضای تیم مجبور شدند که برای مدتی جای کار خود را عوض کنند. آن‌ها سواحل زیبای دریای خزر را برای کار انتخاب کردند. پس از شرکت به سمت شِمال به راه افتادند. زمانی که اعضای تیم به ساحل رسیدند یک دفعه هوایی شدند و تصمیم گرفتند که بی‌خیال دنیا شده و "ای‌بی‌یوخته‌بابا" زندگی ‌کنند تا این حد که قرار گذاشتند که لپتاپ‌های خود را به درون آب پرت کرده و هر کس که پرش روی‌ آب لپتاپش بیشتر بود بتواند شب توی ننویی که ببین دو درخت ساحلی وصل کرده‌اند بخوابد! نحوه‌ی پرش لپتاپ هم به این شکل است که اگر برای مثال دفعه‌ی اولی که لپتاپ به آب می‌رسد، $d$ متر را از مکان پرتاب طی کرده باشد، به زیر آب رفته و اگر بیرون بیاید به اندازه‌‌ی $\frac d 2 $ پیش می‌رود تا دوباره به آب می‌خورد و بعد اگر بیرون بیاید به اندازه‌ی $\frac d 4$ پیش می‌رود تا دوباره به آب بخورد و همینطور پیش می‌رود تا زمانی که به داخل آب می‌رود و دیگر بیرون نمی‌آید. حال مصطفی لپتاپش را پرت کرده و می‌داند فاصله‌ی مکانی که لپتاپش را به داخل آب پرت کرد تا جایی که لپتاپ پایین رفت و دیگر بالا نیامد $t$ متر است. همچنین او می‌داند که لپتاپ او دقیقا $w$ بار(شامل بار آخر که لپتاب به آب می‌رود و دیگر بالا نمی‌آید) با آب برخورد داشته است. حال بگویید که فاصله‌ی مکانی که مصطفی لپتاپ خود را پرت کرد تا اولین برخورد لپتاپ به آب چقدر می‌باشد. # ورودی در تنها سطر ورودی دو عدد طبیعی $t$ و $w$ می‌آید که به ترتیب نمایانگر فاصله‌ی مکان پرتاب لپتاپ تا آخرین باری‌ که دیده شده و تعداد برخورد لپتاپ با آب(شامل بار آخر که لپتاب به آب می‌رود و دیگر بالا نمی‌آید) می‌باشد. $$ 1 \le t \le 10000 $$ $$ 1 \le w \le 20 $$ # خروجی در تنها سطر خروجی فاصله‌ی مکان پرتاب لپتاپ تا اولین برخورد لپتاب به آب را تا دقیقاً ۴ رقم اعشار چاپ کنید. برای فهمیدن چگونگی چاپ کردن یک عدد تا چند رقم اعشار در زبان برنامه‌نویسی خود می‌توانید از اینترنت کمک بگیرید D:| . # مثال ## ورودی نمونه ۱ ``` 7 2 ``` ## خروجی نمونه ۱ ``` 4.6667 ``` توضیح: طبق جواب تست، دفعه‌ی اول لپتاپ $ \frac {14} 3$ متر رفته است و دفعه‌ی دوم $ \frac 7 3 $. ## ورودی نمونه ۲ ``` 5 1 ``` ## خروجی نمونه ۲ ``` 5.0000 ``` ## ورودی نمونه ۳ ``` 14 3 ``` ## خروجی نمونه ۳ ``` 8.0000 ``` ## ورودی نمونه ۴ ``` 15 4 ``` ## خروجی نمونه ۴ ``` 8.0000 ```

صدف فلزی

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ"

برای مثال، بعد از اینکه کوئرا تصمیم گرفت که دکوراسیون خود را تغییر دهد، از آنجایی که دیگر نمی‌شد در مکان فعلی شرکت کار کرد، اعضای تیم مجبور شدند که برای مدتی جای کار خود را عوض کنند. آن‌ها سواحل زیبای دریای خزر را برای کار انتخاب کردند. پس از شرکت به سمت شِمال به راه افتادند.

زمانی که اعضای تیم به ساحل رسیدند یک دفعه هوایی شدند و تصمیم گرفتند که بی‌خیال دنیا شده و "ای‌بی‌یوخته‌بابا" زندگی ‌کنند تا این حد که قرار گذاشتند که لپتاپ‌های خود را به درون آب پرت کرده و هر کس که پرش روی‌ آب لپتاپش بیشتر بود بتواند شب توی ننویی که ببین دو درخت ساحلی وصل کرده‌اند بخوابد!

نحوه‌ی پرش لپتاپ هم به این شکل است که اگر برای مثال دفعه‌ی اولی که لپتاپ به آب می‌رسد، $d$ متر را از مکان پرتاب طی کرده باشد، به زیر آب رفته و اگر بیرون بیاید به اندازه‌‌ی $\frac d 2$ پیش می‌رود تا دوباره به آب می‌خورد و بعد اگر بیرون بیاید به اندازه‌ی $\frac d 4$ پیش می‌رود تا دوباره به آب بخورد و همینطور پیش می‌رود تا زمانی که به داخل آب می‌رود و دیگر بیرون نمی‌آید.

حال مصطفی لپتاپش را پرت کرده و می‌داند فاصله‌ی مکانی که لپتاپش را به داخل آب پرت کرد تا جایی که لپتاپ پایین رفت و دیگر بالا نیامد $t$ متر است. همچنین او می‌داند که لپتاپ او دقیقا $w$ بار(شامل بار آخر که لپتاب به آب می‌رود و دیگر بالا نمی‌آید) با آب برخورد داشته است. حال بگویید که فاصله‌ی مکانی که مصطفی لپتاپ خود را پرت کرد تا اولین برخورد لپتاپ به آب چقدر می‌باشد.

ورودی🔗

در تنها سطر ورودی دو عدد طبیعی $t$ و $w$ می‌آید که به ترتیب نمایانگر فاصله‌ی مکان پرتاب لپتاپ تا آخرین باری‌ که دیده شده و تعداد برخورد لپتاپ با آب(شامل بار آخر که لپتاب به آب می‌رود و دیگر بالا نمی‌آید) می‌باشد.

$1 \le t \le 10000$ $1 \le w \le 20$

خروجی🔗

در تنها سطر خروجی فاصله‌ی مکان پرتاب لپتاپ تا اولین برخورد لپتاب به آب را تا دقیقاً ۴ رقم اعشار چاپ کنید. برای فهمیدن چگونگی چاپ کردن یک عدد تا چند رقم اعشار در زبان برنامه‌نویسی خود می‌توانید از اینترنت کمک بگیرید D:| .

مثال🔗

ورودی نمونه ۱🔗

7 2

خروجی نمونه ۱🔗

4.6667

توضیح: طبق جواب تست، دفعه‌ی اول لپتاپ $\frac {14} 3$ متر رفته است و دفعه‌ی دوم $\frac 7 3$ .

ورودی نمونه ۲🔗

5 1

خروجی نمونه ۲🔗

5.0000

ورودی نمونه ۳🔗

14 3

خروجی نمونه ۳🔗

8.0000

ورودی نمونه ۴🔗

15 4

خروجی نمونه ۴🔗

8.0000

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ" برای مثال، وقتی کوئرا بالاخره بعد از مدت‌ها تصمیم گرفت که دکوراسیون شرکت را تغییر دهد، سر و صدای زیادی به راه افتاد؛ به طوری که خبرنگاران پشت در صف کشیده و مشغول تهیه گزارش از این خبر مهم شدند. تیم کوئرا که نتوانستند در آن سر و صدا کار کنند تصمیم گرفتند که به کافه گراف بروند و آنجا کارشان را ادامه دهند. کارگرانی که در کوئرا مشغول تغییر دکوراسیون شرکت بودند هم نتوانستند در این سر و صدا کار کنند و تصمیم گرفتند که آن‌ها هم همراه تیم کوئرا به کافه گراف بروند و کارشان را آنجا ادامه دهند! اکنون همه در شرکت گیر کرده‌اند و اگر در را باز کنند خبرنگاران به داخل خواهند ریخت. از این رو آنها از پنجره به پشت بام رفتند و می‌خواهند از روی پشت‌بام‌ها بپرند تا سیل عظیم خبرنگاران را رد کنند. از پشت بام شرکت تا جایی که دیگر از خبرنگاران خبری نباشد تعدادی پشت‌بام در یک خط وجود دارد.(پشت‌بام‌ها را از ۰ تا $n$ به ترتیب شماره‌گذاری می‌کنیم. پشت‌بام شرکت شماره‌ی ۰ است) زمانی که آنها به پشت‌بام $n$ برسند دیگر از خبرنگاران خبری نخواهد بود. خوشبختانه چون آن‌ها خیلی بافرهنگ هستند ابتدا به تمامی صاحب‌های ‌پشت‌بام‌ها زنگ زدند و از آن‌ها اجازه گرفتند. آن‌ها هم در این صورت اجازه‌ی عبور دادند که پول تعمیر پشت‌بامشان توسط شرکت پرداخته شود. پول تعمیر هم به این صورت پرداخته می‌شود که صاحب پشت‌بام $i$، برای پشت‌بامش یک قیمت $c_i$ اعلام کرده است و اگر بچه‌ها از پشت بام $j$ روی آن بپرند باید به اندازه‌ی $|j-i| \times c_i $ پرداخت کنند.( هر چی دورتر باشند فشار بیشتری به پشت‌بام مقصد وارد می‌شود.) حالا بچه‌ها می‌خواهند با کمترین هزینه به پشت‌بام $n$ برسند. این هزینه را به بچه‌ها بگویید. # ورودی در سطر اول ورودی عدد $n$ آمده‌است که نمایانگر تعداد پشت‌بام‌ها می‌باشد. سپس در خط بعد $n$ عدد آمده‌ است که عدد $i$، نمایانگر $c_i$ می‌باشد. $$ 1 \le n \le 1 \ 000 \ 000 $$ $$ 1 \le c_i \le 1 \ 000 \ 000 \ 000 $$ # خروجی در یک سطر خروجی کمینه‌ی هزینه‌ی جابجایی را چاپ کنید. . # مثال ## ورودی نمونه ۱ ``` 3 5 4 5 ``` ## خروجی نمونه ۱ ``` 13 ``` توضیح: در این مثال حالت بهینه این است که ابتدا از بام ۰ به بام ۲ بروند که هزینه‌ی این کار $2 \times 4$ می‌باشد. سپس از بام ۲ به بام ۳ بروند که هزینه‌ی این کار $ 1 \times 5$ می‌باشد که در مجموع می‌شود ۱۳. ## ورودی نمونه ۲ ``` 1 5 ``` ## خروجی نمونه ۲ ``` 5 ``` ## ورودی نمونه ۳ ``` 4 1 1 1 1 ``` ## خروجی نمونه ۳ ``` 4 ``` ## ورودی نمونه ۴ ``` 5 3 2 3 2 4 ``` ## خروجی نمونه ۴ ``` 12 ```

تعمیر پشت‌بام

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ"

برای مثال، وقتی کوئرا بالاخره بعد از مدت‌ها تصمیم گرفت که دکوراسیون شرکت را تغییر دهد، سر و صدای زیادی به راه افتاد؛ به طوری که خبرنگاران پشت در صف کشیده و مشغول تهیه گزارش از این خبر مهم شدند. تیم کوئرا که نتوانستند در آن سر و صدا کار کنند تصمیم گرفتند که به کافه گراف بروند و آنجا کارشان را ادامه دهند. کارگرانی که در کوئرا مشغول تغییر دکوراسیون شرکت بودند هم نتوانستند در این سر و صدا کار کنند و تصمیم گرفتند که آن‌ها هم همراه تیم کوئرا به کافه گراف بروند و کارشان را آنجا ادامه دهند!

اکنون همه در شرکت گیر کرده‌اند و اگر در را باز کنند خبرنگاران به داخل خواهند ریخت. از این رو آنها از پنجره به پشت بام رفتند و می‌خواهند از روی پشت‌بام‌ها بپرند تا سیل عظیم خبرنگاران را رد کنند. از پشت بام شرکت تا جایی که دیگر از خبرنگاران خبری نباشد تعدادی پشت‌بام در یک خط وجود دارد.(پشت‌بام‌ها را از ۰ تا $n$ به ترتیب شماره‌گذاری می‌کنیم. پشت‌بام شرکت شماره‌ی ۰ است) زمانی که آنها به پشت‌بام $n$ برسند دیگر از خبرنگاران خبری نخواهد بود.

خوشبختانه چون آن‌ها خیلی بافرهنگ هستند ابتدا به تمامی صاحب‌های ‌پشت‌بام‌ها زنگ زدند و از آن‌ها اجازه گرفتند. آن‌ها هم در این صورت اجازه‌ی عبور دادند که پول تعمیر پشت‌بامشان توسط شرکت پرداخته شود. پول تعمیر هم به این صورت پرداخته می‌شود که صاحب پشت‌بام $i$ ، برای پشت‌بامش یک قیمت $c_i$ اعلام کرده است و اگر بچه‌ها از پشت بام $j$ روی آن بپرند باید به اندازه‌ی $|j-i| \times c_i$ پرداخت کنند.( هر چی دورتر باشند فشار بیشتری به پشت‌بام مقصد وارد می‌شود.)

حالا بچه‌ها می‌خواهند با کمترین هزینه به پشت‌بام $n$ برسند. این هزینه را به بچه‌ها بگویید.

ورودی🔗

در سطر اول ورودی عدد $n$ آمده‌است که نمایانگر تعداد پشت‌بام‌ها می‌باشد. سپس در خط بعد $n$ عدد آمده‌ است که عدد $i$ ، نمایانگر $c_i$ می‌باشد.

$1 \le n \le 1 \ 000 \ 000$

$1 \le c_i \le 1 \ 000 \ 000 \ 000$

خروجی🔗

در یک سطر خروجی کمینه‌ی هزینه‌ی جابجایی را چاپ کنید. .

مثال🔗

ورودی نمونه ۱🔗

3
5 4 5

خروجی نمونه ۱🔗

توضیح: در این مثال حالت بهینه این است که ابتدا از بام ۰ به بام ۲ بروند که هزینه‌ی این کار $2 \times 4$ می‌باشد. سپس از بام ۲ به بام ۳ بروند که هزینه‌ی این کار $1 \times 5$ می‌باشد که در مجموع می‌شود ۱۳.

ورودی نمونه ۲🔗

1
5

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

4
1 1 1 1

خروجی نمونه ۳🔗

ورودی نمونه ۴🔗

5
3 2 3 2 4

خروجی نمونه ۴🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ" برای مثال، وقتی کوئرا بالاخره موفق شد که دکوراسیون شرکتش را تغییر دهد، باید دوباره کارتون‌هایی را که چند روز پیش اعضا بسته بودند، دوباره باز می‌کردند و می‌چیدند. قبل از تغییر آنها این جعبه‌ها را در یک ردیف چیده بودند و در حین تغییر ترتیب این جعبه‌ها به هم ریخت. از این رو تصمیم گرفتند که قبل از باز کردن جعبه‌ها، آن‌ها را دوباره مرتب کنند و به حالت سابق برگردانند تا سرعتشان در چینش بیشتر شود. آنها می‌دانند که جعبه‌ای که الآن در مکان $i$ام قرار دارد، قبل از تغییر در مکان $a_i$ بود. حال ‌آن‌ها تعدادی کارگر گرفته‌اند (خود ناتوانند) تا جعبه‌ها را برایشان مرتب کنند. آنها در هر ثانیه می‌توانند به یک کارگر بگویند که جعبه‌ای که در مکان $i$ است را با جعبه‌ای که در مکان $j$ است عوض کند و اینکار برای هر کارگر تنها یک ثانیه طول می‌کشد. تنها نکته‌ای که وجود دارد این است که زمانی که به یک کارگر گفته‌شد که جعبه‌ی در مکان $i$ را با جعبه‌ی در مکان $j$ عوض کند، به کارگر دیگری نمی‌توان گفت که جعبه‌ی در مکان $i$ یا $j$ را با جعبه‌ی دیگری عوض کند؛ یعنی در آن ثانیه هیچ عملیات دیگری روی این دو جعبه نمی‌تواند صورت پذیرد یا به عبارت دیگری روی هر جعبه در هر ثانیه تنها یک عملیات می‌تواند انجام شود. دقت کنید که کارگر‌ها در هر ثانیه به صورت موازی کار می‌کنند. متاسفانه سایت‌های رقیب کوئرا از این فرصت دوری کوئرا استفاده کرده و هی مسابقه برگزار کردند. از این رو تیم تصمیم دارد که هر چه زودتر به میادین برگردد. پس می‌خواهد در کمترین زمان ممکن جعبه‌ها را مرتب شده ببیند. حال از شما می‌خواهد که به کارگران در مرتب کردن جعبه‌ها کمک کرده و بگویید که چگونه و به چه ترتیبی جعبه‌ها را مرتب کنند. دقت کنید که تیم در استخدام کارگر محدودیتی ندارد و هر تعداد که بخواهد می‌تواند کارگر استخدام کند. # ورودی در خط اول ورودی عدد $n$‌ آمده است که نمایانگر تعداد جعبه‌ها می‌باشد. سپس در خط بعد $n$‌ عدد آمده است که عدد $i$‌ام $a_i$ می‌باشد و نمایانگر مکان قبلی جعبه‌ای است که الآن در مکان $i$ام قرار دارد. دقت کنید هیچ دو جعبه‌ای مکان قبلیشان یکسان نیست؛ یعنی در خط دوم ورودی به شما یک جایگشت از ۱ تا $n$ داده می‌شود. $$ 1 \le n \le 100 \ 000 $$ $$ 1 \le a_i \le n $$ # خروجی در سطر اول خروجی کمترین تعداد ثانیه‌‌ای را که لازم دارند تا جعبه‌ها را مرتب کنند، چاپ کنید. سپس در سطر‌های بعدی توضیح هر ثانیه را به این صورت خروجی دهید: ابتدا تعداد عملیات‌ها را در این ثانیه خروجی دهید. سپس در سطر‌های بعدی، در هر سطر، یک عملیات را به صورت "$a$ $b$" خروجی دهید که نمایانگر این است که یک کارگر در این ثانیه جعبه‌ی در مکان $a$ را با جعبه‌ی در مکان $b$ عوض کند. در صورت وجود چند جواب به دلخواه یکی را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 2 1 4 3 ``` ## خروجی نمونه ۱ ``` 1 2 1 2 3 4 ``` ## ورودی نمونه ۲ ``` 3 3 2 1 ``` ## خروجی نمونه ۲ ``` 1 1 1 3 ``` ## ورودی نمونه ۳ ``` 3 2 3 1 ``` ## خروجی نمونه ۳ ``` 2 1 1 2 1 1 3 ```

بازگشت جعبه

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ"

برای مثال، وقتی کوئرا بالاخره موفق شد که دکوراسیون شرکتش را تغییر دهد، باید دوباره کارتون‌هایی را که چند روز پیش اعضا بسته بودند، دوباره باز می‌کردند و می‌چیدند. قبل از تغییر آنها این جعبه‌ها را در یک ردیف چیده بودند و در حین تغییر ترتیب این جعبه‌ها به هم ریخت. از این رو تصمیم گرفتند که قبل از باز کردن جعبه‌ها، آن‌ها را دوباره مرتب کنند و به حالت سابق برگردانند تا سرعتشان در چینش بیشتر شود. آنها می‌دانند که جعبه‌ای که الآن در مکان $i$ ام قرار دارد، قبل از تغییر در مکان $a_i$ بود.

حال ‌آن‌ها تعدادی کارگر گرفته‌اند (خود ناتوانند) تا جعبه‌ها را برایشان مرتب کنند. آنها در هر ثانیه می‌توانند به یک کارگر بگویند که جعبه‌ای که در مکان $i$ است را با جعبه‌ای که در مکان $j$ است عوض کند و اینکار برای هر کارگر تنها یک ثانیه طول می‌کشد. تنها نکته‌ای که وجود دارد این است که زمانی که به یک کارگر گفته‌شد که جعبه‌ی در مکان $i$ را با جعبه‌ی در مکان $j$ عوض کند، به کارگر دیگری نمی‌توان گفت که جعبه‌ی در مکان $i$ یا $j$ را با جعبه‌ی دیگری عوض کند؛ یعنی در آن ثانیه هیچ عملیات دیگری روی این دو جعبه نمی‌تواند صورت پذیرد یا به عبارت دیگری روی هر جعبه در هر ثانیه تنها یک عملیات می‌تواند انجام شود. دقت کنید که کارگر‌ها در هر ثانیه به صورت موازی کار می‌کنند.

متاسفانه سایت‌های رقیب کوئرا از این فرصت دوری کوئرا استفاده کرده و هی مسابقه برگزار کردند. از این رو تیم تصمیم دارد که هر چه زودتر به میادین برگردد. پس می‌خواهد در کمترین زمان ممکن جعبه‌ها را مرتب شده ببیند. حال از شما می‌خواهد که به کارگران در مرتب کردن جعبه‌ها کمک کرده و بگویید که چگونه و به چه ترتیبی جعبه‌ها را مرتب کنند. دقت کنید که تیم در استخدام کارگر محدودیتی ندارد و هر تعداد که بخواهد می‌تواند کارگر استخدام کند.

ورودی🔗

در خط اول ورودی عدد $n$ ‌ آمده است که نمایانگر تعداد جعبه‌ها می‌باشد.

سپس در خط بعد $n$ ‌ عدد آمده است که عدد $i$ ‌ام $a_i$ می‌باشد و نمایانگر مکان قبلی جعبه‌ای است که الآن در مکان $i$ ام قرار دارد. دقت کنید هیچ دو جعبه‌ای مکان قبلیشان یکسان نیست؛ یعنی در خط دوم ورودی به شما یک جایگشت از ۱ تا $n$ داده می‌شود.

$1 \le n \le 100 \ 000$ $1 \le a_i \le n$

خروجی🔗

در سطر اول خروجی کمترین تعداد ثانیه‌‌ای را که لازم دارند تا جعبه‌ها را مرتب کنند، چاپ کنید.

سپس در سطر‌های بعدی توضیح هر ثانیه را به این صورت خروجی دهید:

ابتدا تعداد عملیات‌ها را در این ثانیه خروجی دهید.

سپس در سطر‌های بعدی، در هر سطر، یک عملیات را به صورت " $a$ $b$ " خروجی دهید که نمایانگر این است که یک کارگر در این ثانیه جعبه‌ی در مکان $a$ را با جعبه‌ی در مکان $b$ عوض کند.

در صورت وجود چند جواب به دلخواه یکی را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

4
2 1 4 3

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

3
3 2 1

خروجی نمونه ۲🔗

1
1
1 3

ورودی نمونه ۳🔗

3
2 3 1

خروجی نمونه ۳🔗

+ محدودیت زمان: ۲.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ" برای مثال، وقتی کوئرا بالاخره بعد از مدت‌ها تصمیم گرفت که دکوراسیون شرکت را تغییر دهد، در تیم کوئرا روحیه‌ی تخریب‌کاری بسیار تشدید شد؛ زیرا کارگران آمدند و شروع به تخریب دیوارهای شرکت کردند. دیوارهایی که نوشته‌های مهمی رویشان بود... سپس تیم کوئرا به کافه گراف رفتند تا به دور از این دیوارهای تخریب شده، با آرامش به جلای روحیه‌ی تخریب‌کاریشان فکر کنند. در کافه گراف تنها روشی که به ذهن تیم رسید، تخریب یک گراف بود! آن‌ها $n^2$ راس درست کردند و آن‌ها را در $n$ ردیف $n$ تایی قرار دادند. (به راس در ردیف $y$ام از پایین و ستون $x$ام از چپ، راس $(x, y)$ می‌گوییم.) سپس بین هر راس و رئوس بالایی، پایینی، چپی و راستی‌اش (در صورت وجود) یال کشیدند. (در مجموع $2n(n-1)$ یال کشیده شد.) بعد از آن شروع به تخریب یال‌های گراف کردند؛ دانه دانه یال‌ها را انتخاب و نابود می‌کردند. پس از چند دور تخریب، تیم به فکر آنالیز عملکردش افتاد. (بالاخره کار استارت-آپ است دیگر...) آن‌ها یک تخریب را بد در نظر می‌گیرند اگر پس از حذف آن یال، تعداد مولفه‌های همبندی گراف تغییری نکند. یک دلال کلاه‌بردار، شما را بعنوان یک آنالیزور تخریب گراف به کوئرا معرفی کرده و شما باید با گرفتن ترتیب تخریب‌ها، پس از هر تخریب بگویید که آیا این تخریب بد بوده است یا خیر. # ورودی در سطر اول ورودی دو عدد طبیعی $n$ و $k$ آمده است که $n$ تعداد سطرها و ستون‌های متشکل از رئوس گراف را مشخص می‌کند و $k$ نمایانگر تعداد تخریب‌های انجام شده می‌باشد. سپس ورودی به شکل رمز شده می‌آید؛ این کار برای این است که شما مجبور شوید نتیجه‌ی تخریب‌ها را به ترتیب ورودی بدست آورید. به این صورت که در هر یک از $k$ خط بعدی ورودی، یک یال با دو عدد $x$ و $y$ و کاراکتر $dir$ آمده‌اند. جهت یال یا برابر `E` است که یعنی یال توصیف شده از راس $(x, y)$ به راس$(x+1, y)$ است. در غیر این صورت جهت یال برابر `N` است که یعنی یال توصیف شده از $(x, y)$ به راس $(x, y + 1)$ است. ** جهت یال با توجه به کاراکتر ورودی $dir$ و نتیجه‌ی تخریب قبلی تعیین می‌شود؛ ** اگر تخریب یال قبلی یک تخریب بد نبود، جهت یال تخریبی جدید با مقدار $dir$ متفاوت است و در غیر این صورت جهت یال تخریبی برابر مقدار $dir$ است. **جهت اولین یال با مقدار $dir$ برابر است.** (جهت وضوح بیشتر به مثال توجه کنید.) تضمین می‌شود که یال پس از رمزگشایی یک یال درست است و شماره ردیف و ستون هر دو راس انتهاییش بین ۱ تا $n$ خواهد بود؛ اما ممکن است پیش از رمزگشایی این درست نباشد. تضمین می‌شود که هیچ یالی دو بار تخریب نمی‌شود. $$ 1 \le x, y \le n \le 2\ 000 $$ $$ 1 \le k \le 2\ 000\ 000 $$ # خروجی در $k$ خط، نتیجه‌ی بد بودن هریک از تخریب‌ها را بنویسید؛ اگر یک تخریب بد بود `Yes` و اگر بد نبود `No` را چاپ کنید. . # مثال ## ورودی نمونه ``` 3 3 1 1 E 1 1 N 2 1 N ``` ## خروجی نمونه ``` Yes No Yes ``` یال‌های تخریب شده به ترتیب برابر $(1, 1)$ با جهت `E`، $(1, 1)$ با جهت `N` و $(2, 1)$ با جهت `E` هستند که تخریبشان مطابق این شکل‌ها بوجود می‌آید: ![توضیح تصویر](https://blog.quera.ir/wp-content/uploads/2017/02/photo_2017-02-17_11-08-19.jpg) ![توضیح تصویر](https://blog.quera.ir/wp-content/uploads/2017/02/photo_2017-02-17_11-08-18.jpg) ![توضیح تصویر](https://blog.quera.ir/wp-content/uploads/2017/02/photo_2017-02-17_11-08-17.jpg)

تخریب گراف

محدودیت زمان: ۲.۵ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ"

برای مثال، وقتی کوئرا بالاخره بعد از مدت‌ها تصمیم گرفت که دکوراسیون شرکت را تغییر دهد، در تیم کوئرا روحیه‌ی تخریب‌کاری بسیار تشدید شد؛ زیرا کارگران آمدند و شروع به تخریب دیوارهای شرکت کردند. دیوارهایی که نوشته‌های مهمی رویشان بود...

سپس تیم کوئرا به کافه گراف رفتند تا به دور از این دیوارهای تخریب شده، با آرامش به جلای روحیه‌ی تخریب‌کاریشان فکر کنند. در کافه گراف تنها روشی که به ذهن تیم رسید، تخریب یک گراف بود! آن‌ها $n^2$ راس درست کردند و آن‌ها را در $n$ ردیف $n$ تایی قرار دادند. (به راس در ردیف $y$ ام از پایین و ستون $x$ ام از چپ، راس $(x, y)$ می‌گوییم.) سپس بین هر راس و رئوس بالایی، پایینی، چپی و راستی‌اش (در صورت وجود) یال کشیدند. (در مجموع $2n(n-1)$ یال کشیده شد.) بعد از آن شروع به تخریب یال‌های گراف کردند؛ دانه دانه یال‌ها را انتخاب و نابود می‌کردند. پس از چند دور تخریب، تیم به فکر آنالیز عملکردش افتاد. (بالاخره کار استارت-آپ است دیگر...) آن‌ها یک تخریب را بد در نظر می‌گیرند اگر پس از حذف آن یال، تعداد مولفه‌های همبندی گراف تغییری نکند. یک دلال کلاه‌بردار، شما را بعنوان یک آنالیزور تخریب گراف به کوئرا معرفی کرده و شما باید با گرفتن ترتیب تخریب‌ها، پس از هر تخریب بگویید که آیا این تخریب بد بوده است یا خیر.

ورودی🔗

در سطر اول ورودی دو عدد طبیعی $n$ و $k$ آمده است که $n$ تعداد سطرها و ستون‌های متشکل از رئوس گراف را مشخص می‌کند و $k$ نمایانگر تعداد تخریب‌های انجام شده می‌باشد.

سپس ورودی به شکل رمز شده می‌آید؛ این کار برای این است که شما مجبور شوید نتیجه‌ی تخریب‌ها را به ترتیب ورودی بدست آورید. به این صورت که در هر یک از $k$ خط بعدی ورودی، یک یال با دو عدد $x$ و $y$ و کاراکتر $dir$ آمده‌اند. جهت یال یا برابر E است که یعنی یال توصیف شده از راس $(x, y)$ به راس $(x+1, y)$ است. در غیر این صورت جهت یال برابر N است که یعنی یال توصیف شده از $(x, y)$ به راس $(x, y + 1)$ است. ** جهت یال با توجه به کاراکتر ورودی $dir$ و نتیجه‌ی تخریب قبلی تعیین می‌شود؛ ** اگر تخریب یال قبلی یک تخریب بد نبود، جهت یال تخریبی جدید با مقدار $dir$ متفاوت است و در غیر این صورت جهت یال تخریبی برابر مقدار $dir$ است. جهت اولین یال با مقدار $dir$ برابر است. (جهت وضوح بیشتر به مثال توجه کنید.)

تضمین می‌شود که یال پس از رمزگشایی یک یال درست است و شماره ردیف و ستون هر دو راس انتهاییش بین ۱ تا $n$ خواهد بود؛ اما ممکن است پیش از رمزگشایی این درست نباشد. تضمین می‌شود که هیچ یالی دو بار تخریب نمی‌شود.

$1 \le x, y \le n \le 2\ 000$

$1 \le k \le 2\ 000\ 000$

خروجی🔗

در $k$ خط، نتیجه‌ی بد بودن هریک از تخریب‌ها را بنویسید؛ اگر یک تخریب بد بود Yes و اگر بد نبود No را چاپ کنید. .

مثال🔗

ورودی نمونه🔗

خروجی نمونه🔗

Yes
No
Yes

یال‌های تخریب شده به ترتیب برابر $(1, 1)$ با جهت E، $(1, 1)$ با جهت N و $(2, 1)$ با جهت E هستند که تخریبشان مطابق این شکل‌ها بوجود می‌آید: توضیح تصویر