120 - Stacks of Flapjacks
Moderator: Board moderators
-
- Learning poster
- Posts: 53
- Joined: Sat Jul 29, 2006 7:33 am
- Location: (CSE,DU), Dhaka,Bangladesh
can anybody help me (120)(stack of flapjack)?
removed the code
Last edited by ishtiaq ahmed on Mon Feb 05, 2007 3:17 pm, edited 1 time in total.
-
- Experienced poster
- Posts: 162
- Joined: Thu Jul 13, 2006 7:07 am
- Location: Campus Area. Dhaka.Bangladesh
- Contact:
dear ishtiaq
you have made your programe so complex
try to make it simple
try these input:
output should be:
but your programe shows
now try to sholve it
best of luck
newton................. simply the best!
you have made your programe so complex
try to make it simple
try these input:
Code: Select all
1 9 33 4 45 2 78 100
Code: Select all
1 9 33 4 45 2 78 100
4 3 5 4 6 0
Code: Select all
1 9 33 4 45 2 78 100
7 2 3 5 4 7 0
best of luck
newton................. simply the best!
-
- New poster
- Posts: 9
- Joined: Sat Nov 18, 2006 4:56 pm
- Location: Taiwan
- Contact:
120 Stack of flapjack...
I've tried some easy test cases on papers, then I found some strange situations...
The most popular algorithm discussed in previous threads is to find the largest diameter pancake and flip it to the top, then reversed the stack. Without doubt this algorithm works well to any cases.
But I found that this algorythm doesn't give out the shortest path sorting the stack. Here's an example.
1 3 5 4 2
Followed by the algorithm, the sorting process should be like this:
1 3 5 4 2 flip(3)
5 3 1 4 2 flip(1)
2 4 1 3 5 flip(4)
4 2 1 3 5 flip(2)
3 1 2 4 5 flip(3)
2 1 3 4 5 flip(2)
1 2 3 4 5 flip(0)...done
And it takes 6 flips to complete sorting the stack.
However if I tried another path:
1 3 5 4 2 flip(2)
4 5 3 1 2 flip(4)
5 4 3 1 2 flip(1)
2 1 3 4 5 flip(4)
1 2 3 4 5 flip(0)...done
It only takes 4 flips and the stack is sorted.
Then I rechecked the problem, only to find that it didn't put any limits to the output. Does it means that all the paths, short or long, can be accepted? Or does it require a best solution to get AC?
The most popular algorithm discussed in previous threads is to find the largest diameter pancake and flip it to the top, then reversed the stack. Without doubt this algorithm works well to any cases.
But I found that this algorythm doesn't give out the shortest path sorting the stack. Here's an example.
1 3 5 4 2
Followed by the algorithm, the sorting process should be like this:
1 3 5 4 2 flip(3)
5 3 1 4 2 flip(1)
2 4 1 3 5 flip(4)
4 2 1 3 5 flip(2)
3 1 2 4 5 flip(3)
2 1 3 4 5 flip(2)
1 2 3 4 5 flip(0)...done
And it takes 6 flips to complete sorting the stack.
However if I tried another path:
1 3 5 4 2 flip(2)
4 5 3 1 2 flip(4)
5 4 3 1 2 flip(1)
2 1 3 4 5 flip(4)
1 2 3 4 5 flip(0)...done
It only takes 4 flips and the stack is sorted.
Then I rechecked the problem, only to find that it didn't put any limits to the output. Does it means that all the paths, short or long, can be accepted? Or does it require a best solution to get AC?
-
- New poster
- Posts: 9
- Joined: Sat Nov 18, 2006 4:56 pm
- Location: Taiwan
- Contact:
To much surprise, this problem is actually somewhat prominent in Academia. In fact, the minimum number of flips for all n! orderings of n pancakes is unknown for n >= 14. It cannot exhaustively be searched because 14! (factorial) is 87,178,291,200. There are many papers in academia bounding the number of flips to go from any pancake stack to any other ordering of the pancakes.
Another fun fact is that the only paper Bill Gates ever published created a tighter bound on the maximum number of flips necessary for any given n.
And so one could turn this into an A* problem with the heuristic of the minimum number of flips required (can be counted by seeing that you need to stick the spatula between any two pancakes that do not belong next to each other in the final ordering). Fortunately, however, this is not necessary =).
Another fun fact is that the only paper Bill Gates ever published created a tighter bound on the maximum number of flips necessary for any given n.
And so one could turn this into an A* problem with the heuristic of the minimum number of flips required (can be counted by seeing that you need to stick the spatula between any two pancakes that do not belong next to each other in the final ordering). Fortunately, however, this is not necessary =).
120 (Stacks of Flapjacks)
I get a problem with 120. Can anyone help me.
I send my code to Online Judge and get "Runtime Error (Signal 11) "
Is any function I did not include??
here are my code :
And other question is "The input is terminated by end-of-file" !?
I use
Is it correct?
![:)](./images/smilies/icon_smile.gif)
I send my code to Online Judge and get "Runtime Error (Signal 11) "
Is any function I did not include??
here are my code :
Code: Select all
//Question http://acm.uva.es/p/v1/120.html
//CPU: 0.002, Memory: Minimum
//state: Runtime Error (Signal 11)
#include <iostream>
#include <cstring>
using namespace std;
void sortPancake(int *r, int n) //array R have 5 element
{
for(int j=1; j<n; j++) //Insertion Sort
{
int k = r[j];
int i = j-1;
while(i>=0 && r[i]>k){
r[i+1] = r[i];
i--;
}
r[i+1] = k;
}
}
void flip(int *r, int n)
{
for(int i=0; i<=n/2; i++)
{
int temp = r[i];
r[i] = r[n-i];
r[n-i] = temp;
}
}
int main()
{
int p[30]={0}, count=0, r[30]={0}, input;
while(cin >> input)
{
p[count++] = r[count] = input;
if(cin.eof())
break;
}
for(int i=0; i<count; i++)
cout << p[i] << " ";
cout << "\n";
sortPancake(r, count); //Insertion Sort
for(int i=count-1; i>=0; i--)
{
if(p[i]==r[i])
continue;
if(p[0]!=r[i])
{
int position = 0;
while(p[position]!=r[i])
position++;
flip(p, position);
cout << count-position << " ";
}
flip(p, i); //p[0]==r[i]
cout << count-i << " ";
}
cout << "0";
//system("pause");
return (0);
}
I use
Code: Select all
if(cin.eof()) break;
Search the board first. Dont open a new thread if there is one already. And for your question the answer is 'no'.
Ami ekhono shopno dekhi...
HomePage
HomePage
Can anyone show me a tricky input?
I got multiple WA on this problem.
Can someone check the correctness of this I/O set?
INPUT
OUTPUT
Can someone post more tricky I/O set?
Thanks![:D](./images/smilies/icon_biggrin.gif)
Can someone check the correctness of this I/O set?
INPUT
Code: Select all
2
33 21 45
33 55
1
2 1
1 2
12 45 1 2 4 7 5 11 21 99 12 47
56 12 48
75 2 1 44 53 84 21 46 82 43 99 49 89 7 9
1 2 3 6 7 8 4 5
1 3 19 4 95 62 42 43 13 2
1 2 3 4 5 6 7 8 9 10 11 12 14 13 15 16 17 18 19 20
Code: Select all
2
0
33 21 45
1 1 0
33 55
0
1
0
2 1
1 0
1 2
0
12 45 1 2 4 7 5 11 21 99 12 47
3 1 2 11 3 11 4 6 6 7 7 11 8 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 10 3 11 4 5 9 6 11 7 14 8 13 9 12 10 13 11 12 13 13 0
1 2 3 6 7 8 4 5
3 1 6 2 5 3 7 4 0
1 3 19 4 95 62 42 43 13 2
6 1 6 2 4 3 4 8 5 6 8 7 9 8 0
1 2 3 4 5 6 7 8 9 10 11 12 14 13 15 16 17 18 19 20
1 1 2 3 3 4 5 5 6 8 7 8 0
Thanks
![:D](./images/smilies/icon_biggrin.gif)
-
- New poster
- Posts: 5
- Joined: Sat Jul 28, 2007 6:33 am
- Location: Taiwan
120 WA plz help me~(I need more test case)
I have seen several topics about Q120.
I tested several test case and I got correct output.
But I still got WA...
Could someone who got AC give me more test case?
thank you!
I tested several test case and I got correct output.
But I still got WA...
Could someone who got AC give me more test case?
thank you!
-
- Learning poster
- Posts: 63
- Joined: Tue Sep 20, 2005 12:31 am
- Location: Dhaka
- Contact:
-
- New poster
- Posts: 5
- Joined: Sat Jul 28, 2007 6:33 am
- Location: Taiwan
Sedefcho wrote:
INPUT:Code: Select all
... 4 4 1 4 4 5 4 4 1 4 4 5 4 99 7 99 0 7 99 0 2 4 4 4 2 4 11 13 15 17 13 15 11 20 20 200 20 20 200 20 20
![:)](./images/smilies/icon_smile.gif)
"All pancakes in a stack have different diameters," so there are no two things of the same size. I post some test cases again.
May it be helpful~
INPUT
Code: Select all
8 4 6 7 5 2
1 2 3 5 4
7 3 5 4 8 9 10 1 13
2
33 21 45
33 55
1
2 1
1 2
56 12 48
75 2 1 44 53 84 21 46 82 43 99 49 89 7 9
1 2 3 6 7 8 4 5
1 3 19 4 95 62 42 43 13 2
1 2 3 4 5 6 7 8 9 10 11 12 14 13 15 16 17 18 19 20
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
Re: 120 Still WA. If you get AC, please try this input.
be aware that the bring-to-top method is not always optimal:
http://www.google.com/url?sa=t&source=w ... CfG0QBaWIg
http://www.google.com/url?sa=t&source=w ... CfG0QBaWIg
WA ?
Could any one temme wats wrong with my prog
If there are more than one solution is there any criteria to select one among them? :|
Code: Select all
#include<iostream>
#include<sstream>
#include<stack>
using namespace std;
int min(int a[],int i,int n)
{
int m=i;
for(int j=i;j<n;j++)
if(a[m]>a[j])m=j;
return m;
}
void flip(int a[],int ind,int n)
{
stack<int> sta;
for(int i=ind;i<n;i++)
sta.push(a[i]);
for(int i=ind;i<n;i++)
{
a[i]=sta.top();
sta.pop();
}
}
int main()
{
int sta[100];
char s[300];
while(cin.getline(s,300))
{
stringstream sin(s);
int i=0;
while(sin>>sta[i++])cout<<sta[i-1]<<" ";
int n=i-1;
cout<<"\n";
for(i=0;i<n-1;i++)
{
int ind=min(sta,i,n);
if(ind!=i)
{
if(ind<n-1)
{
cout<<ind+1<<" ";
flip(sta,ind,n);
}
cout<<i+1<<" ";
flip(sta,i,n);
}
}
cout<<"0\n";
}
return 0;
}