2929. توزیع آب نبات در بین کودکان II

2929. توزیع آب نبات در بین کودکان II

مشکل: واسطه

مباحث: Mathبا Combinatoricsبا Enumeration

به شما دو عدد صحیح مثبت داده می شود n وت limitبشر

بازگشت در تعداد کل از راه های توزیع n آب نبات در میان 3 کودکان به گونه ای که هیچ کودکی بیش از limit آب نباتبشر

مثال 1:

• ورودی: n = 5 ، حد = 2
• خروجی: 3
• توضیح: 3 روش برای توزیع 5 آب نبات وجود دارد به گونه ای که هیچ کودکی بیش از 2 آب نبات نمی گیرد: (1 ، 2 ، 2) ، (2 ، 1 ، 2) و (2 ، 2 ، 1).

مثال 2:

• ورودی: n = 3 ، حد = 3
• خروجی: 10
• توضیح: 10 راه برای توزیع 3 آب نبات وجود دارد به گونه ای که هیچ کودکی بیش از 3 آب نبات نمی کند: (0 ، 0 ، 3) ، (0 ، 1 ، 2) ، (0 ، 2 ، 1) ، (1 ، 0 ، 2) ، (1 ، 1 ، 1 ، 1) ، (1 ، 2 ، 0) ، (2 ، 0 ، 1) ، (2 ، 1 ، 0)) و (3 ، 0).

محدودیت ها:

• 1 <= n <= 106
• 1 <= limit <= 106

نکته:

1. ما می توانیم تعداد آب نبات های یک کودک خاص را ذکر کنیم ، بگذارید i که 0 <= i <= min(limit, n)بشر
2. فرض کنید کودک 2 می شود j آب نبات پس 0 <= j <= limit وت i + j <= nبشر
3. از این رو کودک سوم می شود n - i - j آب نبات و ما باید داشته باشیم 0 <= n - i - j <= limitبشر
4. بعد از برخی تحولات ، برای هر یک i، ما داریم max(0, n - i - limit) <= j <= min(limit, n - i)، ، هر یک j مربوط به یک راه حل. بنابراین تعداد راه حل ها برای برخی i است ، max(min(limit, n - i) - max(0, n - i - limit) + 1, 0)بشر عبارت را برای هر i در [0, min(n, limit)]بشر

راه حل:

ما باید تعداد راه های توزیع را تعیین کنیم n آب نبات در بین 3 کودک به گونه ای که هیچ کودکی بیش از آن را دریافت نمی کند limit آب نبات راه حل شامل استفاده از ریاضیات ترکیبی و اصل گنجاندن-محاصره برای محاسبه کارآمد نتیجه بدون تکرار در تمام توزیع های ممکن است.

رویکرد

1. تجزیه و تحلیل مسئله: مشکل نیاز به شمارش تعداد راه حل های عدد صحیح غیر منفی به معادله دارد x₁ + x₂ + x₃ = N کجا 0 ≤ x_من ≤ حد برای هر یک منبشر

2. بینش ترکیبی: تعداد کل راه حل های غیر منفی برای معادله بدون هیچ گونه محدودیتی توسط فرمول ستارگان و میله ها ارائه شده است ، که (n + 2)/2بشر با این حال ، ما باید راه حل هایی را که باعث نقض محدودیت می شود ، کم کنیم x_من ≤ حدبشر

3. اصل شمول: برای پاسخگویی به محدودیت ها ، ما از اصل ورود-محاصره استفاده می کنیم:

   • کل راه حل ها: تمام راه حل های ممکن را بدون محدودیت محاسبه کنید.
   • راه حل های نامعتبر را کم کنید: راه حل های تفریق که حداقل یک کودک از حد مجاز فراتر رود. این شامل مواردی است که حداقل یک کودک دارد حد + 1 آب نبات
   • راه حل های بیش از حد قرارداد را اضافه کنید: راه حل های را اضافه کنید که در آن دو کودک از حد مجاز فراتر باشند (از آنجا که این دو بار از بین رفتند).
   • راه حل های بیش از حد اضافه شده: راه حل های کمتری را که هر سه کودک از حد مجاز فراتر می روند (از آنجا که این مرحله در مرحله قبل اضافه شده است).

4. کارایی: رویکرد ورود به مطالعه به ما امکان می دهد تا نتیجه را در زمان ثابت محاسبه کنیم o (1) با استفاده از فرمول های ترکیبی ، آن را حتی برای مقادیر بزرگ کارآمد می کند حرف وت محدود کردنبشر

بیایید این راه حل را در PHP پیاده سازی کنیم: 2929. توزیع آب نبات در بین کودکان II

/**
 * @param Integer $n
 * @param Integer $limit
 * @return Integer
 */
function distributeCandies($n, $limit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo distributeCandies(5, 2) . "\n"; // Output: 3
echo distributeCandies(3, 3) . "\n"; // Output: 10
?>

توضیح:

1. عملکرد یاور _F (x)_: این عملکرد تعداد راه حل های عدد صحیح غیر منفی را محاسبه می کند x₁ + x₂ + x₃ = x با استفاده از فرمول ستاره ها و میله ها (x + 2)/2بشر اگر x منفی است ، از آنجا که هیچ راه حل وجود ندارد ، 0 را برمی گرداند.

2. کل راه حل ها: اصطلاح F (n) تمام توزیع های احتمالی را محاسبه می کند n آب نبات بدون هیچ گونه محدودیتی.

3. کمال راه حل های نامعتبر: اصطلاح -3 xf (n – حد – 1) مواردی را برای مواردی که حداقل یک کودک بیشتر از آن دریافت می کند حساب می کند limit آب نبات در اینجا n – حد – 1 آب نبات های باقیمانده را بعد از یک کودک تنظیم می کند حد + 1 آب نبات

4. اضافه کردن راه حل های بیش از حد قرارداد: اصطلاح +3 xf (n – 2 x حد – 2) تصحیح بیش از حد در مواردی که دو کودک هر یک از آنها از حد مجاز فراتر می روند حد + 1 آب نبات

5. تفریق راه حل های بیش از حد اضافه شده: اصطلاح -f (n – 3 x حد – 3) برای مواردی که هر سه کودک از حد مجاز فراتر می روند ، اطمینان حاصل می کند که این راه حل ها شمارش نشده اند.

6. محاسبه نتیجه: نتیجه نهایی این اصطلاحات را ترکیب می کند تا تعداد توزیع های معتبر را ارائه دهد و به یک عدد صحیح داده شود تا اطمینان حاصل شود که نتیجه به درستی قالب بندی شده است.

این رویکرد به طور مؤثر راه حل را با استفاده از ریاضیات ترکیبی محاسبه می کند ، و از نیاز به تکرار نیروی بی رحمانه و رسیدگی به مقادیر بزرگ در پیچیدگی زمان بهینه جلوگیری می کند.

پیوندهای تماس

اگر این سریال را مفید دیدید ، لطفاً در نظر بگیرید مخزن یک ستاره در GitHub یا به اشتراک گذاری پست در شبکه های اجتماعی مورد علاقه خود. حمایت شما برای من بسیار معنی دارد!

اگر می خواهید مطالب مفید تری مانند این ، احساس راحتی کنید که از من پیروی کنید: