المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۸:سوال ۱

Party

‎$n$‎ نفر با شماره‌های ‎$0$‎ تا ‎$n-1$‎ به ترتیب دور یک میز نشسته‌اند. شماره نفر سمت راست فرد ‎$i$‎ام، ‎$i+1$‎ و شماره نفر سمت چپ وی، ‎$i-1$‎ است. (شماره نفر سمت راست فرد ‎$n-1$‎، ‎$0$‎‎ است)

این ‎$n$‎ نفر برای رفتن به یک مهمانی به صورت مخفیانه تصمیم‌گیری می‌کنند. هر نفر تصمیمش را به صورت ‎$1$ (به معنای آمدن) و ‎$0$ (به معنای نیامدن) به یک آدرس ایمیل می‌کند و بعد از اینکه همه ایمیل زدند محتوای ایمیل‌ها خوانده می‌شود.

هر نفر بسته به تصمیم خود و دو نفر کناری‌اش یک امتیاز خوشحالی دارد. مثلا فرد شماره ‎۱۰‎ ممکن است برای حالت ‎$1‎, ‎1‎, ‎0$‎ (یعنی نفر سمت راست ‎$0$‎، و خود فرد و نفر سمت چپ تصمیم ‎$1$‎ را اتخاذ کرده‌اند) امتیاز ‎۲۰‎ و برای بقیه حالات امتیاز ‎۵‎ بدهد. در واقع برای هر نفر ‎۸‎ عدد که متناظر با امتیازهای وی به ‎۸‎ حالت ممکن است را می‌دانیم.

یک حالت همه خوشحال از تصمیم‌ها حالتی است که هیچ یک از افراد نتواند با عوض کردن تصمیمش (از ‎$0$‎ به ‎$1$‎ یا بالعکس ) بدون این‌که هیچ کس دیگری تغییری در تصمیمش دهد امتیاز بهتری بگیرد. مثلاً در مثال قبل اگر حالت تصمیم‌گیری فرد ‎۱۰‎ و اطرافیانش ‎$(1‎, ‎0‎, ‎0)$‎ باشد این فرد میتواند با تغییر تصمیمش به ‎$1$‎ امتیاز بهتری کسب کند (از ‎۵‎ به ‎۲۰‎) در نتیجه خوشحال نیست.

هدف ما این است که با دانستن امتیازهای افراد برای حالات مختلف حداقل یک حالت همه خوشحال (در صورت وجود) پیدا کنیم.

ورودی

  • در خط اول ‎$n$‎، تعداد افراد و در ‎$n$‎ سطر بعدی جداول امتیازی افراد آمده است.
  • در سطر ‎$i+1$‎ جدول‌های امتیازی فرد ‎$i$‎ به ترتیب حالت‌های زیر است: ‎$(0‎, ‎0‎, ‎0)$‎، ‎$(0‎, ‎0‎, ‎1)$‎، ‎$(0‎, ‎1‎, ‎0)$‎، ‎$(0‎, ‎1‎, ‎1)$‎، ‎$(1‎, ‎0‎, ‎0)$‎، ‎$(1‎, ‎0‎, ‎1)$‎، ‎$(1‎, ‎1‎, ‎0)$‎ و ‎$(1‎, ‎1‎, ‎1)$‎. حالت ‎$(z‎, ‎y‎, ‎x)$‎ برای فرد ‎$i$‎ به این معنی است که فرد سمت راستش تصمیم ‎$x$‎، فرد سمت چپ‌ش تصمیم ‎$z$‎ و خود فرد ‎$i$‎ تصمیم ‎$y$‎ را گرفته است.‎
  • ‎$3 \le n \le 10000$‎

خروجی

در صورت وجود نداشتن جواب پیغام ‎No Answer‎ و در غیر این‌صورت در خروجی یک حالت همه خوشحال را در ‎$i$‎ سطر که سطر ‎$i$‎ام شامل تصمیم فرد ‎$i$‎ام (‎$0$‎ یا ‎$1$‎) باشد، بنویسید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3‎
‎1 2 3 4 5 6 7 8‎
8 7 6 5 4 3 2 1‎
4 5 4 6 4 6 5 5
1
0
1

ابزار صفحه