120 - Stacks of Flapjacks

[Hilly Billy]

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]

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]

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]

There are some way already described:
http://acm.uva.es/board/viewtopic.php?t ... forum=13&3
Maybe it will help you.

[ftomi]

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]

Thanks a LOT!

[FlyDeath]

<font size=-1>[ This Message was edited by: FlyDeath on 2002-03-21 14:16 ]</font>

[C8H10N4O2]

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]

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]

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]

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{

static String ReadLn (){
StringBuffer s = new StringBuffer("");
int car = -1;
try{
do{
car = System.in.read();
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 int[] ordenado;

public static void main (String[] args){

String line;
while((line = ReadLn()) != null){
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 = "";

ordenado = sort(s);

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++){
if(((Integer)s.elementAt(i)).intValue() != ordenado){
/*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++){
tmp.addElement(res.pop());
}
for(int i = 0; i < tmp.size(); i++){
res.push(tmp.elementAt(i));
}
//System.out.println("After: " + res);
return res;
}

}

[/java]

[ec3_limz]

[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]

Hi
I have finally solved this problem, if you want I can post it here.

[Ozton]

This is my source code...T.T
please check code...
[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]

[yiuyuho]

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

Does anyone know about this? I would like to have some further information on it.

Thanks