Flipping Pancake

From Progteam

Revision as of 01:45, 14 October 2009 by Msobell (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by Msobell.



Flipping Pancake
Problem Number 2275
Sorter: Uncategorized
Source: Unknown
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2275



Flipping Pancake is problem number 2275 on the Peking University ACM site.

SOLVED!!!

I solved this actually, but the code is sitting somewhere on Eric's shared directory or something like that. I don't entirely remember what the path is/how you access it, but the solution does exist! Somewhere...
- Nina

Thanks -- figured it out.
- Max So.

CODE

//RUNNING: java Main < input.txt 

import java.util.*;

public class Main {

    public static Scanner in;
    public static int len = 0;
    public static String out = "";
    public static int count;

    public static void main(String[] args) {
	in = new Scanner(System.in);
	solve();
    }

    public static void solve() {
	while (true) {
	    out = "";
	    count = 0;
	    len = in.nextInt();
	    //	    System.out.println("Length: " + len);
	    if (len == 0)
		System.exit(0);
	    Stack<Integer> s = new Stack<Integer>();
	    for (int i = 0; i < len; i++) {
		s.push(in.nextInt());
	    }
	    flip( s, len );
	    solveThis( s, len );
	    System.out.println( count + " " + out );
	}
    }

    public static boolean inOrder(Stack<Integer> s) {
	boolean inOrder = true;
		/*Stack<Integer> hold = new Stack<Integer>();
	while (!s.empty() && inOrder == true) {
	    hold.push(s.pop());
	    Integer one = (Integer) hold.peek();
	    try { 
		Integer two = (Integer) s.peek();
		if (two > one)
		    inOrder = false;
	    } catch (EmptyStackException e) {
		inOrder = true;
	    }
	}
	while (!hold.empty()) {
	    s.push(hold.pop());
	}
	return inOrder; */
	for( int i = 0; i < len; i++ ) {
	    inOrder = s.search(i) < s.search(i+1);
	    //	    System.out.println("Comparing " + i + " and " + (i+1) + " " + inOrder);
	    if( !inOrder ) break;
	}
	return inOrder;
    }

    public static void flip(Stack<Integer> s, int n) {
	Queue<Integer> q = new LinkedList<Integer>();
	for (int i = 0; i < n; i++) {
	    q.add(s.pop());
	}
	for (int i = 0; i < n; i++) {
	    s.push(q.remove());
	}
	//	System.out.println("Flipping " + n);
    }

    public static void solveThis(Stack<Integer> s, int n) {
	int bigPos = s.search(n); //assume n = unsorted ones
	if( bigPos == -1 || inOrder(s) ) return;
	//	System.out.println("Pos of biggest: " + bigPos);
	//	printThis(s);
	/*
	 * Gets the biggest one on top - don't need if bigPos == 1
	 */
	if( bigPos > 1 && !(bigPos == n) ) {
	    flip(s, bigPos);
	    count++;
	    out = out + bigPos + " ";
	    //	    printThis(s);
	}
	/*
	 * Now flips n so its on the bottom
	 */
	if( !inOrder(s) && !(bigPos == n) ) {
	    flip(s, n);
	    count++;
	    out = out + n + " ";
	    //	    printThis(s);
	}
	// 		System.out.println(out);
	solveThis(s, n - 1);
    }

    public static void printThis(Stack<Integer> s) {
	Stack<Integer> hold = new Stack<Integer>();
	while (!s.empty()) {
	    System.out.print(s.peek() + " ");
	    hold.push(s.pop());
	}
	System.out.println();
	while (!hold.empty()) {
	    s.push(hold.pop());
	}
    }
}
Personal tools