UAB – 2006: Problem 2: Circle Intersection


In this problem you must write a program that determines if two circles intersect each other. The input to your program will be the coordinates for the center of each circle, followed by the radius of each circle.

The output will state whether the circles overlap, do not overlap, or are tangential (i.e., tangential circles touch each other at just one common point).

Example 1:
Enter the coordinates and radius for circle 1: 10 10 3
Enter the coordinates and radius for circle 2: 10 6 1

The circles are tangential.

Example 2:
Enter the coordinates and radius for circle 1: 8 8 3
Enter the coordinates and radius for circle 2: 8 4 2

The circles overlap.





// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

int square (int x)
{
    return x * x;
}

// distance between a and b
int distance (int x1, int y1, int x2, int y2)
{
    return square(x1 - x2) + square(y1 - y2);
}

int main (int argc, char *argv [])
{
    int circle1X, circle1Y, circle1Radius;
    
    printf ("Enter the coordinates and radius for circle 1: ");
    
    scanf ("%d %d %d", &circle1X, &circle1Y, &circle1Radius);
    
    int circle2X, circle2Y, circle2Radius;
    
    printf ("Enter the coordinates and radius for circle 2: ");
    
    scanf ("%d %d %d", &circle2X, &circle2Y, &circle2Radius);
    
    int centerDistance = distance(circle1X, circle1Y, circle2X, circle2Y);
    
    if ( centerDistance == circle1Radius + circle2Radius ) {
        printf ("The circles are tangential.\n");
        
    } else if ( centerDistance < circle1Radius + circle2Radius ) {
        printf ("The circles overlap");
        
    } else {
        printf ("The circles do not overlap");
        
    }

    return 0;
}

// @END_OF_SOURCE_CODE

UAB – 2005: Problem 6: Shortest Path in Alabama


Write a program to find the shortest routing and distance between two Alabama cities using the following distance table.

You are not allowed to use any other manually computed distances in your program.

Alabaster-Birmingham 24 miles
Alabaster-Montgomery 71 miles
Birmingham-Huntsville 103 miles
Birmingham-Tuscaloosa 59 miles
Demopolis-Mobile 141 miles
Demopolis-Montgomery 101 miles
Demopolis-Tuscaloosa 65 miles
Mobile-Montgomery 169 miles
Montgomery-Tuscaloosa 134 miles

Example 1:
Enter city #1: Demopolis
Enter city #2: Birmingham
Shortest routing and distance:
Demopolis-Tuscaloosa-Birmingham, 124 miles

Example 2:
Enter city #1: Mobile
Enter city #2: Huntsville
Shortest routing and distance: Mobile-Montgomery-Alabaster-Birmingham-Huntsville, 367 miles


Enter city #1: Tuscaloosa
Enter city #2: Alabaster
Shortest routing and distance:
Tuscaloosa-Birmingham-Alabaster, 83 miles

Enter city #1: Demopolis
Enter city #2: Mobile
Shortest routing and distance:
Demopolis-Mobile, 141 miles

Enter city #1: Huntsville
Enter city #2: Birmingham
Shortest routing and distance:
Huntsville-Birmingham, 103 miles

Enter city #1: Demopolis
Enter city #2: Alabaster
Shortest routing and distance:
Demopolis-Tuscaloosa-Birmingham-Alabaster, 148 miles

Enter city #1: Alabaster
Enter city #2: Demopolis
Shortest routing and distance:
Alabaster-Birmingham-Tuscaloosa-Demopolis, 148 miles


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <string>
#include <iostream>
#include <vector>

#define Alabaster   "Alabaster"
#define Birmingham  "Birmingham"
#define Demopolis   "Demopolis"
#define Mobile      "Mobile"
#define Montgomery  "Montgomery"
#define Huntsville  "Huntsville"
#define Tuscaloosa  "Tuscaloosa"

using namespace std;

struct node {
    string sourceCity;
    string destinationCity;
    int miles;
    
    node () {}
    
    node (string sourceCity, string destinationCity, int miles) {
        this->sourceCity = sourceCity;
        this->destinationCity = destinationCity;
        this->miles = miles;
    };
    
} routing [9];

void populateData()
{
    routing [0] = node (Alabaster, Birmingham, 24);
    routing [1] = node (Alabaster, Montgomery, 71);
    routing [2] = node (Birmingham, Huntsville, 103);
    routing [3] = node (Birmingham, Tuscaloosa, 59);
    routing [4] = node (Demopolis, Mobile, 141);
    routing [5] = node (Demopolis, Montgomery, 101);
    routing [6] = node (Demopolis, Tuscaloosa, 65);
    routing [7] = node (Mobile, Montgomery, 169);
    routing [8] = node (Montgomery, Tuscaloosa, 134);
}

// best path among all the paths
vector <string> bestPath;

// best cost among all the acceptable cost
int bestCost;

// intermediate path
vector <string> path;

// user input, source and destination city 
string city1, city2;

// check if the cityName is already visited 
bool notInPath(string cityName)
{
    for ( int i = 0; i < path.size(); i++ ) {
        if ( path [i] == cityName ) return false;
    }
    
    return true;
}

void recurShortestPath(string currentCity, int currentCost)
{
    if (currentCity == city2) {
        if (currentCost < bestCost) {
            bestCost = currentCost;
            bestPath = path;
        }
        return;
    }
    
    // loop through all the routing paths 
    for ( int i = 0; i < 9; i++ ) {
        if (routing [i].sourceCity == currentCity && notInPath(routing [i].destinationCity)) {
            // put the next city in the path 
            path.push_back(routing [i].destinationCity);
            // lets do the experiment
            recurShortestPath(routing [i].destinationCity, currentCost + routing [i].miles);
            // preserve the previous state 
            path.pop_back();
            
        } else if (routing [i].destinationCity == currentCity && notInPath(routing [i].sourceCity)) {
            path.push_back(routing [i].sourceCity);
            recurShortestPath(routing [i].sourceCity, currentCost + routing [i].miles);
            path.pop_back();
        }
    }
}

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

    // initially bestCost is the maximum value ever
    bestCost = INT_MAX;
    
    printf ("Enter city #1: ");
    cin >> city1;
    
    printf("Enter city #2: ");
    cin >> city2;
    
    path.push_back(city1);
    
    recurShortestPath(city1, 0);
    
    printf ("Shortest routing and distance:\n");
    bool isHyphen = false;
    
    for ( int i = 0; i < bestPath.size(); i++ ) {
        if (isHyphen) printf ("-");
        isHyphen = true;
        
        cout << bestPath [i];
    }
    
    printf (", %d miles\n", bestCost);
    
    return 0;
}

// @END_OF_SOURCE_CODE

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;
}

The Next Number


General Statement:
A relatively simple task for humans to do is to identify the next number in an arithmetic sequence of numbers. For example, given the sequence of numbers 3, 6, and 9, we know that the next number in the sequence is 12 since each number is followed by a number increasing it by 3. Alternatively, given the sequence of numbers 3, 6, and 12, we know that the next number in the sequence is 24 since each number is followed by a number that doubles it.

Your task is to write a program that will deduce the next integer in a given sequence of three integers where the same arithmetic operation is applied to each integer to produce the next. The only arithmetic operations that will be used are addition, subtraction, multiplication, or division.

Input: The first line of the input contains an integer n that represents the number of data collections that follow where each data collection is on a single line. Each input line contains three integers with each pair of integers separated by a single space. The integers represent a sequence as described in the General Statement.

Output: Your program should produce n lines of output (one for each data collection). The output for each data collection should be the next integer in the corresponding input sequence.

The output is to be formatted exactly like that for the sample output given below.

Assumptions: The value of n will be between 1 and 100, inclusive.
There will be exactly one answer to each input sequence.
The answer will always be an integer (even if division is used).

Sample Input:
3
7 21 35
-10 20 -40
64 16 4

Sample Output:
49
80
1

#include <stdio.h>

int main ()
{
    int n;
    scanf ("%d", &n);

    while ( n-- ) {
        double x, y, z;

        scanf ("%lf %lf %lf", &x, &y, &z);

        if ( y - x == z - y )
            printf ("%0.lf\n", z + y - x);

        else
            printf ("%0.lf\n", z / (x / y));
    }

    return 0;
}

Anything You Can Do, I Can Do Better


General Statement:
You have a colleague that is extremely competitive and always tries to “top” one of your stories. If you say your car is fast, your colleague will say his or her car is faster. If you say your car is faster, your colleague will say his or her car is fastest. After a few such conversations, you realize that you can always predict what your colleague will say next.

To demonstrate how annoying this is, you decide to write a program that can accurately predict the responses of your colleague. Your task is to write this program. Specifically, given any adjective, your program will return its comparative form by appending “er” to it. Note that if the adjective already ends in “e”, you should only append “r”. If your program is given an adjective already in its comparative form, your program should return the superlative form of the adjective created by simply replacing the “er” with “est”. Your program should consider any string that ends in “er” to be an adjective in comparative form.

Input:
The first line of the input contains an integer n that represents the number of data collections that follow where each data collection is on a single line. Each input line contains a string representing an adjective or its comparative form. Each string will be given in all lower case letters.

Output:
Your program should produce n lines of output (one for each data collection). Each line should be in lower case letters. If the input is the comparative form of an adjective (ends in “er”), your program should output the superlative form.

Otherwise, your program should output the comparative form of the string given as input.

The output is to be formatted exactly like that for the sample output given below.

Assumptions:
The value of n will be between 1 and 100, inclusive.
Each input word will have between 1 and 30 characters, inclusive.

Sample Input:
3
warm
smaller
rare

Sample Output:
warmer
smallest
rarer

#include <stdio.h>
#include <string.h>

int main ()
{
    int dataset;
    scanf ("%d", &dataset);

    while ( dataset--) {
        char input [35];
        scanf ("%s", input);

        int length = strlen (input);

        if ( input [length - 1] == 'r' && input [length - 2] == 'e' ) {
            input [length - 1] = 's';
            input [length] = 't';
            input [length + 1] = 0;
        }

        else {
            if ( input [length - 1] == 'e' )
                strcat (input, "r");
            else
                strcat (input, "er");
        }

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

    }

    return 0;
}

Training Times


General Statement:
Some training simulation systems automatically record the response time of their users in order to gauge the effectiveness of the training system. The goal is for the user to become faster at completing the simulation. There are times, however, when a user gets fatigued and starts becoming slower at completing the simulation. Your task is to write a program that can determine from a collection of two input recorded times if the user is improving.

Input:
The first line of the input is an integer n that represents the number of data collections that follow where each data collection is on a single line. Each data collection contains two integers x and y separated by a single space. The integers represent the first and second times (in milliseconds) of the users, respectively.

Output:
Your program should produce n lines of output (one for each data collection). If the second time is smaller than the first, then the user is getting faster. In this case, your program should print IMPROVING. Otherwise, the user is not improving, and your program should print NOT IMPROVING.
The output is to be formatted exactly like that for the sample output given below.

Assumptions:
The value of n will be between 1 and 100, inclusive.
Each input integer will be between 0 and 1,000,000, inclusive.

Sample Input:
3
500 450
1000 1001
75 75

Sample Output:
IMPROVING
NOT IMPROVING
NOT IMPROVING

#include <stdio.h>

int main ()
{
    int dataset;
    scanf ("%d", &dataset);

    while ( dataset--) {
        int first;
        int second;

        scanf ("%d %d", &first, &second);

        if ( second < first )
            printf ("IMPROVING\n");

        else
            printf ("NOT IMPROVING\n");
    }

    return 0;
}