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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s