Processing math: 16%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۸:سوال ۳

Triangle

یک دمجموعه‌ی ‎A‎ از اعداد طبیعی داده شده است. زیرمجموعه‌ی ‎TA‎ زیرمجموعه‌ی ‎TA‎ را ‎«مثلثی»‎ می‌گوییم اگر برای هر سه عنصر متفاوت (ولی نه لزوما نامساوی) ‎x,y,zT‎ رابطه‌ی زیر برقرار باشد: ‎ x+y>z‎, ‎\ x+z>y‎, \ ‎\text{and} \ ‎y+z>x‎ برنامه‌ای بنویسید تا با دریافت اعداد موجود در ‎A‎، بزرگ‌ترین زیرمجموعه‌ی مثلثی A (یعنی زیرمجموعه‌ای با بیش‌ترین تعداد عضو) را به‌دست آورد. (مجموعه ‎A‎ و زیر مجموعه‌هایش می‌توانند عضو تکراری داشته باشند.)‎‎

ورودی

  • در سطر اول ‎n‎ آمده است.
  • در ‎n‎ سطر بعد اعداد موجود در ‎A‎ به این صورت آمده است: در سطر ‎i،‎ام سه عدد ‎s_{i} \ t_{i} \ k_{i}‎ آمده، به این معنی که همه اعداد s_{i}+j \times t_{i} (0 \leq j < k)‎ عضو ‎A‎ هستند.
  • تمام اعداد ورودی صحیح می باشند.
  • 1\leq n\leq 100‎ و ‎1\leq \Sigma k_{i} \leq 1000000 (همه اعضای ‎A‎ کوچک‌تر از ‎10^9‎ می‌باشند.)‎

خروجی

در یک سطر دو عدد نوشته شود. عدد اول ‎M‎ تعداد عناصر ‎T‎ که بزرگ‌ترین زیرمجموعه‌ی مثلثی ‎A‎ است و عدد دوم مجموع عناصر موجود در ‎T‎. اگر بیش از یک زیرمجموعه مثلثی با ‎M‎ عنصر وجود داشت عدد مربوط به مجموعه‌ای که جمع عناصرش کم‌ترین است را بنویسد.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3‎
1 2 10‎
4 2 6‎
3 5 3
10 105

ابزار صفحه