120 - Stacks of Flapjacks
Moderator: Board moderators
-
- 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
-
- 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
Re: 120 Still WA. If you get AC, please try this input.
Hi, vahid sanei.
My output:
For example, the following input:
Output should be:
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
Code: Select all
1 2 3 5 4
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
-
- 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
![:(](./images/smilies/icon_frown.gif)
Code: Select all
I submit the same code in the next day
and it is accepted-.-
-
- 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;
}
-
- 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.
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 ..??????
2 1 2 3 0
I DIDNT UNDERSTAND THIS CASE ............
PLS ANYONE MAKE ME UNDERSTOOD ELABORATELY ..??????
Re: 120 Still WA. If you get AC, please try this input.
My friend,raj wrote:1 2 3 5 4
2 1 2 3 0
I DIDNT UNDERSTAND THIS CASE ............
PLS ANYONE MAKE ME UNDERSTOOD ELABORATELY ..??????
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.
-
- 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!
need eyes to feel it!
-
- 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!
-
- 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 output is
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 ?
Code: Select all
5 1 2 3 4
Code: Select all
5 1 2 3 4
1 2 0
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
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
-
- 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
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!
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.
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");
}
}
Re: 120 - Stacks of Flapjacks
Your code is accepted code. ![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman