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

ishtiaq ahmed
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)?

Post by ishtiaq ahmed » Mon Feb 05, 2007 6:04 am

removed the code
Last edited by ishtiaq ahmed on Mon Feb 05, 2007 3:17 pm, edited 1 time in total.

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Mon Feb 05, 2007 2:41 pm

dear ishtiaq

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
output should be:

Code: Select all

              1 9 33 4 45 2 78 100
              4 3 5 4 6 0 
but your programe shows

Code: Select all

              1 9 33 4 45 2 78 100
              7 2 3 5 4 7 0
now try to sholve it
best of luck




newton................. simply the best!

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Mon Feb 05, 2007 3:52 pm

dear imLazy,

you should delete your code afte AC.










newton ..................... simply the best player.

joehuang92
New poster
Posts: 9
Joined: Sat Nov 18, 2006 4:56 pm
Location: Taiwan
Contact:

120 Stack of flapjack...

Post by joehuang92 » Tue Feb 20, 2007 2:41 pm

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?

joehuang92
New poster
Posts: 9
Joined: Sat Nov 18, 2006 4:56 pm
Location: Taiwan
Contact:

Post by joehuang92 » Wed Feb 21, 2007 8:27 am

Well, to my test using the algorithm discussed above, I get AC. So the output doesn't need to be the shortest path.

nbauernf
New poster
Posts: 5
Joined: Thu Mar 08, 2007 4:33 am

Post by nbauernf » Fri Mar 23, 2007 2:47 am

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 =).

owokko
New poster
Posts: 7
Joined: Sat Apr 28, 2007 7:11 am

120 (Stacks of Flapjacks)

Post by owokko » Sun May 06, 2007 1:52 pm

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 :

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);
}
And other question is "The input is terminated by end-of-file" !?

I use

Code: Select all

  if(cin.eof())    break; 
Is it correct?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun May 06, 2007 9:01 pm

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

User avatar
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Can anyone show me a tricky input?

Post by algoJo » Sat May 26, 2007 6:39 pm

I got multiple WA on this problem.
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
OUTPUT

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

Can someone post more tricky I/O set?
Thanks :D

anderson101866
New poster
Posts: 5
Joined: Sat Jul 28, 2007 6:33 am
Location: Taiwan

120 WA plz help me~(I need more test case)

Post by anderson101866 » Sat Jul 28, 2007 6:45 am

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!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Jul 28, 2007 10:12 pm

Dont open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu » Mon Dec 03, 2007 10:25 pm

To Sedefcho:

Plz correct ur i/o set....



To algoJo:
The problem statement:
all pancakes separated by a space.

So, there is no such Input that u given...
Amra korbo joy akhdin............................

anderson101866
New poster
Posts: 5
Joined: Sat Jul 28, 2007 6:33 am
Location: Taiwan

Post by anderson101866 » Wed Dec 26, 2007 6:15 pm

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
:) I think you maybe forgot one condition in the problem.
"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
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

amacfie
New poster
Posts: 2
Joined: Tue Dec 23, 2008 3:36 am

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

Post by amacfie » Tue Dec 23, 2008 3:38 am

be aware that the bring-to-top method is not always optimal:

http://www.google.com/url?sa=t&source=w ... CfG0QBaWIg

vinocit
New poster
Posts: 10
Joined: Mon Oct 13, 2008 10:11 am

WA ?

Post by vinocit » Fri Jan 30, 2009 11:08 am

Could any one temme wats wrong with my prog

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;
}
If there are more than one solution is there any criteria to select one among them? :|

Post Reply

Return to “Volume 1 (100-199)”