- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۶۴ مگابایت
پس از رمزگشایی دفترچه خاطرات رستم، مشخص شد که پس از خوان هفتم و کشته شدن دیو سپید به دست رستم، رستم و سپاهش برای استراحت به سینما رفته‌اند.
چینش صندلی‌های سینما به صورت یک جدول $n \times n$ است و بعضی از صندلی‌ها خراب است. رستم و سپاهش وارد سینما شدند و روی صندلی‌های سالم نشستند. تعداد صندلی‌های سالم دقیقاً به تعداد سربازان بود...
در هنگام پخش فیلم، هریک از سربازان در هر زمان، نسبت به فیلم در یکی از ۳ وضعیت زیر قرار داشت:
- بیخیال
- متعجب (باخیال)
- سؤال‌دار (باخیال)
اگر سربازان متعجب را با علامت !، سربازان سؤال‌دار را با ?، سربازان بیخیال را با _ (underline) و صندلی‌های خراب را با # نمایش دهیم، یک وضعیت از سربازان در سینما می‌تواند به این صورت باشد:
????___?
##_???_?
!!??#_??
!#__????
____!!!!
!!!___!!
_!!!!!!#
!!!?????
مدت فیلم ۱۰۰۰ ثانیه بود. در طول پخش فیلم، سربازان در مورد فیلم با سربازان مجاور حرف می‌زدند و وضعیت سربازان در هر ثانیه نسبت به ثانیه قبل طبق قوانین زیر تغییر می‌کرد.
- دو سرباز، مجاور محسوب می‌شوند اگر در جدول $n \times n$، صندلی‌های آن‌ها در یک ضلع یا رأس، مشترک باشند. پس هر یک از صندلی‌های میانی سینما، ٨ صندلی مجاور دارد و هریک از ۴ صندلی گوشه‌ی سینما، ٣ صندلی مجاور دارد.
- اگر در میان سربازان مجاور یک سرباز بیخیال، دقیقاً ۳ سرباز باخیال وجود داشته باشد، در ثانیه بعد، این سرباز نیز باخیال می‌شود (اگر اکثریت ۳ سرباز مجاور متعجب بودند، او نیز متعجب می‌شود و اگر اکثریت سؤال‌دار بودند، او نیز سؤال‌دار می‌شود.)
- اگر در میان سربازان مجاور یک سرباز باخیال، کمتر از ۲ یا بیشتر از ۳ سرباز باخیال وجود داشته باشد، آن سرباز در ثانیه‌ی بعد بیخیال می‌شود.
- اگر در میان سربازان مجاور یک سرباز متعجب، ۲ یا ۳ سرباز باخیال وجود داشته باشد، و در بین آن ۲ یا ۳ سرباز باخیال، تعداد سؤال‌دارها بیشتر از متعجب‌ها باشد، آن سرباز در ثانیه بعد سؤال‌دار می‌شود.
- اگر در میان سربازان مجاور یک سرباز سؤال‌دار، ۲ یا ۳ سرباز باخیال وجود داشته باشد، و در بین آن ۲ یا ۳ سرباز باخیال، تعداد متعجب‌ها بیشتر از سؤال‌دارها باشد، آن سرباز در ثانیه بعد متعجب می‌شود.
- اگر برای یک سرباز در یک مرحله هیچ یک از اتفاقات بالا نیفتاد، وضعیت آن سرباز نسبت به فیلم در ثانیه بعد تغییر نمی‌کند.
وضعیت سربازان را در شروع فیلم می‌دانیم. می‌خواهیم بدانیم در پایان فیلم (یعنی بعد از ۱۰۰۰ ثانیه) چه تعداد سرباز متعجب و چه تعداد سرباز سؤال‌دار هستند.
ورودی
برنامه باید در ابتدا عدد $n$ را بخواند و سپس نقشه‌ی اولیه‌ی سینما را که به صورت یک جدول $n \times n$ است، بخواند. $n$ حداکثر ۵٠ خواهد بود. پس یک آرایه ۵٠ × ۵٠ برای ذخیره جدول کافی است.
خروجی
در خط اول خروجی تعداد سربازان سؤال‌دار و در خط بعدی تعداد سربازان متعجب در انتهای فیلم را بنویسید.
مثال
ورودی نمونه ۱
8
????___?
##_???_?
!!??#_??
!#__????
____!!!!
!!!___!!
_!!!!!!#
!!!?????
خروجی نمونه ۱
4
0
ورودی نمونه ۲
30
??_???_?_?_?_#?_????_?____??__
_?__?_???_?_?#???__?_??_?_????
__???___???__#________________
________???__##!!!!!____?_____
________???__#________________
_____________#________________
_____________??_______________
______________________________
______________________________
______!!!!!____________??????_
______________________________
___________!?!?!?!?!!!________
_____######____#########______
________#_??????!!!!??________
________#_____________________
________#___________?!?!?!?!__
______________________________
_____________________________?
____________________________??
____!!!_______________#######?
____________________________??
_____________________________?
______________________________
____________________!!_!!_____
______________________________
______________!_______________
####_______#!!!!!_____________
#__!_!!!_!!!!!!!!!!!!_!!!_!___
#_!!!!!!!!!!!!!!!!!!!!!!!!!!__
#############!!!!!!!!!!!!!!!!_
خروجی نمونه ۲
9
19
مثالی از وضعیت سربازان در ۱۰۰۰ مرحله
در شروع فیلم:
????___?
##_???_?
!!??#_??
!#__????
____!!!!
!!!___!!
_!!!!!!#
!!!?????
ثانیه ۱:
_???__?_
##___?_?
!!?_#___
!#?_____
!__!?___
!_______
_______#
!______?
ثانیه ۲:
__?___?_
##_?__?_
!_?_#___
!#!_____
!__?____
________
_______#
________
ثانیه ۳:
________
##??____
__??#___
!#??____
_!______
________
_______#
________
ثانیه ۴:
________
##??____
____#___
_#_?____
_!?_____
________
_______#
________
ثانیه ۵:
________
##______
__??#___
_#?_____
__?_____
________
_______#
________
ثانیه ۶:
________
##______
__??#___
_#?_____
________
________
_______#
________
در ثانیه ۷ تا ۱۰۰۰ (تا پایان فیلم) وضعیت سربازان به این شکل ثابت است:
________
##______
__??#___
_#??____
________
________
_______#
________
ارسال پاسخ برای این سؤال