Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۱:گراف:سوال ۱

بازی یال‌ها در گراف

بازی دو نفره «یال‌ها در گراف» به این صورت است:

گراف G با n راس 1,2,,n و بدون یال را در نظر بگیرید. دو بازیکن به ترتیب یکی بعد از دیگری بازی می‌کنند( یک بازیکن در نوبت‌های زوج و دیگری در نوبت‌های فرد) در نوبت i ام بازیکنی که نوبتش است باید یالی از گراف را وصل کند که اختلاف اعداد دو سر آن یال دقیقا ni باشد و با یال‌های قبلی کشیده شده در نوبت‌های قبل دوری در G تشکیل ندهد. بازیکنی که نتواند در نوبتش یالی بکشد بازنده است.

الگوریتمی چند جمله‌ای بر حسب n پیدا کنید که با گرفتن n، برنده‌ی بازی را پیدا کند و به جای او بازی کند.

پاسخ


ابزار صفحه