Learn Swift by comparison (Part – 1)


Swift IDE

If you do not have access to a Mac then try these online IDE to run swift.

http://www.runswiftlang.com

swift1

http://swiftstub.com

Swift2

Both are free.

Playground

If you are using Xcode 6.x+ then you have a playground to learn swift. You can play around with swift in the playground and learn it.

Playground runs code instantly and displays the results right beside the code.

I am using Xcode Version 6.4 (6E35b)

swift3

Hello World!

Let’s write a Hello world program


import UIKit

println ("Hello World!")


import java.lang.*;
import java.io.*;


public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		System.out.println("Hello World!");
	}
}
print ("Hello World")
#include <iostream>;

using namespace std;

int main()
{
	cout << "Hello World!" << endl;
}
console.log("Hello world!");

Noticeable differences in Swift language:

  • Swift is not C-Compatible and it is not a superset of C
  • Swift does not require a main method/function
  • Swift does not require semicolon at the end of each statement

Declaring variable

import UIKit

/*
To declare a variable, use keyword "var"
using "var" is mandatory to declare variable in Swift.
*/

var address = "Dhaka"   // a string variable
var number = 20         // an integer variable
import java.lang.*;
import java.io.*;


public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		String address = "Dhaka";
		int number = 20;

	}
}
address = "Dhaka"
number = 20
#include <iostream>
#include <string>

using namespace std;

int main()
{
	string address = "Dhaka";
	int number = 20;
}
var address = "Dhaka";
var number = 20;

Noticeable differences in Swift language:

  • Swift is a strongly typed (type-safe) language.
  • Swift compiler can infers the type of the variable. If the initial value is Integer then it is an Integer variable.
  • Once a variable has been declared, it will remain to that type. You can not change the variable type after decalred.

Data types

import UIKit

/*
If you want to declare a variable without setting an initial value then you have specify the type of the variable
*/
var anIntegerVariable : Int
var aStringVariable : String
var aFloatVariable : Float
var aDoubleVariable : Double
var aCharacterVariable: Character
var aBooleanVariable: Bool

/*
Decalre and set value in one line
*/

var numberOfItems : Int = 20
import java.lang.*;
import java.io.*;


public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int anIntgerVariable;
		String aStringVariable;
		float aFloatVariable;
		double aDoubleVariable;
		char aCharacterVariable;
		bool aBooleanVariable;

		int numberOfItems = 20;

	}
}
#include &lt;iostream&gt;
#include &lt;string&gt;

using namespace std;

int main()
{
		int anIntgerVariable;
		string aStringVariable;
		float aFloatVariable;
		double aDoubleVariable;
		char aCharacterVariable;
		bool aBooleanVariable;

		int numberOfItems = 20;
}

Noticeable differences in Swift language:

  • Variable can not be declared without default value or explicit types. Either set a value or define a type.
  • Python and Javascript does not have explicit data types
Advertisements

Using C++11 with Eclipse in Mac Yosemite


I am using Eclipse Luna SR1a (4.4.1) and assuming you can install and run Eclipse

C++11

Download gcc-5.0-bin.tar.gz from http://hpc.sourceforge.net

Unzip the file

You will get a usr folder and the folder structure will be following

usr ▸ local ▸ bin
usr ▸ local ▸ include
usr ▸ local ▸ lib
usr ▸ local ▸ libexec
usr ▸ local ▸ share

Rename the local folder to hpc-gcc and move it to your home directory.

For my case the path will be like,

Users ▸ shahabuddin ▸ hpc-gcc ▸ bin
Users ▸ shahabuddin ▸ hpc-gcc ▸ include
Users ▸ shahabuddin ▸ hpc-gcc ▸ lib
Users ▸ shahabuddin ▸ hpc-gcc ▸ libexec
Users ▸ shahabuddin ▸ hpc-gcc ▸ share

Version Test

Create a CPP project in Eclipse and run the code

// version-test.cpp by Bill Weinman <http://bw.org/>

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

int main( int argc, char ** argv ) {
	stringstream version;
	version << "GCC version: "
			<< __GNUC__ << "." << __GNUC_MINOR__ << "." << __GNUC_PATCHLEVEL__
			<< "\nVersion string: " << __VERSION__;

	cout << version.str() << endl;

//	vector<string> v = { "one", "two", "three" }; // C++11 feature - initializer list
//
//	for( string s : v ) {	// C++11 feature - range-based for loop
//		cout << s << endl;
//	}

	return 0;
}

Output should be like,

GCC version: 4.2.1
Version string: 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.56)

Configuration of C++11

Right click the project and select Properties (Cmd + I)

Under C/C++ Build -> Environment
Add these variables

Variable: CPATH
Value: ${HOME}/hpc-gcc/include

Variable: DYLD_LIBRARY_PATH
Value: ${HOME}/hpc-gcc/lib

Variable: LIBRARY_PATH
Value: ${HOME}/hpc-gcc/lib

Variable: PATH
Value: ${HOME}/hpc-gcc/bin:/usr/bin:/bin:/usr/sbin:/sbin

Finally it will look like this,

Screen Shot 2015-02-04 at 2.52.47 AM
Carefully set the Variable and Value. Otherwise you might get the following error,

dyld: Library not loaded: /usr/local/lib/libmpc.3.dylib
Referenced from: /Users/shahabuddin/hpc-gcc/bin/../libexec/gcc/x86_64-apple-darwin14.0.0/5.0.0/cc1plus
Reason: image not found
g++: internal compiler error: Trace/BPT trap: 5 (program cc1plus)
make: *** [version-test.o] Abort trap: 6

Now go to C/C++ Build -> Settings

Under GCC C++ Compiler -> Miscellaneous -> Other flags
Add -std=c++11

Under GCC C Compiler -> Miscellaneous -> Other flags
Add -std=gnu11

Finally it will look like this,

Screen Shot 2015-02-04 at 2.53.15 AM

Screen Shot 2015-02-04 at 2.53.30 AM

Clean the project and Run again

Output should be,

GCC version: 5.0.0
Version string: 5.0.0 20141005 (experimental)

You might as well uncomment the bottom part now.

Output should be,

GCC version: 5.0.0
Version string: 5.0.0 20141005 (experimental)
one
two
three

Big-Integer Tutorial with C


বড় বড় নাম্বার যোগ, গুন করার সময় আমরা প্রায়ই চিন্তায় পড়ে যাই। যেমন আমরা যদি C Data type range দেখি,

int (signed) –2,147,483,648 to 2,147,483,647
unsigned int 0 to 4,294,967,295
long long (signed) –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
unsigned long long 0 to 18,446,744,073,709,551,615

অর্থ্যাৎ সবচেয়ে বেশি গেলেও ২০ ডিজিটের চেয়ে বড় নাম্বার রাখা না। কিন্তু আমাদের আরও বড় সংখ্যা নিয়ে কাজ করার প্রয়োজন হতে পারে। যেমন ধরা যাক, 100! বা 2^1000 যদি বের করতে চাই।

এই কাজগুলা করতে চাইলে আমাদের ছোটবেলার বাংলা পদ্ধতির সাহায্য নিতে হবে। প্রথমে আমি আলোচনা করব বড় বড় যোগ কিভাবে বের করতে হয়, তারপর আসব গুন কিভাবে করতে হয়।

মনে করি, আমাদের দুইটা সংখ্যা দেয়া আছে, 87654 and 74692
এই দুইটা সংখ্যা যোগ করতে হবে।


8
7
6
5
4

7
4
6
9
2

প্রথমে আমরা দুইটা সংখ্যা নিচে নিচে লিখে ফেললাম, এবার আমরা যোগ শুরু করব।


8
7
6
5
4

7
4
6
9
2





6

৪ যোগ ২ সমান ৬


8
7
6
5
4

7
4
6
9
2




4
6

৫ যোগ ৯ সমান ১৪
১৪-এর ৪ বসালাম, হাতে থাকল ১


8
7
6
5
4

7
4
6
9
2



3
4
6

৬ যোগ ৬ সমান ১২
হাতের ১ যোগ করে পেলাম ১৩
৩ বসালাম, হাতে থাকল ১

….
বুঝাই যাচ্ছে আমি কি করতে যাচ্ছি। সবশেষে পুরো বিষয়টা দাড়াবে এরকম

8

7

6

5

4

7

4

6

9

2

1

6

2

3

4

6

এই কাজটাই এখন আমরা প্রোগ্রাম দিয়ে করব। মানে কম্পিউটারকে দিয়ে করাব।

প্রথমে সংখ্যাগুলাকে ডিজিটে ভাগ করে Array-তে নিব।


#include <cstdio>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    return 0;
}

একটা ছোট সমস্যা। আমরা তো যোগ করা শুরু করি ডানদিক থেকে। কিন্তু আমাদের অ্যারে শুরু হয় বামদিক থেকে।
মানে হল, আমাদের প্রথমে যোগ করতে হবে ৪ এবং ২; কিন্তু এগুলা অ্যারেতে শেষ এলিমেন্ট। কি করা যেতে পারে?

আমরা Array উল্টাদিক থেকে পড়া শুরু করতে পারি অথবা অ্যারেটাকেই উল্টে নিতে পারি।
আমরা বরং অ্যারেটাকে উল্টে নিই। তাতে করে আমাদের অ্যারে দেখাবে এরকম।

4
5
6
7
8

2
9
6
4
7

এবং যোগ করার পর আমাদের যোগফল অ্যারেটা হবে এরকম

4
5
6
7
8

2
9
6
4
7

6
4
3
2
6
1

সমস্যা নাই যদিও। সবকাজ শেষ হবার পর আমরা রেজাল্ট অ্যারেটা উল্টে নিব। তাতেই সবকিছু সোজা হয়ে যাবে।

#include <cstdio>
#include <algorithm>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    reverse(firstNumber, firstNumber + 5);
    reverse(secondNumber, secondNumber + 5);
    
    return 0;
}

এবার যোগ করা শুরু করি।

প্রথমে যখন আমরা যোগ করা করি তখন কিন্তু আমাদের হাতে কিছু থাকে না।
আমরা একটা variable নিবো carry;
আমাদের হাতে যা থাকে সেটা এই carry তে থাকবে। প্রথমে হাতে কিছুই থাকে না, তাই carry = 0

এরপর আমরা যোগ করব, firstNumber [i] + secondNumber [i] + carry এইভাবে

যোগফলটা carry-তেই রাখলাম।

#include <cstdio>
#include <algorithm>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    reverse(firstNumber, firstNumber + 5);
    reverse(secondNumber, secondNumber + 5);
    
    int carry = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
    }
    
    return 0;
}

কিভাবে কাজটা হবে সেটা একটু বুঝার চেষ্টা করি।
আমারা প্রথম দুইটা ডিজিটের যোগফল বের করালাম। এবং সেই যোগফল carry-তে আছে।
এখন দেখতে হবে, carry >= 10 কিনা।

যদি carry >= 10 হয় তাহলে আমরা রেজাল্টে বসাব, carry % 10
এবং আমাদের হাতে থাকবে carry / 10

যদি carry < 10 হয় তাহলে আমরা রেজাল্টে বসাব, carry
এবং আমাদের হাতে থাকবে 0

এই দুইটা if-else কন্ডিশন আসলে একই কাজ করে। মানে একটা লাইন দিয়েই দুইটা কাজ করা যায়; if-else লাগবে না।
যেমন ধরি, আমাদের একটা নাম্বার আছে, number
এবং আমরা রেজাল্টে বসাব, number % 10
এবং carry তে বসাব number / 10

result = number % 10
carry = number / 10

একটু খেয়াল করলে দেখা যায়, number value 10 থেকে বড় বা ছোট যাই হোক না কেন, result and carry value সবসময় একই আসবে। একটু চিন্তা করে দেখেন


    int carry = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
        result [i] = carry % 10;
        carry /= 10;
    }

এইভাবে লুপটা ঘুরতে থাকবে। এবং লুপ ঘুরা শেষ হলে আমরা আমাদের উত্তরটা পেয়ে যাব result অ্যারেতে।

একটা সমস্যা কিন্তু থেকে গেল। এখন যদি আমরা result array print দিই তাহলে কি পাব?

64326

result অ্যারেটা reverse করতে হবে, সেটা আমরা জানি। কিন্তু 1 টা কোথায় গেল?

খেয়াল করে দেখেন, লুপ শেষ হয়ে গেলেও আমাদের carry-তে একটা 1 ছিল, যেটা আমরা result array তে ঢুকাতে পারি নাই। সেটা ঢুকাতে হবে।

এইক্ষেত্রে আমরা জানি, carry তে এখন 1 আছে। কিন্তু ধরেন, আমরা অনেক অনেক বড় নাম্বার যোগ করছি। তখন হয়তো carry-তে 54362; এতবড় একটা নাম্বারও থাকতে পারে। তাই না?

এইজন্য আমরা একটা লুপ চালাবো। এবং একটা একটা করে ডিজিট carry থেকে নিয়ে result array তে ঢুকাব।


    int carry = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
        result [i] = carry % 10;
        carry /= 10;
    }
    
    while ( carry ) {
        result [i] = carry % 10;
        carry /= 10;
        i++;
    }
    
    return 0;

আরেকটা সমস্যা। সেটা হল, for loop এর loop variable i-কে আমরা while loop-এর ভেতরে পাব না।

কিন্তু while loop-এর ভেতরে আমাকে তো জানতে হবে, result array-তে কত নাম্বার index থেকে আমি ঢুকানো শুরু করব?

for loop-এ যে পর্যন্ত ঢুকানো হয়েছিল, তারপরের থেকে, তাই না?

বেশি ঝামেলা না করে আমরা result array-টার জন্য আলাদা একটা variable রাখতে পারি।

সবশেষে আমরা result array টা reverse করে দিব।


#include <cstdio>
#include <algorithm>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    reverse(firstNumber, firstNumber + 5);
    reverse(secondNumber, secondNumber + 5);
    
    int carry = 0;
    int resultLength = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }
    
    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }
    
    reverse(result, result + resultLength);
    
    return 0;
}

এখন কথা হল, আমরা এইখানে firstNumber and secondNumber initialize করে দিয়েছিলাম। এটা তো আসলে করা যাবে না। আমাদেরকে ইনপুট নিতে হবে। কিন্তু অনেক বড় বড় সংখ্যা আমরা কিভাবে ইনপুট নিব?

ইনপুটটা আমরা string হিসেবে নিতে পারি।
যদি তাই করি, তাহলে যোগ করার সময় আমাদের একটা কাজ অতিরিক্ত করতে হবে।

সেটা হল, এইক্ষেত্রে ডিজিটগুলা তো আসলে একেকটা character; তাই যোগ করার সময় character গুলাকে ডিজিট করে নিতে হবে।

মানে হল, ‘0’-কে convert করে 0 করবো
‘1’-কে convert করে 1 করবো

আমরা কোডটা দেখে ব্যাপারটা বুঝার চেষ্টা করি।


#include <cstdio>
#include <algorithm>
#include <cstring>

#define N 100

using namespace std;

int main (int argc, char *argv [])
{
    char firstNumber [N];
    char secondNumber [N];
    int result [N + 10];

    scanf ("%s %s", firstNumber, secondNumber);

    reverse(firstNumber, firstNumber + strlen(firstNumber));
    reverse(secondNumber, secondNumber + strlen(secondNumber));

    int carry = 0;
    int resultLength = 0;

    for ( unsigned int i = 0; i < strlen(firstNumber); i++ ) {
        carry = (firstNumber [i] - '0') + (secondNumber [i] - '0') + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    reverse(result, result + resultLength);

    for ( int i = 0; i < resultLength; i++ )
        printf ("%d", result [i]);

    printf ("\n");

    return 0;
}

অতীব চমকপ্রদ একটা কোড করে ফেললাম। এবার একটা ইনপুট দিয়ে টেস্ট করা যাক।

input:
123
1

expected output:
124

actual output:
🙄

ঘটনা যেটা হইছে সেটা অনেকটা এমন

1
2
3
আলু
পটল
1
😕
😐
4

মানে হল, ২য় নাম্বারটা ছোট হবার কারনে তার আগের ঘরগুলাতে Garbage value থাকবে।

সমাধান যেটা করা যেতে পারে, যোগ শুরু করার আগেই অ্যারেগুলা 0 দিয়ে initialize করে দেয়া, যাতে করে আলু, পটল থাকতে না পারে।

0 দিয়ে initialize করে দেয়ার পর আমরা ইনপুট নিবো। ইনপুটের নাম্বারগুলো 0 কে replace করে বসে যাবে। আমাদের অ্যারে সাইজ তো বেশ বড়, ইনপুট নেয়ার পর যে ঘরগুলো খালি থাকবে সেগুলোতো তখন 0 পাওয়া যাবে, আলু পটল না।

আরেকটা ছোট সমস্যা আছে।
আমরা তো এখন string হিসেবে ইনপুট নিচ্ছি। আমরা জানি, string ইনপুট নিলে শেষে একটা

 End of string ('\0') character 

automatically বসে যায়। কাজেই কাজ শুরুর আগে এটাকেও 0 করে দিতে হবে।

এরপরের চিন্তার বিষয় হল, আমরা আমাদের লুপটা কতবার চালাব?

উত্তর হল, দুইটা নাম্বারের মধ্যে যে নাম্বারের length সবচেয়ে বেশি ততবার চালাব।

আমি কি ঠিক বলতেছি? আচ্ছা, এবার তাহলে কোডটা দেখা যাক।


#include <cstdio>
#include <algorithm>
#include <cstring>

#define N 100

using namespace std;

int main (int argc, char *argv [])
{
    char firstNumber [N];
    char secondNumber [N];
    int result [N + 10];

    // initialize the array with '0'
    memset(firstNumber, '0', sizeof firstNumber);
    memset(secondNumber, '0', sizeof secondNumber);

    scanf ("%s %s", firstNumber, secondNumber);

    int firstNumberLength = strlen (firstNumber);
    int secondNumberLength = strlen (secondNumber);
    int maximumLength = max (firstNumberLength, secondNumberLength);

    reverse(firstNumber, firstNumber + strlen(firstNumber));
    reverse(secondNumber, secondNumber + strlen(secondNumber));

    // normalize the last end of string character
    firstNumber [firstNumberLength] = '0';
    secondNumber [secondNumberLength] = '0';

    int carry = 0;
    int resultLength = 0;

    for ( int i = 0; i < maximumLength; i++ ) {
        carry = (firstNumber [i] - '0') + (secondNumber [i] - '0') + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    reverse(result, result + resultLength);

    for ( int i = 0; i < resultLength; i++ )
        printf ("%d", result [i]);

    printf ("\n");

    return 0;
}

যোগের কাহিনি শেষ। :mrgreen:

এবার আসি গুনের কাহিনিতে। ধরি, আমাদের গুন করতে দেয়া হল,
9452 X 675

সাধারনত আমরা ছোটবেলায় গুনটা যেভাবে করতাম,




9
4
5
2



X
6
7
5


4
7
2
6
0

6
6
1
6
4
X
5
6
7
1
2
X
X
6
3
8
0
1
0
0

এইবার আমরা বড়বেলার গুনফল বের করব। এবং সেটা দেখতে হবে অনেকটা এমন




9
4
5
2





X
675
6
3
8
0
1
0
0

মানে একবারেই আমরা গুনফলটা বের করে ফেলব। ঘটনাটা আমি বুঝানোর চেষ্টা করি।

এখানে 675 কে অ্যারেতে আলাদা আলাদা ডিজিট হিসেবে চিন্তা না করে একটা সংখ্যা হিসেবে চিন্তা করতে হবে। এবং একবারে 675 দিয়েই গুনের কাজ করতে হবে। যেমন:

675 X 2    =    1350 
675 X 50   =   33750
675 X 400  =  270000
675 x 9000 = 6075000
-----------------------
             6380100

অথবা আরেকটা কাজ করা যায়। মনে করি আমাদের কাছে একটা খালি অ্যারে আছে








675 x 2 = 1350
put the last 0 in the array
carry = 135







0

675 X 5 = 3375 + carry = 3375 + 135 = 3510
put the last 0 in the array
carry = 351






0
0

675 X 4 = 2700 + carry = 2700 + 351 = 3051
put the last 1 in the array
carry = 305





1
0
0

675 X 9 = 6075 + carry = 6075 + 305 = 6380
put the last 0 in the array
carry = 638




0
1
0
0

এখন হাতে যে carry আছে সেটাই অ্যারেটার আগে বসিয়ে দিতে হবে

6
3
8
0
1
0
0

এবার দেখব আমাদের সবশেষ কোড


#include <cstdio>
#include <algorithm>
#include <cstring>

#define N 100

using namespace std;

int main (int argc, char *argv [])
{
    char firstNumber [N];
    int secondNumber;
    int result [N + 10];

    scanf ("%s %d", firstNumber, &secondNumber);

    int firstNumberLength = strlen (firstNumber);

    reverse(firstNumber, firstNumber + strlen(firstNumber));

    int carry = 0;
    int resultLength = 0;

    for ( int i = 0; i < firstNumberLength; i++ ) {
        carry = ((firstNumber [i] - '0') * secondNumber) + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    reverse(result, result + resultLength);

    for ( int i = 0; i < resultLength; i++ )
        printf ("%d", result [i]);

    printf ("\n");

    return 0;
}

একটাই প্রশ্ন থেকে যায়, ২য় নাম্বারটা আমরা কেন অ্যারেতে নিলাম না? যদি ২য় নাম্বারটা অনেক অনেক বড় হয় তখন কি হবে?

উত্তর: হবে আর কি কিছু একটা। এই শিশু বয়সে ওইসব নিয়ে টেনশন করার কি দরকার? চেপে যান 😐

UIU: Prime Number using Square_Root Algorithm


প্রাইম নাম্বার: যে সংখ্যাকে 1 এবং ওই সংখ্যা ছাড়া আর কোন সংখ্যা দিয়ে ভাগ করা যায় না, সেগুলা প্রাইম নাম্বার।

যেকোন সংখ্যাকেই 1 দিয়ে ভাগ করা যায়
আর, যেকোন সংখ্যাকেই ওই সংখ্যা দিয়ে ভাগ করা যাবেই।

মনে করি, আমাদের একটা সংখ্যা দেয়া আছে n
এখন আমরা যেটা করব, 2 থেকে শুরু করে n – 1 পর্যন্ত সবগুলা সংখ্যা দিয়ে n-কে ভাগ করব

যদি কোন সংখ্যা দিয়েই ভাগ করা না যায় তাহলে n প্রাইম
আর যদি কোন সংখ্যা দিয়ে ভাগ করা যায় তাহলে n প্রাইম না

আমরা প্রথমে কতগুলা প্রাইম নাম্বার দেখি,
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 …. এইগুলা হল প্রাইম নাম্বার

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

int main(int argc, char *argv[]) {
	
	int n;	

	scanf ("%d", &n);

	for ( int i = 2; i < n; i++ ) {
		if (n % i == 0) {
			printf ("%d is not prime", n);
		}
	}
}

// @END_OF_SOURCE_CODE

#11: আমরা 2 থেকে n – 1 পর্যন্ত লুপ রান করবো

#12: if condition চেক করে দেখলাম, n-কে i দিয়ে ভাগ করা যায় কিনা
যদি ভাগ করা যায় তাহলে n প্রাইম হবে না

আমরা বুঝলাম কখন প্রাইম হবে না, কিন্তু তাহলে কখন প্রাইম হবে?

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

int main(int argc, char *argv[]) {
	
	int n;	

	scanf ("%d", &n);

	bool flag = true;

	for ( int i = 2; i < n; i++ ) {
		if (n % i == 0) {
			printf ("%d is not prime", n);
			flag = false;
		}
	}

	if (flag) {
		printf ("%d is prime", n);
	}
}

// @END_OF_SOURCE_CODE

#11: আমরা একটা bool variable নিলাম
আপনারা bool variable C++-এ পাবেন। জিনিসটা খুব সহজ
bool variable-এ মাত্র ২টা value রাখা যায়। হয় true নাহয় false
আমরা প্রথমে flag-এ true রাখলাম

#14-16: if condition-এর ভেতরে আসলে আমরা জানি, প্রাইম না
তখন আমরা flag-কে flase করে দিলাম

#20: flag চেক করে দেখছি, true কিনা

if (flag) {

}

এবং

if (flag == true) {

}

একই কথা

যদি flag == true হয়, তার মানে #16-তে কখনই আমরা যাই নাই

অতএব, n প্রাইম

এবার প্রাইমের পুরো ব্যপারটা আমরা একটা function-এর ভিতরে নিয়ে যাই

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

bool isPrime(int n)
{
	for ( int i = 2; i < n; i++ ) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

int main(int argc, char *argv[]) {
	
	int n;	

	scanf ("%d", &n);

	if (isPrime(n)) {
		printf ("%d is prime\n", n);
	} else {
		printf ("%d is not prime\n", n);
	}
}

// @END_OF_SOURCE_CODE

#5: একটা function নিলাম, যাকে আমি একটা integer নাম্বার দিব
এবং সে আমাকে বলবে, ওই নাম্বারটা প্রাইম কিনা
যদি প্রাইম হয় তাহলে সে আমাকে true return করবে
আর যদি প্রাইম না হয় তাহলে সে আমাকে false return করবে

#9: if condition-এর ভিতরে আসা মানেই প্রাইম না, তাই না?
তাহলে আমরা সাথে সাথে return false করব
return করা মানে, এই function থেকে আমরা বের হয়ে যাব

#13: এই লাইনে আসা মানে কিন্তু #9 কাজ করে নাই। যদি #9 কাজ করত তাহলে আমরা isPrime() Function-এর ভিতরে থাকতাম না,
অনেক আগেই বের হয়ে যেতাম, কাজেই এইখানে আসলে আমরা বুঝবো #9 কাজ করে নাই এবং n প্রাইম

#22: isPrime(n) == true হলে, n প্রাইম .. সহজ ব্যপার, তাই না?

এবার আমরা আরেকটু সামনে আগাবো

1 থেকে 1000 পর্যন্ত কতগুলা প্রাইম আছে, সেটা বের করব
এবং এই কাজটা করতে আমাদের কতটুকু সময় লাগলো সেটাও বের করব

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <ctime>

bool isPrime(int n)
{
	for ( int i = 2; i < n; i++ ) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

int main(int argc, char *argv[]) {

	clock_t t = clock();

	int numberOfPrime = 0;

	for ( int i = 1; i <= 1000; i++ ) {
		if ( isPrime(i) ) {
			numberOfPrime++;
		}
	}

	t = clock() - t;

	printf ("Number of Prime: %d\n", numberOfPrime);

	printf ("Time needed: %f\n", ((float)t) / CLOCKS_PER_SEC);
}

// @END_OF_SOURCE_CODE

আপনি যদি Code::Blocks ব্যবহার করেন, তাহলে এমনিতেই প্রোগ্রাম রান করার পরে কতটুকু সময় লাগলো সেটা জানা যায়

আমি ধরে নিলাম আপনি Code::Blocks ব্যবহার করছেন না, তাহলে আপনি কি করবেন? আপনার জন্যই প্রোগ্রামটা এইভাবে করা
(ওহ! আপনার জন্য আমার দরদ দেখছেন? Code::Blocks না থাকলে আপনার কি হবে? কত টেনশন করি আপনার জন্য!
আসলে এইগুলা কিছুই না, আমার নিজের Code::Blocks নাই তো! এইজন্য আমাকে এইভাবে কোড করতে হইলো :()

#4: সময় নিয়ে কাজ করার জন্য এই Header File-টা লাগবে

#19: সময় গুনতে শুরু করলাম আমরা

#23-27: আমরা একটা লুপ রান করলাম 1 থেকে 1000 পর্যন্ত
তারপর if condition check করলাম
যদি isPrime(i) আমাদের true দেয় তাহলে i একটা প্রাইম .. তাই আমরা numberOfPrime++ করলাম

#29: সময় গণনা সমাপ্ত

output:
Number of Prime: 169
Time needed: 0.000000 second

একটু ভুল হয়ে গেল!

1000-এর নিচে প্রাইম আছে 168-টা
আমাদের তাহলে 169 আসলো কেন?

উপরের কোডে কোথাও কোন ভুল হল কিনা দেখেন, একটু চিন্তা করেন, তারপর নিচের লেখা পড়েন

আমাদের isPrime() Function ভুল করে একটা নাম্বারকে প্রাইম বলছে, কিন্তু সেটা আসলে প্রাইম না

ওই নাম্বারটা হল 1

n = 1 হলে #8 লুপটা রানই করবে না, তাই না?

সবচেয়ে ছোট প্রাইম হল 2
এবং 2 হল একমাত্র প্রাইম যেটা জোড় সংখ্যা

তাহলে আমরা isPrime() function-টা একটু ঠিকঠাক করি

bool isPrime(int n)
{
	if ( n < 2 ) return false;

	for ( int i = 2; i < n; i++ ) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

যদি n, 2 থেকে ছোট হয় তাহলে সাথে সাথে return false, নীচে যাওয়ার দরকারই নাই .. ঠিক আছে?

এইবার আবার রান করে দেখি

output:
Number of Prime: 168
Time needed: 0.000000 second

এখন ঠিক আছে 🙂

এবার 1000 বদলে 10000 করি, তারপর রান করি

output:
Number of Prime: 1229
Time needed: 0.021000 second

এবার 10000 বদলে 100000 করি, তারপর রান করি

output:
Number of Prime: 9592
Time needed: 1.669000 second

এবার 100000 বদলে 1000000 করি, তারপর রান করি

output:
Number of Prime: 78498
Time needed: 136.707001 second

Time needed-এর value আপনাদের ভিন্ন হতে পারে, এটা আমার কম্পিউটারের value

কথা সেইটা না .. কথা হইলো, আপনার কোড রান করতে কম্পিউটারের জান বের হয়ে গেছে!

খালি একটু চিন্তা করেন, আপনার কোড রান করতে কম্পিউটারের ১৩৬ সেকেন্ড লাগছে!

কনটেস্টে আপনার কোড যদি ৩ সেকেন্ডের মধ্যে রান করে শেষ না হয়, তাহলে আপনি Time Limit Exceed (TLE) খাবেন

আমরা বুঝতে পারলাম, আপনার এই প্রাইম কোডটার​ পারফরমেন্স খুবই খারাপ

একটা জিনিস খেয়াল করেছেন?
কিছুক্ষণ আগেও আমি সবখানে “আমাদের কোড”, “আমাদের কোড” বলতেছিলাম
যখনই দেখা গেল, কোডের​ পারফরমেন্স খারাপ, তখনই বলা শুরু করলাম, “আপনার কোড”, “আপনার কোড”

শুধু কোডিং শিখলে হবে? কিভাবে অন্যদের চকোলেট খাওয়াতে হয় সেটাও শিখেন! 😉

আমরা এখন কোডটার​ পারফরমেন্স ঠিক করব, কাজেই এটা আবার “আমাদের কোড”, ওকে? 😀

পারফরমেন্স ইমপ্রুভমেন্ট 1:

আমরা এতক্ষণ 2 থেকে শুরু করে n – 1 পর্যন্ত লুপ রান করাচ্ছিলাম
আমাদের আসলে 2 থেকে শুরু করে n / 2 এর বেশি যাবার দরকার নাই
কারন, n / 2 + 1 থেকে n – 1 পর্যন্ত কোন সংখ্যা দিয়ে n-কে ভাগ করা যাবে না

ব্যপারটা খুবই সাধারন। যেমন: ৫০ থেকে বড় কোন সংখ্যা দিয়েই ১০০-কে ভাগ করা যায় না

bool isPrime(int n)
{
	if ( n < 2 ) return false;

	for ( int i = 2; i <= n / 2; i++ ) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

এবার কোড রান করে দেখা যাক কতটুকু ইমপ্রুভমেন্ট হল

output:
Number of Prime: 78498
Time needed: 77.183998 second

কিছুটা ভাল হলেও, এখনও আপনার কোডের পারফরমেন্স তেমন ভাল না ..

পারফরমেন্স ইমপ্রুভমেন্ট 2:

আমরা জানি, 2 হল একমাত্র প্রাইম, যেটা জোড়
তার মানে 2 ছাড়া আর কোন জোড় সংখ্যাই প্রাইম হতে পারে না

কিভাবে এই ব্যপারটা কাজে লাগাতে হবে আমি ধাপগুলা বলি

1. n == 2 যদি হয়, তাহলে সাথে সাথে return true

2. তারপর দেখব, যদি n জোড় হয় তাহলে সাথে সাথে return false

3. এখন আমাদের কাছে শুধু বেজোড় সংখ্যা আছে
আমরা জানি, কোন বেজোড় সংখ্যাকেই, জোড় সংখ্যা দিয়ে ভাগ করা যায় না

4. তাহলে আমাদের লুপ শুরু হবে ৩ থেকে, ২ থেকে নয়

5. এবং আমাদের লুপ বাড়বে ২ করে, মানে হল,
৩, ৫, ৭, ৯, ১১ .. এইভাবে

মূলত আমরা যা করলাম: লুপ চালানোর আগেই সব জোড় সংখ্যাকে বাদ দিয়ে দিলাম

bool isPrime(int n)
{
	if ( n < 2 ) return false;

	if ( n == 2 ) return true;

	if ( n % 2 == 0 ) return false;

	for ( int i = 3; i <= n / 2; i += 2 ) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

এবার কোড রান করে দেখা যাক কতটুকু ইমপ্রুভমেন্ট হল

output:
Number of Prime: 78498
Time needed: 40.703999 second

40 second! এইটা কিছু হইল? কোথায় আমাদের লাগবে < 3 second , আর এইখানে আসছে 40 second

অনেক হইছে! আর সহ্য করা যায় না .. আপনার এই দেশী অ্যালগরিদম দিয়ে আর কাজ করা সম্ভব না

এখন আমাদের বিদেশী অ্যালগরিদম লাগবে
প্রথমে বিদেশী অ্যালগরিদমের কোডটা দেখি

পারফরমেন্স ইমপ্রুভমেন্ট 3:

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <ctime>
#include <cmath>

bool isPrime(int n)
{
	if ( n < 2 ) return false;

	int squareRoot = (int) sqrt(n);

	for ( int i = 2; i <= squareRoot; i++ ) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

int main(int argc, char *argv[]) {

	clock_t t = clock();

	int numberOfPrime = 0;

	for ( int i = 1; i <= 1000000; i++ ) {
		if ( isPrime(i) ) {
			numberOfPrime++;
		}
	}

	t = clock() - t;

	printf ("Number of Prime: %d\n", numberOfPrime);

	printf ("Time needed: %f second\n", ((float)t) / CLOCKS_PER_SEC);
}

// @END_OF_SOURCE_CODE

রান করে দেখি কি অবস্থা

output:
Number of Prime: 78498
Time needed: 0.327000 second

ওহ! সুপারম্যান স্পীড .. এইটাইতো দরকার 😀

#11: আমরা n-এর square root বের করলাম
sqrt() আমাদের একটা double নাম্বার দেয় ..
আমাদের double দরকার হবে না, তাই আমরা (int) দিয়ে cast করে নিলাম
integer cast করা মানে হলো জোর করে integer বানানো, মানে আমরা শুধুমাত্র integer অংশটা আমরা পাব
একটা উদাহরণ দেই

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

int main(int argc, char *argv[])
{
    int n;

    n = (int) 7.6;

    printf ("%d\n", n);

    n = (int) 7.1;

    printf ("%d\n", n);

}

// @END_OF_SOURCE_CODE

output: 
7
7

আমাদের কেন double দরকার হবে না?

উত্তর: আমরা তো লুপ চালাচ্ছি .. আমাদের লুপ 1 করে increment হবে
তাই, square root result 7.6 হোক বা 7.1, আমরা আসলে 7 বারই ঘুরব

আচ্ছা, মনে করেন আমি ২টা কোড লিখলাম
কোড ২টা একই কাজ করে

// example 1
int squareRoot = (int) sqrt(n);

for ( int i = 2; i <= squareRoot; i++ ) {

}

// example 2
for ( int i = 2; i <= (int) sqrt(n); i++ ) {

}

কোন কোড রান করতে বেশি সময় লাগবে?

yes! example 2 কোড রান করতে বেশি সময় লাগবে
কারণ প্রতিবার লুপ condition চেক করার সময় সে একবার করে sqrt (n) ক্যালকুলেট করে
তাই আমরা example 1-এর মত করে কোড করব

প্রাইম নাম্বার ব্যপারটা একটু অন্যভাবে বলি,

আমাদের আসলে জানা দরকার, 1 এবং n ছাড়া n-এর আর কোন গুনিতক আছে কিনা

যদি থাকে, n প্রাইম না
যদি না থাকে, n প্রাইম
তাই না?

এবার আমরা যেটা করব, 2 থেকে sqrt (n) পর্যন্ত লুপ চালাবো

আমরা ধরে নিচ্ছি, যদি n-এর কোন গুনিতক থাকে (1 এবং n ছাড়া) তাহলে 2 থেকে sqrt(n)-এর মধ্যেই থাকবে
যদি না থাকে, তাহলে 2 থেকে sqrt(n)-এর বাইরেও থাকবে না

মজার ব্যপার হল, আমাদের এই ধারনা কাজ করতেছে, এবং খুব বেশি ভালভাবে কাজ করতেছে
কিন্তু কেন কাজ করছে সেটা হল বিষয়

ব্যপারটা আজব না? 2 থেকে sqrt(n)-এর মধ্যে গুনিতক পাওয়া না গেলে n-এর আর গুনিতক নাই, কাজেই প্রাইম

আমরা একটা উদাহরন দেখি,

মনে করি, একটা সংখ্যা ৩৬ দেয়া আছে
৩৬-এর গুনিতক গুলা কি কি?

1	x	36	= 36
2	x	18	= 36
3	x	12	= 36
4	x	9	= 36
6	x	6	= 36

একটা ব্যপার খেয়াল করেন, বামপাশের সংখ্যাগুলা আস্তে আস্তে বাড়ে।
যেমন: 1, 2, 3, 4, 6
এবং ডানপাশের সংখ্যাগুলা আস্তে আস্তে কমে।
যেমন: 36, 18, 12, 9, 6

একটু এলোমেলো হয়ে গেল না?

আমরা বলেছিলাম, 2 থেকে 6-এর মধ্যেই 36-এর গুনিতক পাওয়া যাবে। কিন্তু 6-এর চেয়ে বড় গুনিতকও আছে 36-এর। যেমন: 9, 12, 18

ব্যপারটা আসলে এরকম না

আমরা আসলে বলেছিলাম, যদি 36-এর গুনিতক থাকে তবে অবশ্যই 2 থেকে 6-এর মধ্যে থাকবে।
আমরা কিন্তু বলছি না, 6-এর চেয়ে বড় গুনিতক থাকবে না

মানে হল, 36-এর যদি ১০০টা গুনিতকও থাকে, তাহলে তার মধ্যে ১ টা 2 থেকে 6-এর মধ্যে থাকবেই।

আমাদের সবগুলা গুনিতকের দরকারও নাই। একটা পেলেই আমরা বলে দিতে পারব, 36 প্রাইম না

2 থেকে 6-এর মধ্যে যদি 36 এর গুনিতক পাওয়া না যায় তাহলে, বুঝতে হবে 36-এর কোন গুনিতকই নাই।

এবার আমরা প্রমান করব, আমাদের ধারনা কেন ঠিক
আমাদের প্রমান করার পদ্ধতির নাম Proof by Contradiction

ধরি, 2 থেকে 6-এর মধ্যে 36-এর কোন গুনিতক নাই, কিন্তু 6 থেকে বড় একটা গুনিতক আছে, যেটা হল P, তাহলে
P x Q = 36

36-এর একটা গুনিতক P
তারমানে, 36-কে P দিয়ে ভাগ করা যায় .. ভাগ করলে কিছু একটা রেজাল্ট আসবে, সেটাই হলো, Q
Q = 36 / P
or, P x Q = 36

আমরা একটু আগেই দেখেছিলাম,
6 x 6 = 36

যেহেতু P > 6 তাহলে অবশ্যই Q < 6

তাহলে 36-এর একটা গুনিতক পাওয়া গেল যেটা 6 থেকে ছোট

এটা Contradictory! কারন আমরা ধরে নিয়েছিলাম, 2 থেকে 6-এর মধ্যে 36-এর কোন গুনিতক নাই

কাজেই, 2 থেকে 6-এর মধ্যে যদি 36 এর গুনিতক পাওয়া না যায় তাহলে, 6 থেকে বড় 36-এর কোন গুনিতক থাকতে পারে না । (প্রমানিত)

UIU: বাঁচতে হলে জানতে হবে


মাই ডিয়ার ভাই ও বোনেরা,
ACM Programming Problems সলভ করতে চাওয়া খুবই উত্তম সিদ্ধান্ত
কিন্তু কিছু ছোটখাটো কনটেস্টের নিয়ম-কানুন না জেনে আচমকা কনটেস্ট করা শুরু করে দিলে
ধুমায়ে wrong answer / runtime error / time limit exceed খাইতে খাইতে মারা যাবেন
সেইজন্যই বলতেছি, বাঁচতে হলে জানতে হবে!

কনটেস্ট শুরু করার জন্য C জানা যথেষ্ট .. তবে আপনাকে C++ ও জানতে হবে পরে
কনটেস্ট করার জন্য C++ সবচাইতে জনপ্রিয় programming language
C++ এ আপনি C-এর সবকিছু ব্যবহার করতে পারবেন, সাথে আরো অনেক সুবিধা পাবেন
আমরা আস্তে আস্তে সেগুলা দেখব

প্রথম কথা হলো, কনটেস্ট কোডিং করার টেম্পলেট .. মানে হলো, কনটেস্ট করার জন্য আপনাকে নিচের ফরমেট ফলো করতে হবে

#include <stdio.h>

int main(int argc, const char ** argv[])
{

    // write your code here

    return 0;
} 

main ফাংশনের প্যারামিটার হিসেবে কিছু ক্যাচাল মার্কা জিনিস দেয়া আছে .. ভয় পাওয়ার কিছু নাই
এইগুলা না দিলেও হবে, আপনাদের সাথে একটু ভাব নিলাম আরকি
এই জিনিসগুলা আপনার কোডে থাকলে সবাই মনে করবে আপনি অনেক কিছু জানেন, ব্যপক জ্ঞানী!
আরেকটু ইনফরমেশন জেনে রাখেন .. যাতে Junior question করলে একেবারে চিপায় না পড়েন
argc = argument counter
argv = argument variable [double pointer constant character array]

যদি আপনি command line / teminal থেকে প্রোগ্রাম রান করেন তখনি এই জিনিসগুলা ব্যবহার হয়
এছাড়াও কোনো কোনো IDE-তে argument পাস করার option থাকে প্রোগ্রাম রান করার সময়
ব্যস, আর কিছু জানার দরকার নাই .. এরপরেও যদি আঁতেল Junior question করে তখন কি করবেন?
ব্যপক vaabz নিয়ে বলবেন, এখন তোমরা এইগুলা বুঝবা না .. আগে বড় হও তখন বুঝবা, ওক্কে? গুড

তাহলে আমাদের বেসিক টেম্পলেট হলো,

#include <stdio.h>

int main()
{

    // write your code here

    return 0;
} 

এইভাবে না করলে হবে না, ঠিক আছে?
বাংলা কথা হলো,

void main () {

}

দেয়া যাবে না
কেন দেয়া যাবে না? .. ভালো question
আমরা যে GCC compiler use করি, এই স্টাইলটা হলো সেটার convention
এই স্টাইল ফলো না করে কোড করলে সে অনেক mind করে 😦
আর সে mind করলে কি হয় জানেন? Runtime error, compile error

২য় কথা হলো,
অতিরিক্ত কোনো কিছু প্রিন্ট করা যাবে না ..
যেভাবে আউটপুট দিতে বলা হইছে, ঠিক সেইভাবে আউটপুট দিতে হবে

মনে করেন, আপনাকে ২টা সংখ্যা যোগ করতে বলা হলো
Sample input
1 2
Sample output
3

আপনি যেটা করবেন, প্রথমে ইনপুট নিবেন

scanf ("%d %d", &a, &b);

তারপর আউটপুট দিবেন

printf ("summation = %d", a + b);    // wrong!!

বা

printf ("ans %d", a + b);    // wrong!!

যেভাবে দিতে হবে:

printf ("%d\n", a + b);    // correct!! 

একটা নাম্বার প্রিন্ট করতে বলা হইছে, জাস্ট নাম্বারটাই প্রিন্ট করবেন ..
অতিরিক্ত কোনো কিছুই প্রিন্ট করা যাবে না ..
একটা অতিরিক্ত space (” “) ও যদি প্রিন্ট করেন তাহলেও হবে না .. বোঝা গেল বিষয়টা?

খেয়াল করেন, প্রিন্ট করার পর আমি একটা নিউলাইন দিয়েছি .. এইটা দিতে হবে ..
প্রোগ্রামের সব প্রিন্ট করার কাজ শেষ হয়ে যাবার পর একটা নিউলাইন দিতে হবে

৩য় কথা হলো,
অনেকগুলা ইনপুট থাকবে .. এবং আপনার প্রোগ্রাম একবার রান করেই সব ইনপুট প্রসেস করে আউটপুট দিতে হবে
তাই এইভাবে করলে হবে না

int main(int argc, const char ** argv[])
{
    int a;
    int b;
    
    scanf ("%d %d", &a, &b);
    
    printf ("%d\n", a + b);

    return 0;
} 

কারণ হলো, এই প্রোগ্রাম একবার ইনপুট নিবে, একবার আউটপুট দিবে, তারপর বন্ধ হয়ে যাবে
কিন্তু Judge-দের ইনপুট অনেকগুলা থাকে (একটা ফাইলের মধ্যে)
তাই আপনাকে যেটা করতে হবে, ইনপুট নিবেন, আউটপুট দিবেন, আবার ইনপুট নিবেন ….
এইভাবে চলতে থাকবে .. যতক্ষণ পর্যন্ত না Judge-দের ইনপুট ফাইল শেষ হয়
আপনাকে করতে হবে এইভাবে

int main(int argc, const char ** argv[])
{
    int a;
    int b;
    
    while ( scanf ("%d %d", &a, &b) != EOF ) {

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

    return 0;
} 

এইটার মানে হলো,
আপনার প্রোগ্রাম একটার পর একটা ইনপুট নিতেই থাকবে, যতক্ষণ না পর্যন্ত EOF (End Of File) পাওয়া যায়
আপনি যদি Windows OS ব্যবহার করেন তাহলে EOF হলো, ctrl + z

এবার আসি, Judge Response এবং সেগুলার অর্থ কি, সেই বিষয়ে

Compile Error = প্রোগ্রাম কম্পাইল করা যায় নাই।
এই ধরনের Response আসলে, ওই Response-এর লিঙ্কে ক্লিক করলে এররটা জানা যাবে

Presentation Error = প্রোগ্রামের আউটপুট ঠিক আছে, কিন্তু ঠিক ভাবে প্রেজেন্ট করা হয় নাই।
যেমন, আপনি ঠিকভাবে নিউলাইন, স্পেস দেন নাই .. অথবা বেশি নিউলাইন, স্পেস দিছেন

Runtime Error = প্রোগ্রাম রান করতে গিয়ে এরর .. বা, রান করতে করতে এরর
বেশিরভাগ ক্ষেত্রে এই এররটার কারণ হলো, এরে সাইজ কম নেয়া
০ (শূন্য) দিয়ে কোনো সংখ্যা কে ভাগ করলেও এই এরর হবে

Time Limit Exceed = আউটপুট দিতে আপনার প্রোগ্রাম অনেক সময় নিচ্ছে
সময় কি বাংলালিঙ্ক দামে পাইছেন নাকি? এত সময় দেয়া যাবে না
এই এরর-এর কারণ হলো, দুর্বল লজিক .. বা, আপনার প্রোগ্রামের লুপ শেষ হয় না, ঘুরতেই থাকে

Wrong Answer = আউটপুট ভুল

Accepted = আপনার প্রোগ্রামে নাকি কোনো এরর নাই! সবকিছু পারফেক্ট!! .. এইটা কোনো কথা হইলো? আজিব!

UIU: Beginner’s Practice Contest – 03 (solutions)


Link: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=24540#overview
Password: UIU#

Mostafiz (Rank 1)
কোডিং স্টাইল অনেক ক্লিন .. বেশ ছোট এবং কম্প্যাক্ট কোডিং স্টাইল ..
তবে ইন্ডেন্টেশন ঠিক নাই .. ওটা ঠিক থাকলে কোড গুলা দেখতেও ভালো লাগবে
প্রবলেম D, E, J-এর কোডিং ভালো লাগলো

​Cyborn13x​ (Rank 2)
STL-এর বেশ বড় ফ্যান মনে হচ্ছে
কোডিং স্টাইল একটু কঠিন হলেও সবখানেই গুড প্রোগ্রামিং প্র্যকটিস লক্ষ্য করা যায়
প্রবলেম D, G, J-এর কোডিং ভালো লাগলো

rima (Rank 3)
চিন্তা ভাবনা একটু কঠিন .. যদিও কোডিং স্টাইল সুন্দর
ভেঙ্গে ভেঙ্গে কোড করা .. এতে করে যদিও কোড গুলা বড় হয় কিন্তু বুঝতে সুবিধা
প্রবলেম E, G-এর কোডিং ভালো লাগলো

প্রথম ৫টা প্রবলেমের সল্যুশন:
https://tausiq.wordpress.com/2013/05/21/uiu-beginners-practice-contest-01-solutions/

Analysis of Problem F:

হাসমত ভাই এবং তার শত্রুপক্ষের সৈন্য সংখ্যা দেয়া আছে
এই ২টা সংখ্যার পার্থক্য বের করতে হবে
খুবই বাংলা প্রবলেম .. বিয়োগ করে দিলেই হবে
কিন্তু অনেকেই একটা ভুল করে .. সেটা হলো ২^৩২
যে ২টা নাম্বার ইনপুট দেয়া হবে সেগুলা ২^৩২ থেকে বড় হবে না
২^৩২ = ৪২৯৪৯৬৭২৯৬
এত বড় নাম্বার int রেঞ্জ ক্রস করবে, তাই long long নিতে হবে

আশা করি, আমরা জানি abs () কি জিনিস
abs () = absolute value

abs (1) = 1
abs (-1) = 1

কিন্তু abs হলো absolute value of Integer
আমরা যেহেতু long long নিলাম তাই llabs() ব্যবহার করব


//
//  main.cpp
//  TestCpp
//
//  Created by Shahab Uddin on 05/21/13.
//  Copyright (c) 2013 ___Shahab__. All rights reserved.
//

#include <cstdio>
#include <cstdlib>

int main(int argc, const char * argv[])
{
    long long a;
    long long b;

    while ( scanf ("%lld %lld", &a, &b) != EOF ) {
        printf ("%lld\n", llabs(a - b));
    }

    return 0;
} 

===================

Analysis of Problem G:

presentation error খাইতে খাইতে কার কার মনে হইছে “মাইরালা আম্রে মাইরালা”, তারা হাত তুলেন
প্রবলেম সহজ .. অনেকেই সলভ করে ফেলছেন .. কিন্তু প্রবলেম হলো presentation error

প্রথমে আসি, প্রবলেমটায় আমাদের কি করতে হবে
সহজ করে বললে একটা লাইন দেয়া আছে .. আমাদের ওয়ার্ড গুলা রিভার্স করে দিতে হবে

১ম লাইনে থাকবে test case, এর মানে হলো, আমাদের কতগুলা ডেটা সেট দেয়া হবে
তারপর ২য় লাইনে একটা খালি লাইন থাকবে
৩য় লাইনে থাকবে, ১ম ডেটা সেটে কতগুলা লাইন থাকবে
তারপরে, ৩য় লাইনে যে সংখ্যা ছিল, ততগুলা বাক্য

বাক্য গুলা শেষ হলে একটা খালি লাইন থাকবে
তারপরে থাকবে একটা সংখ্যা, ২য় ডেটা সেটে কতগুলা লাইন থাকবে
তারপরে থাকবে ২য় ডেটা সেটের বাক্য গুলা …

একটা উদাহরণ দেই,

Sample Input 
3
<-- blank line -->
3
I am happy today
To be or not to be
I want to win the practice contest 
<-- blank line -->
1
contest running 
<-- blank line -->
4
How are you 
I am fine 
I am happy today
To be or not to be
<-- end of file -->

Sample Output
I ma yppah yadot
oT eb or ton ot eb
I tnaw ot niw eht ecitcarp tsetnoc
<-- blank line -->
tsetnoc gninnur
<-- blank line -->
woH era uoy
I ma enif
I ma yppah yadot
oT eb or ton ot eb
| <<-- this is the cursor

ট্রিকস হলো, ডেটা সেটগুলার মাঝখানে একটা করে অতিরিক্ত লাইন প্রিন্ট করতে হবে
আমি একটা উদাহরণ দেই
মনে করেন, আপনাকে আমি প্রিন্ট করতে বললাম: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

for ( int i = 1; i <= 10; i++ ) {
    printf ("%d, ", i);
}

output: 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 

হলো না, ১০ এর পরে একটা কমা চলে আসছে
আমরা যেটা করি,
প্রথমে ১ প্রিন্ট করে দেই
তারপর থেকে “, %d” এইভাবে প্রিন্ট করি

bool space = false;

for ( int i = 1; i <= 10; i++ ) {
    if (space) printf (", ");
    space = true;

    printf ("%d", i);
}

output: 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

#১: একটা ভ্যারিয়েবল নিলাম, space = false, মানে হলো, ফার্স্ট টাইম আমাদের space লাগবে না
#৩: আমাদের লুপ শুরু হলো
#৪: space = false, তাই এই লাইন কাজ করবে না .. তার মানে, “, ” প্রিন্ট হবে না
কিন্তু তারপরে লাইনে আমরা space = true করে দিলাম, তার মানে, এরপর থেকে প্রতিবার “, ” প্রিন্ট হবে

এবার আমরা স্ট্রিং টোকেন বলে একটা জিনিস শিখব .. যারা জানেন তারা তো জানেনই
যারা জানেন না তাদের জন্য বলছি
স্ট্রিং টোকেন মানে হলো, একটা স্ট্রিং কে টোকেনে ভাগ করে ফেলা
উদাহরণ দিলে ক্লিয়ার হবে
নিচের কোড রান করে দেখি

#include <cstdio>
#include <cstring>

using namespace std;

int main(int argc, const char * argv[])
{
    char string [100] = "This is a contest";

    char *pch;
    pch = strtok (string, " ");

    while ( pch != NULL ) {
        printf ("%s\n", pch);
        pch = strtok(NULL, " ");
    }

    return 0;
}

output: 
This
is
a
contest

আমরা স্ট্রিংটা (space) টোকেন দিয়ে ভাগ করে ফেললাম
#১০: একটা char পয়েন্টার লাগবে
#১১: স্ট্রিংটা আমরা space দিয়ে ভাগ করব
#১৩: যতক্ষণ পর্যন্ত টোকেন পাওয়া যাবে ততক্ষণ পর্যন্ত ঘুরব .. NULL মানে টোকেন শেষ
#১৪: টোকেন প্রিন্ট করলাম
#১৫: নেক্সট টোকেন নিলাম

এবার আপনাদের বলতে হবে নিচের কোডের আউটপুট কি?
তাহলে বুঝা যাবে আপনারা স্ট্রিং টোকেন জিনিসটা বুঝতে পারলেন কিনা

#include <cstdio>
#include <cstring>

using namespace std;

int main(int argc, const char * argv[])
{
    char string [100] = "This,is,a contest and this is another,line";

    char *pch;
    pch = strtok (string, ",");

    while ( pch != NULL ) {
        printf ("%s\n", pch);
        pch = strtok(NULL, ",");
    }

    return 0;
} 

এরপরে আমরা সবচাইতে সহজ পদ্ধতিতে রিভার্স করা শিখব

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[])
{
    char string [100] = "This is a string";

    reverse(string, string + strlen(string));

    printf ("%s\n", string);

    return 0;
}

রিভার্স ফাংশন, এটা পাওয়া যাবে algorithm header file-এ
খুবই সহজ .. প্রথমে স্ট্রিংটা দিবেন, তারপর স্ট্রিং + স্ট্রিংটার length

কেউ কি বলতে পারেন, reverse function-এর parameter গুলার অর্থ কি?
মানে প্রথমে স্ট্রিং, তারপর স্ট্রিং + স্ট্রিংটার length কেন দিতে হয়, এটার মানে কি?

এবার আমরা সরাসরি আমাদের কোডটা দেখি


//
//  main.cpp
//  TestCpp
//
//  Created by Shahab Uddin on 05/21/13.
//  Copyright (c) 2013 ___Shahab__. All rights reserved.
//

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[])
{
    int testCases;
    scanf ("%d", &testCases);
    bool blankLine = false;

    while ( testCases-- ) {
        int lineNumber;
        scanf ("%d", &lineNumber);
        getchar();

        char line [1000];

        if (blankLine) printf ("\n");
        blankLine = true;

        while (gets(line) && strlen(line)) {

            char *pch;
            pch = strtok(line, " ");
            bool space = false;

            while ( pch != NULL ) {
                reverse(pch, pch + strlen(pch));

                if (space) printf (" ");
                space = true;

                printf("%s", pch);

                pch = strtok(NULL, " ");
            }

            printf ("\n");
        }
    }

    return 0;
} 

#১৯: প্রথমে আমরা কোনো অতিরিক্ত নিউলাইন প্রিন্ট করব না .. ২য় ডেটাসেট থেকে আমরা অতিরিক্ত নিউলাইন প্রিন্ট করব

#২৪: লাইন নাম্বার ইনপুট দেয়ার পর আমরা enter প্রেস করি .. এই enter-টাকে gets() ইনপুট হিসেবে নেয়
এই enter-কে বাদ দেয়ার জন্য আমরা getchar() দিলাম

#২৮-২৯: ডেটাসেট প্রিন্ট করার আগে আমরা আগের লজিক অনুযায়ী, ১ম ডেটাসেট বাদ দিয়ে, ২য় ডেটাসেট থেকে অতিরিক্ত নিউলাইন প্রিন্ট করব

#৩১: gets দিয়ে ইনপুট নিতে থাকব .. থামব কখন?
যখন আমরা একটা খালি লাইন পাব (বা আমাদের ইনপুট ফাইল শেষ হয়ে যাবে) তখন আমরা বুঝব আমাদের ডেটাসেট শেষ
অথবা,
আমরা একটা লুপ চালাতে পারি যেটা lineNumber পর্যন্ত ঘুরবে এবং ইনপুট নিবে
যেকোনো একটা করলেই হবে
আমি যেই লুপটা দিলাম সেটা থামবে যখন strlen(line) == ০ হবে .. মানে একটা খালি নিউলাইন, যার length ০

#৩৩-৩৪: স্ট্রিং টোকেন নিয়ে আমরা আগেই আলোচনা করেছি

#৩৮: প্রতিটা টোকেন রিভার্স করে দিলাম

#৪০-৪১: আগের মতই, প্রথম ওয়ার্ড-এর আগে কোনো space প্রিন্ট করব না .. তবে তারপরের ওয়ার্ডগুলার আগে একটা করে space প্রিন্ট করব

===================

Analysis of Problem H:

একটা recursive function f91(N) দেয়া আছে
যদি N <= 100 হয় তাহলে, f91(N) = f91(f91(N + 11))
নাহলে, f91(N) = N - 10

কঠিন কিছু দেখি না
এমন একটা recursive function লিখে ফেলেন,তাহলেই কাজ শেষ


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

int f91(int n)
{
    if ( n <= 100 )
        return f91(f91(n + 11));
    else
        return n - 10;
}

int main(int argc, const char * argv[])
{

    int n;

    while ( scanf ("%d", &n) != EOF ) {
        if (n == 0)
            break;

        printf ("f91(%d) = %d\n", n, f91(n));
    }

    return 0;
}

// @END_OF_SOURCE_CODE

===================

Analysis of Problem I:

একটা প্যাটার্ন খুঁজে বের করতে হবে
প্রথমে 0, 1, 4, 5, 8, 9, 12 এই সংখ্যাগুলো ভালো করে দেখেন

(0, 0) = 0
(1, 1) = 1
(2, 2) = 4
(3, 3) = 5
(4, 4) = 8
(5, 5) = 9
(6, 6) = 12
(7, 7) = ?

পয়েন্ট ১: এইখানে x এবং y সমান
পয়েন্ট ২: যদি x এবং y জোড় হয় তাহলে, x + y
যদি বেজোড় হয় তাহলে x + y – 1

এইবার, 2, 3, 6, 7, 10, 11 এই সংখ্যাগুলো ভালো করে দেখেন

(2, 0) = 2
(3, 1) = 3
(4, 2) = 6
(5, 3) = 7
(6, 4) = 10
(7, 5) = 11
(8, 6) = ?

পয়েন্ট ১: এইখানে x বড় এবং y ছোট .. x কত বড়? .. x সবসময় y + 2 বড়
পয়েন্ট ২: আবার একই রকম করে, যদি x এবং y জোড় হয় তাহলে, x + y
যদি বেজোড় হয় তাহলে x + y – 1

তাহলে কখন No Number প্রিন্ট করতে হবে?

যদি x এবং y সমান না হয়
এবং, x == y + 2 না হয়
তাই না?


//
//  main.cpp
//  TestCpp
//
//  Created by Shahab Uddin on 05/21/13.
//  Copyright (c) 2013 ___Shahab__. All rights reserved.
//

#include <cstdio>

int main(int argc, const char * argv[])
{

    int testCases;
    scanf ("%d", &testCases);

    while ( testCases-- ) {
        int x, y;
        scanf ("%d %d", &x, &y);

        if ( x == y || x - y == 2 ) {
            printf ("%d\n", x % 2 == 0 ? x + y : x + y - 1);
        } else {
            printf ("No Number\n");
        }
    }

    return 0;
} 

#২২: যদি if দিয়ে লিখি,

if (x % 2 == 0)
    printf ("%d\n", x + y);
else 
    printf ("%d\n", x + y - 1);

===================

Analysis of Problem J:

কেন যে এত কঠিন প্রবলেম দিতে গেলাম! নিজে বুঝতে পারলেও পোলাপানরে এখন কেমনে বুঝাই? 😦

মম মানে এইটা হলো মনে করেন, ভেড়ার প্রবলেম
ভেড়া চিনেন তো? ওই ভেড়া আর কি
তো ভেড়ার প্রবলেম ভেড়ারা সলভ করবে, আমাদের টেনশন করার কি দরকার! তাই না?

কিন্তু একটা সমস্যা .. ভেড়ারা তো জানে না কিভাবে প্রোগ্রামিং করতে হয় ..
তাই ভেড়ার প্রবলেমও আমাদেরকেই সলভ করতে হবে 😦

আচ্ছা আমরা প্রথমে প্রবলেমটা বুঝার চেষ্টা করি
আমাদেরকে একটা মাঠ দেয়া আছে, যেখানে অনেকগুলা ভেড়া আছে
মনে করেন, ৯টা ভেড়া আছে, এবং ওদের একটা করে নাম্বার দিয়ে দিলাম ১ থেকে ৯

12304
00500
60789

১ থেকে ৯ হলো ভেড়া
আর ০ গুলা হলো ঘাস

এখন দেখেন, ১, ২, ৩ নাম্বার ভেড়া একসাথে আছে, তাই না?
আবার ৩ নাম্বার ভেড়ার সাথে ৫ নাম্বার ভেড়াও আছে
৫ নাম্বার ভেড়ার সাথে ৭ নম্বর ভেড়াও আছে
এবং ৭ নাম্বার ভেড়ার সাথে ৮, ৯ নাম্বার ভেড়া আছে

তাহলে বলা যায় ১, ২, ৩, ৫, ৭, ৮, ৯ এই ভেড়াগুলা একসাথে আছে .. এরা হলো একটা ভেড়ার গ্রুপ

কিন্তু দেখেন ৪ নাম্বার ভেড়াটা একলা আছে .. সে একা একাই একটা গ্রুপ করছে
মানে, এমন একটা ভেড়ার গ্রুপ, যেখানে ভেড়ার সংখ্যা ১ টা

এবং একইভাবে ৬ নাম্বার ভেড়াও একলা একটা ভেড়ার গ্রুপ

আমাদেরকে বলতে হবে মাঠে কয়টা ভেড়ার গ্রুপ আছে

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

এইবার আমাকে বলেন, যদি # গুলা ভেড়া হয় .. এবং . গুলা ঘাস হয়
তাহলে নিচের মাঠে কয়টা ভেড়ার গ্রুপ আছে?

#.#.
.#.#
#.##
.#.#

২টা ভেড়া কোনাকুনি থাকলে তারা একই গ্রুপের হবে না
উপরে, নিচে, ডানে, বামে থাকলে হবে

উত্তর হলো: ৬টা ভেড়ার গ্রুপ

আমরা যা করব সেটা হলো,
মাঠের প্রথম থেকে শেষ পর্যন্ত যাব
যখনই একটা ভেড়া পাব তখন থামব
সেই ভেড়া এবং সেই গ্রুপের সব ভেড়াকে vanish করে দিব
তারপর আবার চলতে শুরু করব

তারমানে, আমরা যতবার থামবো ততগুলা ভেড়ার গ্রুপ মাঠে ছিল .. তাই না?
কারণ, একটা ভেড়া পাওয়ার সাথে সাথে সেই গ্রুপের সব ভেড়াকে vanish করে দিচ্ছি
তাহলে নেক্সট টাইম যখন আমরা আরেকটা ভেড়া পাব, সেটা আসলে অন্য গ্রুপের ভেড়া

ব্যস অনেক হইছে! .. নিচে কোড দেয়া আছে, যা বুঝার বুঝে নেন


//
//  main.cpp
//  TestCpp
//
//  Created by Shahab Uddin on 05/21/13.
//  Copyright (c) 2013 ___Shahab__. All rights reserved.
//

#include <cstdio>

int h, w;
char grid [100 + 5] [100 + 5];

bool isValid(int row, int col)
{
    if (row >= 0 && row < h && col >= 0 && col < w)
        return true;

    return false;
}

void killAllFlocksOf(int row, int col)
{
    if (!isValid (row, col)) {
        return;
    }

    if (grid [row] [col] == '.') return;

    grid [row] [col] = '.';

    // up
    killAllFlocksOf(row - 1, col);

    // right
    killAllFlocksOf(row, col + 1);

    // down
    killAllFlocksOf(row + 1, col);

    // left
    killAllFlocksOf(row, col - 1);
}

int main(int argc, const char * argv[])
{

    int testCases;
    scanf ("%d", &testCases);

    while ( testCases-- ) {
        scanf ("%d %d", &h, &w);

        for ( int i = 0; i < h; i++ )
            scanf ("%s", grid[i]);

        int ans = 0;

        for ( int row = 0; row < h; row++ ) {
            for ( int col = 0; col < w; col++ ) {
                if (grid [row] [col] == '#') {
                    ans++;
                    killAllFlocksOf(row, col);
                }
            }
        }

        printf ("%d\n", ans);
    }

    return 0;
} 

আরেকটু বুঝাতে হবে?

আচ্ছা ঠিক আছে আরেকটু বুঝাই

আগে আমরা কোডটা নিজেরা একটু ভালোভাবে দেখি

#১২: আমরা মাঠের ইনফরমেশনগুলা রাখব grid array-টার মধ্যে
মানে কোথায় ভেড়া আছে, আর কোথায় ঘাস আছে

#৫১-৫২: ইনপুট নিলাম

#৫৬-৫৭: একদম top-left থেকে শুরু করে পুরা মাঠ আমরা ঘুরব

#৫৮: যখনি একটা ভেড়া পাব, সাথে সাথে ans++ করব
এবং ওই গ্রুপের সব ভেড়াকে vanish করে দিব

#৬০: killAllFlocksOf() – এই function কে যদি আপনি একটা ভেড়ার কথা বলে দেন, তাহলে
সে ঘুরে ঘুরে ওই গ্রুপের সব ভেড়াকে vanish করে দিবে

এখন কথা হলো killAllFlocksOf() কিভাবে কাজ করে
এটা একটা recursive function

#২৪-২৬:
আমরা একটা পজিশন পেলাম row and col
মানে, কত নাম্বার row এবং কত নাম্বার column

শুধু পজিশন পেলেই হবে না .. আমাদের কে যাচাই করতে হবে আসলেই পজিশনটা ঠিক কিনা
মনে করেন, একদম top-left পজিশনটা হলো row = ০ and col = ০
এই পজিশনের কিন্তু উপরে বা বামে কিছু নাই! তাই না?
এইজন্য আমরা row, col পেলে যাচাই করে দেখব পজিশনটা ঠিক কিনা

#১৪-২০:
isValid function আমাদের বলবে যে, একটা row and column valid কিনা
আমাদের row-এর value সবচেয়ে কম ০ হতে পারে
আর সবচেয়ে বেশি হতে পারে h – 1 [ h is height ]

আমাদের col-এর value সবচেয়ে কম ০ হতে পারে
আর সবচেয়ে বেশি হতে পারে w – 1 [ w is width ]

এই ব্যপারটাই আমরা isValid function দিয়ে চেক করলাম
যদি সবকিছু ঠিক থাকে তাহলে return করব true
নাহলে false

#২৮:
আমরা যে row and col পেলাম, সেটা যদি একটা ঘাস হয় তাহলে লাভ কি?
আমাদের তো ভেড়া দরকার, আমরা ভেড়া vanish করব, তাই না?
তাই আমরা যদি ঘাস পাই তাহলে return

#৩০:
লাইন ৩০-এ চলে আসা মানে, আমাদের row and col valid
এবং আমাদের row and col ঘাস না, অবশ্যই ভেড়া
এইবার এইটাকে আমরা vanish করব ..
ওই পজিশনে আমরা একটা ঘাস দিয়ে দিলাম .. মানে, ভেড়াটা vanish হয়ে গেল

#৩৩
এইবার আমরা দেখব, উপরে কোনো ভেড়া আছে কিনা
তারমানে row – 1 হবে, কিন্তু column একই থাকবে

#৩৬-৪২
একইভাবে আমরা ডানে, নিচে, বামে ভেড়া আছে কিনা দেখব
ভেড়া vanish করার কাজটা কে করে? — killAllFlocksOf() function করে
তাই আমরা উপরে, নিচে, ডানে, বামের পজিশনগুলা দিয়ে killAllFlocksOf() function call করব

UIU: Beginner’s Practice Contest – 01 (solutions)


Link: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=22375#overview
Password: UIU

Analysis of Problem A:

প্রবলেম এ বলা আছে, একটা স্ট্রিং দেয়া থাকবে
সেই স্ট্রিং টার রিভার্স স্ট্রিং আউটপুট দিতে হবে
বেশি রকমের সহজ প্রবলেম।
নিশ্চয়ই আপনি জানেন কিভাবে স্ট্রিং রিভার্স করতে হয় … (না জানলে আপনার খবর আছে)
তবে চাইলে এইখানে একটা ছোট বুদ্ধি করা যায়
জাস্ট উল্টা করে স্ট্রিংটা প্রিন্ট করে দিলেই হচ্ছে
আপনি আসলেই স্ট্রিং রিভার্স করছেন কিনা, সেটা কে দেখতে আসবে?
তবে strrev() ফাংশন ব্যবহার করা যাবে না, কারণ এইটা ANSI-C স্ট্যান্ডার্ড না


#include <cstdio>
#include <cstring>

using namespace std;

int main ()
{

	char str [20 + 5];

	scanf ("%s", str);

	int length = strlen(str);

	for ( int i = length - 1; i >= 0; i-- )
		printf ("%c", str [i]);

	printf ("\n");

	return 0;
}

Watch out!

scanf function return type documentation:

… If a reading error happens or the end-of-file is reached while reading, the proper indicator is set (feof or ferror). And, if either happens before any data could be successfully read, EOF is returned …
Source: http://www.cplusplus.com/reference/cstdio/scanf/?kw=scanf

gets function return type documentation:

… If the end-of-file is encountered while attempting to read a character, the eof indicator is set (feof). If this happens before any characters could be read, the pointer returned is a null pointer …
Source: http://www.cplusplus.com/reference/cstdio/gets/?kw=gets

বাংলা কথা হলো,
যখন আপনার প্রোগ্রাম ইনপুট নিতে নিতে ফাইলের শেষে চলে আসে তখন
gets রিটার্ন করে null pointer
এবং scanf রিটার্ন করে EOF


char str [20 + 5];

// this is wrong!
while ( gets (str) != EOF ) {
    ...
} 

// this is correct!
while ( gets (str) ) {
    ...
}

// you should not do this, unless you know otherwise 
while ( scanf ("%d", &n) ) {
    ...
}

// try to maintain this style 
while ( scanf ("%d", &n) != EOF ) {
    ...
}

===================

Analysis of Problem B:

অনেক কঠিন! একটা জ্যামিতির প্রবলেম
তিনটি বাহুর দৈর্ঘ্য দেয়া আছে, বলতে হবে তারা সমকোণী ত্রিভুজ গঠন করে কিনা

এখন আবার জিজ্ঞেস কইরেন না, সমকোণী ত্রিভুজ কি জিনিস!
(পোলাপানগুলারে খাইতে দিলে শুইতে চায়!)

http://www.mathsisfun.com/triangle.html

Equilateral Triangle = সমবাহু ত্রিভুজ
Isosceles Triangle = সমদ্বিবাহু ত্রিভুজ
Scalene Triangle = বিষমভূজ ত্রিভুজ
Acute Triangle = সুক্ষকোণী ত্রিভুজ
Right Triangle = সমকোণী ত্রিভুজ
Obtuse Triangle = স্থুলকোণী ত্রিভুজ

ট্রিকস:
“সমকোণী ত্রিভুজ” কথাটা দেখলেই ৯৮% ক্ষেত্রে পিথাগোরাসের উপপাদ্য চলে আসে

সুত্রটা সহজ,
অতিভূজ * অতিভূজ = (১ম বাহু * ১ম বাহু) + (২য় বাহু * ২য় বাহু)
প্রবলেমের তিনটা বাহু এই সূত্র মেনে চললে তারা সমকোণী ত্রিভুজ

একটা সমস্যা হলো, তিনটা বাহু দেয়া আছে, কিন্তু
কোনটা ১ম বাহু,
কোনটা ২য় বাহু এবং
কোনটা অতিভূজ সেটা তো বলা নাই

তাহলে যেটা করা যায়, তিনটা কম্বিনেশনই চেক করে দেখতে হবে
যেমন ধরি আমাদের ৩ টা বাহু দেয়া আছে: A, B, C

১ম কম্বিনেশন-এ আমরা ধরে নিব,
A = অতিভূজ এবং
B, C হলো ১ম বাহু এবং ২য় বাহু

২য় কম্বিনেশন-এ আমরা ধরে নিব,
B = অতিভূজ এবং
A, C হলো ১ম বাহু এবং ২য় বাহু

৩য় কম্বিনেশন-এ আমরা ধরে নিব,
C = অতিভূজ এবং
A, B হলো ১ম বাহু এবং ২য় বাহু


#include <cstdio>

using namespace std;

int main ()
{

	int testCases;
	scanf ("%d", &testCases);

	while ( testCases-- ) {
		int a, b, c;
		scanf ("%d %d %d", &a, &b, &c);

		if ((a * a) == (b * b) + (c * c))
			printf ("YES\n");

		else if ((b * b) == (a * a) + (c * c))
			printf ("YES\n");

		else if ((c* c) == (a * a) + (b * b))
			printf ("YES\n");

		else
			printf ("NO\n");
	}

	return 0;
}

===================

Analysis of Problem C:

একটা সংখ্যা দিবে n
এমন ৪ টা সংখ্যা বের করতে হবে যেগুলা যোগ করলে n হয়

তার মানে আমাদের কাছে ৪ টা খালি ঘর আছে

___ + ___ + ___ + ___ = n

একটা কাজ করি
প্রবলেমটার একটা ছোট ভার্সন নিয়ে কাজ করি
ছোট ভার্সন সলভ করার পর আসল প্রবলেমটা নিয়ে কাজ করব
ধরি আমাদের ২ টা সংখ্যা বের করতে হবে যেগুলা যোগ করলে n হয়
তাহলে আমাদের ২ টা খালি ঘর পূরণ করতে হবে

___ + ___ = n

১ম ঘরে ০-৯ পর্যন্ত যেকোনো সংখ্যা বসতে পারে
আমরা যেটা করব, একটা একটা করে ০-৯ পর্যন্ত সবগুলা সংখ্যা ১ম ঘরে বসাবো

০ + ___ = n
১ + ___ = n
২ + ___ = n
৩ + ___ = n
৪ + ___ = n
৫ + ___ = n
৬ + ___ = n
৭ + ___ = n
৮ + ___ = n
৯ + ___ = n

এইবার ২য় ঘরে সংখ্যা বসানোর পালা
২য় ঘরেও কিন্তু ০-৯ পর্যন্ত যেকোনো সংখ্যা বসতে পারে

১ম ঘরে যখন ০ বসলো তখন ২য় ঘরে কি বসতে পারে?

উত্তর: ০-৯ পর্যন্ত যেকোনো সংখ্যাই বসতে পারে

ওকে, দেখি বসানোর পর কেমন দেখায়

০ + ০ = n
০ + ১ = n
০ + ২ = n
০ + ৩ = n
০ + ৪ = n
০ + ৫ = n
০ + ৬ = n
০ + ৭ = n
০ + ৮ = n
০ + ৯ = n

মানে প্রথম ঘরে যখন ০ হলো, তখন ২য় ঘরে ০-৯ সবগুলা কম্বিনেশন বসালাম
একইভাবে যখন ১ম ঘরে ১ হবে তখন ২য় ঘরে ০-৯ পর্যন্ত যেকোনো সংখ্যা হতে পারে

মনে করি আমাদের n = ১১
আমাদের এমন ২ টা সংখ্যা বের করতে হবে যাদের যোগফল n
তখন পুরো ব্যাপারটা দেখাবে এরকম

0 + 0 = 0
0 + 1 = 1
0 + 2 = 2
0 + 3 = 3
0 + 4 = 4
0 + 5 = 5
0 + 6 = 6
0 + 7 = 7
0 + 8 = 8
0 + 9 = 9
1 + 0 = 1
1 + 1 = 2
1 + 2 = 3
1 + 3 = 4
1 + 4 = 5
1 + 5 = 6
1 + 6 = 7
1 + 7 = 8
1 + 8 = 9
1 + 9 = 10
2 + 0 = 2
2 + 1 = 3
2 + 2 = 4
2 + 3 = 5
2 + 4 = 6
2 + 5 = 7
2 + 6 = 8
2 + 7 = 9
2 + 8 = 10
2 + 9 = 11
3 + 0 = 3
3 + 1 = 4
3 + 2 = 5
3 + 3 = 6
3 + 4 = 7
3 + 5 = 8
3 + 6 = 9
3 + 7 = 10
3 + 8 = 11
3 + 9 = 12
4 + 0 = 4
4 + 1 = 5
4 + 2 = 6
4 + 3 = 7
4 + 4 = 8
4 + 5 = 9
4 + 6 = 10
4 + 7 = 11
4 + 8 = 12
4 + 9 = 13
5 + 0 = 5
5 + 1 = 6
5 + 2 = 7
5 + 3 = 8
5 + 4 = 9
5 + 5 = 10
5 + 6 = 11
5 + 7 = 12
5 + 8 = 13
5 + 9 = 14
6 + 0 = 6
6 + 1 = 7
6 + 2 = 8
6 + 3 = 9
6 + 4 = 10
6 + 5 = 11
6 + 6 = 12
6 + 7 = 13
6 + 8 = 14
6 + 9 = 15
7 + 0 = 7
7 + 1 = 8
7 + 2 = 9
7 + 3 = 10
7 + 4 = 11
7 + 5 = 12
7 + 6 = 13
7 + 7 = 14
7 + 8 = 15
7 + 9 = 16
8 + 0 = 8
8 + 1 = 9
8 + 2 = 10
8 + 3 = 11
8 + 4 = 12
8 + 5 = 13
8 + 6 = 14
8 + 7 = 15
8 + 8 = 16
8 + 9 = 17
9 + 0 = 9
9 + 1 = 10
9 + 2 = 11
9 + 3 = 12
9 + 4 = 13
9 + 5 = 14
9 + 6 = 15
9 + 7 = 16
9 + 8 = 17
9 + 9 = 18

ঠিক এরকমভাবে আমরা সবগুলা কম্বিনেশন বের করব
তার মানে দাড়ালো, কে কে ১১ বানাতে পারে?
2 + 9
3 + 8
4 + 7
5 + 6
6 + 5
7 + 4
8 + 3
9 + 2

আসলে আমাদের আউটপুট দিতে হবে, কতগুলা লাইনে যোগফল ১১ পাওয়া গেল
যেমন এইখানে আমরা ৮ টা লাইন পেলাম যাদের যোগফল ১১
সুতরাং আউটপুট ৮

একইভাবে যদি ৪-টা সংখ্যা বের করতে হয় (যাদের যোগফল n), তাহলেও প্রসেস টা একই হবে

১। ৪-টা ঘর পূরণ করার জন্য আমরা ০-৯ পর্যন্ত সংখ্যা দিয়ে ট্রাই করব
২। যেগুলার যোগফল n হবে সেগুলার জন্য ans++ করব
৩। এই ans++ টাই আউটপুট হবে


//
//  main.cpp
//  TestCpp
//
//  Created by Shahab Uddin on 05/21/13.
//  Copyright (c) 2013 ___Shahab__. All rights reserved.
//

#include <cstdio>

int main(int argc, const char * argv[])
{
    int n;

    while ( scanf ("%d", &n) != EOF ) {

        int ans = 0;

        for ( int a = 0; a <= 9; a++ ) {
            for ( int b = 0; b <= 9; b++ ) {
                for ( int c = 0; c <= 9; c++ ) {
                    for ( int d = 0; d <= 9; d++ ) {
//                    printf ("%d + %d + %d + %d = %d\n", a, b, c, d, a + b + c + d);

                        if (a + b + c + d == n)
                            ans++;
                    }
                }

            }
        }

        printf ("%d\n", ans);
    }

    return 0;
}

এখন আপনাদের জন্য ছোট একটা কাজ

একটু আগেই আমরা দেখালম n = ১১
আমাদের এমন ২ টা সংখ্যা বের করতে হবে যাদের যোগফল n
এবং আমরা বের করলাম
2 + 9
3 + 8
4 + 7
5 + 6
6 + 5
7 + 4
8 + 3
9 + 2

কিন্তু ২+৯ এবং
৯ + ২ তো একই জিনিস, তাই না?
আমরা এইগুলা বাদ দিতে চাই

অর্থাৎ আমরা আসলে চাই,
2 + 9
3 + 8
4 + 7
5 + 6

আপানদের জন্য নতুন প্রবলেম হলো,
একটা নাম্বার n দেয়া থাকবে
আউটপুট হবে, এমন ৪-টা নাম্বারের কম্বিনেশন যাদের যোগ করলে n হয়
কম্বিনেশন মানে হলো, একই ৪ টা নাম্বার, আবার থাকতে পারবে না

sample input: 
11
sample output:
0 + 0 + 2 + 9 = 11
0 + 0 + 3 + 8 = 11
0 + 0 + 4 + 7 = 11
0 + 0 + 5 + 6 = 11
0 + 1 + 1 + 9 = 11
0 + 1 + 2 + 8 = 11
0 + 1 + 3 + 7 = 11
0 + 1 + 4 + 6 = 11
0 + 1 + 5 + 5 = 11
0 + 2 + 2 + 7 = 11
0 + 2 + 3 + 6 = 11
0 + 2 + 4 + 5 = 11
0 + 3 + 3 + 5 = 11
0 + 3 + 4 + 4 = 11
1 + 1 + 1 + 8 = 11
1 + 1 + 2 + 7 = 11
1 + 1 + 3 + 6 = 11
1 + 1 + 4 + 5 = 11
1 + 2 + 2 + 6 = 11
1 + 2 + 3 + 5 = 11
1 + 2 + 4 + 4 = 11
1 + 3 + 3 + 4 = 11
2 + 2 + 2 + 5 = 11
2 + 2 + 3 + 4 = 11
2 + 3 + 3 + 3 = 11

===================

Analysis of Problem D:

একটা সংখ্যা দেয়া থাকবে
বলতে হবে, ওই সংখ্যাটার চাইতে ছোট বা সমান কতগুলা প্রাইম নাম্বার আছে

আমরা জানি, সবচাইতে ছোট প্রাইম নাম্বার হলো ২
তাহলে আমরা একটা ফাংশন লিখতে পারি, যেটা আমাদের বলবে, একটা নাম্বার প্রাইম কিনা
তারপরের কাজ খুব সহজ
২ থেকে n পর্যন্ত একটা লুপ চালাব এবং চেক করে দেখব, কতগুলা নাম্বার প্রাইম


//
//  main.cpp
//  TestCpp
//
//  Created by Shahab Uddin on 05/21/13.
//  Copyright (c) 2013 ___Shahab__. All rights reserved.
//

#include <cstdio>
#include <cmath>

bool isPrime (int p)
{
    // any number less than 2 is not prime
    if ( p < 2 ) return false;

    // 2 is the only even number which is prime
    if ( p == 2 ) return true;

    // 2 is the only even number which is prime
    // so, all the other even numbers are not prime
    if ( p % 2 == 0 ) return false;

    int squareRoot = (int) sqrt (p);

    // why are we looping only up to squareRoot??
    for ( int i = 3; i <= squareRoot; i += 2 ) {
        if ( p % i == 0 )
            return false;
    }

    return true;
}

int main(int argc, const char * argv[])
{
    int n;

    while ( scanf ("%d", &n) != EOF ) {
        int ans = 0;

        for ( int i = 2; i <= n; i++ ) {
            if (isPrime(i)) ans++;
        }

        printf ("%d\n", ans);
    }

    return 0;
} 

হুমম, একটা সমস্যা! Time Limit Exceed :-/
প্রবলেমটা হলো, একটা আউটপুট দিতে হলে আমাদের n * sqrt (n) পর্যন্ত ঘুরতে হবে
মানে হলো, আমরা একটা লুপ চালাচ্ছি ২ থেকে n … তাই না?
ধরা যায় এই লুপ তা আসলে n বার ঘুরবে
এবং প্রতিবার ঘুরার সময় এই লুপটা isPrime একটা ফাংশন কল করে
isPrime ফাংশন প্রতিবার sqrt (n) বার করে ঘুরে
লুপটা টোটাল ঘুরবে n * sqrt (n), for every output

এটাও আসলে সমস্যা না!সমস্যা অন্য জায়গাতে

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

তারপর যদি ইনপুট দেয়া হয় ১০০০
তাহলে কি করবেন?
১। ২ থেকে ১০০০ পর্যন্ত একটা লুপ চালাবেন
২। ২ থেকে ১০০০ পর্যন্ত সবগুলা প্রাইম বের করবেন

এইখানে একটা কাজ আপনি দুইবার করলেন
কারণ হলো, যখন আমরা ২ থেকে ১০০০০০ পর্যন্ত সবগুলা প্রাইম বের করলাম,
তখনই কিন্তু ২ থেকে ১০০০ পর্যন্ত প্রাইমগুলা আমরা ক্যালকুলেট করেছিলাম
তবে আমরা সেভ করে রাখি নাই দেখে আবার ক্যালকুলেট করা লাগলো

আমি সমস্যাটা আরেকটু ক্লিয়ার করি,
মনে করেন, ইনপুটগুলা এইরকমভাবে দেয়া আছে

ইনপুট ১: ১০০০০০
আউটপুট দেয়ার জন্য আপনি n * sqrt (n) লুপ রান করলেন

ইনপুট ২: ১০০০০০
আউটপুট দেয়ার জন্য আপনি n * sqrt (n) লুপ রান করলেন

ইনপুট ৩: ১০০০০০
আউটপুট দেয়ার জন্য আপনি n * sqrt (n) লুপ রান করলেন

মানে হলো, ৩ বার একই নাম্বার দেয়া হলো, কাজেই রেজাল্টও একই হবে
কিন্তু আপনি আলাদাভাবে ৩ বার লুপ রান করলেন
অথচ যেহেতু নাম্বার একই, তাই একবার লুপ রান করলেই কাজ হতে পারত, বুঝা যাচ্ছে?

আমরা যেটা করব সেটা হলো, প্রথমেই সবগুলা প্রাইম বের করে রাখব ১০০০০০০ পর্যন্ত
কারণ আমাদের সর্বোচ্চ ইনপুট দিবে ৯৯৯৯৯৯ পর্যন্ত
তাই আমরা যদি ১০০০০০০ পর্যন্ত প্রাইম বের করে রাখি তাহলে কাজ হবে
কারণ ১০০০০০০ পর্যন্ত প্রাইম বের করা মানে, ১০০০০০০ থেকে ছোট সবার জন্য বের করা

প্রাইম বের করার পর আমরা প্রাইম গুলা একটা এরেতে ফ্লাগ দিয়ে রাখব
যাতে পরেরবার থেকে জাস্ট এরে দেখেই রেজাল্ট বলা যায়, ক্যালকুলেট করা লাগবে না


//
//  main.cpp
//  TestCpp
//
//  Created by Shahab Uddin on 05/21/13.
//  Copyright (c) 2013 ___Shahab__. All rights reserved.
//

#include <cstdio>
#include <cmath>
#include <cstring>

#define N 1000000

bool primeArray [N];

bool isPrime (int p)
{
    // any number less than 2 is not prime
    if ( p < 2 ) return false;

    // 2 is the only even number which is prime
    if ( p == 2 ) return true;

    // 2 is the only even number which is prime
    // so, all the other even numbers are not prime
    if ( p % 2 == 0 ) return false;

    int squareRoot = (int) sqrt (p);

    // why are we looping only up to squareRoot??
    for ( int i = 3; i <= squareRoot; i += 2 ) {
        if ( p % i == 0 )
            return false;
    }

    return true;
}

void generate()
{
    // set the primeArray with false 
    memset(primeArray, false, sizeof primeArray);

    for ( int i = 0; i < N; i++ ) {
        if (isPrime(i)) 
            primeArray [i] = true;
        // isPrime(i) == true means, i is a prime 
        // so, primeArray[i] = true
        // otherwise, primeArray [i] = false
    }
}

int main(int argc, const char * argv[])
{

    // generating all the prime numbers, before taking input 
    generate();

    int n;

    while ( scanf ("%d", &n) != EOF ) {
        int ans = 0;

        for ( int i = 2; i <= n; i++ ) {
            // we are not calling the function isPrime()
            // just accessing an array we generated before 
            if(primeArray[i]) ans++;
        }

        printf ("%d\n", ans);
    }

    return 0;
} 

এইখানে চাইলে Sieve of Eratosthenes ব্যবহার করা যায়, এবং করলে ভালো
কারণ এই প্রবলেম বিগিনার লেভেলের দেখে sqrt (n) দিয়ে করা গেল
আপনাকে শুধু বলতে হচ্ছে, একটা নাম্বারের চাইতে ছোট কতগুলা প্রাইম আছে
কিন্তু সামনের দিকে প্রবলেমগুলাতে আরো কাজ থাকবে
তখন sqrt (n) পদ্ধতি কাজ করবে না, Sieve লাগবে
তাই আগের থেকেই অভ্যাস থাকা ভালো


//
//  main.cpp
//  TestCpp
//
//  Created by Shahab Uddin on 05/21/13.
//  Copyright (c) 2013 ___Shahab__. All rights reserved.
//

#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

#define N 1000005

bool isPrime [N];

void sieve()
{
    memset(isPrime, true, sizeof isPrime);

    isPrime [0] = isPrime [1] = false;

    for ( int i = 4; i < N; i += 2 )
        isPrime [i] = false;

    int squareRoot = (int) sqrt (N);

    for ( int i = 3; i <= squareRoot; i += 2 ) {
        if (isPrime[i]) {
            for ( int j = i * i; j < N; j += i )
                isPrime [j] = false;
        }
    }
}

int main(int argc, const char * argv[])
{
    sieve();

    int n;

    while ( scanf ("%d", &n) != EOF ) {
        int ans = 0;

        for ( int i = 2; i <= n; i++ ) {
            if (isPrime [i]) ans++;
        }

        printf ("%d\n", ans);
    }

    return 0;
}

===================

Analysis of Problem E:

factorial বের করতে হবে
শুধু খেয়াল রাখতে হবে, factorial ২০ বেশ বড় একটা নাম্বার
তাই long long int নিতে হবে ডাটা টাইপ


//
//  main.cpp
//  TestCpp
//
//  Created by Shahab Uddin on 05/21/13.
//  Copyright (c) 2013 ___Shahab__. All rights reserved.
//

#include <cstdio>

int main(int argc, const char * argv[])
{
    int n;
    scanf ("%d", &n);

    long long int ans = 1;

    for ( int i = 2; i <= n; i++ ) {
        ans *= i;
    }

    printf ("%lld\n", ans);

    return 0;
}