المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۴:تئوری:سوال ۹

روند اداری

در شرکت $LiHa$ کلیه‌ي اطلاعات به وسیله‌ی کارت پانچ منتقل می‌شود. کلیه‌ی کارت پانچ‌ها دارای $n$ مکان می‌باشند که می‌توان آن‌ها را سوراخ کرد یا دست نخورده نگه داشت.

روند اداری در این شرکت به این شکل استکه به هر ارباب رجوعی که مراجعه می‌کند، یک کارت پانچ داده می‌شود. ارباب رجوع نخست به آقای نامیا مراجعه می‌کند. آقای نامیا عددی به این ارباب رجوع نسبت می‌دهد و آن را بر روی کارت پانچ او به صورت خاصی نمایش می‌دهد. سپس ارباب رجوع به بخش بازرسی‌های اداری می‌رود و این بخش دوباره کار ارباب رجوع را بررسی می‌کنند و ممکن است بخواهند عددی را که بر روی کارت پانچ نوشته شده تغییر بدهند، در حالی که نمی‌توانند مکان‌هایی که قبلا سوراخ شده را پر بکنند. ارباب رجوع بعد از کلیه‌ی این کارها کارت خود را تحویل شهرداری می‌دهد.

می‌خواهیم به آقای نامیا و مسئول بازرسی‌های اداری و مسئول شهرداری روش‌هایی برای سوراخ کردن کارت‌ها یاد بدهیم به صورتی که بعد از عملیات، شهرداری بتواند با دیدن کارت پانچ، آخرین عددی که روی آن حک شده را تشخیص بدهد. توجه کنید که لزومی ندارد نمایش اعداد به صورت نمایش باینری‌‌شان که به صورت معمول به کار می‌رود باشد.

فرض کنید کارت پانچ $2t-1$ مکان برای سوراخ شدن دارد و همچنین اعدادی که باید روی کارت نوشته شوند $2^t-1$ عدد هستند. روشی برای این کار ارئه دهید.


ابزار صفحه