## 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.

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.

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.

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.

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.

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.

@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.

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.

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

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.

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

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

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

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

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