Flipping Burned Pancakes

From Progteam

Revision as of 18:38, 22 February 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by hjfreyer.


Flipping Burned Pancakes
Problem Number E
Sorter: hjfreyer
Source: GNYR ICPC 2007
Link: http://www.acmgnyr.org/year2007/E.pdf




This is problem E from the GNYR ICPC 2007





Code

import java.util.*;

public class Main{
    public static Scanner in;

    public static boolean[] bottom;
    public static int[] val;

    public static void main(String[] args){
	in = new Scanner(System.in);
	doStuff();
    }
 
    public static void doStuff(){
	int N = in.nextInt();
	for(int i = 1; i <=N; i++){
	    solve(i);	    
	}

    }

    public static void solve(int round){
	flips.clear();
	int cakes = in.nextInt();
	
	bottom=new boolean[cakes];
	val=new int[cakes];

	for(int i=0;i<cakes;i++){
	    String n=in.next();

	    if(n.charAt(0)=='+'){
		bottom[i]=true;
		val[i]=Integer.parseInt(n.substring(1));
	    } else if(n.charAt(0)=='-'){
		bottom[i]=false;
		val[i]=Integer.parseInt(n.substring(1));
	    } else
		throw new AssertionError();
	}

	correct(cakes-1);
	System.out.printf("%d %d ",round,flips.size());
	for(int i:flips)
	    System.out.printf("%d ",i+1);

	System.out.println();

	/*	for(int i=0;i<cakes;i++){
	    System.out.printf("%+d ",bottom[i]?val[i]:-val[i]);
	    }*/
	//	System.out.println();
    }

    public static List<Integer> flips=new LinkedList<Integer>();
    public static void correct(int idx){

	
	//	System.out.printf("Correct(%d)\n",idx);

	if(idx==0){
	    if(!bottom[0]){
		flip(0);
	    }   
	    return;
	}
	
	int max=maxIdx(idx);

	if(max==idx && bottom[max]){
	    correct(idx-1);
	    return;
	}
	
	if(max!=0)
	    flip(max);
	
	if(bottom[0]){
	    flip(0);
	}
	flip(idx);
	    
	correct(idx-1);
    }
    
    public static void flip(int idx){
	flips.add(idx);
	
	//	System.out.printf("%d ",idx+1);

	for(int i=0;i<=idx;i++){
	    bottom[i]=!bottom[i];
	}
	int l=0;
	int r=idx;
	
	while(l<r){
	    int tmp=val[l];
	    val[l]=val[r];
	    val[r]=tmp;
	
	    boolean tmp_b=bottom[l];
	    bottom[l]=bottom[r];
	    bottom[r]=tmp_b;

	    l++;
	    r--;
	}
    }

    public static int maxIdx(int upTo){
	int max=-1;
	int max_idx=-1;

	for(int i=0;i<=upTo;i++){
	    if(val[i]>max){
		max=val[i];
		max_idx=i;
	    }
	}

	return max_idx;
    }
    
}

Personal tools