+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی عاشق ترب شده و ترب روی محور اعداد گم شده‌... علی دل توی دلش نیست تا اون رو پیدا کنه...* در ابتدا علی و ترب در دو نقطه **مختلف** از محور اعداد ایستاده‌اند. علی در نقطه $x_1$ و ترب در نقطه $x_2$ قرار دارد. بعد از آمدن یک صدای جیغ، در یک لحظه به صورت همزمان هر دوی آن‌ها شروع به حرکت می‌کنند. علی با سرعت‌ ثابت $v_1$ و ترب با سرعت ثابت $v_2$ تا ابد حرکت می‌کنند. از شما می‌خواهیم سرنوشت حرکت آن‌ها را مشخص کنید! در واقع می‌خواهیم بدانیم آیا لحظه‌ای وجود دارد که علی و ترب به هم برسند؟! اگر هرگز به هم نمی‌رسند آیا فاصله آن‌ها از هم زیاد می‌شود یا فاصله‌شان همواره ثابت می‌ماند؟! منظور از به هم رسیدن علی و ترب یعنی لحظه‌ای پس از آغاز حرکت وجود داشته باشد که هر دوی آن‌ها در یک نقطه از محور اعداد قرار داشته باشند. توجه کنید که اگر سرعت یک نفر عددی مثبت باشد به سمت راست محور اعداد و اگر منفی باشد به سمت چپ و اگر برابر صفر باشد سر جای خود ثابت می‌ماند. همچنین حرکت به صورت پیوسته است و لحظه و محل برخورد لزوماً عددی صحیح نیست. # ورودی ورودی تنها چهار سطر دارد و در هر کدام یک عدد صحیح آمده است. در سطر اول $x_1$ که نشان دهنده مکان اولیه علی است. در سطر دوم $v_1$ که نشان دهنده سرعت علی است. در سطر سوم $x_2$ که نشان دهنده مکان اولیه ترب است. در سطر چهارم $v_2$ که نشان دهنده سرعت ترب است. $$-1\ 000 \le x_1 \neq x_2 \le 1\ 000$$ $$-100\le v_1, v_2 \le 100$$ تضمین می‌شود مکان اولیه علی و ترب یکسان نیست. # خروجی در تنها سطر خروجی، در صورت به هم رسیدن علی و ترب، عبارت `SEE YOU`، در صورتی که فاصله آن‌ها زیاد می‌شود عبارت `BORO BORO` و در صورتی که فاصله آن‌ها همواره ثابت می‌ماند، عبارت `WAIT WAIT` را چاپ کنید. دقت کنید بزرگ یا کوچک بودن حروف انگلیسی مهم است. # مثال ## ورودی نمونه ۱ ``` 1 5 10 6 ``` ## خروجی نمونه ۱ ``` BORO BORO ``` علی ابتدا در نقطه ۱ از محور اعداد قرار دارد و با سرعت ثابت ۵ (به سمت راست) در حرکت است و ترب ابتدا در نقطه ۱۰ از محور مختصات قرار دارد و با سرعت ثابت ۶ (به سمت راست) در حرکت است. چون در ابتدا ترب سمت راست علی قرار دارد و با سرعت بیشتری نسبت به علی به سمت راست می‌رود فاصله آن‌ها همواره زیاد می‌شود. ## ورودی نمونه ۲ ``` 1 -5 -10 -5 ``` ## خروجی نمونه ۲ ``` WAIT WAIT ``` علی ابتدا در نقطه ۱ از محور اعداد قرار دارد و با سرعت ثابت ۵ (به سمت چپ) در حرکت است و ترب ابتدا در نقطه ۱۰- از محور اعداد قرار دارد و با سرعت ثابت ۵ (به سمت چپ) در حرکت است. بنابراین فاصله علی و ترب همواره برابر ۱۱ خواهد بود. ## ورودی نمونه ۳ ``` 1 6 10 -5 ``` ## خروجی نمونه ۳ ``` SEE YOU ``` علی ابتدا در نقطه ۱ از محور مختصات قرار دارد و با سرعت ثابت ۶ (به سمت راست) در حرکت است و ترب ابتدا در نقطه ۱۰ از محور مختصات قرار دارد و با سرعت ثابت ۵ (به سمت چپ) در حرکت است. بنابراین بعد از گذشت یک واحد زمان از آغاز حرکت علی و ترب بالاخره روی محور اعداد به هم می‌رسند. # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary> راهنمایی ۱ </summary> ابتدا به سرعت دو نفر توجه کنیم. می‌دانیم که تنها اختلاف سرعت دو نفر مهم است و نه بزرگی‌ آن‌ها. برای مثال با فرض بیشتر بودن سرعت علی نسبت به امین و مثبت بودن سرعت هر دو، اگر سرعت علی $a$ و سرعت ترب $b$ باشد، علی در هر ثانیه $a - b$ واحد بیشتر به سمت راست حرکت می‌کند. </details> <details class="blue"> <summary>راهنمایی ۲</summary> بر اساس شهودی که در راهنمایی قبل پیدا کردیم، اکنون فرض می‌کنیم که سرعت نفر اول برابر صفر است و ثابت سر جایش ایستاده است. حال سرعت نفر دوم را نسبت به نفر اول حساب می‌کنیم و بر اساس علامت عدد حاصل، مسئله را حل می‌کنیم. اگر سرعت اول برابر $x$ و سرعت نفر دوم برابر $y$ باشد، سرعت نفر دوم نسبت به نفر اول برابر $y - x$ خواهد بود. </details> <details class="blue"> <summary>راهنمایی ۳</summary> حال سرعت نفر دوم نسبت به نفر اول را $v$ در نظر می‌گیریم. اگر $v$ برابر صفر باشد، از آن‌جایی که این دو نفر مکان اولیه‌شان متفاوت است، هیچ‌گاه به‌ هم نمی‌رسند و فاصله‌شان نیز همواره ثابت است. همچنین برای رسیدن هر دو نفر به هم، اگر نفر دوم سمت راست نفر اول است، باید $v$ منفی و در غیر این صورت باید مثبت باشد. اگر این شرط برقرار بود،‌ به هم می‌رسند و اگر نبود، فاصله‌شان همواره زیاد می‌شود. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی نتوانست ترب را پیدا کند و خیلی از لحاظ روانی به هم ریخته... تصمیم گرفت یک زمین کشاورزی بخرد و در آن ترب بکارد...* زمینی که علی خریده است یک مستطیل $n \times m$ است. این زمین دارای $nm$ قطعه است. قطعات این زمین به صورت یک جدول با $n$ سطر و $m$ستون است. در هر قطعه از این زمین می‌توان یک ترب کاشت یا آن را خالی گذاشت. علی می‌خواهد دقیقاً در $s$ قطعه از این زمین ترب بکارد. علی دچار وسواس تقارن شده و می‌خواهد این کار را طوری انجام دهد، که جدول زمین کشاورزی متقارن باشد. یعنی حداقل یکی از دو محور تقارن افقی یا عمودی وجود داشته باشد که زمین کشاورزی نسبت به آن متقارن باشد. به علی کمک کنید تا روشی برای کاشت $s$ ترب در زمین پیدا کند و اگر این کار ممکن نیست این خبر بد را به او اطلاع دهید. # ورودی در تنها سطر ورودی سه عدد صحیح $n$ و $m$ و $s$ با فاصله از هم آمده است که نشان دهنده ابعاد زمین علی و تعداد قطعاتی است که می‌خواهد در آن‌ها ترب بکارد. $$1 \le n, m \le 100$$ $$0 \le s \le nm $$ # خروجی در خط اول خروجی در صورت امکان پذیر بودن این کار کلمه `possible` و در صورت ممکن نبودن کلمه `impossible` را چاپ کنید. در صورت امکان پذیر بودن باید در $n$ سطر بعدی و در هر سطر یک رشته از $m$ کاراکتر بدون فاصله چاپ شود.اگر در قطعه سطر $i$ام ستون $j$ام ترب کاشته شود کاراکتر `T` و در صورت خالی بودن آن کاراکتر `E` را چاپ کنید. توجه کنید که در صورت وجود جواب، می‌توانید هر جواب دلخواهی را چاپ کنید و مساله جواب یکتا ندارد. # مثال ## ورودی نمونه ۱ ``` 3 3 5 ``` ## خروجی نمونه ۱ ``` possible TTT ETE ETE ``` با کاشت ترب‌ها به روش فوق زمین کشاورزی نسبت به محور عمودی متقارن خواهد بود. ## ورودی نمونه ۲ ``` 4 4 1 ``` ## خروجی نمونه ۲ ``` impossible ``` هیچ روشی برای کاشتن ترب در زمین کشاورزی وجود ندارد. ## ورودی نمونه ۳ ``` 2 3 1 ``` ## خروجی نمونه ۳ ``` possible EEE ETE ``` با کاشت ترب‌ها به روش فوق زمین کشاورزی نسبت به محور عمودی متقارن خواهد بود. ## ورودی نمونه ۴ ``` 2 2 2 ``` ## خروجی نمونه ۴ ``` possible TE TE ``` با کاشتن ترب‌ها به روش فوق زمین کشاورزی نسبت به محور افقی متقارن خواهد بود. # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary> راهنمایی ۱ </summary> با کمی بررسی متوجه می‌شویم که اگر حداقل یکی از $n$ و $m$ فرد باشند، علی همواره می‌تواند روشی برای کاشت ترب در زمین پیدا کند. حال اگر هر دو بعد مستطیل زوج باشند، در می‌یابیم که تعداد ترب‌های کاشته شده هم باید زوج باشد وگرنه زمین ما نمی‌تواند نسبت به هیچ یک از محورهای تقارن قرینه باشد. دلیل آن هم این است که محورهای تقارن ما در یک طرف خود زوج و در طرف دیگر فرد ترب کاشته شده دارند که شرط تقارن را نقض می‌کند. </details> <details class="blue"> <summary>راهنمایی ۲</summary> اگر $n$ و $m$ زوج باشند، می‌دانیم که حتما $s$ هم باید زوج باشد تا بتوانیم جدول مورد نظر را بسازیم. در این صورت می‌توانیم سطرها را به دو نیمه بالا و پایین تقسیم کنیم و به هر قسمت، نیمی از ترب‌ها را اختصاص دهیم. برای متقارن بودن جدول هم به این صورت عمل می‌کنیم که در نیمه بالا سطرها را از پایین به بالا و در نیمه پایین سطرها را از بالا به پایین کار می‌کنیم. همچنین در حین حرکت روی هر سطر نیز خانه‌های آن را از سمت به چپ به راست پر می‌کنیم. </details> <details class="blue"> <summary>راهنمایی ۳</summary> حال به بررسی حالاتی می‌پردازیم که حداقل یکی از $n$ و $m$ فرد است. فرض کنیم $n$ فرد است (اگر نبود، همه این کارها را به صورت ستونی انجام دهید). در ابتدا سطر وسط را در نظر می‌گیریم و شروع به پر کردن آن می‌کنیم. اگر ترب‌ها در سطر وسط جا می‌شدند که همه را همان‌جا می‌گذاریم. در غیر این صورت،‌ بیشترین تعداد ترب را در آن‌جا می‌گذاریم به‌طوری که تعداد ترب‌های باقی‌مانده زوج باشد (این تعداد بسته به زوجیت $s$ تعیین می‌شود و برابر $m$ یا $m - 1$ است). حال بدون در نظر گرفتن سطر وسط، نیمه بالای سطرهای جدول و نیمه پایین آن را با ترب‌های باقی‌مانده پر می‌کنیم به صورتی که نصف ترب‌ها به نیمه پایین و نصف دیگر به نیمه بالا برسد و این‌کار را همانند روش گفته شده در پایان راهنمایی قبل انجام می‌دهیم. با این الگوریتم، جدول نسبت به محور افقی متقارن خواهد شد. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی که حسابی از کار کشاورزی سود کرده... تصمیم گرفت یک شرکت با هدف موتور جست و جوی کالا، تاسیس کند و به یاد مرحوم ترب، نام آن را ترب گذاشته...* *تربچه تصمیم گرفته در این شرکت استخدام شود برای همین می‌خواهد در آزمون استخدامی شرکت کند. در این آزمون سوال زیر آمده... به تربچه کمک کنید تا این سوال را حل کند.* در این سوال یک دنباله از اعداد طبیعی مانند $a_1, a_2, a_3, ..., a_n\ $ آمده است و از تربچه خواسته شده تا حاصل عبارت زیر را محاسبه کند. $$ \sum_{i=1}^{n}\sum_{j=1}^{n}\lfloor\frac{a_i}{a_j}\rfloor$$ به تربچه کمک کنید تا این عبارت را محاسبه کند و در شرکت ترب استخدام شود. # ورودی در سطر اول ورودی عدد صحیح $n$ که نشان دهنده تعداد اعداد دنباله است و در سطر دوم $n$ عدد صحیح با فاصله آمده که عدد $i$ام نشان دهنده مقدار $a_i$ است. $$1 \le n, a_i \le 100\ 000$$ # خروجی در تنها سطر خروجی، یک عدد صحیح که پاسخ مسئله است را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 3 ``` ## خروجی نمونه ۱ ``` 9 ``` حاصل عبارت برابر است با: $$\lfloor\frac{1}{1}\rfloor + \lfloor\frac{1}{2}\rfloor + \lfloor\frac{1}{3}\rfloor + \lfloor\frac{2}{1}\rfloor + \lfloor\frac{2}{2}\rfloor + \lfloor\frac{2}{3}\rfloor + \lfloor\frac{3}{1}\rfloor + \lfloor\frac{3}{2}\rfloor + \lfloor\frac{3}{3}\rfloor =$$ $$ 1 + 0 + 0 + 2 + 1 + 0 + 3 + 1 + 1 = 9$$ ## ورودی نمونه ۲ ``` 4 1 1 1 1 ``` ## خروجی نمونه ۲ ``` 16 ``` چون همه مقادیر باهم برابر است حاصل عبارت برابر است با: $$4 \times 4 \times \lfloor\frac{1}{1}\rfloor = 16$$ # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary>راهنمایی ۱</summary> فرض کنید مقدار $\lfloor\frac{a_i}{a_j}\rfloor = k$ در این صورت داریم $$k \leq \frac{a_i}{a_j} < k + 1 \Rightarrow k a_j \leq a_i \leq (k + 1) a_j $$ مقدار $M$ را بزرگ ترین عدد آمده در دنباله در نظر بگیرید یعنی: $$M = \max_{1 \le i \le n}\{ a_i \}$$ مقدار $cnt_k$ را تعریف می‌کنیم تعداد همه $a_i$ هایی که $a_i < k$ باشد. به راحتی می‌توان مقدار $cnt_k$ را برای همه $1 \le k \le max\{a_i\}$ از مرتبه زمانی $O(M)$ با استفاده از ایده جمع تجمعی یا `partial sum` محاسبه کرد. </details> <details class="blue"> <summary>راهنمایی ۲</summary> مقدار خواسته شده را با حالت بندی روی $k$های مختلف محاسبه می‌کنیم. $$\sum_{i=1}^{n}\sum_{j=1}^{n} \lfloor\frac{a_i}{a_j}\rfloor = \sum_{j=1}^{n} \sum_{k=1}^{max\{a_i\}} k(cnt_{(k + 1)a_j} - cnt_{ka_j})$$ با کمی مشاهده متوجه می‌شویم نیازی نیست مجموع دوم تا انتهای کار محاسبه شود (چرا؟). و همین که $k \leq \frac{M}{a_j}$ باشید کافی است پس داریم : $$ = \sum_{j = 1}^{n}\sum_{k = 1}^{\frac{M}{a_j}} k(cnt_{(k + 1)a_j} - cnt_{ka_j}) $$ </details> <details class="blue"> <summary>راهنمایی ۳</summary> به جای مجموع روی اندیس $a_j$ روی مقدار $a_j$ مجموع را حساب می‌کنیم یعنی اگر $a_j = l$ باشد داریم: $$ = \sum_{l = 1}^{M}\sum_{k=1}^{\frac{M}{l}} k(cnt_{(k + 1)a_j} - cnt_{ka_j})$$ همانطور که می‌دانیم دو مجموع فوق مشابه الگوریتم غربال-اراتستن از مرتبه زمانی $O(M \log{M})$ بنابراین کل مسئله از مرتبه زمانی $O(n + M \log{M})$ حل می‌شود. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی توانست شرکتش را توسعه دهد و یک زمین که به صورت یک جدول نامتناهی خریده و در هر خانه آن یک ترب کاشته است. همچنین یک دستگاه تربچین دارد که می‌خواهد با کمک آن ترب‌ها را برداشت کند...* علی از تربچه خواسته ابتدا تربچین را در قطعه $(0, 0)$ زمین قرار ‌دهد. تربچه برای آغاز کار یک رشته از حروف $\{L, R, U, D, ?\}$ دریافت می‌کند و طبق آن روی قطعه‌های زمین حرکت می‌کند و در هر قطعه که قرار بگیرد ترب داخل آن را می‌چیند. همچنین اگر در یک خانه از جدول بیش از یک بار قرار بگیرد دیگر تربی برداشت نمی‌کند. اگر رشته داده شده به تربچین $s_1s_2s_3...s_n\ $ باشد. تربچین با توجه به این رشته $n$ حرکت انجام می‌دهد.اگر تربچین در خانه $(x, y)$ باشد بعد از انجام حرکت $i$ام : + اگر $s_i=L$ باشد به خانه $(x-1, y)$ + اگر $s_i=R$ باشد به خانه $(x+1, y)$ + اگر $s_i=U$ باشد به خانه $(x, y+1)$ + اگر $s_i=D$ باشد به خانه $(x, y-1)$ + اگر $s_i=?$ باشد به یکی از چهار قطعه مجاور ضلعی می‌رود. علی رشته $s_1s_2s_3...s_n\ $ را به ترب داده و او ترتیب عناصر این رشته را به هم ‌می‌ریزد. توجه کنید او نمی‌تواند حرفی به رشته اضافه یا کم کند! علی که پیش‌بینی برایش خیلی مهم است؛ می‌خواهد بداند برای همه حالت‌های مختلف که ممکن است اتفاق بیفتد حداقل و حداکثر چند ترب توسط تربچین برداشت خواهد شد. به علی کمک کنید تا این دو عدد را محاسبه کند. # ورودی در خط اول ورودی عدد $t$ داده می‌شود. در هر یک از $t$ سطر بعدی هر کدام یک رشته از حروف $\{L, R, U, D, ?\}$ داده می‌شود. تضمین می‌شود مجموع طول همه رشته‌ها از $100\ 000$ بیشتر نمی‌شود. # خروجی خروجی باید شامل $t$ سطر باشد که در سطر $i$ام دو عدد $a_i$ و $b_i$ چاپ می‌شود که نشان دهنده حداقل و حداکثر تعداد ترب‌های برداشت شده توسط تربچین است. # مثال ## ورودی نمونه ۱ ``` 5 L L? UDU ???? LRURLDURDDD ``` ## خروجی نمونه ۱ ``` 2 2 2 3 2 3 2 5 4 12 ``` ترتیب‌های بیشینه و کمینه به ترتیب در هر مورد به صورت زیر است: $L \to min = max = 2$ $LU \to max = 3, LR \to min = 2$ $UDU\to min = 2, UDU\to max = 3$ $LRLR \to min = 2, DDDD \to max = 5$ $RLRLRDUDUDD \to min = 4$ $LLUURRRDDDD \to max = 12$ # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary>راهنمایی ۱</summary> فرض کنید در رشته ورودی تعداد حرکت‌های از نوع `L` برابر $L$، نوع `R` برابر $R$، نوع `U` برابر $U$، نوع `D` برابر $D$ و تعداد `؟` برابر $Q$ باشد. در ابتدا برای سادگی فرض کنید هیچ `؟` در ورودی به شما داده نمی‌شود. اگر بخواهیم حالت‌ کمینه را محاسبه کنیم. در این وضعیت حرکت‌های بالا و پایین و حرکت‌های چپ راست مستقل از هم هستند. اگر بخواهیم حالت بیشینه را محاسبه کنیم در **اکثر** حالت‌ها می‌تونیم به اندازه طول رشته خانه جدید برویم و ترب برداشت کنیم. </details> <details class="blue"> <summary>راهنمایی ۲</summary> برای محاسبه کمینه اگر هیچ حرکت چپ یا راستی نداشته باشیم به جز خانه ابتدایی صفر ترب برداشت می‌کنیم. اگر حداقل یک حرکت چپ یا راست داشته باشیم حداقل $\max(|R - L|, 1)$ ترب برداشت می‌کنیم. به طور مشابه برای حرکت های بالا و پایین نیز می‌توان این را محاسبه کرد. یعنی اگر حداقل یک حرکت بالا یا پایین داشته باشیم حداقل $\max(|U - D|, 1)$ ترب برداشت می‌کنیم. برای محاسبه بیشینه اگر هیچ حرکت چپ یا راست نداشته باشیم حداکثر خانه‌ای که به جز خانه ابتدایی از آن ترب برداشت می‌کنیم برابر است با $max(U, D)$ به طور مشابه اگر هیچ حرکت بالا و پایین نداشته باشیم حداکثر خانه‌ای که به جز خانه ابتدایی از آن ترب برداشت می‌کنیم برابر است با $max(L, R)$ حال اگر از هر دو نوع بالا حداقل یک حرکت داشته باشند می‌توان در **اکثر** حالت‌ها به جز خانه ابتدایی از $L+R+U+D$ خانه جدول ترب برداشت کنیم. </details> <details class="blue"> <summary>راهنمایی ۳</summary> حال فرض کنید $Q$ نیز ناصفر باشد برای حالت کمینه می‌توان $Q$ واحد از اختلاف $|R - L|$ و $|U - D|$ کاهش داد. برای حالت بیشینه می‌توان $Q$ ترب اضافه برداشت کرد. اما تنها حالت خاصی که در شرایط صدق نمی‌کند حالتی است که $Q = 0, L = R, U = D$ این تنها حالتی است که ما به خانه ابتدایی باز می‌گردیم و یک ترب کمتر برداشت می‌کنیم. </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی برای افزایش روحیه تیم ترب تصمیم گرفته آن‌ها را به اسکیپ روم ببرد... آن‌ها باید سوال زیر را حل کنند تا وارد مرحله بعد شوند... به آن‌ها کمک کنید تا این گردش برایشان جذاب شود* یک گراف ساده مانند $G$ با $n$ راس با شماره‌های ۱ تا $n$ و $m$ یال دو طرفه داریم. بین هر دو راس حداکثر یک یال وجود دارد. هر یال دو راس مختلف را به هم وصل می‌کند. توجه کنید لزوماً این گراف همبند نیست! هر راس از این گراف در ابتدا با یکی از دو رنگ سیاه و سفید رنگ آمیزی شده است. در هر عملیات می‌توانیم یک زیر مجموعه از رئوس مانند $S$، انتخاب کنیم و رنگ هر راس در مجموعه $S$ و همه رئوسی که به حداقل یک راس از $S$ یال دارند را عوض کنیم. (رنگ سفید را به سیاه و رنگ سیاه را به سفید) می‌خواهیم با حداکثر $n + 1$ عملیات کل رئوس گراف را سفید کنیم. اگر چنین کاری ممکن است یک روش برای انجام این کار ارائه دهید در غیر اینصورت بگویید این کار ممکن نیست. # ورودی در خط اول ورودی دو عدد صحیح $n$ و $m$ با فاصله از هم آمده است. $$0 \le n \le 1500$$$$ 0 \le m \le \frac{n(n - 1)}{2}$$ در سطر بعدی یک رشته از $0$ و $1$ به طول $n$ آمده است که اگر عدد $i$ام آن $0$ باشد یعنی راس شماره $i$ سفید و اگر $1$ باشد یعنی رنگ راس شماره $i$ سیاه است. در $m$ سطر بعدی هر کدوم دو عدد $u$ و $v$ آمده است. که نشان دهنده یال‌های گراف است. $$ 1 \le u \neq v \le n$$ # خروجی در صورت امکان پذیر بودن در سطر اول $k$ که تعداد مراحلی که نیاز دارید تا رنگ همه رئوس را سفید کنید چاپ کنید. $$0 \le k \le n + 1$$ در $k$ سطر بعدی در هر سطر یک رشته از $0$ و $1$ چاپ کنید که عدد $i$ام آن $1$ است اگر راس شماره $i$ در مرحله $i$ام در مجموعه $S$ باشد و در غیر اینصورت $0$ خواهد بود. در صورت امکان پذیر نبودن در تنها سطر خروجی `-1` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 3 0110 1 2 2 3 3 4 ``` ## خروجی نمونه ۱ ``` 3 0100 0010 1001 ``` ## ورودی نمونه ۲ ``` 3 3 110 1 2 2 3 3 1 ``` ## خروجی نمونه ۲ ``` -1 ``` # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary>راهنمایی ۱</summary> اول بیاییم یک شرط برای `-1` شدن جواب پیدا کنیم. فرض کنید دو تا راس $u$ و $v$ که به هم وصل هستند و مجموعه همسایه های یکسانی دارند، رنگشان فرق دارد. این‌جوری هیچ مجموعه‌ای که دقیقا یکی از این دو راس را شامل شود، نداریم. پس جواب برابر `-1` است. </details> <details class="blue"> <summary>راهنمایی ۲</summary> ابتدا به ازای هر $u$ و $v$ که با هم همسایه‌اند و مجموعه همسایه‌هایشان برابر است، یکی را حذف کنید چون رنگ این دو همیشه برابر است و در انتها هر دو سفید می‌شوند. حال راس‌های گراف را بر حسب درجه مرتب کنید. فرض کنید برای هر راس $v$ می‌توانیم با تعدادی عملیات رنگ $v$ را عوض کنیم طوری که برای هر $u$ که $deg_v \le deg_u$ رنگ $u$ ثابت بماند. حال راس هارا به ترتیب درجه از بزرگ بررسی کنید و به هرکس که رسیدید، رنگ او را با عملیات گفته شده تغییر دهید. </details> <details class="blue"> <summary>راهنمایی ۳</summary> ادعا میکنیم عملیات گفته شده در قبل برای راس $v$ اینگونه انجام میشود: یکبار $S$ را برابر تمام ریوس غبر از $v$ قرار دهید که با $v$ مجاور نیستند. و یکبار هم $S$ را برابر با تمام ریوس قرار دهید. بدیهتا عملیات دوم رنگ تمام ریوس را تغییر میدهد پس بیایید عملیات اول را بررسی کنیم: بدیهتا هر راس غیر همسایه $v$ تغییر میکند و خود $v$ نیز تغییر نمیکند. پس فقط همسایه های $v$ میمانند. اگر راس $u$ داشتیم که $deg_u>deg_v$ رنگ $u$ تغییر میکند چون به حداقل یک راس غیر همسایه $v$ وصل است. اگر هم راس $u$ با درجه برابر $v$ داشتیم باز هم $u$ همسایه ای در $S$ دارد وگرنه مجموعه همسایه های $u$ و $v$ برابر بود. پس با عملیات اول رنگ همه به جز $v$ و تعدادی از همسایه های با درجه کمترش عوض میشوند و پس از عملیات دوم که رنگ همه عوض میشود انگار فقط رنگ $v$ و تعدادی راس با درجه کمتر عوض شده است. با این روش به ازای هر راس حداکثر 2 عملیات انجام داده ایم که یکی از انها روی تمام ریوس بوده است. چون از هر نوع عملیات فقط زوجیت تعداد دفعات ان مهم است پس در مجموع $n+1$ عملیات داریم. زمان اجرای این راه حل از $O(n^3)$ است که با `std::bitset` در زمان مطلوب اجرا میشود </details>

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی برای بهبود کار شرکت می‌خواهد چند نفر از اعضای شرکت که می‌توانند سوال زیر را حل کنند انتخاب کند و آن‌ها را برای آموزش پیشرفته آماده کند... تربچه که خیلی دوست دارد آموزش‌های پیشرفته را ببیند می‌خواهد این سوال را حل کند... به او کمک کنید تا این کار را انجام دهد...* برای هر عدد طبیعی فرض کنید $P_n$ مجموعه همه دنباله‌هایی از اعداد طبیعی باشد که جمع اعضای این دنباله برابر $n$ است. به عبارت دیگر: $$P_n = \{ (a_1a_2a_3\dots a_m) | a_1+a_2+a_3+\dots+a_m=n\}$$ اکنون ترب می‌خواهد عبارت زیر را محاسبه کند. $$ \sum_{(a_1a_2a_3\dots a_m) \in P_n} {a_1}^k{a_2}^k{a_3}^k\dots{a_m}^k$$ به ترب کمک کنید تا این عبارت را محاسبه کند چون ممکن است پاسخ شما بسیار عدد بزرگی باشد باقی‌مانده آن را به پیمانه $10^9+7$ حساب کنید. # ورودی ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده است. $$1 \le k\le 100,1 \le n\le 10^9$$ # خروجی در تنها سطر خروجی پاسخ مسئله را به پیمانه $10^9+7$ چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 4 2 ``` ## خروجی نمونه ۲ ``` 63 ``` تمام اعضای مجموعه $P_4$ عبارت است از: $$P_4=\{ (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2), (3,1), (1,3), (4) \} $$ بنابراین حاصل مجموع فوق برابر است با: $$ 1 + 4 + 4 + 4 + 16 + 9 + 9 + 16 = 63$$ # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary> راهنمایی ۱ </summary> اولین نکته‌ای که توجه به آن برای حل مسئله ضروری می‌باشد، این است که افرازهایمان ترتیب دارند و برای مثال افراز `1 2` با افراز `2 1` فرق دارد. حال بر اساس این نکته می‌توان دریافت که تعداد افرازهای ترتیب‌دار عدد $n$ برابر $2^{n - 1}$ می‌باشد چرا که می‌توانیم $n$ توپ در یک ردیف در نظر بگیریم و هر افراز را با یک حالت دیوار گذاشتن در $n - 1$ جایگاه خالی بین‌ توپ‌ها متناظر کنیم. حال برای عبارت جواب، مسئله‌ای ترکیبیاتی تعریف می‌کنیم و تلاش می‌کنیم تا با شمارش مضاعف، آن را به روش دیگری محاسبه کنیم: در یک ردیف، $n$ جعبه متوالی با شماره ۱ تا $n$ داریم. می‌خواهیم آن‌ها را بلوک‌بندی کنیم و در هر بلوک، به ازای همه رنگ‌های ۱ تا $k$، دقیقا یک توپ با آن رنگ را در یکی از جعبه‌های این بلوک قرار دهیم. اگر ترتیب قرار دادن توپ‌ها در جعبه‌ها اهمیتی نداشته باشد، به چند طریق این کار ممکن است؟ </details> <details class="blue"> <summary>راهنمایی ۲</summary> برای حل مسئله مطرح شده در انتهای راهنمایی قبل، از برنامه‌نویسی پویا استفاده می‌کنیم یا به عبارت دیگر $dp$ می‌زنیم :) ابتدا به تعریف $dp$ می‌پردازیم. $dp[i][j]$ یعنی تعداد روش‌های چیدن توپ‌ها در $i$ جعبه اول به گونه‌ای که بلوک آخرمان برای تکمیل شدن،‌ به $j$ توپ رنگی دیگر نیاز داشته باشد. دقت کنید که تعداد بلوک‌ها برایمان اهمیتی ندارد و نه در مولفه و نه در پاسخ هر خانه آرایه، به آن اشاره‌ای نمی‌کنیم. حالت پایه که تقریبا واضح است، $dp[0]0] = 1$. برای اپدیت کردن یک استیت، بر روی تعداد توپ‌های رنگی خانه $i$ام حالت می‌بندیم. به ازای همه $r$هایی که $j \le r \le k$، از $dp[i - 1][r]$ اپیدت می‌شوم و ضریب این اپدیت هم برابر حاصل انتخاب $j$ از $r$ می‌باشد چرا که قرار است از $r$ توپ رنگی باقی‌مانده در مرحله قبل، $j$ تا را برای ادامه بلوک انتخاب کنیم و بقیه را در جعبه $i$ ام قرار دهیم. همچنین یک حالت دیگر هم وجود دارد و آن هم اینکه خانه $i$ام اولین خانه بلوک جدید باشد که در این حالت $dp[i][j]$ باید از $dp[i - 1][0]$ با ضریب $j$ از $k$ اپدیت شود. با توجه به راه‌حل تعداد خانه‌های آرایه $dp$ که باید پر شوند، $nk$ می‌باشد و برای اپدیت کردن هر خانه هم $O(k)$ عملیات انجام می‌دهیم. بنابراین پیچیدگی زمانی راه‌حل فعلی از $O(nk^2)$ می‌باشد. </details> <details class="blue"> <summary>راهنمایی ۳</summary> حال که بلدیم برای مسئله $dp$ دو بعدی مناسبی تعریف کنیم که هر سطر آن، فقط از سطر قبلی و به صورت خطی با ضرایب آپدیت می‌شود، می‌توانیم از ماتریس برای حل مسئله استفاده کنیم. به این صورت که یک ماتریس یک بعدی به طول $k + 1$ را به عنوان پایه در نظر می‌گیریم و از یک ماتریس دو بعدی $(k + 1) \times (k + 1)$ برای اپدیت کردن آن استفاده می‌کنیم، به این صورت که اگر ماتریس دو بعدی ما در ماتریس یک بعدی ما که نشان‌دهنده مقادیر خانه‌های سطر $i$ام است ضرب شود، حاصل ماتریس یک بعدی خواهد شد که مقادیر سطر $i + 1$ را داراست. ساختن این ماتریس نیز بر اساس ضرایب اپدیت $dp$ است و تعدادی انتخاب و به علاوه یک خواهد بود. حال می‌دانیم که مقادیر سطر صفر را در ماتریس پایه‌ بریزیم، برای داشتن سطر پایانی باید $n$ بار در ماتریس اپدیت ضرب شویم و از آن‌جایی که ضرب ماتریس به صورت بالا خاصیت شرکت‌پذیری دارد، ابتدا ماتریس اپدیت را در $O(k^3lg_n)$ به توان $n$ می‌رسانیم و سپس حاصل را در ماتریس پایه ضرب می‌کنیم تا سطر $n$ام $dp$ به دست آید و خانه اول آن یعنی $dp[n][0]$ پاسخ مسئله ما خواهد بود. </details>

+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی که در این گرمای تابستان اعضای شرکت را به اسکیپ روم برده بود برای رفع خستگی تصمیم می‌گیرد برای آن‌ها نوشابه بخرد... اما می‌خواهد تنها برای افرادی نوشابه بخرد که بتوانند سوالات زیر را درباره گراف پاسخ دهند...* فرض کنید $G$ یک گراف وزن دار بدون جهت **همبند** باشد. $G$ دارای $n$ راس و $m$ یال است. هر یال $G$ دو راس مختلف را به هم متصل می‌کند. همچنین راس‌های این گراف با ۱ تا $n$ شماره گذاری شده‌اند. روی راس شماره $i$ عدد $a_i$ نوشته شده است. از ما تعدادی سوال پرسیده می‌شود. در هر سوال سه عدد $v$ و $x$ و $k$ داده می‌شود و از ما کوچک‌ترین مقدار $w$ را می‌خواهند که حداقل $k$ راس وجود داشته باشند که فاصله آن‌ها از $v$ فاصله حداکثر $w$ باشد و عدد نوشته شده روی آن نسبت به $x$ اول باشد. منظور از وزن یک مسیر بزرگ ترین عددی است که روی یال‌های آن مسیر وجود دارد. منظور از **فاصله** دو راس مانند $u$ و $v$ کمینه مقدار وزن تمام مسیرهای ممکن بین $u$ و $v$ است. # ورودی در سطر اول ورودی سه عدد طبیعی $n$ و $m$ و$q$ با فاصله از هم آمده است که به ترتیب نشان دهنده تعداد رئوس، یال‌ها و سوالاتی است که باید به آن‌ها پاسخ بدهیم. $$1 \le n, m, q \le 100\ 000$$ در سطر دوم $n$ عدد مانند $a_1, a_2, a_3,..., a_n$ با فاصله آمده که نشان دهنده اعداد نوشته شده روی رئوس گراف است. در $i$امین سطر از $m$ سطر بعدی، سه عدد $v_i$ و $u_i$ و $w_i$ عدد آمده است که نشان‌دهنده وجود یالی با وزن $w_i$ بین دو راس $v_i$ و $u_i$ است. دقت کنید که لزومی ندارد گراف ساده باشد و ممکن است طوقه یا یال چندگانه داشته باشیم. $$1 \le u_i, v_i \le n$$ $$1 \le w_i \le 10^9 $$ در $j$امین سطر از $q$ سطر بعدی، سه عدد $v_j$ و $x_j$ و $k_j$ آمده است که نشان دهنده سوال علی از شماست؟$$1 \le a_i, x_j \le 500\ 000$$ $$1 \le v_j \le n$$ $$2 \le k_j \le n$$ # خروجی در $q$ سطر خروجی در سطر $i$ام پاسخ سوال $i$ام را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 3 2 6 9 5 1 2 10 2 3 20 1 3 30 3 7 2 1 25 2 ``` ## خروجی نمونه ۱ ``` 20 10 ``` ## ورودی نمونه ۲ ``` 4 3 4 1 2 3 4 1 2 10 2 3 1 3 4 2 3 3 2 4 5 3 4 5 4 1 2 4 ``` ## خروجی نمونه ۲ ``` 2 2 10 -1 ``` # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary>راهنمایی ۱</summary> در ابتدا برای حل مسئله، *mst* گراف را در نظر می‌گیریم. برای این کار از الگوریتم *kruskal* با *dsu* استفاده میکنیم. حال درخت باینری $T$ را بدین‌شکل می‌سازیم که $n$ برگ و $n-1$ غیر برگ داشته باشد و هر برگ آن متناظر یکی از رئوس گراف اولیه و هر غیر برگ آن متناظر یکی از یال های *mst* بوده و دقیقا 2 بچه داشته باشد. اگر در $T$ برگ های هر زیردرخت را بگیریم، در *mst* تشکیل یک زیرگراف همبند می‌دهند که زمانی یکی از مولفه های همبندی *dsu* بوده است. این درخت را همزمان با پیدا کردن *mst* می‌سازیم بدین‌صورت که برای هر مولفه در *dsu* شماره راس ریشه آن را نگه می‌داریم و موقع ادغام کردن دو مولفه، یک راس ریشه جدید ساخته و *parent* ریشه‌های دو مولفه قبلی را راس جدید می‌گذاریم و $value$ راس جدید را هم برابر وزن یال متناظرش در *mst* قرار می‌دهیم. </details> <details class="blue"> <summary>راهنمایی ۲</summary> فرض کنید جعبه‌ای داریم که دو عملیات زیر را در $O(2^6)$ برای دامنه $x$ موجود در صورت مسئله انجام می‌دهد. + `add x` عدد $x$ را به دنباله $A$ اضافه می‌کند. + `get x` تعداد اعضای $A$ که نسبت به $x$ اول هستند را برمی‌گرداند. برای این کار $cnt_x$ را تعریف می‌کنیم را تعداد اعداد $A$ که مضرب $x$ هستند. حال برای پرسش نوع دوم از اصل شمول و عدم شمول استفاده می‌کنیم. به ازای هر مجموعه از عوامل اول $x$ مانند $S$ که ضرب اعضایش $y$ است، مقدار $(-1)^{|S|}*cnt_y$ را به جواب اضافه می‌کنیم. چون همه $x$ ها حداکثر $500\ 000$ اند، پس حداکثر ۶ عامل اول متفاوت دارند و هر درخواست در $O(2^6)$ انجام می‌شود. حال به سوال اصلی باز گردیم. برای جواب دادن کوئری‌های ورودی، می‌توانیم از *Binary Search* روی جواب استفاده کنیم. پاسخ درخواستی که به شکل `v x w` داده می‌شود، تعداد رئوسی است که عدد نوشته شده بر روی آن‌ها، نسبت به $x$ اول است و فاصله‌شان تا $v$ حداکثر $w$است. همچنین می‌دانیم تمام راس‌هایی که شرط فاصله برایشان برقرار است، برگ های یک زیردرخت از $T$ هستند. پس می‌توانیم همه آن‌ها را به جعبه اضافه کرده و در انتها جواب را از جعبه بپرسیم ولی پیچیدگی زمانی این راه بیش از حد مطلوب ماست. </details> <details class="blue"> <summary>راهنمایی ۳</summary> برای بهتر کردن راه قبل میتوان از *Parallel Binary Search* یا باینری سرچ موازی استفاده کرد. میخواهیم همزمان جواب کوئری‌های سوال را حساب کنیم. برای اینکار روی انها همزمان باینری سرچ میزنیم و $O(log(n))$ بار جواب همه کوئری‌ های `v x subtree` را حساب میکنیم. برگ های $T$ را بر حسب *starting time* مرتب کنید. حال هر کویری معادل برگ های یک بازه است که هر کدام معادل دو کویری پریفیکس است. برای جواب دادن کویری های پریفیکس هم برگ ها را به ترتیب به جعبه اضافه کنید و به هر کویری که رسیدید $x$ آن کویری را از جعبه بپرسید. پیچیدگی زمانی: $O((n+q).log(n).2^6)$ </details>