المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:عملی:سوال ۷

تخصیص ثبات به متغیرها در حلقه

در یک حلقه در برنامه‌ای از $v$ متغیر استفاده شده است. این حلقه شامل $n$ خط از برنامه که با شماره خط‌های 0 تا $n-1$ مشخص می‌شوند است.

متغیر $i$ ام این حلقه مقداردهی شده است و از مقدار آن در طی $d_i$ خط بعدی استفاده شده است. پس از این $d_i$ خط، دیگر نیازی به مقدار این متغیر نداریم.

کامپیوتری که قرار است این برنامه روی آن اجرا شود دارای $k$ ثبات است. $(k<10)$ برای سریع‌تر شدن اجرای برنامه باید مقدار متغیرهای برنامه را در ثبات‌ها ثبت کنیم.

مسئله به این صورت است: برنامه‌ای بنویسید که با دریافت داده‌های فوق، مشخص کند که مقدار هر یک از متغیرها را باید در کدام یک از ثبات‌ها ثبت کنیم به طوری که هیچ دو متغیری که از آن‌ها در یک خط برنامه استفاده می‌شود، از یک ثبات استفاده نکنند. به عبارت دیگر اگر دو متغیر $i$ و $j$ در یک ثبات ذخیره شده باشند و $s_i\leq s_j$ باشد، آن‌گاه:

$$s_i+d_i<s_j \quad \& \quad s_j+d_j-n< s_i$$

ورودی

در سطر اول فایل ورودی عددهای $v$، $n$ و $k$ و در $v$ سطر بعدی $s_i$ ها و $d_i$ ها نوشته شده است. فرض کنید که $v<50$ است.

خروجی

خروجی را مانند مثال زیر در فایل خروجی بنویسید. (در صورتی که مسئله جواب ندارد، پیغام NO Solution را در این فایل چاپ کنید.)

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

ورودي نمونه خروجي نمونه
4 10 3
0 5
1 6
6 6
8 2
Variable 1 in register 1‎
Variable 2 in register 2
Variable 3 in register 3
Variable 4 in register 4

ابزار صفحه