====== Line Fiting ======

خوراندن (یا برازش) یک تابع به یک مجموعه از نقاط نمونه‌برداری شده از یک تابع نامشخص ‎$\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'' خاتمه می‌یابد که نیازی به پردازش آن نیست.

===== خروجی =====

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


===== محدودیت‌ها =====

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

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|2 \\ 0 2 0 1 50 50 \\ 1 2 0 1 50 50 \\ 0 | 0.5|
</WRAP>


<پاسخ>
منتظر پر کردن این قسمت توسط علاقمندان هستیم.
</پاسخ>

  * [[J|سوال قبل]]