Processing math: 26%

المپدیا

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

ابزار کاربر

ابزار سایت


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

Party

n‎ نفر با شماره‌های ‎0‎ تا ‎n1‎ به ترتیب دور یک میز نشسته‌اند. شماره نفر سمت راست فرد ‎i‎ام، ‎i+1‎ و شماره نفر سمت چپ وی، ‎i1‎ است. (شماره نفر سمت راست فرد ‎n1‎، ‎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

ابزار صفحه