# Flipping Burned Pancakes

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by hjfreyer.

 Sorter: hjfreyer GNYR ICPC 2007 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){

//	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;
}

}

```