به‌مناسب نیمه شعبان، اهالی کوچه‌ی پرستوی هفت (قربانعلی‌زاده‌ی سابق) قصد دارند کوچه را با آویزان کردن تعدادی ریسه چراغانی کنند. برای شبیه‌سازی روشن و خاموش بودن چراغ‌های ریسه‌ها، آن‌ها از نوید (برنامه‌نویس محله!) خواسته‌اند که به‌شان کمک کند. می‌دانیم هر ریسه بین ۶ تا ۶۰ لامپ دارد و تعداد لامپ‌های هر ریسه با بقیه ریسه‌ها ممکن‌ست متفاوت باشد. تعداد ریسه‌ها (که آن را $W$ می‌نامیم) هم عددی نامعلوم است.

نوید ادعا می‌کند که اطلاعات هر ریسه (شامل تعداد لامپ‌ها و وضعیت هر لامپ) را می‌تواند دقیقاً در یک متغیر نگه‌داری کند. دقت کنید که نوید هنوز struct یا مفاهیم مشابه را نخوانده و اطلاعاتش در حد اطلاعاتی هست که در کلاس تدریس شده است.

1. به نظر شما نوید این کار را چگونه انجام می‌دهد؟ توضیح دهید.
2. قطعه کد زیر را برای انجام این کار تکمیل کنید.
3. قطعه کدی بنویسید که با گرفتن متغیر data، مجدداً یک آرایه (حاوی اطلاعات) و یک $n$ (تعداد لامپ‌ها) را پر کند. در
4. واقع این کد معکوس عمل خواسته شده (از نظر ورودی/خروجی) در مرحله قبل را باید انجام دهد.

int a[100];
int n;
X data; //تایپ متغیر مربوطه را بنویسید X به جای
//کد شما برای تیدیل اطلاعات فوق به یک متغیر در این قسمت است

پس از مأموریت یکم، نوید توانست اطلاعات $W$ ریسه را در یک آرایه از تایپ X ذخیره کند. اکنون اهالی محل از نوید می‌خواهند که تابعی بنویسد که یک ریسه (یک متغیر از تایپ X) و یک بازه متوالی از لامپ‌های آن ریسه (نظیر $[u,v]$) و یک متغیر «امر» (به اسم $c$) بگیرد و:

• اگر متغیر امر برابر با صفر بود، همه لامپ‌های شماره $i$ که $u \leq i\leq v$ از ریسه مربوطه، خاموش شوند.
• اگر متغیر امر برابر با یک بود، همه لامپ‌های شماره $i$ که $u\leq i\leq v$ از ریسه مربوطه، روشن شوند.
• اگر متغیر امر برابر با دو بود، همه لامپ‌های شماره $i$ که $u \leq i\leq v$ از ریسه مربوطه، تغییر وضعیت داده شوند (اگر خاموش بوده، روشن و اگر روشن بوده، خاموش بشود).

برای انجام این منظور، به آقا نوید کمک کرده و تابع زیر را تکمیل کنید:

X DoAction(X data, int u, int v, int c) {
	   // ابتدا باید دستور خواسته شده انجام شود و سپس
	   // مقدار جدید اطلاعات باید در قالب یک متغیر X برگردانده شود. 
	
}

نوید مأموریت قبلی را با استفاده از یک حلقه انجام داد (که راه عادی بود). اما از آنجا که تعداد این دستورها زیاد بود، نوید احساس کرد که برنامه را می‌تواند سریع‌تر کند. در واقع در حالت کنونی، اگر حداکثر تعداد لامپ‌های یک ریسه (که گفته‌ایم ۶۰ است) را به‌صورت پارامتریک با $T$ نمایش دهیم، برای اجرای $K$ دستور در بدترین حالت به $O(KT)$ زمان احتیاج داریم و نوید قصد دارد این زمان را بهبود بخشد. برای این منظور نوید مجاز است یک پیش پردازش و یک حافظه عمومی (global) از $O(T)$ داشته باشد. بهترین ایده خود را فقط شرح دهید.

• سوال بعد
• سوال قبل