1541. পাওয়ারের সিরিজ

নিচের ফাংশনটা দেখি:

S(l, h, k) = l^k + (l + 1)^k + (l + 2)^k + … + (h – 1)^k + h^k

l, h আর k এর মান দেওয়া থাকবে। S(l, h, k) এর মান বের করতে হবে।

ইনপুট

9999 টির বেশি টেস্ট কেস থাকবে না। প্রতি লাইনে থাকবে তিনটি সংখ্যা l, h (0 £ l £ h £ 15000000, |l – h| £ 1000) আর k (1 ≤ k ≤ 15000000). ইনপুট শেষ হবে তিনটি -1 দিয়ে।

আউটপুট

প্রতিটি টেস্ট কেসের জন্যে আলাদা লাইনে উত্তর দেখাতে হবে। প্রথমে চার অঙ্কে কেস নম্বর এবং S(l, h, k) এর আসন্ন মান দেখাতে হবে। এই মানের ফরম্যাট হবে এমন 0.ddddddedddddddddd. e এর আগের অংশটুকুকে আমরা ম্যান্টিসা বলবো যেটা সব সময় 1 এর কম হবে এবং দশমিকের পরে ঠিক ছয় ঘর থাকবে। ম্যান্টিসা শূণ্য না হলে, দশমিকের পরের প্রথম অঙ্কটা শূণ্য হতে পারবে না। e এর পরের দশ ঘরকে আমরা বলবো এক্সপোনেন্ট। উত্তরের মান হবে ম্যান্টিসা x 10 ^{এক্সপোনেন্ট}। কোন ক্ষেত্রে যদি এক্সপোনেন্টের যে কোন মানের জন্যে উত্তরের মান হেরফের না ঘটে সে ক্ষেত্রে এক্সপোনেন্ট 1 ধরতে হবে।

উদাহরণ

ইনপুট

1 10 10

10 15 100

-1 -1 -1

আউটপুট

Case 0001: 0.149143e0000000011

Case 0002: 0.406971e0000000118

সমাধান

গাণিতিক

অ্যালগোরিদম বিশ্লেষণ

প্রতিটি i^k পদকে আকারে লিখি। k এর সর্বোচ্চ মানের জন্যে (h^k = ) 10 এর ঘাত হয় to klgh। যেহেতু |l – h| £ 1000, অন্যান্য ছোট ঘাতের মানের সাথে klgh এর পার্থক্য খুব বেশি হবে না। ধরি exponent = . সুতরাং , i^k আকারের পদগুলো যোগ করার পরিবর্তে আমরা = = আকারে যোগ করতে থাকব। এভাবে করলে ম্যান্টিসার মান খুব বড় হবে না, তাই double টাইপ ব্যবহার করাটাই যথেষ্ট হবে। উত্তর শূণ্য হলে জিনিসটা আলাদাভাবে দেখতে হবে। তখন ম্যান্টিসা শূণ্য আর এক্সপোনেন্ট এক হবে।

উদাহরণ

দ্বিতীয় উদাহরণ কেসে

10¹⁰⁰ + 11¹⁰⁰ + … + 15¹⁰⁰ বের করতে বলা হয়েছে।

10¹⁰⁰ এর এক্সপোনেন্ট এর মান 100, 15¹⁰⁰ কে লেখা যায় 10^100lg15 ≈ 117.609. ধরি exponent = 117. যোগফলকে by 10¹¹⁷ দিয়ে ভাগ করি এবং ফলাফলকে double এ রাখি।

(10¹⁰⁰ + 11¹⁰⁰ + … + 15¹⁰⁰ ) / 10¹¹⁷ = (10¹⁰⁰ + 10^100lg11 + … + 10^100lg15 ) / 10¹¹⁷ =

10^-17 + 10^-12,861 + … + 10^0,609 ≈ 4.06971

যেহেতু ম্যান্টিসার মান 1 এর চেয়ে কম, একে 10 দিয়ে ভাগ করি। ম্যান্টিসা হবে 0.406971। আর এক্সপোনেন্ট এর মান এক বেড়ে হবে 118।

অ্যালগোরিদম বাস্তবায়ন

ইনপুট ডাটা পড়ি।

while(scanf("%d %d %d",&l,&h,&k),l + h + k > 0)

{

ম্যান্টিসার বর্তমান মান s কে শূণ্য করে দিই। এর ইন্টিজার অংশকে exponent নামক integer এ রাখি।

s = 0; exponent = k*log10(1.0*h);

l থেকে h এর মধ্যে সব i এর মানের জন্যে এর মানের যোগফলই হবে s।

for(i = l; i <= h; i++)

s += pow(10,k*log10(1.0*i) - exponent);

ম্যান্টিসার মানকে এক এক অংক করে কমাই যতক্ষণ সেটা শূণ্যের কম থাকে। সেই সাথে এক্সপোনেন্ট এর মান বাড়াতে থাকি।

while (s >= 1) s /= 10, exponent++;

শূণ্যের ব্যাপারটা আগে যেভাবে বলা হয়েছে সেভাবে আলাদাভাবে দেখি।

if (!h) s = 0, exponent = 1;

printf("Case %04d: %.6lfe%010d\n", cs++, s, exponent);

}