DCP-111: Chocolates Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/111

খুবই সহজ একটি প্রোবলেম ,

                             c
                            c c
                           c c c
                          c c c c
                         c c c c c
                        c c c c c c

তোমাকে কিছু পরিমাণ , চকলেট দেয়া থাকবে ----- উপরোক্তভাবে সাজানোর পর , যে কয়টি চকলেট বাকি থাকবে , সে কয়টা তোমাকে আউটপুটে দেখাতে হবে । এটা খুব সহজেই লুপ চালিয়েই করতে পারবে , কিন্তু - তাতে Time Limit Exceeded খাবার সম্ভাবনা আছে , তাই আমদের সুত্র ব্যবহার করে করতে হবে । 




তোমাকে , দেয়া n সংখ্যক চকলেট দিয়ে কয়টি , এরকম সারি বানানো যাবে - তার একটি , সূত্র আছে ।

সেটা হলো , ((sqrt(1+(8*n)))-1)/2 । এখন কথা হলো , N টি চকলেট দিয়ে - যে কয়টা সারি ,

এই সুত্র দিয়ে বানাতে পারবো । সে কয়টা , সারিতে মোট কয়টা চকলেট থাকবে সেটা বের করতে হবে ,

উপরের সিকুয়েন্স দেখে বুঝতেই পারছো --- প্রতিটি সারিতে চকলেট এর পরিমাণ , আগের সারি থেকে ১ করে বাড়ছে । অর্থাৎ , ১+২+৩+৪ ... এর মানে , যেটা - যততম সারি সেটাতে সে কয়টা চকলেট আছে । 




    তোমায় যদি , দেয়া থাকে N=23 । তাহলে , এরকম সারি - বানানো যাবে ,
         ((sqrt(1+(8*n)))-1)/2 সুত্র অনুযায়ী - মোট 6 টি ।

এখন,এই ৬টি সারিতে মোট চকলেট থাকবে-(৬*(৬+১)/২)=২১টি [ যেহেতু, এটা ১+২+৩+৪+৫+৬ ধারা হবে]

তাহলে , চকলেট দিয়ে এরকম সারি বানানোর পর বাকি থাকবে , মোট 23-21=2 টি । এটাই , আমাদের উত্তর , চলো কোড দেখি এবার 


#include <bits/stdc++.h>

////Nayeem Mollick  Joy , Applied Physics And Electronic Engineering,University Of Rajshahi.

using namespace std;

typedef unsigned long long llu;

int main()

{
    llu n,column=0,total=0;

    int T;

    cin>>T;

    while(T--)

    {
        cin>>n;

         column=((sqrt(1+(8*n)))-1)/2;

         total=(column*(column+1))/2;

         cout<<column<<endl<<n-total<<endl;
    }
    return 0;
}