மக்களுக்கு லீட்கோட் தீர்வுக்கு மிட்டாய்களை விநியோகிக்கவும்


சிரமம் நிலை எளிதாக
பைனரி தேடல் கணித

பொருளடக்கம்

சிக்கல் அறிக்கை

இந்த சிக்கலில், எங்களுக்கு இரண்டு எண்கள் வழங்கப்படுகின்றன மிட்டாய்கள் மற்றும் எண்_ மக்கள். முதல் எண் மிட்டாய்கள் நம்மிடம் உள்ள மிட்டாய்களின் எண்ணிக்கை. num_people நாம் மிட்டாய்களை விநியோகிக்க வேண்டிய நபரின் எண்ணிக்கையைக் காட்டுகிறது.

மிட்டாய்கள் விநியோகத்தின் விதி:
நாங்கள் இடதுபுறத்தில் இருந்து 1 மிட்டாய் கொடுக்க ஆரம்பிக்கிறோம், பின்னர் 2 வது நபருக்கு 2 மிட்டாய்கள், 3 மிட்டாய்கள் 3 வது நபருக்கு n மிட்டாய்கள் வரை n வது நபருக்கு கொடுக்கிறோம். அதன்பிறகு இடதுபுற நபரிடமிருந்து அவருக்கு n + 1 மிட்டாய்களைக் கொடுப்போம், பின்னர் n + 2, n + 3. நாம் மிட்டாய்கள் வெளியேறும் வரை இந்த சுழற்சி விநியோகம் தொடர்கிறது, அதாவது எங்களது மீதமுள்ள மிட்டாய்கள் தற்போதைய தேவைக்கு குறைவாக இருக்கும்போது, ​​மீதமுள்ள மிட்டாய்களை தற்போதைய நபருக்குக் கொடுப்போம், பின்னர் நாங்கள் நிறுத்துகிறோம்.

உதாரணமாக

candies = 7, num_people = 4
[1,2,3,1]

விளக்கம்:

முதல் திருப்பத்தில், பதில் [0] + = 1, மற்றும் வரிசை [1,0,0,0].
இரண்டாவது திருப்பத்தில், பதில் [1] + = 2, மற்றும் வரிசை [1,2,0,0].
மூன்றாவது முறை, பதில் [2] + = 3, மற்றும் வரிசை [1,2,3,0].
நான்காவது முறை, பதில் [3] + = 1 (ஏனென்றால் ஒரே ஒரு மிட்டாய் மட்டுமே உள்ளது), மற்றும் இறுதி வரிசை [1,2,3,1].

candies = 10, num_people = 3
[5,2,3]

விளக்கம்:

முதல் திருப்பத்தில், பதில் [0] + = 1, மற்றும் வரிசை [1,0,0].
இரண்டாவது திருப்பத்தில், பதில் [1] + = 2, மற்றும் வரிசை [1,2,0].
மூன்றாவது முறை, பதில் [2] + = 3, மற்றும் வரிசை [1,2,3].
நான்காவது முறை, பதில் [0] + = 4, மற்றும் இறுதி வரிசை [5,2,3].

அணுகுமுறை 1 (முரட்டு படை)

எளிமையான அணுகுமுறை முதல் நபருக்கு எல் மிட்டாய் கொடுப்பதும், 2 முதல் 2 வது நபரைக் கொடுப்பதும், கடைசி நபருக்கு நகர்த்துவதும் ஆகும். முதல் நபருக்கு அதற்கேற்ப மிட்டாய்களைக் கொடுப்பதில் இருந்து மீண்டும் தொடங்கவும்.
இதைப் பயன்படுத்தி இதைச் செய்யலாம் உள்ளமை வளைய, இதில் எந்த மிட்டாய் மீதமுள்ளதா இல்லையா என்ற நிலைக்கு வெளிப்புற வளையம் இயங்கும். உள் வளைய இடமிருந்து வலமாக இயங்கும், இது ஒவ்வொரு நிலை மதிப்புகளையும் தற்போதைய மிட்டாய்களுடன் தொகுக்கும். ஆனால் தற்போது மீதமுள்ள மிட்டாய்கள் தற்போதைய தேவையை விட சிறியதாக இருக்கும் சூழ்நிலை இருக்கலாம். எனவே, உள் சுழற்சியில் வேறு ஒரு நிலை உள்ளது.

தற்போது தேவைப்படும் மிட்டாய்கள் மீதமுள்ள மிட்டாய்களை விட அதிகமாக இருக்கும்போது, ​​மீதமுள்ள மிட்டாய்கள் தற்போதைய நபருக்கு வழங்கப்படும். இல்லையெனில், தற்போதைய தேவையான மிட்டாய்கள் தற்போதைய நபருக்கு வழங்கப்படும்.

மக்களுக்கு லீட்கோட் தீர்வுக்கான கேண்டிகளை விநியோகிப்பதற்கான நடைமுறை

சி ++ திட்டம்

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        vector<int>ans;
        /*
        initially everyone has no candy. Thus, answer array is filled up with zeros.
        */
        for(int i=0;i<num_people;i++){
            ans.push_back(0);
        }
        int cur=0;//current requirement is initialized to zero
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++; //current requirement increments by one each time.
                if(candies>=cur){ //checks if the remaining candies are greater than current requirement 
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}
5 2 3

ஜாவா திட்டம்

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
        int[]ans=new int[num_people];
        Arrays.fill(ans,0);
        int cur=0;
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++;
                if(candies>=cur){
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
}
5 2 3

மக்களுக்கு லீட்கோட் தீர்வுக்கான மிட்டாய்களை விநியோகிப்பதற்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (அதிகபட்சம் (சதுரடி (மிட்டாய்கள்)): தற்போதைய தேவை ஒவ்வொரு சுழலிலும் ஒன்று அதிகரிக்கிறது. எனவே, மிட்டாய்களின் எண்ணிக்கை முதலில் 1 ஆகவும் பின்னர் 2 ஆகவும் குறைகிறது.
எனவே, நேரம் t க்குப் பிறகு, கைவிடப்பட்ட மிட்டாய்களின் எண்ணிக்கை t * (t + 1) / 2 அல்லது சுமார் t ^ 2 மிட்டாய்கள் நேரம் t க்குப் பிறகு கைவிடப்படுகின்றன.
இவ்வாறு சி மிட்டாய்களைக் கைவிட நமக்கு சதுர (சி) நேரம் தேவை.
எனவே, நேர சிக்கலானது சதுரடி (மிட்டாய்கள்) ஆகும்.

விண்வெளி சிக்கலானது 

ஓ (எண்_ மக்கள்): Num_people அளவு வரிசை பயன்படுத்தப்படுகிறது. எனவே, விண்வெளி சிக்கலானது O (num_people) ஆகும்.

அணுகுமுறை 2 (பைனரி தேடல்)

முந்தைய அணுகுமுறையில், ஒவ்வொரு நபருக்கும் ஒவ்வொன்றாக மிட்டாய்களை வழங்குகிறோம். பின்னர், மீண்டும் சுழற்சி முறையில் மிட்டாய்களை தொடக்கத்திலிருந்தே கொடுக்க ஆரம்பிக்கிறோம். இது நிச்சயமாக நேரம் எடுக்கும் செயல்.
எனவே, இந்த அணுகுமுறையில், நாங்கள் பின்வரும் படிகளைச் செய்வோம்.

முதலாவதாக, மிட்டாய்களின் முழுமையான நிறைவேற்றத்தின் மொத்த எண்ணிக்கையை நாங்கள் கணக்கிடுகிறோம். அதாவது விதிப்படி சரியான மிட்டாய்களைப் பெறும் மொத்த நபர்களைக் கண்டுபிடிப்போம்.
விநியோகம் 1 இலிருந்து தொடங்குகிறது மற்றும் 1 ஆல் அதிகரிக்கிறது. இவ்வாறு விநியோகம் 1 2 3 4 5 6. போன்றதாக இருக்க வேண்டும். இப்போது நாம் வெற்றிகரமாக மிட்டாய்களை 6 முறை கொடுத்துள்ளோம். மொத்த மிட்டாய்களின் எண்ணிக்கை முதல் 6 இயற்கை எண்களின் கூட்டுத்தொகையாகும்.
ஆகவே, எந்த நேரத்திலும், நுகரப்படும் மிட்டாய்களின் எண்ணிக்கை n இயற்கை எண்களின் கூட்டுத்தொகை என்று நாம் கூறலாம், அங்கு n என்பது அந்த நேரம் வரை செய்யப்படும் விநியோகம்.
இப்போது விதியின் படி அதிகபட்ச வெற்றிகரமான விநியோகத்தை நாங்கள் விரும்புகிறோம். அதாவது n இன் அதிகபட்ச மதிப்பை நாம் விரும்புகிறோம், அதாவது n (n + 1) / 2 <= மிட்டாய்களின் மொத்த எண்ணிக்கை.

N இன் மதிப்பைக் கண்டுபிடிக்க, எங்களுக்கு பல அணுகுமுறைகள் உள்ளன. N க்கான இருபடிச் செயல்பாட்டை நாம் தீர்க்க முடியும் அல்லது நாம் n = 1 க்குத் தொடங்கலாம் மற்றும் n இன் மதிப்பை 1 இன் நேர்மாறாக அதிகரிக்கும் n இன் மதிப்பை மாற்றலாம். ஆனால் பைனரி தேடலை இங்கே பயன்படுத்துவதே மிகவும் பொருத்தமான தீர்வு.

N இன் மதிப்பைக் கண்டுபிடிக்க பைனரி தேடல்.

இங்கே பைனரி தேடலைப் பயன்படுத்த, n வரக்கூடிய வரம்பை நாம் அறிந்திருக்க வேண்டும். N இன் குறைந்த பட்ச மதிப்பு 1 ஆக இருக்கலாம் என்று நாம் கூறலாம், ஏனெனில், மிட்டாய்களின் கட்டுப்பாடு குறைந்தது 1 ஆகும். எனவே, முதல் நபருக்கு குறைந்தபட்சம் 1 மிட்டாய் கொடுக்கலாம், எனவே ஒரு வெற்றிகரமான விநியோகத்தை உருவாக்குகிறது (எனவே, குறைந்த பிணைப்பு l = 1) . N இன் மேல் எல்லை கணக்கிட சிக்கலானது, எனவே நாம் அதை நம் சுயத்தால் மிகப் பெரிய முழு மதிப்பைக் கொடுக்கிறோம் (மேல் பிணைப்பு r = 1000000 ஆகட்டும்).

இப்போது நாம் l மற்றும் r க்கு இடையில் ஒரு புள்ளியை விரும்புகிறோம், இது சமன்பாட்டை திருப்திப்படுத்தும் அதிகபட்ச மதிப்பு.
n (n + 1) / 2 <= மிட்டாய்களின் மொத்த எண்ணிக்கை.
L மற்றும் r க்கு இடையில் எந்த புள்ளியும் (ஒரு புள்ளியை நடுவில் விடட்டும்) மேற்கண்ட சமன்பாட்டை திருப்திப்படுத்தினால். அடுத்த புள்ளி (அதாவது நடுப்பகுதி + 1) சமன்பாட்டை பூர்த்தி செய்ய முடியாது. வெற்றிகரமான விநியோகத்தின் அதிகபட்ச எண்ணிக்கையாக நடுப்பகுதி இருக்கும்.

வெற்றிகரமான நிறைவேற்றங்களின் எண்ணிக்கையை (நடுப்பகுதியில்) கண்டறிந்த பிறகு, விநியோகத்தின் முழுமையான சுழற்சிகளின் எண்ணிக்கையை எளிதில் கணக்கிடலாம், இது k = mid /எண்_ மக்கள்.

K முழுமையான சுழற்சிகளுக்குப் பிறகு ஒவ்வொரு நபருக்கும் மிட்டாய்களைக் கணக்கிடுகிறோம்.

மக்களுக்கு லீட்கோட் தீர்வுக்கு மிட்டாய்களை விநியோகிக்கவும்

 

எனவே, k முழுமையான சுழற்சிகளுக்குப் பிறகு மிட்டாய்களின் எண்ணிக்கையைக் கணக்கிட கணித சொற்களைக் கண்டறிந்துள்ளோம். K + 1 வது முழுமையற்ற சுழற்சி பற்றி என்ன.
K + 1 வது முழுமையற்ற சுழற்சியில், மிட்டாய்களை வெற்றிகரமாக நிறைவேற்றுவது n வது நபர்களுக்குப் போவதில்லை, எங்கள் மிட்டாய்கள் இடையில் எங்காவது முடிக்கப்படும் என்று எளிதாகக் கூறலாம்.

எங்கள் கடைசி வெற்றிகரமான பூர்த்தி நடுப்பகுதி என்று நாங்கள் ஏற்கனவே கணக்கிட்டுள்ளோம். மற்றும் நடுப்பகுதி%எண்_ மக்கள் நபர் அந்த நடுப்பகுதியில் மிட்டாய்களை எடுத்துக்கொள்வார். அடுத்த நபர் மீதமுள்ள அனைத்து மிட்டாய்களையும் பெறுவார்.

மக்களுக்கு லீட்கோட் தீர்வுக்கு மிட்டாய்களை விநியோகிக்கவும்
இந்த கடைசி முழுமையற்ற சுழற்சி விநியோகத்தை எங்கள் முதல் நடுப்பகுதியில்% சேர்ப்போம்எண்_ மக்கள் மற்றும் 1 + நடுப்பகுதி%எண்_ மக்கள் மீதமுள்ள அனைத்து மிட்டாய்களையும் பெறும்.

மக்களுக்கு லீட்கோட் தீர்வுக்கான கேண்டிகளை விநியோகிப்பதற்கான நடைமுறை

சி ++ திட்டம்

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        long l=0,r=1000000;
        long mid=0;
        /*
        searching the last successful fulfilment point mid
        */
        while(l<=r){
            mid=l+(r-l)/2;
            long a=((mid+1)*(mid))/2;
            long c=((mid+2)*(mid+1))/2;
            if(a<=candies && c>candies)break;
            else if(a>candies)r=mid;
            else l=mid;
        }
        long k=mid/num_people;
        /*
        here k is the number of complete cycles
        */
        long ans[num_people];
        int i=0;
        for(i=0;i<num_people;i++){
            ans[i]=((k*(k-1)*num_people)/2)+(i+1)*k;//calculating the number of candies to each person after k complete cycles.
        }
        for(i=0;i<mid%num_people;i++){
            ans[i]+=((k*num_people)+i+1);//giving candies to first mid%num_people in k+1 th incomplete cycle.
        }
        ans[i%num_people]+=candies-(mid*(mid+1)/2);// giving all the remaining candies to next person 
        vector<int> ans1;
        for(i=0;i<num_people;i++){
            ans1.push_back((int)(ans[i]));
        }
        return ans1;
        
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}
5 2 3

ஜாவா திட்டம்

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
       
        long l=0,r=1000000;
        long mid=0;
        /*
        searching the last successful fulfilment point mid
        */
        while(l<=r){
            mid=l+(r-l)/2;
            long a=((mid+1)*(mid))/2;
            long c=((mid+2)*(mid+1))/2;
            if(a<=candies && c>candies)break;
            else if(a>candies)r=mid;
            else l=mid;
        }
        long k=mid/num_people;
        /*
        here k is the number of complete cycles
        */
        long[]ans=new long[num_people];
        int i=0;
        for(i=0;i<num_people;i++){
            ans[i]=((k*(k-1)*num_people)/2)+(i+1)*k;//calculating the number of candies to each person after k complete cycles.
        }
        for(i=0;i<mid%num_people;i++){
            ans[i]+=((k*num_people)+i+1);//giving candies to first mid%num_people in k+1 th incomplete cycle.
        }
        ans[i%num_people]+=candies-(mid*(mid+1)/2);// giving all the remaining candies to next person
        int[]ans1=new int[num_people];
        for(i=0;i<ans1.length;i++){
            ans1[i]=(int)(ans[i]);
        }
        return ans1;
    }
}
5 2 3

மக்களுக்கு லீட்கோட் தீர்வுக்கான மிட்டாய்களை விநியோகிப்பதற்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (எண்_ மக்கள்):  வெற்றிகரமான பூர்த்திசெய்தலின் எண்ணிக்கையைக் கண்டுபிடிக்க, நாங்கள் சிறிது நேர சுழற்சியைப் பயன்படுத்துகிறோம், இது பதிவுக்கு (10 ^ 6) முறை 32 க்கு மேல் இருக்கும் மோசமான நிலையில் இயங்கும். ஆக, நேர முழுமையானது O (num_people + 32) அல்லது O (num_people).

குறிப்பு: மிட்டாய்களின் எண்ணிக்கை மக்களின் எண்ணிக்கையை விட அதிகமாக இருக்கும்போது இந்த வழிமுறை சிறப்பாக இருக்கும். ஏனெனில், இந்த வழிமுறை மிட்டாய்களின் எண்ணிக்கையைப் பொறுத்தது அல்ல.

விண்வெளி சிக்கலானது 

ஓ (எண்_ மக்கள்): Num_people அளவு வரிசை பயன்படுத்தப்படுகிறது. எனவே, விண்வெளி சிக்கலானது O (num_people) ஆகும்.