المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های ای سی ام سایت تهران:دوره ی ۱۵:f

2D-Solar System

منظومه‎ شمسی ‎$ ‎2‎ $‎ بعدی مانند منظومه شمسی ما شامل خورشیدی بزرگ و تعدادی سیاره‌ی دایره‌ای که به دور آن می‌چرخند می‌باشد. ‎‎به خاطر جاذبه زیاد خورشید در این منظومه تمامی سیاره‌ها به سوی آن جذب می‌شوند. در واقع سیاره‌ها در حین چرخش به دور خورشید به آن مماس می‌شوند. همان‌طور که در شکل نشان داده شده است خورشید به اندازه‌ای بزرگ است که سطح بیرونی آن مانند خط به نظر می‌رسد. به طرز عجیبی تا زمان کنونی هیچ دو سیاره‌ای با یکدیگر برخورد نکرده‌اند. با این حال کسی نمی‌داند که در آینده برخوردی رخ خواهد داد یا خیر. شما باید برنامه‌ای بنویسید که احتمال هرگونه برخورد را در آینده بررسی کند و در صورت احتمال وقوع اولین زمان آن را محاسبه کند. دانشمندان ناسا به این نتیجه رسیده‌اند که تمامی سیاره‌ها در این منظومه با سرعت ثابتی در حال حرکت هستند. معادله‌ی حرکت سیاره‌ها را می‌توان با توجه به موقعیت نقطه تماس آن سیاره با سطح خورشید در طول زمان با فرمول ‎$ y‎ =‎ ‎at ‎+ ‎b‎ $‎ که ‎$ ‎a‎ $‎ و ‎$ ‎b‎ $‎ دو پارامتر معین و ‎$ ‎t‎ $‎ بیانگر زمان است‏، نشان داد.

ورودی

  • سناریوهای مختلفی در ورودی به شما داده می‌شود. در خط اول هر سناریو ‎$ n‎‎ ‎(‎0 ‎\leq n ‎\leq 50000‎‎‎)‎ $‎ داده شده است.
  • در ‎$ ‎n‎ $‎ خط بعدی در هر خط ‎$ ‎3‎ $‎ عدد داده شده است.(هر ‎$ ‎3‎ $‎ عدد از ‎$ ‎1000000000‎ $‎ کوچک‌تر هستند.) اولی ‎$ ‎r_{‎i‎}‎ $‎ یک مربع کامل است که شعاع سیاره ‎$ ‎i‎ $‎ است. دو عدد بعدی نیز ‎$ ‎a_{‎i‎}‎ $‎ و ‎$ ‎b_{‎i‎}‎ $‎ ثابت‌های معادله حرکت سیاره ‎‎ ‎‎$ ‎i‎ $‎‎هستند. مکان نقطه تماس سیاره با خورشید در زمان ‎$ ‎t‎ $‎ از رابطه ‎$ ‎a_{‎i}t +‎ ‎b_{‎i}‎‎‎ $‎ به دست می‌آید. ورودی با ‎$ ‎"0"‎ $‎ خاتمه می‌یابد که نباید پردازش گردد.

خروجی

برای هر سناریو زمان اولین برخورد را در یک خط جداگانه چاپ نمایید.(زمان فعلی سیستم صفر فرض کنید‏، تمامی سیاره‌ها در این زمان از یکدیگر جدا هستند.) اگر امکان برخورد در سناریو وجود نداشت ‎$ ‎"Collision-Free ‎System‎"‎ $‎ را چاپ نمایید. خروجی‌ها باید تا دو رقم بعد اعشار رند شوند.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3
1 1 1
4 3 6
9 -7 30
2
4 -1 1
1 1 7
2
1 1 10
1 2 5
0
1.20
Collision-Free System
3.00

ابزار صفحه