المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۳:عملی:سوال ۲

پیش‌گویی

یکی از درس‌های مدرسه جادویی هاگوارتر درس پیش‌گویی می‌باشد. در یکی از تمرین‌های عملی این درس که در سایت برگزار می‌شود. خانم ماریا، استاد این درس، از دانش‌آموزان خواسته که وضعیت خانه‌های بازی زندگی را پیش‌گویی کنند. این بازی بر روی یک صفحه شطرنجی نامتناهی برگزار می‌شود. خانه‌های آن دارای دو وضعیت زنده و مرده هستند. وضعیت اولیه بازی در زمان صفر داده می‌شود. پس از آن وضعیت خانه‌ها مطابق برنامه زیر تغییر می‌کند:

**اگر یک خانه در زمان $t$ زنده باشد و بیش‌تر از ۳ خانه‌‌ی مجاورش زنده باشد در زمان $t+1$ می‌میرد. اگر یک خانه در زمان $t$ مرده باشد و دقیقا ۳ تا از خانه‌ی مجاورش زنده باشد، در زمان $t+1$ زنده می‌شود.(دقت کنید دو خانه مجاورند اگر حداقل در یک راس مشترک باشند.)

ورودی

در سطر اول فایل ورودی عدد $n$ و در $n$ سطر بعد هر کدام یک زوج عدد صحیح(مختصات یک خانه) می‌باشد که نشان می‌دهد این خانه در زمان $t=0$ زنده می‌باشد. در سطر بعدی عدد $m$ و در $m$ سطر بعد هر کدام سه عدد صحیح ( دو تای اول مختصات یک خانه و سومی زمان داده شده) می‌باشد.(تمام اعداد ورودی صحیح نامنفی و کوچک‌تر از ۱۰۰ می‌باشند.)

خروجی

فایل خروجی شامل $m$ سطر می‌باشد. که در هر سطر یکی از حروف $D$ یا $L$ را نوشته‌اید که به ترتیب نمایشگر مرده یا زنده بودن خانه متناظر در زمان مربوطه می‌باشد.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3
1 1
1 2
1 3
2
2 2 2
1 1 4
D
L

ابزار صفحه