المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۴:سوال ۱۷

شیمیدان فراموش‌کار

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

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

به پروفسور بیچاره کمک کنید و برنامه‌ای بنویسید که با دریافت اطلاعات هر ماده کم‌ترین تعداد ماده‌هایی را که باید پروفسور با خود ببره، به او بگوید.

ورودی

در سطر اول $n$ آمده که تعداد مواد اختراعی پروفسور را نشان می‌دهد؛ $1\leq n \leq 10^5$.

در هر یک از $n$ سطر بعدی مشخصات یک ماده به صورت سه عدد صحیح نامنفی که نمایانگر مقدار مواد اولیه در ۱۰۰ میلی‌لیتر از ماده است، داده شده.

خروجی

در سطر اول کم‌ترین تعداد مواد لازم را بنویسید. در هر سطر دیگر شماره‌ی یکی از مواد را بنویسید.

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

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

100 0 0
50 25 25
0 50 50

2
1
3

ابزار صفحه