+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ" برای مثال، بعد از اینکه کوئرا تصمیم گرفت که دکوراسیون خود را تغییر دهد، از آنجایی که دیگر نمی‌شد در مکان فعلی شرکت کار کرد، اعضای تیم مجبور شدند که برای مدتی جای کار خود را عوض کنند. آن‌ها سواحل زیبای دریای خزر را برای کار انتخاب کردند. پس از شرکت به سمت شِمال به راه افتادند. زمانی که اعضای تیم به ساحل رسیدند یک دفعه هوایی شدند و تصمیم گرفتند که بی‌خیال دنیا شده و "ای‌بی‌یوخته‌بابا" زندگی ‌کنند تا این حد که قرار گذاشتند که لپتاپ‌های خود را به درون آب پرت کرده و هر کس که پرش روی‌ آب لپتاپش بیشتر بود بتواند شب توی ننویی که ببین دو درخت ساحلی وصل کرده‌اند بخوابد! نحوه‌ی پرش لپتاپ هم به این شکل است که اگر برای مثال دفعه‌ی اولی که لپتاپ به آب می‌رسد، $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 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ" برای مثال، وقتی کوئرا بالاخره موفق شد که دکوراسیون شرکتش را تغییر دهد، باید دوباره کارتون‌هایی را که چند روز پیش اعضا بسته بودند، دوباره باز می‌کردند و می‌چیدند. قبل از تغییر آنها این جعبه‌ها را در یک ردیف چیده بودند و در حین تغییر، ترتیب این جعبه‌ها به هم ریخت. از این رو اعضا تصمیم گرفتند که قبل از باز کردن جعبه‌ها، آن‌ها را دوباره مرتب کنند و به حالت سابق برگردانند تا سرعتشان در چینش بیشتر شود. آنها می‌دانند که جعبه‌ای که الآن در مکان $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 ```

+ محدودیت زمان: ۲.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ" برای مثال، وقتی کوئرا بالاخره بعد از مدت‌ها تصمیم گرفت که دکوراسیون شرکت را تغییر دهد، در تیم کوئرا روحیه‌ی تخریب‌کاری بسیار تشدید شد؛ زیرا کارگران آمدند و شروع به تخریب دیوارهای شرکت کردند. دیوارهایی که نوشته‌های مهمی رویشان بود... سپس تیم کوئرا به کافه گراف رفتند تا به دور از این دیوارهای تخریب شده، با آرامش به جلای روحیه‌ی تخریب‌کاریشان فکر کنند. در کافه گراف تنها روشی که به ذهن تیم رسید، تخریب یک گراف بود! آن‌ها $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` هستند که تخریبشان مطابق این شکل‌ها بوجود می‌آید:   

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