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

حل سؤال در بانک سؤالات