+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در این سوال از شما میخواهیم که در یک حرکت نمادین یک بازی ساده بنویسید. باشد که صنعت بازی‌سازی مملکت راه بیفتد... ## توضیحات بازی ۱- زمین بازی یک جدول $n \times m $ است و دو تیم در این زمین مشغول بازی هستند. سطر‌های این جدول را از بالا به پایین با اعداد ۱ تا $n$ و ستون‌های آن را از چپ به راست با ۱ تا $m$ شماره‌گذاری می‌کنیم. هر تیم یک امتیازی دارد که در ابتدا امتیاز هر دو تیم صفر می‌باشد. در آخر بازی هم تیمی برنده است که امتیاز آن بیشتر باشد. ۲- تیم اول $a$ و تیم دوم $b$ مهره در زمین دارند. هر کدام از این مهره‌ها در یکی از خانه‌های جدول هستند به طوری که در هر خانه حداکثر یک مهره می‌باشد. در نتیجه $n \times m \ge a + b$. حال مهره‌ها را با اعداد ۱ تا $ a + b$ شماره‌گذاری میکنیم؛ به طوری که از ۱ تا $a$ اندیس مهره‌های تیم اول، و از $ a + 1 $ تا $ a + b $ اندیس مهره‌های تیم دوم می‌باشند. ۳- هر مهره دو نوع کار می‌تواند انجام دهد. به یکی از خانه‌های مجاور ضلعی خانه‌ی الآنش برود و یا به یکی از چهار طرف خانه‌ای که در آن قرار دارد (چپ، بالا، راست، پایین) تیر شلیک کند. او در هر ثانیه می‌تواند حداکثر یک بار جابجا شود(می‌تواند هم جابجا نشود) و حداکثر یک بار شلیک کند(‌می‌تواند هم شلیک نکند). **دقت کنید که یک مهره به خانه‌ای که در آن مهره‌ای وجود دارد نمی‌تواند برود. همچنین از جدول نیز نمی‌تواند خارج شود. ** ۴- در هنگام شلیک کردن یک تیر، هر مهره می‌تواند تیر خود را در یکی از چهار جهت اصلی شلیک کند. همچنین هر تیر در هر ثانیه یک خانه در جهتی که شلیک شده است جلو می‌رود؛ یعنی اگر برای مثال مهره‌ای در خانه‌ی $(tx, ty)$ باشد و تیری در جهت بالا شلیک کند، در ثانیه‌ی شلیک، ** تیر در خانه‌ی ** $(tx - 1, ty)$ ** به وجود می‌آید و از ثانیه‌ی بعدی با بردار ** $(-1, 0)$ ** حرکت خواهد کرد. ** اگر تیر به دیواره‌ی جدول یا به یکی از مهره‌های تیم حریف برخورد کند، از بین می‌رود. ** دقت کنید که در هر لحظه در هر خانه به هر تعداد می‌تواند تیر وجود داشته باشد. همچنین تیرها با هم برخورد نمی‌کند و از هم رد می‌شود.** ۵- هر مهره یک پارامتر جان و یک پارامتر قدرت دارد که برای مهره‌ی $i$، این دو را به ترتیب با $h_i$ و $d_i$ نمایش می‌دهیم. اگر جان مهره‌ای صفر یا کمتر شود، آن مهره می‌میرد و از بازی حذف خواهد شد. همچنین تیری که مهره‌ی $i$ شلیک می‌کند دارای قدرت $d_i$ است و اگر به هر کدام از مهره‌‌های تیم حریف برخورد کند از جان او به اندازه‌ی $d_i$ کم می‌کند. ** دقت کنید که تیر مهره‌ی یک تیم بر مهره‌های همان تیم اثر ندارد و بدون برخورد از آن‌ها عبور می‌کند. ** ۶- هر مهره نمی‌تواند به صورت همزمان بیش از ۵ تیر در زمین بازی داشته باشد؛ دقت کنید که این جمله به این معنا نیست که هر مهره باید در کل بازی حداکثر ۵ تیر بزند. ۷- در زمان بازی و در حین انجام بازی، گاهی اوقات، یک «افزونه» در یکی از خانه‌های جدول به وجود می‌آید. افزونه یک موجودی است که اگر توسط مهره‌ای خورده شود بر آن مهره تاثیر می‌گذارد. افزونه‌ها دو نوع هستند. افزونه‌های جانی که جان مهره $(h_i)$ را زیاد می‌کنند و افزونه‌های قدرتی که مقدار قدرت مهره $(d_i)$ را زیاد می‌کنند. هر افزونه یک پارامتر «تغییر» $s$ دارد که به همان مقدار در مهره تغییر ایجاد می‌کند. اگر یک مهره در خانه‌ای برود که تعدادی افزونه در آن قرار دارد، آن مهره این افزونه‌ها را خورده و تغییرات رویش انجام می‌شود و ۱ امتیاز به امتیاز تیمش اضافه خواهد شد. ** دقت کنید که بعد از خورده شدن افزونه‌های یک خانه، در آن خانه دیگر افزونه‌ای وجود ندارد. همچنین در هر خانه‌ به تعداد دلخواه افزونه می‌تواند وجود داشته باشد‌. ** ۸- همانند افزونه، چیزی به نام «بمب» وجود دارد که هر از چند گاهی در یکی از خانه‌‌های جدول به وجود می‌آید. هر بمب یک پارامتر قدرت $g$ دارد که اگر مهره‌ای به خانه‌ای برود که در آن تعدادی بمب وجود دارد، بمب‌ها ترکیده و از جان آن مهره و تمام مهره‌هایی که با بمب‌ها در یک ردیف و یا یک ستون هستند، به اندازه‌ی مجموع $g$ بمب‌ها کم می‌شود. ** دقت کنید که بعد از ترکیدن بمب‌ها، دیگر بمبی در آن خانه وجود ندارد. همچنین بمب بر روی تمام مهره‌ها تاثیر داشته و تاثیر بمب به اینکه هر مهره در کدام تیم است بستگی ندارد. ** ## توضیحات سوال تعدادی بازیکن در حال بازی کردن این بازی هستند و هر کدام از آن‌ها کنترل یک مهره را در اختیار دارند. حال ما حالت اولیه‌ی بازی و تغییرات زمین بازی در هر لحظه و دکمه‌هایی که این بازیکن‌ها می‌زنند را به شما می‌دهیم و شما باید در آخر بازی، امتیاز هر تیم را به ما بگویید. **‌ دقت کنید که اگر به علتی (ترکیدن بمب‌ها یا مردن توسط تیر‌های حریف) یکی از مهره‌های یک تیم بمیرد، ۱۰ امتیاز به امتیاز تیم حریف اضافه خواهد شد.** نحوه‌ی کلی ورودی دادن هم به این صورت است در هر ثانیه تغییرات بازی را به شما ورودی می‌دهیم. تغییرات بازی در هر ثانیه چهار نوع هستند: ۱- بازیکنی دکمه‌ای زده است که مهره‌ی ‌$i$ در جهت $d$ حرکت کند.($d$ نمایانگر یک از چهار جهت اصلی می‌باشد.) دقت کنید که شاید به خاطر پر بودن خانه یا خوردن به دیواره‌ی جدول مهره نتواند حرکت کند. ** همچنین دقت کنید که شاید اصلا مهره‌ی $i$ مرده باشد اما به خاطر سماجت بازیکن، همچنان دکمه حرکتش زده شود و این درخواست برای شما ارسال شود. در این حالت شما باید این را در نظر نگرفته و رد کنید. همچنین امکان دارد که بازیکنی دکمه‌ی شلیک را بزند در حالیکه مهره‌ی مربوط به او دارای بیش از ۵ تیر در زمین می‌باشد.** ۲- مهره‌ی $i$ در جهت $d$ شلیک کرد.($d$ نمایانگر یک از چهار جهت اصلی می‌باشد.) ** دقت کنید که شاید اصلا مهره‌ی $i$ مرده باشد اما به خاطر سماجت بازیکن، همچنان دکمه شلیک زده شود و این درخواست برای شما ارسال شود. در این حالت شما باید این را در نظر نگرفته و رد کنید. ** ۳- یک افزونه از نوع $k$ با مقدار پارامتر «تغییر» $s$ در خانه‌ی $(x, y)$ قرار بده.( $k$ نمایانگر یکی از دو نوع جانی و قدرتی می‌باشد.) ۴- یک بمب با پارامتر قدرت $g$ در خانه‌ی $(x, y)$ قرار بده. ## ترتیب اعمال اتفاقات در هر ثانیه به ترتیب زیر اتفاقات رخ می‌دهد: ابتدا تیرهای درون زمین جابجا می‌شود. سپس گلوله‌هایی که در آن ثانیه به وجود آمده‌اند به بازی اضافه می‌شود. سپس تمام این گلوله‌ها اگر در حال حاضر به مهره‌ای برخورد می‌کنند، برخوردشان تاثیر داده شده و از جان افراد کم می‌شود. **‌دقت کنید که شاید چند گلوله به کسی بخورد. در این حالت شما باید تمام این گلوله‌ها را تاثیر دهید حتی اگر هر کدام از این گلوله‌ها به تنهایی جان مهره را صفر یا منفی کنند. ** بعد از آن تمام مهره‌هایی که مرده‌اند از بازی حذف می‌شوند. سپس افزونه‌ها و بمب‌هایی که در آن ثانیه باید به زمین بازی اضافه شود، اضافه می‌شود. سپس تمام بمب‌هایی که در حال حاضر با یک مهره در یک خانه قرار دارد، می‌ترکد. ** دوباره در این مرحله مانند زمان تاثیر گلوله‌ها امکان دارد که چنتا بمب جان یک مهره را کم کنند که در این حالت شما باید تمام آن‌ها را تاثیر داده و سپس آن مهره را از بازی حذف کنید. ** سپس تمام مهره‌هایی که مرده‌اند از بازی حذف می‌شود. و در نهایت تمام مهره‌هایی که با یک افزونه در یک خانه قرار دارند، از افزونه بهره می‌برند و افزونه از آن خانه حذف می‌شود. حال تمام مهره‌هایی که می‌خواهند در این ثانیه جابجا شود به ترتیب از ۱ تا $a + b$ جابجایی‌شان را انجام می‌دهند. سپس دوباره تمام اتفاقات بالا(غیر از اضافه شدن بمب‌ها و افزونه‌ها) به همان ترتیبی که در بالا گفته شد انجام می‌شود. # زیرمسئله‌ها این سوال شامل سه زیرمسئله می‌باشد: ۱- اولین مورد که شامل «۲۰۰» امتیاز بوده و فقط شامل بند‌های ۱ تا ۶ بازی می‌شود؛ یعنی بند‌های ۷ و ۸ و تمام موارد مربوط به این دو بند را در نظر نگرفته و بازی را بنویسید. ** ورودی نیز شامل افزونه و بمب نیست؛ یعنی هیچ درخواستی مبنی بر اضافه کردن یک افزونه و یا بمب در آن نیامده است. ** ۳- دومین زیر مسئله «۳۰۰» امتیاز دارد و شامل موارد ۱ تا ۷ می‌شود؛‌ یعنی در ورودی هیچ بمبی وجود نخواهد داشت. ۴- سومین زیر مسئله که «۴۰۰» امتیاز دارد و شامل کل بازی می‌شود؛ با تمام بند‌ها و جزئیات آن. # ورودی در خط اول ورودی دو عدد $n$ و $m$ و $a$ و $b$ آمده است که به ترتیب نمایانگر تعداد سطر‌ها و ستون‌های جدول، تعداد مهره‌های تیم اول و تعداد مهره‌های تیم دوم می‌باشد. در $ a + b $ خط بعدی، در خط $i$،‌ دو عدد $x_i$ و $y_i$ آمده است که نمایانگر مختصات اولیه‌ی مهره‌ی $i$ ام می‌باشد. مهره‌های با شمار‌ه‌ی ۱ تا $a$ متعلق به تیم اول و مهره‌های با شماره‌ی ‌$a + 1$ تا $b$ متعلق به تیم دوم می‌باشد. در $ a + b $ خط بعدی، در خط $i$،‌ دو عدد $h_i$ و $d_i$ آمده است که به ترتیب نمایانگر پارامتر جان و پارامتر قدرت مهره‌ی $i$ ام می‌باشد. مهره‌های با شمار‌ه‌ی ۱ تا $a$ متعلق به تیم اول و مهره‌های با شماره‌ی ‌$a + 1$ تا $b$ متعلق به تیم دوم می‌باشد. در خط بعدی عدد $t$ آمده است که نمایانگر مدت زمان بازی به ثانیه می‌باشد. بازی از زمان ۰ شروع به کار می‌کند و در آخر ثانیه‌‌ی $t$ تمام می‌شود. سپس در خط بعدی $q$ آمده است که نمایانگر تعداد تغییرهای کل بازی می‌باشد. در $q$ خط بعدی، در هر خط یک تغییر به این صورت آمده است: ابتدا $T$ می‌آید که نمایانگر این است که در چه ثانیه‌ای باید این تغییر تاثیر داده شود. تضمین می‌شود که ابتدا تغییرهای مربوط به ثانیه‌ی ۱، سپس ثانیه‌ی ۲ و... می‌آید؛ یعنی تغییرها به ترتیب زمانی می‌آیند. سپس عدد $p$ می‌آید که نمایانگر نوع تغییر است. اگر تغییر از نوع اول باشد،($p$ = 1) در ادامه‌ی خط یک عدد $i$ می‌آید که نمایانگر مهره‌ای است که باید حرکت کند. سپس با یک فاصله یک کاراکتر $d$ می‌آید که نمایانگر جهتی است که مهره‌ی $i$ می‌خواهد حرکت کند. اگر $d$ برابر با `L` یا `D` یا `R` و یا `U` باشد، به ترتیب نمایانگر این است که مهره می‌خواهد به سمت چپ، پایین، راست و بالا برود. اگر تغییر از نوع دوم باشد،($p$ = 2) در ادامه‌ی خط یک عدد $i$ می‌آید که نمایانگر مهره‌ای است که می‌خواهد تیر بزند. سپس با یک فاصله یک کاراکتر $d$ می‌آید که نمایانگر جهتی است که مهره‌ی $i$ می‌خواهد تیر بزند. اگر $d$ برابر با `L` یا `D` یا `R` و یا `U` باشد، به ترتیب نمایانگر این است که مهره می‌خواهد به سمت چپ، پایین، راست و بالا تیر بزند. اگر تغییر از نوع سوم باشد،($p$ = 3) ابتدا یک عدد $j$ می‌آید که نمایانگر نوع افزونه است. اگر $j$ برابر با ۱ بود، افزونه از نوع جانی و گرنه از نوع قدرتی می‌باشد. سپس با یک فاصله عدد $s$ می‌آید که نمایانگر پارامتر تغییر افزونه می‌باشد. در نهایت دو عدد می‌آید که نمایانگر مختصات افزونه هستند. اگر تغییر از نوع چهارم باشد،($p$ = 4) ابتدا یک عدد $g$ می‌آید که نمایانگر پارامتر قدرت بمب می‌باشد و سپس دو عدد می‌آید که نمایانگر مختصات بمب هستند. تضمین می‌شود که مختصات داخل ورودی حتما در زمین بازی است. همچنین مکان اولیه‌ی مهره‌ها دو به دو متمایز می‌باشد. همچنین در اول بازی هیچ افزونه‌ و بمبی در جدول بازی وجود ندارد. **‌ دقت کنید که در هر لحظه می‌تواند در هر خانه به تعداد دلخواه بمب و افزونه وجود داشته باشد.** $$ 5 \le n, m \le 12 $$ $$ 1 \le a, b \le 10 $$ $$ 1 \le x_i \le n $$ $$ 1 \le y_i \le m $$ $$ 3 \le h_i \le 20 $$ $$ 1 \le d_i \le 5 $$ $$ 2 \le t \le 1\ 000 $$ $$ 1 \le q \le 5\ 000 $$ $$ 1 \le T \le t $$ $$ 1 \le p \le 4 $$ $$ 1 \le i \le a + b $$ $$ 1 \le j \le 2 $$ $$ 1 \le s \le 5 $$ $$ 1 \le g \le 5 $$ # خروجی در تنها سطر خروجی امتیاز تیم اول و امتیاز تیم دوم را خروجی دهید. # مثال ## ورودی نمونه ۱ (مثالی از زیر مسئله‌ی اول) ``` 5 8 1 1 1 1 1 8 6 1 6 1 10 6 1 2 1 R 2 2 1 R 3 2 1 R 4 2 1 R 5 2 1 R 6 2 1 R ``` ## خروجی نمونه ۱ (مثالی از زیر مسئله‌ی اول) ``` 0 0 ``` ## ورودی نمونه ۲ (مثالی از زیر مسئله‌ی دوم) ``` 5 8 1 1 1 1 1 8 6 1 6 1 10 7 1 3 2 5 1 1 1 2 1 R 2 2 1 R 3 2 1 R 4 2 1 R 5 2 1 R 6 2 1 R ``` ## خروجی نمونه ۲ (مثالی از زیر مسئله‌ی دوم) ``` 11 0 ``` ## ورودی نمونه ۳ (مثالی از زیر مسئله‌ی سوم) ``` 8 8 5 5 7 8 5 2 3 6 7 2 1 2 4 1 1 8 7 7 5 5 2 8 4 3 4 3 4 3 4 3 3 3 4 3 4 3 4 3 4 3 4 3 10 12 1 4 4 5 4 1 3 1 2 5 6 2 1 5 D 2 2 5 R 2 1 9 R 2 2 2 U 3 1 9 L 3 1 6 R 3 2 5 R 4 1 9 L 4 2 1 U 4 2 6 D ``` ## خروجی نمونه ۳ (مثالی از زیر مسئله‌ی سوم) ``` 10 11 ```

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