خوراندن (یا برازش) یک تابع به یک مجموعه از نقاط نمونه‌برداری شده از یک تابع نامشخص ‎$\mathrm{F}:\mathbb{R} \rightarrow \mathbb{R}$ یکی از مسائل پایه‌ای در ریاضیات است. یک نوع رایج، برازش نقاط با استفاده از بهترین تابع خطی $\overline{\mathrm{F}}$ است. یک معیار برای تعیین میزان خوبی یک تابع $\overline{\mathrm{F}}$ بدین‌گونه تعریف می‌شود. فرض کنید تابع $\mathrm{F}$ در نقاط $x_1<\ldots<x_n$‎ نمونه‌گیری شده است. خطای تابع $\overline{\mathrm{F}}$ بصورت زیر تعریف می‌شود:

$$\text{error}(\mathrm{F},\overline{\mathrm{F}}) = \max_{‎1\leq i\leq n} (|\mathrm{F}(x_i)-\overline{\mathrm{F}}(x_i)|)$$‎

بدیهی است تابعی بهتر است که خطای آن کم‌تر باشد. متاسفانه مقدار دقیق تابع $\mathrm{F}$ معلوم نیست. در عوض، تابع $\mathrm{F}$ بصورت احتمالی در دسترس است به این معنی که مقدار تابع در نقطه $x_i$ یکی از مقادیر $y_{i,1},\dots,y_{i,m_i}$‎ به ترتیب با احتمال‌های $p_{i,1},\dots, p_{i,m_i}$ است؛ به عبارت دقیق‌تر $\mathbf{Pr}[\mathrm{F}(x_i)=y_{i,j}] = p_{i,j}$. حال با توحه به مفهوم امیدریاضی خطا بصورت زیر قابل تعریف است. $$\text{error}(\mathrm{F},\overline{\mathrm{F}}) = \max_{‎1\leq i\leq n} \mathbf{E}[|\mathrm{F}(x_i)-\overline{\mathrm{F}}(x_i)|]$$‎

حال هدف پیدا کردن تابع خطی $\overline{\mathrm{F}}= ax+b$ است که خطا کمینه شود. شما باید برنامه‌ای بنویسد که نقاط نمونه همراه با احتمال‌شان را از ورودی دریافت کند و خطای کمینه را محاسبه کند.

ورودی شامل چند سناریو است. خط اول هر سناریو شامل $n$ تعداد نقاط نمونه‌برداردی شده است. سپس اطلاعات مربوط به نقاط در $n$ خط (بصورت صعودی) می‌آید. خط $i$ام مربوط به نقطه $i$ام است. در این خط ابتدا $x_i$ (مختصاتی که در آن از تابع نمونه‌برداری شده) و $m_i$ (اندازه تابع توزیع احتمالات) ظاهر می‌شوند. در ادامه این خط یک لیست شامل $m_i$ عدد غیرمنفی صحیح کوجک‌تر از $10^9$ می‌آید که نشان دهنده مقدار تابع $\mathrm{F}$ در $x_i$ است. در نهایت در انتهای خط یک لیست $m_i$ تایی از احتمال‌ها ظاهر می‌شود. برای سادگی می‌توانید فرض کنید هر احتمال $p$ یک عدد غیرمنفی صحیح نابزرگ‌تر از $100$ است. احتمال واقعی با تقسیم $p$ بر $100$ بدست می‌آید. تضمین می‌شود جمع احتمال‌های داده شده برابر $100$ است. ورودی با 0 خاتمه می‌یابد که نیازی به پردازش آن نیست.

به ازای هر سناریو، در یک خط خطای کمینه را با دقیقا یک رقم اعشار چاپ کنید.

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

• سوال قبل