මිනිසුන්ට ලීට්කෝඩ් විසඳුමට කැන්ඩි බෙදා දෙන්න


දුෂ්කරතා මට්ටම පහසු
ද්විමය සෙවීම ගණිතය

ගැටළු ප්රකාශය

මෙම ගැටලුවේදී අපට අංක දෙකක් ලබා දී ඇත ඉටිපන්දම් සහ num_people. පළමු අංක කැන්ඩි යනු අප සතුව ඇති ඉටිපන්දම් ගණනයි. num_people අපට ඉටිපන්දම් බෙදා හැරිය යුතු පුද්ගලයින් ගණන පෙන්වයි.

ඉටිපන්දම් බෙදා හැරීමේ රීතිය:
අපි වම් කෙළවරේ සිට ඔහුට පැණිරස 1 ක් දෙන්නෙමු, පසුව අපි 2 වන පුද්ගලයාට ඉටිපන්දම් 2 ක් ද, 3 වන පුද්ගලයාට ඉටිපන්දම් 3 ක් ද, ඉටිපන්දම් n වන පුද්ගලයාට ද ලබා දෙමු. ඊට පසු අපි නැවතත් වම් කෙළවරේ සිට ඔහුට n + 1 ඉටිපන්දම් ලබා දී n + 2, n + 3 ලබා දෙන්නෙමු. අපි ඉටිපන්දම් ඉවර වන තුරු මෙම චක්‍රීය ව්‍යාප්තිය අඛණ්ඩව පවතී, එනම් අපගේ ඉතිරි ඉටිපන්දම් වර්තමාන අවශ්‍යතාවයට වඩා අඩු වන විට, ඉතිරි ඉටිපන්දම් වත්මන් පුද්ගලයාට ලබා දෙන අතර පසුව අපි නතර කරමු.

උදාහරණයක්

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

පැහැදිලි කිරීම:

පළමු වාරයේ දී, ans [0] + = 1, සහ අරාව [1,0,0,0] වේ.
දෙවන වාරයේදී, ans [1] + = 2, සහ අරාව [1,2,0,0] වේ.
තෙවන වාරය, ans [2] + = 3, සහ අරාව [1,2,3,0] වේ.
හතරවන වාරය, ans [3] + = 1 (ඉතිරිව ඇත්තේ එක් රසකැවිලි පමණක් බැවින්), සහ අවසාන අරාව [1,2,3,1] වේ.

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

පැහැදිලි කිරීම:

පළමු වාරයේ දී, ans [0] + = 1, සහ අරාව [1,0,0] වේ.
දෙවන වාරයේදී, ans [1] + = 2, සහ අරාව [1,2,0] වේ.
තෙවන වාරය, ans [2] + = 3, සහ අරාව [1,2,3] වේ.
හතරවන වාරය, ans [0] + = 4, සහ අවසාන අරාව [5,2,3] වේ.

ප්‍රවේශය 1 (තිරිසන් බලය)

සරලම ප්‍රවේශය නම් පළමු පුද්ගලයාට කැන්ඩි ලබා දීම සහ 2 සිට 2 දක්වා පුද්ගලයෙකුට ලබා දීම සහ අවසාන පුද්ගලයා වෙත ගමන් කිරීමයි. පළමු පුද්ගලයා ඔහුට ඉටිපන්දම් ලබා දීමෙන් නැවත ආරම්භ කරන්න.
මෙය භාවිතා කර a කැදැලි ලූපය, පිටත ලූපය පැණිරස හෝ ඉතිරිව ඇති තත්වය සඳහා ක්‍රියාත්මක වේ. අභ්‍යන්තර පුඩුවක් වමේ සිට දකුණට දිවෙන අතර එමඟින් ලබා දිය යුතු වත්මන් ඉටිපන්දම් සමඟ එක් එක් ස්ථාන අගයන් සාරාංශ කරනු ඇත. නමුත් දැනට ඉතිරිව ඇති ඉටිපන්දම් වර්තමාන අවශ්‍යතාවයට වඩා කුඩා වන තත්වයක් තිබිය හැකිය. මේ අනුව, අභ්‍යන්තර පුඩුවේ වෙනත් තත්වයක් තිබේ.

දැනට අවශ්‍ය ඉටිපන්දම් ඉතිරි ඉටිපන්දම් වලට වඩා වැඩි වූ විට, ඉතිරි ඉටිපන්දම් වත්මන් පුද්ගලයාට දෙනු ලැබේ. එසේ නොමැති නම්, දැනට අවශ්‍ය ඉටිපන්දම් වත්මන් පුද්ගලයාට ලබා දෙනු ඇත.

මිනිසුන්ට ලීට්කෝඩ් විසඳුම සඳහා කැන්ඩි බෙදා හැරීම සඳහා ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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

මිනිසුන්ට ලීට්කෝඩ් විසඳුම සඳහා කැන්ඩි බෙදා හැරීම සඳහා සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (උපරිම (වර්ග (කැන්ඩි)): වත්මන් අවශ්‍යතාවය සෑම පුඩුවක් තුළම එකකින් වැඩිවේ. ඉතින්, ඉටිපන්දම් ගණන පළමුව 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 /num_people.

දැන් අපි k සම්පූර්ණ චක්‍රයෙන් පසු එක් එක් පුද්ගලයාට ඉටිපන්දම් ගණනය කරමු.

මිනිසුන්ට ලීට්කෝඩ් විසඳුමට කැන්ඩි බෙදා දෙන්න

 

K සම්පූර්ණ චක්‍රයෙන් පසු ඉටිපන්දම් ගණන ගණනය කිරීම සඳහා ගණිතමය පද අපි සොයාගෙන ඇත්තෙමු. K + 1 වන අසම්පූර්ණ චක්‍රය ගැන කුමක් කිව හැකිද?
K + 1 වන අසම්පූර්ණ චක්‍රයේ දී, ඉටිපන්දම් සාර්ථකව ඉටු කිරීම නව වැනි පුද්ගලයින්ට නොයන බව අපට පහසුවෙන් පැවසිය හැකිය, අපගේ ඉටිපන්දම් අතර කොතැනක හෝ අවසන් වනු ඇත.

අපගේ අවසාන සාර්ථක ඉටුවීම මැද බව අපි දැනටමත් ගණනය කර ඇත්තෙමු. සහ මැද%num_people පුද්ගලයා එම මැද ඉටිපන්දම් රැගෙන යයි. ඊළඟ පුද්ගලයා ඉතිරි සියලු ඉටිපන්දම් ලබා ගනී.

මිනිසුන්ට ලීට්කෝඩ් විසඳුමට කැන්ඩි බෙදා දෙන්න
මේ අනුව අපි මෙම අවසාන අසම්පූර්ණ චක්‍රීය ව්‍යාප්තිය අපගේ පළමු මැද% ට එකතු කරමුnum_people සහ 1 + මැද%num_people ඉතිරි සියලුම ඉටිපන්දම් ලැබෙනු ඇත.

මිනිසුන්ට ලීට්කෝඩ් විසඳුම සඳහා කැන්ඩි බෙදා හැරීම සඳහා ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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) වේ.