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

برای تعریف یک درخت، یک رشته‌ی پرانتز بندی شده متناظر با آن در ورودی آمده است. رشته‌ی تعریف درخت از قوانین زیر پیروی می‌کند:

توضیح: در فایل ورودی برای هر درخت عبارتی متناظر یک $Definition$ آمده است. عبارت اول در جدول بالا نشان می‌دهد که یک $Definition$ به این صورت است که نخست یک $Identifier$ می‌آید سپس علامت مساوی می‌آید وسپس یک رشته‌ی متناظر $RealTree$ می‌آید. رشته‌ی متناظر $RealTree$ به این صورت است که یک پرانتز باز در اول و یک پرانتز بسته در آخر دارد و در وسط رشته‌ای متناظر $Tree^+$ یعنی تعدادی ناصفر از رشته‌های متناظر $Tree$ دارد که بین هر دوتای متوالی حداقل یک فاصله وجود دارد. یک $RealTree$ در حقیقت یک درخت با یک ریشه است که $Tree$ هایی که در داخل پرانتز اصلی آن می‌آیند متناظر فرزندان ریشه‌ی درخت هستند که هر کدام خود یک درخت هستند. $Tree$ هم در حقیقت یک درخت است با این تفاوت که لازم نیست ریشه‌ی آن فرزندی داشته باشد. هر رشته‌ی متناظر $Tree$ یک از سه حالت زیر را دارد:

• به صورت یک $Identifier$ است که متناظر درخت با آن $Identifier$ استکه در تعاریف آمده است.
• به صورت یک $Integer$ است که متناظر یک درخت تک راسی با مقدار امتیاز آن $Integer$ است (به عبارت دیگر متناظر یک برگ درخت اصلی است).
• به این صورت که یک رشته است که یک پرانتز باز و یک پرانتز بسته در اول و آخر دارد و تعداد ناصفری از رشته‌های متناظر $Tree$ در وسط آن می‌آید که بین هر دوتا از آن‌ها حداقل یک فاصله می‌آید و در این حالت متناظر درخت با یک ریشه است که فرزندان آن ریشه $Tree$ های درون پرانتزگذاری اصلی هستند.

یک $Identifier$ یکی از حروف کوچک انگلیسی است و یک درخت را مشخص می‌کند که تعریفش در مجموعه‌ی تعاریف موجود است و $Integer$ متناظر یک عدد از نوع داده‌گونه‌ی $Integer$ است که یک درخت تک‌راسی با امتیاز متناظر آن $Integer$ را مشخص می‌کند.

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

با توجه به تعریف امید ریاضی برای درخت‌های نامتناهی که به احتمال ۱ بازی در آن‌ها پایان می‌پذیرد، هم می‌توان با تقریب دلخواه امید ریاضی را به دست آورد. توجه دارید که در درخت $T$ به احتمال ۱ بازی در آن پایان می‌یابد، اگر و فقط اگر به ازای هر راس میانی آن یک برگ موجود باشد که در زیر درخت به ریشه‌ی آن راس میانی قرار داشته باشد.

در خط اول فایل ورودی $n$، تعداد درخت‌های تعریف شده در این فایل آمده است. در $n$ خط بعدی در هر خط تعریف متناظر یک درخت آمده است. در این تعاریف مقادیر $Identifier$ ها برابر $n$ حرف کوچک اول الفبای انگلیسی است. تعریف هر درخت در یک متغیر $String$ جا می‌شود.

در هر خط فایل خروجی عدد متناظر امید ریاضی یک درخت با همان ترتیبی که درخت‌ها در ورودی تعریف شده‌اند، می‌آید. هر عدد باید دقیقا تا ۳ رقم اعشار در خروجی ظاهر شود (به صورت $Write(r:0:3);$). در صورتی که بازی با احتمال ۱ پایان نمی‌یابد.، به جای عدد امید ریاضی آن در فایل عدد -۱۳ می‌آید.

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