مربّاها و مشکلات اقتصادی


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

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

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

ورودی🔗

در خط اول ورودی به ترتیب nn که نشان دهنده تعداد شیشه‌های مربّای داخل اتاق و kk که نشان دهنده ظرفیت هر شیشه است، داده می‌شود.

در خط دوم ورودی nn عدد داده می‌شود که عدد ii ام، aia_i است که نشان دهنده مقدار مربّایی است که وقتی وارد اتاق می‌شوید، در شیشه‌ی ii ام هست.

1n1001 \leq n \leq 100 1k1001 \leq k \leq 100

همچنین در هیچ شیشه‌ای در ورودی، بیش از ظرفیتش مربّا نیست.

خروجی🔗

در تنها خط خروجی، بیشینه تعداد شیشه‌ای را که مربّاها می‌توانند بدون ناراحت شدن کنار بگذارند را پیدا کنید.

مثال🔗

ورودی نمونه ۱🔗

5 4
3 4 1 2 2
Plain text

خروجی نمونه ۱🔗

2
Plain text

مربّاها می‌توانند در ۳ شیشه جا شوند، پس می‌توانند ۲ شیشه را داخل کمد بگذارند.

ورودی نمونه ۲🔗

3 8
8 8 8
Plain text

خروجی نمونه ۲🔗

0
Plain text

چون همه شیشه مربّا ها پر هستند، نمی توانیم شیشه ای را کنار بگذاریم. پس پاسخ برابر صفر می باشد.

مربّاها و قفسه‌بندی


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

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

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

طرحی که به مربّاها ارائه شده از nn خط تشکیل شده. مربّاها خط iiام قفسه‌بندی را با دو مقدار aia_i و bib_i نشان می‌دهند که aia_i نشان دهنده شیب خط و bib_i نشان‌دهنده‌ی عرض از مبدا خط iiام روی جدول مختصات فرضی مربّاها است.

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

ورودی🔗

در خط اول ورودی، nn که نشان دهنده تعداد خطوط است، می‌آید. پس از آن در خط i+1i+1 ام ورودی، به ترتیب دو عدد aia_i و bib_i می‌آیند که به ترتیب نشان دهنده شیب و عرض از مبدا خط ii ام می باشند. 1n1 0001 \leq n \leq 1\ 000 109ai,bi109-10^9 \leq a_i, b_i \leq 10^9

خروجی🔗

در تنها خط خروجی تعداد قفسه‌های قفسه‌بندی پیشنهاد شده را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

4
0 0
0 1
2 -1
-2 6
Plain text

خروجی نمونه ۱🔗

10
Plain text

قفسه‌بندی پیشنهاد شده به شکل زیر می‌باشد.

رییس و کارخانه شکلات‌سازی


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

بعد از انقلاب صنعتی، مربّاها در کارخانه‌های ویژه‌ای که توسط انسان‌ها اداره می‌شود، تولید می‌شوند. در این کارخانه‌ها مراتب اداری از هر چیز دیگری مهم‌تر است.

مراتب اداری در این کارخانه‌ها به این صورت است که آقای شماره‌ی ۱، رییس کارخانه است و همه‌ی کارهای کارخانه زیر نظر او انجام می‌گیرد. پس از رییس کارخانه، کارگران رتبه‌ی اول قرار دارند که همگی تحت فرمان مستقیم رییس کارخانه هستند. همچنین به ازای هر i>1i > 1، هر کارگر رتبه‌ی iiام تحت فرمان مستقیم دقیقا یکی از کارگرهای رتبه‌ی i1i-1 هستند. بعلاوه، اگر انسان xx تحت فرمان انسان yy باشد و انسان yy تحت فرمان انسان zz باشد، انسان xx تحت فرمان انسان zz هم هست و هیچ‌کس دیگری در هیچ‌حالتی (به جز دو حالت تحت فرمان مستقیم و با واسطه که گفته شدند) تحت فرمان کس دیگری نیست.

این سلسله مراتب سخت اداری، برای جلوگیری از فساد به وجود آمده؛ بدین صورت که اگر یک روز ii نفر از افراد تحت‌فرمان مستقیم انسان xx فساد کنند، انسان xx علاوه بر پرداخت جریمه‌ی فساد آن‌ها، باید به تعداد کسانی که به هر ترتیبی تحت فرمان او بودند و ملزم به پرداخت جریمه شده‌اند هم شیشه بپردازد (شیشه واحد پولی مربّاهاست که از قضا بسیار ارزشمند هم هست). همچنین او یک شیشه‌ هم برای تنبیه خودش باید بپردازد. به مجموع هزینه‌ای که انسان xx ملزم به پرداخت آن می‌شود، جریمه‌ی انسان xx می‌گوییم.

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

ورودی🔗

در خط اول ورودی nn تعداد افراد کارخانه می‌آید. در خط دوم ورودی n1n - 1 عدد می‌آید که عدد ii ام، pip_i است که نشان می‌دهد که انسان i+1i+1 تحت فرمان مستقیم انسان pip_i می‌باشد. 1n100 0001 \leq n \leq 100\ 000 1pin1 \leq p_i \leq n تضمین می‌شود که همه‌ی انسان‌ها تحت فرمان رییس کارخانه هستند.

خروجی🔗

در تنها خط خروجی تعداد هزینه‌ای که رییس باید بابت جریمه بپردازد را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

5
1 2 1 3
Plain text

خروجی نمونه ۱🔗

12
Plain text

مقدار هزینه‌ای که هر شخص باید بکند به همراه سلسه مراتب کارخانه، به شکل زیر می‌باشد.

مربّا و مجازات کپک


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

دیوان عدالت مربّا (MJC)، پروتکل جدید عدالت اداری خود در خصوص مبارزه با مفسدین اقتصادی را به مجلس ارائه کرده تا مورد تایید آلبالوها قرار بگیرد. در این پروتکل، دو لیست وجود دارد که در یکی از آن ها حداقل میزان اختلاس از بخش های مختلف دولت مربّا که منجر به مجازات «شیره‌کشی» خواهند شد آمده است. مثلا برای شیره‌کشی از یک مربای نگون بخت که از اداره‌ی سوم دولتی اختلاس کرده، نیاز به اثبات اختلاس «دقیقا» ۳ شیشه‌ای داریم (شیشه واحد پول مربّا‌هاست).

مجلس مربّا پس از تایید این پروتکل و دادن جنبه قانونی به آن، در اولین اقدام، قصد دارد کپکی را که از دولت مربّا اختلاس کرده، شیره‌کشی کند تا عبرتی برای کپک‌ها باشد و از دشمنی با مربّاها دست بردارند. از این رو مجلس لیست ساختگی اختلاس‌های کپک را از هر بخش به MJC تحویل داده است، در این لیست ذکر «نشده» که کپک از کدام اداره مقدار iiام را اختلاس کرده و فقط گفته شده که کپک از ادارات اول تا nnام اختلاس کرده. کپک متهم با استفاده از دوستانش به این لیست دسترسی پیدا کرده و مقادیر آن را تغییر داده است، پس ممکن است این لیست برای شیره‌کش کردن کافی نباشد و لیست نیازمند تصحیح باشد.

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

برای فهم بهتر سوال، مثال را مشاهده کنید.

ورودی🔗

در خط اول ورودی عدد nn داده شده است که تعداد اداراتی که از آن‌ها اختلاس شده را نشان می‌دهد در خط دوم ورودی nn عدد می‌آید که عدد ii ام، aia_i است که میزان اختلاس از اداره‌ی iiام برای شیره‌کشی از کپک را نشان می‌دهد. در خط سوم ورودی nn عدد می‌آید که عدد ii ام، bib_i است که عدد iiام لیست دست‌کاری شده توسط کپک‌ها را نشان می‌دهد. 1n100 0001 \leq n \leq 100\ 000 1ai,bi1091 \leq a_i, b_i \leq 10^9 توجه کنید که در لیست دست‌کاری شده، ترتیب مقادیر لزوما درست نیست.

خروجی🔗

در صورتی که مربّاها می‌توانستند لیست را اصلاح کنند، "YES" و در غیر این‌صورت عبارت "NO" را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

6
63 41 80 46 34 32 
23 16 17 31 20 20
Plain text

خروجی نمونه ۱🔗

YES
Plain text

یکی از مقادیر 20 به 80 و دیگری به 41 تغییر پیدا می‌کند. مقدار 31 به 63 تغییر پیدا می‌کند. مقدار 17 به 34، 16 به 32 و 23 به 46 تغییر پیدا می‌کند.

مربّاها و معمای "بیشینه شار"


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

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

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

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

بعد از این که همه‌ی مربّاها راس بدون برچسب خودشان را به گراف چسباندند، بزرگ مربّاها آن‌ها را دور هم جمع کرد و معمایی را برای آن‌ها مطرح کرد. بزرگ مربّاها ابتدا معنی بیشینه‌ شار (max flow) را در گراف برای مربّاها توضیح داد و سپس از آن‌ها خواست که بگویند در تمام حالات برگزاری جشن توسط مربّاها چند گراف با بیشینه شار حداقل mm از راس ۱ به راس ۲ تولید می‌شد. دو حالت برگزاری جشن متفاوتند اگر و فقط اگر گراف ساخته شده در پایان این دو جشن متفاوت باشد، در واقع ترتیب انتخاب یال‌ها مهم نیست. دقت کنید، راس‌های افزوده شده برچسب ندارند (ولی راس ۱ و ۲ دارند).

مربّاها که تازه با گراف آشنا شده بودند نتوانستند که این معما را حل کنند، به همین دلیل پیش شما آمدند تا جواب این معما را به آن‌ها بگویید و مربّاها شرمنده‌ی بزرگشان نشوند. البته آن‌ها متوجه این موضوع هستند که برای شما کار با اعداد خیلی بزرگ سخت است، به همین دلیل باقیمانده‌ی پاسخ معما را بر 109+710^9 + 7 هم بگویید، مربّاها از شما متشکر خواهند شد.

پی‌نوشت: می‌توانید از اینجا اطلاعات بیش‌تری درباره‌ی بیشینه شار به دست بیاورید.

ورودی🔗

در تنها خط ورودی، nn و mm می آیند که به ترتیب نشان دهنده تعداد مربّا و حداقل میزان بیشینه شار می باشند. 1n,m10 0001 \leq n, m \leq 10\ 000

خروجی🔗

در تنها خط خروجی باقیمانده‌ی پاسخ معما بر 109+710^9 + 7 را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

2 2
Plain text

خروجی نمونه ۱🔗

2
Plain text

مربّای اول مجبور است تنها یال گراف را انتخاب کند. و نفر دوم هر یک از دو یال جدید را می‌تواند انتخاب کند. در هر دوی این حالات بیشینه شار برابر ۲ است.

عسل با دوست‌های خوب و شیطونش


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

مربّاها که از حل معما خوششان آمده بود، از بزرگشان خواستند که معمای دیگری به آن‌ها بگوید. بزرگ مربّاها پس از کمی فکر این معما را برای مربّاها مطرح کرد:

یک مثلث قائم‌الزاویه n×nn \times n داریم. مثلث از nn ستون تشکیل شده که ستون iiام آن، nin - i سطر دارد. در mm تا از خانه‌های مثلث مربّا و در بقیه خانه‌های آن عسل قرار داده شده است. یک زیرمثلث kkتایی نشان‌گر اشتراک خانه‌های kk سطر و kk ستون متناظر آن‌ها از مثلث است. یک زیرمثلث خوب، زیرمثلثی‌است که در تمام خانه‌های آن مربّا قرار دارد. همچنین زیرمثلث دوست‌داشتنی زیر‌مثلثی‌است که به ازای هر سطر آن، در اجتماع خانه‌های آن سطر و ستون متناظرش دو مربّا وجود داشته باشد. علاوه بر این یک زیرمثلث عجیب، زیرمثلثی‌ است که دوست‌داشتنی باشد، ولی هیچ زیرمثلثی از آن دوست‌داشتنی نباشد.

تعداد زیرمثلث‌های kkتایی خوب مثلث برابر با f(k)f(k) است. بزرگ مربّاها از آن‌ها خواست تا مقدار Σi=1nf(i)×(1)i+1\Sigma_{i = 1}^n f(i) \times (-1)^{i+1} را بیابند. مربّاها که از شنیدن این معما گیج شده بودند، از بزرگ مربّاها خواستند تا کمکی به آن‌ها بکند. بزرگ مربّاها کمی فکر کرد و سپس به مربّاها گفت که کاری می‌کند که اگر زیرمثلث kkتایی عجیب در مثلث بود، k3k \leq 3 باشد.

مربّاها بعد از این که بزرگشان این شرط را روی مثلث گذاشت، باز هم نتوانستند مسئله را حل کنند، برای همین باز هم دست به دامن شما شدند. لطفا به آن‌ها کمک کنید تا مسئله را حل کنند.

ورودی🔗

در اولین خط ورودی، nn که نشان‌دهنده‌ی اندازه‌ی مثلث است و mm که تعداد مربّاهای داخل مثلث است، می‌آید. در ادامه mm خط می‌آید که در خط iiام، rir_i و cic_i آمده است که به ترتیب سطر و ستون خانه‌ی مربّای iiام را نشان می‌دهد. 1n100 0001 \leq n \leq 100\ 000 0m1000 0000 \leq m \leq 1000\ 000 1ci<rin1 \leq c_i < r_i \leq n

خروجی🔗

در تنها خط خروجی، مقداری که بزرگ مربّا در معما خواسته را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

3 2
1 2
1 3
Plain text

خروجی نمونه ۱🔗

1
Plain text

مجموعه شماره سطرهایی که زیرمثلث خوب می‌سازند عبارتند از:

  • {1}\{1\}
  • {2}\{2\}
  • {3}\{3\}
  • {1,2}\{1, 2\}
  • {1,3}\{1, 3\}

مربّا و کلاس فیزیک


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

مربّا چون خیلی در حل معما فرو رفته بود، یادش رفت تمرین های فیزیکش را انجام دهد. او هم اکنون در سر کلاس فیزیکش است و چیزی از مساحت زیر نمودار نمی داند.

کپک حسود (معلم فیزیک مربّا) که از موضوع خبر دارد، برای تنبیه مربّا، هر ثانیه از qq ثانیه زنگ کلاس، یکی از دو کار زیر را انجام می دهد :

  1. یک خط با عرض از مبدا bib_i و شیب aia_i روی تخته می کشد.
  2. از مربّا می خواهد مساحت زیر نمودار LiL_i تا RiR_i را حساب کند.

در واقع شما در هر xx، ارتفاع نمودار در آن xx را برابر ماکسیمم yy خطوط در آن xx فرض کنید.

مربّا که چیزی از این ها بلد نیست، از شما (کناردستی‌اش) می خواهد به سرعت پاسخ ها را برای اون محاسبه کنید.

برای وضوح بیشتر به مثال ۲ مراجعه کنید.

ورودی🔗

در خط اول ورودی، عدد qq، تعداد ثانیه های زنگ کلاس فیزیک می آید. در ادامه qq خط می آیند. خط ii ام، به یکی از دو صورت زیر است : 1 ai bi1 \ a_i \ b_i 2 Li Ri2 \ L_i \ R_i که حالت اول نشان دهنده اضافه کردن خط توسط کپک حسود است و حالت دوم نشان دهنده یک پرسش از مربّا است.

1q100 0001 \leq q \leq 100\ 000

10 000ai,bi10 000-10\ 000 \leq a_i, b_i \leq 10\ 000

0Li<Ri20 000 0000 \leq L_i < R_i \leq 20\ 000\ 000

خروجی🔗

به ازای هر پرسش از مربّا، در یک خط، مساحت زیر نمودار را چاپ کنید. اختلاف مطلق و نسبی شما با جواب درست نباید بیش از 10610^{-6} باشد. در واقع اگر جواب شما pp و جواب درست jj باشد، در صورتی جواب شما درست در نظر گرفته می‌شود که pjmax(j,1)106\frac{|p - j|}{max(j, 1)} \le 10^{-6}.

مثال🔗

ورودی نمونه ۱🔗

2
1 1 0
2 0 1
Plain text

خروجی نمونه ۱🔗

0.500000
Plain text

دقت کنید که L,RL , R گفته شده به حالت بسته - باز بر روی محور xx هاست. در نتیجه بازه [0,1)[0 , 1) ، شامل یک مثلث قائمه الزاویه به اضلاع قائمه 11 خواهد بود که مساحت آن 0.50.5 است. همچنین دقت کنید ممکن است این مقدار منفی هم باشد (در صورتی که تمام خط ها زیر محور xx ها بروند) همچنین اگر خطی کشیده نشده بود، مساحت زیر نمودار را ۰ در نظر بگیرید.

ورودی نمونه ۲🔗

6
1 -1 2
2 0 1
1 0 1
2 0 2
1 1 -1
2 0 3
Plain text

خروجی نمونه ۲🔗

1.500000
2.500000
4.000000
Plain text