Monkey Vines

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

 Sorter: Mlc413 GNYR ICPC 2007 "http://www.acmgnyr.org/year2007/F.pdf"

 This problem has been solved by Mlc413.

This is problem F from the GNYR ICPC 2007

Calculate the minimum number of monkeys needed to balance a particular (binary) vine configuration. Each vine must hold at least one monkey.

This basically comes down to calculating 2^n, where n is the depth of the tree.

```import java.util.*;

public class Main{
public static Scanner in;
public static void main(String[] args){
in = new Scanner(System.in).useDelimiter("\\n");
doStuff();
}

public static void doStuff(){
int N = in.nextInt();
for(int i = 1; i <=N; i++){
System.out.print(i+" ");
solve(in.next());

}

}

public static void solve(String str){
int len = str.length();
int max = 0, cur = 0;
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == '['){cur++;}
else if(str.charAt(i) == ']'){cur--;}

if(cur>max){max=cur;}
}
System.out.print((int)Math.pow(2, max) + "\n");
}

}

```