المپدیا

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

ابزار کاربر

ابزار سایت


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

کلیک

گراف $G$، $n$ راس و $m$ یال دارد. این گراف طوقه ندارد(یعنی رئوس دو سر هیچ یالی یکی نیست) و بین هر دو راسی حداکثر یک یال وجود دارد. به عبارت دیگر $G$‌ساده است. رئوس $G$ با اعداد ۰ تا $n-1$ (شامل این دو عدد) شماره‌گذاری شده‌اند. روی هر یال $G$‌یک عدد صحیح بین ۰ تا $k-1$‌نوشته شده است. شما به قسمتی از اطلاعات این گراف از طریق یک کتاب‌خانه دسترسی دارید و می‌توانید اعداد یال‌های این گراف را به نحوی خاص که توضیح داده خواهد شد عوض کنید. در این‌ کتاب‌خانه سه تابع به نام‌های lib N، lib K و click جهت کسب اطلاعات از گراف و ایجاد تغییر در آن در نظر گرفته شده‌اند. تابع $libN() و libK() بع ترتیب $n$ و $k$ را برمی‌گردانند. تابع click(i) روی راس $i$ کلیک می‌کند. با این عمل یک واحد بع اعداد روی یال‌های متصل به راس $i$ اضافه می‌شود به جز یال‌های با شماره‌ی $k-1$ که تبدیل به صفر می‌شوند (از ۰ به ۱، از ۱ به ۲، ...، از $k-1$ به ۰). تعداد یال‌هایی که پس از انجام این عمل صفر می‌شوند به عنوان خروجی تابع برگردانده می‌شود. زمان اجرای تابع click(i) متناسب با تعداد یال‌های متصل به راس $i$ است. به عبارت دیگر این تابع در زمان $\Theta (d_i)$ اجرا می‌شود که $d_i$ درجه‌ی راس $i$ام است.

گراف‌های ورودی در کتاب‌خانه نهفته شده‌اند و برنامه‌ی شما از ورودی چیزی نمی‌خواند. یازده عدد گراف ورودی در کتاب‌خانه با شماره‌های ۰ تا ۱۰ طراحی شده‌اند. برای بارگذاری تست $t$ام باید از تابع reset(t) استفاده کنید.

هدف در این مسئله این است که شما با استفاده از کتاب‌خانه‌ای که در اختیارتان گذاشته شده یال‌های هر یک از یازده گرف و اعدادی که در ابتدا روی این یال‌ها قرار داشته را به‌دست آورید. توجه کنید که تابع click اعداد روی بعضی یال‌ها را از حالت اولیه تغیییر می‌دهد.

از شما انتظار میٰ‌رود در نهایت ادب و نزاکت، خروجی خواسته شده را در یازده فایل خروجی با نام‌های click0.out،…،click10.out قرار داده و همه‌ی این فایل‌ها را در یک پوشه با نام click‌ قرار داده، سپس پوشه را فشرده کرده و فایل click.zip یا click.tgz را ارسال کنید. در صورتی که فقط فایل بعضی از تست‌ها در فرسته‌ی شما باشد، داوری فقط برای همان تست‌ها انجام می‌شود.

برای دیدن جزئیات بیش‌تری از توابع کتاب‌خانه به قسمت «کتاب‌خانه» در صورت مسئله توجه کنید.

برنامه‌ای بنویسید که:

  • تست مورد نظر را بارگذاری کند و $n$ و $k$ را از کتاب‌خانه پیوندی بگیرد.
  • با استفاده از کتاب‌خانه پیوندی یال‌های گراف واعدادی که در ابتدا روی آن‌ها قرار دارند را پیدا کند.
  • مشخصات گراف اولیه را در فایل مربوطه ذخیره کند.

ورودی

خروجی

محدودیت‌ها

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

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

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

ابزار صفحه