ACM (UVa) : 101


#include <iostream>
#include <cstdio>
using namespace std;

int a [30] [30];
int n;
int first_x;
int first_y;
int second_x;
int second_y;


/******************* OUTPUT *******************/
void output ()
{
    for ( int i = 0; i < n; i++ ) {
        printf ("%d:", i);
        for ( int j = 0; a [i] [j] != -1; j++ )
            printf (" %d", a [i] [j]);
        printf ("\n");
    }

    //printf ("\n");
}


/******************* CONSTRUCTOR *******************/
void constructor ()
{
    for ( int i = 0; i < n; i++ ) {
        a [i] [0] = i;
        a [i] [1] = -1;
    }
}


/******************* CHECKING ILLEGAL COMMAND *******************/
bool validity (int first, int second)
{
    if ( first == second )
    return false;

    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; a [i] [j] != -1; j++ ) {
            if ( first == a [i] [j] ) {
                for ( int k = 0; a [i] [k] != -1; k++ ) {
                    if ( second == a [i] [k] )
                        return false;
                }
            }
        }
    }

    return true;
}


/******************* FIND *******************/
void find (int first, int second)
{
    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; a [i] [j] != -1; j++ ) {
            if ( a [i] [j] == first ) {
                first_x = i;
                first_y = j;
            }

            else if ( a [i] [j] == second ) {
                second_x = i;
                second_y = j;
            }
        }
    }
}

/******************* MOVE ONTO *******************/
void move_onto_method (int first, int second)
{
    if ( !validity (first, second) )
    return;

    find (first, second);

    //output ();

    for ( int i = first_y + 1; a [first_x] [i] != -1; i++ ) {
        a [a [first_x] [i]] [0] = a [first_x] [i];
        a [a [first_x] [i]] [1] = -1;
    }

    a [first_x] [first_y] = -1;

    for ( int i = second_y + 1; a [second_x] [i] != -1; i++ ) {
        a [a [second_x] [i]] [0] = a [second_x] [i];
        a [a [second_x] [i]] [1] = -1;
    }

    a [second_x] [second_y + 1] = first;
    a [second_x] [second_y + 2] = -1;

}


/******************* MOVE OVER *******************/

void move_over_method (int first, int second)
{
    if ( !validity (first, second) )
    return;

    find (first, second);

    for ( int i = first_y + 1; a [first_x] [i] != -1; i++ ) {
        a [a [first_x] [i]] [0] = a [first_x] [i];
        a [a [first_x] [i]] [1] = -1;
    }

    a [first_x] [first_y] = -1;

    second_y++;
    while ( a [second_x] [second_y] != -1 )
        second_y++;

    a [second_x] [second_y] = first;
    a [second_x] [++second_y] = -1;
}

/******************* PILE ONTO *******************/

void pile_onto_method (int first, int second)
{
    if ( !validity (first, second) )
    return;

    find (first, second);

    for ( int i = second_y + 1; a [second_x] [i] != -1; i++ ) {
        a [a [second_x] [i]] [0] = a [second_x] [i];
        a [a [second_x] [i]] [1] = -1;
    }

    for ( int i = first_y; a [first_x] [i] != -1; i++ )
        a [second_x] [++second_y] = a [first_x] [i];

    a [second_x] [++second_y] = -1;
    a [first_x] [first_y] = -1;

}

/******************* PILE OVER *******************/

void pile_over_method (int first, int second)
{
    if ( !validity (first, second) )
    return;

    find (first, second);

    second_y++;
    while ( a [second_x] [second_y] != -1 )
        second_y++;

    for ( int i = first_y; a [first_x] [i] != -1; i++ )
        a [second_x] [second_y++] = a [first_x] [i];

    a [second_x] [second_y] = -1;
    a [first_x] [first_y] = -1;
}

/******************* SUPPOSED TO BE MAIN *******************/
int main ()
{
    //freopen ("101in.txt", "r", stdin);
    while ( cin >> n ) {

        constructor ();

        //output ();

        string move_pile;
        int first;
        string onto_over;
        int second;

        while ( cin >> move_pile ) {

            if ( move_pile == "quit" )
                break;
            cin >> first;
            cin >> onto_over;
            cin >> second;

            if ( move_pile == "move" && onto_over == "onto" ) {
                move_onto_method (first, second);
            }

            else if ( move_pile == "move" && onto_over == "over" ) {
                move_over_method (first, second);
            }

            else if ( move_pile == "pile" && onto_over == "onto" ) {
                pile_onto_method (first, second);
            }

            else if ( move_pile == "pile" && onto_over == "over" ) {
                pile_over_method (first, second);
            }

            //output ();
        }

        output ();
    }

    return 0;
}

4 thoughts on “ACM (UVa) : 101

  1. শুধু solution দিলে হবে। এই প্রশ্নের ব্যাখা জানা আগে দরকার………। দয়া করে প্রশ্নের ব্যাখাতা add করুন…

    we can not understand the description corresponding “move a onto b”,move a over b”,pile a onto b,”pile a over b”….

    please this describe in bangla language……

  2. ভাইজান, প্রবলেম সলভ কইরাই কোন কুল-কিনারা পাই না। ব্যাখ্যা করব কেমনে?
    বলেছেন যখন ব্যাখ্যা করার চেষ্টা করি।

    move a onto b
    মনে করেন, ৫ টা বক্স আছে।




    move 2 onto 1 মানে হল, ২ নাম্বার বক্সটা ১ নাম্বার বক্স এর উপর উঠাতে হবে। যেমন :
    ১ ২


    এখন, move 3 onto 1 হলে,
    ১ ৩ ২


    হবার কথা, কিন্তু এটা হবে না । কারন,

    problem statement,

    puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.

    মানে হল, ৩ কে ১ এর উপর উঠানোর আগে, ১ এর উপর যত বক্স আছে সেগুলোকে তাদের আগের জায়গায় সরাতে হবে। এবং ৩ এর উপর যত বক্স আছে সেগুলোকেও তাদের আগের জায়গায় সরাতে হবে। কিন্তু এই উদাহরনে ৩ এর উপর কোন বক্স নাই। তাই আমরা শুধু ১ এর উপর থেকে ২ কে সরিয়ে তার আগের জায়গায় রাখবো । তারপর ১ এর উপর ৩ রাখবো।

    ১ ৩


    আর একটা উদাহরন দেই : মনে করি, বক্সগুলোর বর্তমার অবস্থা,
    ১ ২
    ৩ ৪

    এখন, move 3 onto 1, বলা হলে উত্তর হবে,
    ১ ৩


    ব্যাখ্যা : বক্স নাম্বার ৩ কে ১ এর উপর উঠাতে বলা হয়েছে। কিন্তু ১ এর উপর পূর্বে একটি ব্ক্স রয়েছে এবং ৩ এর উপরেও বক্স রয়েছে। কাজেই এখন যেটা করতে হবে সেটা হল, বক্স ১ এর উপর যত বক্স আছে সেগুলোকে তাগের আগের জায়গায় সরাতে হবে। তারপর বক্স ৩ এর উপর যত বক্স আছে সেগুলোকেও তাদের আগের জায়গায় সারাতে হবে। তারপর ৩ নং ব্ক্সকে ১ নং এর উপর রাখতে হবে।

    আর একটি উদাহরন। মনে করি, ১০ টি বাক্সের বর্তমান অবস্থা,
    ১ ২ ৩ ৪
    ৫ ৬ ৮
    ৭ ৯ ১০

    এখন, move 5 onto 1 এর উত্তর,
    ১ ৫




    ৭ ৯ ১০

    বুঝতে সমস্যা হলে জানাবেন। ধন্যবাদ 🙂

  3. bhai thank u আপনি যদি বাকি condition টা যদি কষ্ট করে example দিতেন তা হলে একটু উপকৃত হতাম ।

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