- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
این یک سوال آمار و احتمال است، ولی شما باید روشی الگوریتمی برای حل آن بیابید و برنامه‌ی روشتان را پیاده‌سازی کنید!
فرض کنید تابع rand8 تابعی است که هر بار صدایش می‌کنیم، با احتمال برابر، یک عدد صحیح بین ۰ تا ۷ خروجی می‌دهد. می‌خواهیم تابع rand11 را با استفاده از rand8 بسازیم طوری که با احتمال برابر، یک عدد صحیح بین ۰ تا ۱۰ خروجی دهد. روش ساخت باید کاملا قطعی و غیراحتمالاتی باشد.
نحوه پیاده‌سازی و سامانه داوری
برنامه‌ی شما باید ورودی را از ورودی استاندارد دریافت کند و در خروجی استاندارد بنویسد.
برنامه‌ی شما ابتدا یک عدد $t$ دریافت می‌کند که یعنی برنامه‌ی شما باید $t$ بار مستقل از هم مسئله را حل کند، که در هر بار قرار است با داشتن خروجی ۱۰۰ بار صدا کردن یک تابع ثابتrand8، یک عدد تصادفی با تابع rand11 تولید شود. توجه کنید در دفعات مختلف، ممکن است تابع rand8 رفتارهای مختلف داشته باشد و برنامه‌ی شما باید با توجه به رفتار آن خروجی دهد.
مثلا اگر $t=4$، یعنی ۴ تابع بعنوان rand8 داریم. سپس به ترتیب، خروجی ۱۰۰ بار اجرای هریک از این توابع در ورودی شما آمده است (مجموعا ۴۰۰ عدد). سپس شما باید ۴ عدد خروجی دهید که هر یک از آن‌ها، خروجی تابع rand11 شما با توجه به مقادیر دریافتی است.
توجه کنید که الگوریتم تابع rand11 شما نباید در $t$ تست مختلف تفاوت کند؛ شما باید یک تابع طراحی کنید و بر اساس همان همه‌ی تست‌ها را پاسخ دهید. اما ممکن است تابع rand8 در تست‌های مختلف متفاوت رفتار کند، و حتی گاهی اوقات اشتباه کار کند! اگر تابع rand8 اشتباه باشد و احتمال اعداد خروجی‌اش برابر نباشد، لزومی ندارد توزیع اعداد خروجی شما درست باشد. سامانه‌ی داوری با دادن توابع rand8 مختلف، قطعی و غیر احتمالاتی بودن روش شما را می‌سنجد.
ورودی
در خط اول ورودی مقدار $t$ آمده است. سپس در $t$ خط بعدی، در هر خط ۱۰۰ عدد بین ۰ تا ۷ آمده است هر خط خروجی‌های یک تابع rand8 است.
$$1 \le t \le 2\ 000$$
خروجی
در $t$ سطر مقادیر خروجی تابع rand11 طراح شده به ازای هر یک از rand8ها را چاپ کنید.
توجه کنید که خروجی این سوال یکتا نیست و خروجی درست در این سوال معنا ندارد؛ سامانه‌ی داوری با توجه به رفتار برنامه‌ی شما با توجه به خروجی‌های مختلف، درست بودن روشتان را می‌سنجد.
مثال
ورودی نمونه را از اینجا دانلود کنید
خروجی نمونه را از اینجا دانلود کنید
ارسال پاسخ برای این سؤال