Parencodings

From Progteam

Revision as of 17:39, 22 May 2008 by Mlc413 (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by Mlc413.


Parencodings
Problem Number 1068
Sorter: Uncategorized
Source: Unknown
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1068



Parencodings is problem number 1068 on the Peking University ACM site.

There is probably a more elegant way to do this, but the below code works on PKU.

import java.util.*;

public class Main{

    public static Scanner in;
 
    public static void main(String[] args){
        in=new Scanner(System.in);

        doStuff();
    }

    public static void doStuff(){
        int N=in.nextInt();

        for(int i=0;i<N;i++){
            int n = in.nextInt();
	    solve(n);
        }
    }

    public static void solve(int n){
	String paren = "";
	int prev = 0;
	int a = in.nextInt();
	for(int j =0; j < n;j++){
	    for(int i =0;i<a-prev; i++){
		paren += '(';
	    }
	    paren += ')';
	    prev=a;
	    if(j < n-1)
		a=in.nextInt();
	}

	int len = paren.length();
	//	System.out.println(len + " " + paren);
	for(int k =0; k < len; k++){
	    if(paren.charAt(k)==')'){
		int dist =0;
		for(int j = 0; j <= k ; j++){
		 
		    if((paren.charAt(k-j)=='(')){
			System.out.print("" + dist + ' ');
			paren = paren.substring(0, k-j) + '*' + paren.substring(k-j+1, len);
			j = k;
			//	System.out.println(paren);
		    }
		    if(paren.charAt(k-j)==')'){
			dist++;
		    }
		}
	    }
	}

	System.out.println();
    }

}

Personal tools