1136 - Division by 3 Lightoj Problem Full Logic & Solution

http://www.lightoj.com/volume_showproblem.php?problem=1136
একটু ঝামেলার একটি প্রোব্লেম ,তারপরো চাইলে - বিষয়টা খুবই আনন্দদায়ক ।
প্রথমেই লক্ষ করি , যে - তিনটি ক্রমিক সংখ্যার যোগফল সবসময় ৩ দিয়ে বিভাজ্য হয় ।
যেমন,            x + ( x+1) + ( x+2) == 3x + 3 = 3(x+1)
                        3(x+1) সংখ্যাটি যেহেতু , ৩ এর গুনিতক । সুতরাং , সংখ্যাটি অবশ্যাই ৩ দিয়ে বিভাজ্য ।

এখন প্রোবলেম-এ বলা আছে  যে- একটা সিকুয়েন্স এর কথা ,যেটা ক্রমিকতা বজায় রেখে বাড়তে থাকবে
                    ১ ,     ১২    ,    ১২৩   ,   ১২৩৪  ,   ১২৩৪৫   ,  ১২৩৪৫৬ ..................
                   ১ম     ২য়         ৩য়          ৪র্থ             ৫ম                ৬ষ্ঠ 

তোমাকে ইনপুট-এ দুইটা সংখ্যা দেয়া থাকবে , যেমন ৩ ও ৫ এর মানে হলো , তোমায় বুঝতে হবে - এই সিকুয়েন্স এর    ৩য়  ও  ৫ম  তম সংখ্যা'গুলির মাঝে কয়টি সংখ্যা পাওয়া যাবে (৩য় ও ৫ম সংখ্যা সহ )  , যেটা  ৩ দিয়ে বিভাজ্য হবে ?? 

এখন আমরা জানি যে , প্রত্যেক'টি ত্রয়ী'তে  যেমন - ( ১ ,     ১২    ,    ১২৩  )  [ তিন'টি মিলে একটি ত্রয়ী ]
এমন একটি ,সংখ্যা থাকে ( এখানে, ১২৩ ) যেটা তিন'টি ক্রমিক সংখ্যা দিয়ে গঠিত । অর্থাৎ , এদের যোগফল হবে -   x + ( x+1) + ( x+2) == 3x + 3 = 3(x+1)  যা, ৩ দিয়ে বিভাজ্য । ডিজিট'গুলির যোগফল যদি ৩ দিয়ে বিভাজ্য হয় , তাহলে সংখ্যাটি'ও ৩ দিয়ে বিভাজ্য হবে  অর্থাৎ , ১২৩ অবশ্যই ৩ দিয়ে বিভাজ্য হবে ।খেয়াল করে দেখো , প্রথম ত্রয়ী'র মধ্যে - ১২ ও দ্বিতীয় ত্রয়ী'র মধ্যে ১২৩৪৫ , ৩ দ্বারা বিভাজ্য - এরকমভাবে প্রত্যেক ত্রয়ীর মধ্যেই মোট ২ টা করে সংখ্যা থাকবে - যেটা ৩ দিয়ে বিভাজ্য হবে ।

অর্থাৎ , তাহলে তোমাকে বুঝতে হবে - তোমাকে যে ইনপুট দেয়া হবে - ধরো, ৬ এর মানে ৬ পর্যন্ত এরকম ত্রয়ী আছে  ৬ / ৩ = ২ টা , আর প্রত্যেক ত্রয়ী'তে যেহেতু, ২ টা করে সংখ্যা ৩ দ্বারা বিভাজ্য - সুতরাং , এখানেও তাহলে      ৬ষ্ঠ   অবদি , মোট ২x২ = ৪ টা সংখ্যা ৩ দিয়ে বিভাজ্য , বিশ্বাস না হলে চেক করে দেখো ।  আর , ধরো , ইনপুট দিলো - ৫ তাহলে ত্রয়ী আছে ৫/৩=১ টা , মোট ৩ দ্বরা বিভাজ্য সংখ্যা আছে ১*২ == ২ টা !! কিন্তু , আসলে কিন্তু নয়- কারণ ,আরো একটা ত্রয়ী'র ২য় সংখ্যা এখানে ঢূকে গেছে , তাই - মোট ৩ দ্বারা বিভাজ্য সংখ্যা হবে ২+১=৩ টা , ৫ম সংখ্যা অবদি । অরথাত, ভাগশেষ ২ হলে (৫%৩==২) আরো এক যোগ করতে হবে , আমাদের ।  তাহলে , এবার একটু কোড'টা দেখে ফেলি , নাকি ???

#include<bits/stdc++.h>

//Nayeem Mollick Joy, Applied physics & Electronic Engineering , University of Rajshahi.

using namespace std;



int divisiblecount(int n) {
   
    if (n==0) {
        return 0;
    }
   
    int ans = (n / 3) * 2;
   
    if (n % 3 == 2)
       
    {
        ans=ans+1;
    }
   
    return ans;
}

int main() {
   
    int T, cases = 1, a, b;
   
    scanf("%d", &T);
   
    while (T--) {
           
        scanf("%d %d", &a, &b);
       
        printf("Case %d: %d\n", cases++ , divisiblecount(b) - divisiblecount(a - 1));
    }
    return 0;
}