Page 1 of 8
Posted: 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

Posted: 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++.

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

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

Posted: Sat Feb 23, 2002 12:31 am
There are some way already described:
http://acm.uva.es/board/viewtopic.php?t ... forum=13&3

Posted: 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");
}``````

Posted: Sat Feb 23, 2002 3:42 am
Thanks a LOT!

Posted: Thu Mar 21, 2002 1:17 pm
<font size=-1>[ This Message was edited by: FlyDeath on 2002-03-21 14:16 ]</font>

Posted: 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");
}
}
``````

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

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

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

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]

#120 - WA

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

Posted: Thu Dec 12, 2002 12:41 pm
Hi
I have finally solved this problem, if you want I can post it here.

120 - Stacks of Flapjacks

Posted: Tue Jan 07, 2003 7:57 pm
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]

120 Stacks of Flapjacks

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