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

User avatar
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 » Wed Feb 11, 2009 10:15 am

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

User avatar
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 » Thu Feb 19, 2009 6:58 pm

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 » Thu Feb 19, 2009 9:06 pm

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 » Mon Jun 15, 2009 2:42 am

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 » Mon Jun 06, 2011 1:47 am

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 » Sat Jun 18, 2011 11:15 am

@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 » Sun Feb 17, 2013 11:56 pm

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 » Mon Feb 18, 2013 2:00 am

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.

User avatar
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 » Fri Apr 19, 2013 10:10 am

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 » Sat Apr 20, 2013 12:36 am

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 » Tue Mar 10, 2015 9:08 am

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 » Tue Mar 31, 2015 12:32 am

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 » Fri Apr 08, 2016 8:10 pm

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 120 - Stacks of Flapjacks

Post by lighted » Sun Mar 12, 2017 1:40 pm

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)”