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

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

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

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

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