120 - Stacks of Flapjacks

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 120 Still WA. If you get AC, please try this input.

Post by vahid sanei »

Accepted
Last edited by vahid sanei on Tue Dec 22, 2009 9:35 pm, edited 1 time in total.
Impossible says I`m possible

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 120 Still WA. If you get AC, please try this input.

Post by vahid sanei »

Accepted , thanks coze
Last edited by vahid sanei on Tue Dec 22, 2009 9:35 pm, edited 1 time in total.
Impossible says I`m possible

coze
New poster
Posts: 26
Joined: Tue Nov 27, 2007 7:56 am
Location: Japan

Re: 120 Still WA. If you get AC, please try this input.

Post by 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
New poster
Posts: 3
Joined: Sat May 16, 2009 3:40 am

Re: 120 Still WA. If you get AC, please try this input.

Post by 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
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

Re: 120 Still WA. If you get AC, please try this input.

Post by 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
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 120 Still WA. If you get AC, please try this input.

Post by 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?
You should not always say what you know, but you should always know what you say.

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 120 Still WA. If you get AC, please try this input.

Post by raj »

1 2 3 5 4
2 1 2 3 0

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

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 120 Still WA. If you get AC, please try this input.

Post by lbv »

raj wrote: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
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 120

Post by mahade hasan »

ACCC thanks for help
Last edited by mahade hasan on Sat Apr 20, 2013 10:08 pm, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 120 Still WA. If you get AC, please try this input.

Post by brianfry713 »

Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 120 - Stacks of Flapjacks

Post by 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 ?
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 120 - Stacks of Flapjacks

Post by brianfry713 »

Given: 5 1 2 3 4
After flip(1): 4 3 2 1 5
After flip(2): 1 2 3 4 5
Check input and AC output for thousands of problems on uDebug!

nseph
New poster
Posts: 1
Joined: Fri Apr 08, 2016 8:06 pm

Re: 120 - Stacks of Flapjacks

Post by 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
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 120 - Stacks of Flapjacks

Post by lighted »

Your code is accepted code. :D
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 1 (100-199)”