المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۶:عملی مقدماتی دوم:سوال ۳

Celery

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

«آقای میسیک»، صاحب نانوایی سلری، که از دوستان قدیمی ریک و مورتی است، امروز دست‌تنها است و مشتری‌های زیادی در صف نانوایی منتظر نان‌شان هستند. او با دیدن ریک و مورتی بسیار خوش‌حال می‌شود و از آن‌ها می‌خواهد در امر خطیر نان‌پزی کمکش کنند. آن‌ها به این شکل تقسیم وظیفه می‌کنند که ریک و آقای میسیک نان‌ها را بپزند و مورتی نان‌ها را بین مشتری‌ها پخش کند.

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

آقای میسیک و ریک با کمک یک‌دیگر می‌توانند با سرعت یک نان بر ثانیه نان بپزند. از طرفی، هر مشتری یک میزان حوصله‌ای دارد که برای مشتری $j$ ام در صف $i$ ام آن را با $p_{i,j}$ نشان می‌دهیم. در صورتی که این مشتری تا $p_{i,j}$ ثانیه بعد از شروع به کار ریک و مورتی نان نخرد، نانوایی را به آتش می‌کشد.

در صورت آتش گرفتن مغازه ریک و مورتی می‌توانند با استفاده از دستگاه تله‌پورت فرار کنند و هیچ آسیبی نبینند. اما مورتی از کار نان فروشی لذت می‌برد و دوست دارد تا قبل از آتش گرفتن مغازه یا تمام شدن مشتری‌ها، به بیشترین تعداد مشتری ممکن نان بفروشد. مورتی حداکثر چند نان می‌تواند بفروشد؟ دقت کنید که بعد از شروع به کار ریک و مورتی مشتری دیگری وارد مغازه نخواهد شد.

ورودی

در خط اول ورودی $n$، تعداد صف‌های نانوایی، آمده است.

در $n$ خط بعدی در هر خط ابتدا یک عدد طبیعی $l_i$ آمده است که نشان‌دهنده‌ی طول صف $i$ ام است. در ادامه‌ی خط $i$ ام، $l_i$ عدد طبیعی آمده است که نشان‌دهنده‌ی $p_{i,1}, p_{i,2}, \dots, p_{i,l_i}$، میزان حوصله‌ی مشتری‌های صف $i$ است.

خروجی

در تنها خط خروجی بیشترین تعداد مشتری‌هایی که مورتی می‌تواند به آن‌ها نان بفروشد را چاپ کنید.

زیرمسئله‌ها

  • زیرمسئله اول (۱۰ نمره): $\sum_{i=1}^n{l_i} \le 10$
  • زیرمسئله دوم (۲۰ نمره): $n \le 2, \sum_{i=1}^n{l_i} \le 1000$
  • زیرمسئله سوم (۷۰ نمره): بدون محدودیت اضافی

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le n \le \sum_{i=1}^n{l_i} \le 10^5$
  • $1 \le p_{i,j} \le 10^9$

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

ورودی نمونه خروجی نمونه
2
1 1
2 9 2
2
3
2 1 2
2 3 5
1 4
5
3
1 3
1 4
2 5 2
4

ابزار صفحه