UVA 11254: Consecutive Integers

Prob link: UVA 11254: Consecutive Integers

Problem টায় বলা হয়েছে আমাকে একটা integer দেয়া হবে, আমাকে ঐ integer টি আরো কতোগুলি consecutive integer এর summation এর মাধ্যমে বানানো যায় তা print করতে হবে।
Suppose 15 কে আমরা লিখতে পারি এভাবে ------>

15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8
15 = 15

দেখা যাচ্ছে যে এর মধ্যে প্রথম টির integer সংখ্যা বেশি, তাই আমাকে প্রথম টি ই print করা লাগবে।print করার জন্যে question এ যে format এর কথা বলা হয়েছে, সে অনুযায়ী print করলে আমাদের output হবে এরকম  :::
15 = 1 + ... + 5  ( অর্থাৎ আমাকে consecutive integers এর  first এবং last integer টা print করতে হবে )
যদি এমন integer হয়, যাকে কোন consecutive integer এর summation এ ফেলা যায় না, তখন কেবল ঐ integer টাই print হবে।
Ex : For N = 8  ans   ===   8 = 8 + ... + 8

Solve Technique:

আমরা sum of arithmetic progression সম্পর্কে নিশ্চই জানি।
যদি n তম integer পর্যন্ত summation বের করতে হয়, তাহলে সূত্র ঃ sum, Sn ( n terms ) = n / 2 + [ 2 * a + ( n - 1 ) * d ]
যেখানে , a = first term , n = last term , d = interval between numbers .
আমরা এই সূত্র ব্যবহার করে আমাদের উত্তর বের করবো।
যেহেতু আমাদের বলা আছে , consecutive integers, so আমাদের d এর মান হবে  one  ( 1 ) .
এখন আমাদের n জানা আছে, আমরা চাইলে brute force করে করতে পারি,  কিন্তু আমাদের range টাকে ( 10 ^ 9 ) মাথায় রাখতে হবে।
এতবড় জিনিস বারবার loop চালায়ে করলে TLE  ( Time Limit Exceeded ) খাওয়ার সম্ভাবনা অনেক বেশি, তাই আমরা আমাদের সূত্র ব্যবহার করে একটা ফরমুলা বানানোর চেষ্টা করবো যাতে আমাদের brute force এর time complexity কম হয়।
সূত্র টাকে আরেকভাবে লিখা যাক,  a = ( 2 * Sn + n - n * n ) / ( 2 * n )
হিসাবের সুবিধার জন্য আমরা এভাবে লিখলাম, এখন খেয়াল করে দেখো আমাদের জানা মান হল Sn , যা qs এ দেয়া থাকবে, আমাদের বের করতে হবে a এবং n । আমরা ২ টা কাজ করতে পারি, প্রতি a  এর জন্য লুপ চালায়ে n বের করতে পারি, অথবা উলটা কাজটাও করতে পারি।

এখন কথা হল লুপ চালাবো কতক্ষন ?
equation খেয়াল করলে দেখা যায় আমাদের R.H.S এ আছে 2 * Sn , আমরা square root of 2 * Sn থেকে 1 পর্যন্ত integer এর উপর লুপ চালায়ে n  এর মান বের করতে পারি এবং n  এর মান আমরা equation এ বসায়ে  a এর মান এর validity check করতে পারি।যখন ই আমরা valid একটা মান পাবো তখন আমাদের result এর a হবে
equation থেকে প্রাপ্ত মান এবং n হবে   a + ( যেই মান এর জন্য আমরা valid a পেলাম সেই মান) - 1 ।

Qs 1 : Why sqrt ( 2 * Sn )  ?

Ans : equation থেকে এটা easily observe করা যায়, n * n এই value টার আগে minus sign আছে, কাজেই, আমার  n এর মান sqrt ( 2 * Sn ) এর বেশি হলে negative integer আসবে , যা আসলে ভুল result দিবে।

Qs 2 : a এর validity check করবো কিভাবে ?

Ans : আমরা a = ( 2 * Sn + n - n * n ) / ( 2 * n )  এই সূত্র টা কাজে লাগাবো, sqrt ( 2 * Sn ) থেকে 1 পর্যন্ত লুপ চালায়ে আমরা প্রতি n এর জন্য  a এর মান এর validity দেখবো। a valid হবে তখনই যখন আমার equation এ n এবং Sn বসালে তা সত্য হবে।

a = ( 2 * Sn + n - n * n )  এটা থেকে আমরা একটা মান পাবো, এখন কখন এই মানটা সত্য? যখন a কে  ( 2 * n ) দিয়ে মড করলে মান শুন্য আসবে, কেবলমাত্র তখনই আমরা a এর একটা integer value পাবো এবং value টা হবে ( 2 * Sn + n - n * n ) / ( 2 * n ).

	#include <bits/stdc++.h>
	using namespace std;
	/*(use sum of arithmetic progression:n = r/2× (2 × a + r − 1) or
	a = (2 × n + r − r2)/(2 × r); as n is given,
	brute force all values of r from
	root 2n down to 1, stop at the first valid a)
	*/
	int check_valid(int n,int r) // n = r/2 ( 2a + r - 1 )
	{
	int a=2*n+r-(r*r);
	if(a%(2*r)==0)
	return a/(2*r);
	return -1;
	}
	int main()
	{
	int n;
	while(cin>>n && n>=0)
	{
	int m=sqrt(2*n);
	int p=0;
	for(int i=m;i>=1;i--)
	{
	int a=check_valid(n,i);
	if(a!=-1)
	{
	cout<<n<< " = "<<a<< " + ... + "<<a+i-1<<endl;
	break;
	}
	}
	}
	return 0;
	}

view raw uva 11254.cpp hosted with ❤ by GitHub