প্রবলেমঃ toph.co/.../friendship

আমার কোড এখানে

এই প্রবলেমটা সাবমিট করলে CPU Limit Exceeded দেখাচ্ছে। কীভাবে এই কোডটাকে আরও ইফিশিয়েন্ট করত পারি?

asked 16 Oct, 20:02

saif12345's gravatar image

saif12345
211

edited 17 Oct, 05:57

Mosharraf%20Hosain's gravatar image

Mosharraf Hosain ♦
60618


৩ থেকে শুরু করে সকল বিজোড় সংখ্যা সুন্দর সংখ্যা। সুতরাং নির্ধারিত সীমার মধ্যে ১ বাদ দিয়ে সকল বিজোড় সংখ্যাকে আলাদা করে ফেললে কাজ অনেক কমে যায়।

১ থেকে ১০ পর্যন্ত সুন্দর সংখ্যাগুলো বের করতে চাই। যেহেতু ১ বাদে সব বিজোড় সংখ্যা সুন্দর সংখ্যা, সেহেতু শুরুতেই আমরা পাবো ৩, ৫, ৭, ৯ চারটি সুন্দর সংখ্যা। এখন জোড় সংখ্যাগুলো পরীক্ষা করতে হবে। পরীক্ষায় দেখা যায় ৬ (১+২+৩) ও ১০ (১+২+৩+৪) সুন্দর। আমরা বিজোড় পেলাম ৪টি এবং জোড় ২টি, মোট ৬টি সংখ্যা।

সুতরাং শুধু জোড় সংখ্যাগুলোর উপর পরীক্ষা চালিয়ে কাজ অর্ধেক কমিয়ে আনা সম্ভব। নির্দিষ্ট সীমার মধ্যে বিজোড় সংখ্যা কয়টি তা জানার জন্য

total_odd = round((max_value - min_value)/2)

যেমন ৫ থেকে ১০০ পর্যন্ত মোট বিজোড় সংখ্যা বের করতে হলে (১০০-৫)/২ = ৪৭.৫ হবে। round() ফাংশন থাকার কারণে ফলাফল হবে ৪৮। এখানে min_value-র মান যদি ১ হয় তবে total_odd থেকে ১ বিয়োগ করতে হবে, কারণ ১ই একমাত্র বিজোড় সংখ্যা যা সুন্দর নয়।

if min_value == 1:
    total_odd -= 1

আপডেট

প্রোগ্রামিং স্কুল গ্রুপের এই পোস্টে নিউরনে অনুরণন নামে একজন একটি সুন্দর উত্তর দিয়েছেন। ১, ২, ৪, ৮, ১৬, ৩২, .... এই ধারার সংখ্যাগুলো বাদে বাকি সব সংখ্যা সুন্দর সংখ্যা। একটা লুপ চালিয়ে এই সংখ্যাগুলো বাদ দিয়ে বাকিগুলো গণনা করলেই হবে। কাজটি সহজ (একটু চিন্তা করতে হবে আরকি), করতে কারো তেমন অসুবিধা হবার কথা নয়।

permanent link

answered 17 Oct, 06:31

Mosharraf%20Hosain's gravatar image

Mosharraf Hosain ♦
60618

edited 19 Oct, 07:47

@Mosharraf Hosain আমিও c++ এ চেস্টা কোরেছি.কিন্তু ঠিক আউট্পুট পাছিনা. https://pastebin.com/YUZ3V75z

(17 Oct, 15:56) Grinch

@Grinch, এই কোডটি সঠিক আউটপুট দেয় (কিন্তু সিপিইউ লিমিট এক্সিডেড)। এটাকে উপরের পদ্ধতিতে ইফিশিয়েন্ট করে দেখতে পারো।

(17 Oct, 17:17) Mosharraf Hosain ♦

আমি এখন পুরোপুরি পরিস্কার নয়। দয়াকরে আরেকটু ব্যাখ্যা দিবেন?

(19 Oct, 07:09) saif12345

উত্তর আপডেট করেছি।

(19 Oct, 07:38) Mosharraf Hosain ♦
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int T;
    long long a, b;

    scanf("%d", &T);

    while(T--) {
        scanf("%lld%lld", &a, &b);
        long long bit = 1, c = 0;

        while(bit < a) {
            bit <<= 1;
        }

        while(bit <= b) {
            c++;
            bit <<= 1;
        }

        printf("%d\n", ((b - a) + 1) - c);
    }

    return 0;
}
permanent link

answered 06 Nov, 18:40

sourav_hossain's gravatar image

sourav_hossain
964

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×54

question asked: 16 Oct, 20:02

question was seen: 108 times

last updated: 06 Nov, 18:40