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 করব

Advertisements

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