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

Post Reply
Hilly Billy
New poster
Posts: 1
Joined: Mon Feb 11, 2002 2:00 am

Post by Hilly Billy » Mon Feb 11, 2002 6:20 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 :smile:

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Post by paulhryu » Tue Feb 12, 2002 1:37 am

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

Post by idler » Fri Feb 22, 2002 5:11 pm

I know the algorithm to solve the problem.
But I DO NOT KNOW how to input the data!
Help!!! :sad:

<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:

Post by ftomi » Sat Feb 23, 2002 12:31 am

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

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi » Sat Feb 23, 2002 12:55 am

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

Post by idler » Sat Feb 23, 2002 3:42 am

Thanks a LOT! :smile:

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Thu Mar 21, 2002 1:17 pm

<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
Location: Pasadena, CA

Post by C8H10N4O2 » Sun Mar 24, 2002 6:02 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
Location: Pasadena, CA

Post by C8H10N4O2 » Sun Mar 24, 2002 4:19 pm

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

Post by cyfra » Wed Mar 27, 2002 4:26 pm

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 :smile:

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar » Thu Jul 04, 2002 7:09 am

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
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

#120 - WA

Post by ec3_limz » Mon Nov 11, 2002 4:07 pm

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

Post by PMNOX » Thu Dec 12, 2002 12:41 pm

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

Post by Ozton » Tue Jan 07, 2003 7:57 pm

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]
Hi~~^^

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

120 Stacks of Flapjacks

Post by yiuyuho » Sun Jan 12, 2003 12:01 pm

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

Post Reply

Return to “Volume 1 (100-199)”