120 - Stacks of Flapjacks

[vahid sanei]

Accepted

[vahid sanei]

Accepted , thanks coze

[coze]

Hi, vahid sanei.

My output:

Code: Select all

8 4 6 7 5 2
1 4 2 5 3 4 5 0
1 2 3 5 4
2 1 2 3 0
7 3 5 4 8 9 10 1 13
3 2 8 5 8 6 0
2
0
33 21 45
2 0
33 55
0
1
0
2 1
1 0
1 2
0
56 12 48
1 2 0
75 2 1 44 53 84 21 46 82 43 99 49 89 7 9
5 1 13 2 11 3 6 4 10 5 14 6 7 10 8 12 9 11 14 12 14 0
1 2 3 6 7 8 4 5
3 1 4 6 0
1 3 19 4 95 62 42 43 13 2
6 1 6 2 4 3 4 6 5 9 6 8 9 0
1 2 3 4 5 6 7 8 9 10 11 12 14 13 15 16 17 18 19 20
8 7 8 9 0

For example, the following input:

Code: Select all

1 2 3 5 4

Output should be:

Code: Select all

1 2 3 5 4
2 1 2 3 0

Code: Select all

1         5         4         3         1
2 flip(2) 3 flip(1) 1 flip(2) 2 flip(3) 2
3 ------> 2 ------> 2 ------> 1 ------> 3
5         1         3         4         4
4         4         5         5         5

[asqwzxdfercv]

I got a PE for this problem where is the trick? Below is my output format

Code: Select all

I submit the same code in the next day 
and it is accepted-.-

[shantanu18]

getting wa!

Code: Select all

#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <utility>
#define pa pair<int,int>
using namespace std;
bool com(const pa a,const pa b)
{
	return a.first<b.first;
}

vector<pa> getNumber(string st)
{
	vector <pa> vec;
	int num;
	int ind=0;
	char str[500];
	strcpy(str,st.c_str());
	char *ptr;
	ptr=strtok(str," ");
	while(ptr!=NULL)
	{
		sscanf(ptr,"%d",&num);
		vec.push_back(pa(num,ind++));
		ptr=strtok(NULL," ");
	}
	
	return vec;
}
void _swap(pa &a,pa &b)
{
	pa tmp;
	tmp=a;
	a=b;
	b=tmp;
}
int main()
{
	string st;
	vector <pa> vec;
	vector <pa> cvec;
	int length;
	bool flag=false;
	while(getline(cin,st))
	{
		vec.clear();
		cvec.clear();
		vec = getNumber(st);
		
		cvec = vec;
		sort(cvec.begin(),cvec.end(),com);
		
		length=vec.size();
		flag=false;
		
		for(int i=length-1;i>0;i--)
		{
			if(vec[0].second == cvec[i].second)
			{
				for(int k=0,l=i;k<l;k++,l--)
					_swap(vec[k],vec[l]);
				cout<<length-i<<" ";
			}
			else{
				for(int j=i-1;j>0;j--)
				{
					if(cvec[i].second==vec[j].second)
					{
						for(int k=0,l=j;k<l;k++,l--)
							_swap(vec[k],vec[l]);
						cout<<length-j<<" ";
						for(int k=0,l=i;k<l;k++,l--)
							_swap(vec[k],vec[l]);
						cout<<length-i<<" ";
					}
				}
			}
		}
		cout<<"0"<<endl;
	}
	return 0;
}

[zobayer]

@shantanu18, From a quick look on your code, I think you are always printing a 0 at the end, why does it have to be so?

[raj]

1 2 3 5 4
2 1 2 3 0

I DIDNT UNDERSTAND THIS CASE ............
PLS ANYONE MAKE ME UNDERSTOOD ELABORATELY ..??????

[lbv]

1 2 3 5 4
2 1 2 3 0

I DIDNT UNDERSTAND THIS CASE ............
PLS ANYONE MAKE ME UNDERSTOOD ELABORATELY ..??????

My friend,

Have you read the message posted in this forum thread by coze on Feb 19, 2009? If not, go ahead and read it. It has a very useful diagram that explains that test case you're asking for. I think it would be difficult to be any more elaborate than that.

I see that you're starting to accumulate some experience with algorithm problems and that's great, but I invite you to contemplate that there are many skills involved in this beyond the pure programming aspect. Think about the importance of reading comprehension, patience, perseverance, self-reliance to beat the obstacles you find by yourself.

Keep in mind that it's often necessary to read a problem statement many times until you finally understand it completely, and this is particularly difficult when you're just starting in algorithm problems, but it gets easier with time... For now you just need to do the effort to apply yourself a little more when reading the problems.

You're welcome to keep asking questions, of course, but it would be more helpful if you formulated concrete questions about which detail(s) you don't understand, instead of just saying "I don't understand, please help". Good luck.

[mahade hasan]

ACCC thanks for help

[brianfry713]

http://www.algorithmist.com/index.php/UVa_120

[Shahidul.CSE]

I didn't understand why for the sample input

Code: Select all

5 1 2 3 4

output is

Code: Select all

5 1 2 3 4
1 2 0

My thinking is:
Given: 5 1 2 3 4
After flip(1): 4 1 2 3 5
After flip(2): 3 1 2 4 5
So, finally sorted list is 3 1 2 4 5 . Isn't it ? If so, how the output can be correct ? Shouldn't the sorted list be 1 2 3 4 5 ?
Can any one please explain it ?

[brianfry713]

Given: 5 1 2 3 4
After flip(1): 4 3 2 1 5
After flip(2): 1 2 3 4 5

[nseph]

Hi, I've been getting WA for this problem and I can't find my mistake.

I even wrote a part that does all the flips found on the original stack and in all the cases I checked, the stack finishes sorted. Any help would be much appreciated.

Code: Select all

#include <vector>
#include <iterator>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <sstream>

using namespace std;

int main()
{
//    freopen("data.in", "r", stdin);
//    freopen("data.out", "w", stdout);
    string s;
    while(getline(cin, s))
    {
        istringstream ss(s);
        vector<int> pancakes, flips;
        int p;

        while(ss >> p)
            pancakes.push_back(p);



        printf("%d", pancakes[0]);
        for(int i=1; i<pancakes.size(); i++)
            printf(" %d", pancakes[i]);
        printf("\n");

        reverse(pancakes.begin(), pancakes.end());
         vector<int> originals(pancakes);
        int sorted = 0;
        while(sorted < pancakes.size())
        {

            auto flipIt = max_element(pancakes.begin()+sorted, pancakes.end());
            int flipInd = distance(pancakes.begin()+sorted, flipIt);
            if(flipInd != 0)
            {
                if(flipIt != pancakes.end()-1)
                {
                    flips.push_back(flipInd+sorted+1);
                    reverse(flipIt, pancakes.end());
                }
                flips.push_back(sorted+1);
                reverse(pancakes.begin()+sorted, pancakes.end());
            }
            sorted++;
        }
//        printf("checking\n");
//        for(auto f:flips)
//            reverse(originals.begin()+(f-1), originals.end());
//        reverse(originals.begin(), originals.end());
//        if(is_sorted(originals.begin(), originals.end()))
//           {
//               printf(" Yay!\n");
//           }
//            else
//            printf("                                          Fuck!\n");

        for(auto f:flips)
            printf("%d ", f);
        printf("0\n");
    }
}

[lighted]

Your code is accepted code.