## 120 - Stacks of Flapjacks

Moderator: Board moderators

Hilly Billy
New poster
Posts: 1
Joined: Mon Feb 11, 2002 2:00 am
Having some problems with these two quite a bit. I am trying in in pascal so if anyone can give me a hand taht would be most appreciated.
if you could just type thee right code into a reply that would be great

Thx a lot

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Well, I can help you with 120. Okay, well, you see, say you have:
4 3 5 2 1
You start from the right and sort the pancakes one by one, kind of like a backwards selection sort.
4 3 5 2 1
So you try to get 5 into the last spot, but you can't with a single flip. So instead you flip so that the 5 comes to the front.
4 3 5 2 1
5 3 4 2 1 after flip(3)
And then you can flip(1) to get
1 2 4 3 5
and there you have got 5 in the right place.
And now, you get 4 to the front as we got 5 to the front before:
4 2 1 3 5 with flip(3)
3 1 2 4 5 with flip(2)
Now we have 4 and 5 in place! But look, 3 is already in the front, no need to bring it to the front. Just flip it into place
2 1 3 4 5 with flip(3)
And then, 2 is already in the front, so 1 2 3 4 5 after flip(4) and there you have sorted it.
So the output should be 3 1 3 2 3 4 0.
Just make sure you don't do any meaningless flips, so don't send anything to the front if it's already sorted or anything like that.
And if I knew Pascal I could post my code, but I did it in C++.

idler
New poster
Posts: 9
Joined: Thu Feb 21, 2002 2:00 am
Location: China
I know the algorithm to solve the problem.
But I DO NOT KNOW how to input the data!
Help!!!

<font size=-1>[ This Message was edited by: idler on 2002-02-22 16:14 ]</font>

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
There are some way already described:
http://acm.uva.es/board/viewtopic.php?t ... forum=13&3

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
But I like it much better:

Code: Select all

`````` int i;
while (scanf("%*[ t]"), ungetc(fgetc(stdin),stdin)!=EOF) {
while (scanf("%*[ t]"), ungetc(fgetc(stdin),stdin)!='n') {
scanf("%d",&i);
printf("%d-",i);
}
fgetc(stdin);
printf("EOLn");
}``````

idler
New poster
Posts: 9
Joined: Thu Feb 21, 2002 2:00 am
Location: China
Thanks a LOT!

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
<font size=-1>[ This Message was edited by: FlyDeath on 2002-03-21 14:16 ]</font>

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
After 5 WA, I can't seem to find a test case to disprove my code. Can someone show me my flaw? Thank you.

Code: Select all

``````#pragma warning (disable : 4786)
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>

using namespace std;

void Tokenize(const string& S,vector<string>& T,const string& D = " ")
{
string::size_type LP,P;
LP=S.find_first_not_of(D);
P=S.find_first_of(D, LP);

while (string::npos!=P||string::npos!=LP)
{
T.push_back(S.substr(LP,P-LP));
LP = S.find_first_not_of(D, P);
P = S.find_first_of(D, LP);
}
}

vector<string> gLine(vector<string>&T)
{
char B[1000];
T.clear();
if(gets(B)!=NULL)
Tokenize(B,T);
return T;
}

void Flip(vector<int> &X, int T)
{
reverse(&X[0],&X[X.size()-T+1]);
}

void main()
{
vector<string> T;
vector<int> X,S;
int i;
vector<int>::iterator I,J;
while(gLine(T).size()>0)
{
X.clear();
for(i=0;i<T.size();i++)
{
X.push_back(strtol(T[i].c_str(),NULL,10));
}
S=X;
stable_sort(S.begin(),S.end());
for(I=S.end()-1;I>=S.begin();I--)
{
J=find(X.begin(),X.end(),*I);
if(X.end()-J!=S.end()-I)
{
if(J!=X.begin())
{
printf("%d ",X.end()-J);
Flip(X,X.end()-J);
}
printf("%d ",S.end()-I);
Flip(X,S.end()-I);
}
}
printf("0n");
}
}
``````

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
It says the program uses a special judging program. Does this mean that as long as my flips give the final result, I can be redundant?

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

I am not sure...
I think that if you get the final configuration in the minimum number of flips it doesn't matter if you first made flip(1) and later flip(2) or in other way (but only if you get the final configuration)...

thy to read the solution written by paulhryu...
I think he did it right..

Good Luck

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
Hi, I am having some trouble getting this one right...

I try to place the largest pancake to the top of the stack first, and then flip one more time to the right depth in the stack. At this point the k-th pancake is in the correct position, and I sequencially work my way up sorting the rest of the stack. I get rid of unnecesaary flips by always checking what the next incorrectly positioned pancake is before doing any flipping. I do this, by checking against a previously ordered array.

I havent been able to find THE test case that brakes this, however! i cant get it accepted either!...

This is my code.

[java]
import java.io.*;
import java.util.*;

class Problem120{

StringBuffer s = new StringBuffer("");
int car = -1;
try{
do{
if ((car < 0) || (car == '\n')){
break;
}
else{
s.append((char) car);
}
} while(car > 0);
}
catch (IOException e){
return (null);
}
if (car < 0){
return null;
}else{
return s.toString();
}
}

public static void main (String[] args){

String line;
StringTokenizer st = new StringTokenizer(line);
if (st.countTokens() == 0){
continue;
}
int n = st.countTokens();
Stack s = new Stack();
for(int i = 0; i < n; i++){
Integer myNumero = new Integer(st.nextToken());
s.insertElementAt(myNumero, 0);
}

System.out.println(line.trim());
String res = "";

int index;

while((index = goal(s)) != s.size()){

int pos = s.indexOf(new Integer(maximum(s,index)), index);

if(pos != s.size()-1){
res += (pos + 1) +" ";
s = flip(pos,s);
}

res += (index + 1) + " ";
s = flip(index,s);
}
System.out.println(res + "0");
}
}

public static int maximum(Stack s, int index){
int res = Integer.MIN_VALUE;
for(int i=index;i<s.size();i++){
res = Math.max(res,((Integer)s.elementAt(i)).intValue());
}
return res;
}

public static int goal(Stack s){

for (int i = 0; i < s.size(); i++){
/*System.out.println(((Integer)s.elementAt(i)).intValue()
+ " " +ordenado + " "+i);*/
return i;
}
}
return s.size();
}

public static int[] sort(Stack s){
int[] pila = new int[s.size()];

Stack tempStack = (Stack) s.clone();

for(int i=0;i<pila.length;i++)
pila = ((Integer)s.elementAt(i)).intValue();

for(int i = 0; i<pila.length-1;i++)
for(int j = 0;j<pila.length-i-1;j++)
if(pila[j] < pila[j+1]){
int temp = pila[j];
pila[j] = pila[j+1];
pila[j+1] = temp;
}
return pila;
}

public static Stack flip(int pos, Stack pila){
Stack res = (Stack) pila.clone();
Vector tmp = new Vector();
//System.out.println("Flip with: " + pos);
//System.out.println("Before: " + pila);
int n = pila.size();
for(int i = 0; i < n - pos; i++){
}
for(int i = 0; i < tmp.size(); i++){
res.push(tmp.elementAt(i));
}
//System.out.println("After: " + res);
return res;
}

}

[/java]

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

### #120 - WA

[cpp]#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int d[30];

inline int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}

void flip(int n) {
int i, j, temp;

for (i = 0, j = n; i < j; i++, j--) {
temp = d;
d = d[j];
d[j] = temp;
}
}

int main() {
char line[257];
int size, order[30], temp;
int i, j;

while (gets(line)) {
if (strlen(line) == 0)
break;

for (size = 0; sscanf(line, "%d %[^\0]", &d[size], line) == 2; size++)
order[size] = d[size];
order[size] = d[size];
size++;

for (i = 0; i < size; i++)
printf("%d ", d);
printf("\n");

qsort(order, size, sizeof(int), cmp);

for (i = size - 1; i >= 0; i--)
for (j = 0; j < size; j++)
if (order == d[j]) {
if (i != j) {
if (j != 0) {
flip(j);
printf("%d ", size - j);
}
if (i != 0) {
flip(i);
printf("%d ", size - i);
}
}
break;
}

printf("0\n");
}

return 0;
}[/cpp]

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
Hi
I have finally solved this problem, if you want I can post it here.

Ozton
New poster
Posts: 5
Joined: Sun Jan 05, 2003 10:27 am

### 120 - Stacks of Flapjacks

This is my source code...T.T
[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int i, j, position, length, stack[110], array[110];

char input_data[310];

void flip(int, int);

void Quick_sort(int [], int, int);
int Partition(int [], int, int);
void SWAP(int *, int *);
int search(int, int, int);

int main()
{

while (1) {

length = (int)strlen(gets(input_data));

if (length == 0)
break;

for (i = 0, j = 1; i < length; i++) {

if (input_data == ' ')
continue;

if (input_data != ' ') {
stack[j] = atoi(&input_data);
array[j] = stack[j];
j++;

if (input_data[i + 1] != ' ')
i++;
}

}

Quick_sort(array, 1, j - 1);

for (i = j - 1; i > 0; i--) {

if (array == stack)
continue;
else {

position = search(array, 1, i);

if (position == 1) {
flip(i, 1);
printf("%d ", j - i);
} else {
flip(position, 1);
printf("%d ", j - position);
flip(i, 1);
printf("%d ", j - i);

}

}

}

printf("0\n");

for (i = 0; i < 35; i++) {
stack = 0;
array = 0;
}

}

return 0;

}

void Quick_sort(int array[], int pivot, int n) {

int q;

if (pivot < n) {

q = Partition(array, pivot, n);

Quick_sort(array, pivot, q);
Quick_sort(array, q + 1, n);

}

return;

}

int Partition(int array[], int pivot, int n) {

int i, j, x = array[pivot];

i = pivot - 1;
j = n + 1;

do {

do {
j = j - 1;
} while (array[j] > x);

do {
i = i + 1;
} while (array < x);

if (i < j)
SWAP(&array, &array[j]);
else
return j;

} while (1);

}

void SWAP(int *a, int *b) {

int tmp = *a;
*a = *b;
*b = tmp;

}

int search(int value, int left, int right) {

int i;

for (i = left; i < right; i++)
if ( stack[i] == value)
return i;

return -1;

}

void flip(int bottom, int top) {

while (bottom != top && bottom > top)
SWAP(&stack[bottom--], &stack[top++]);

}
[/c]
Hi~~^^

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

### 120 Stacks of Flapjacks

I just read that Bill Gate actually did research on this problem and proved the complexity of the algorithm f(n) as the number of flips, n for the number of disks is (15/14)n<=f(n)<=(5n+5)/3