Monkey Vines

From Progteam

Revision as of 02:21, 22 February 2008 by Mlc413 (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


Monkey Vines
Problem Number F
Sorter: Mlc413
Source: GNYR ICPC 2007
Link: "http://www.acmgnyr.org/year2007/F.pdf"




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

Personal tools