# Monkey Vines

### From Progteam

Sorter: | Mlc413 |
---|---|

Source: | GNYR ICPC 2007 |

Link: | "http://www.acmgnyr.org/year2007/F.pdf" |

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