0
Your rating: None
CodeChef submission 27240 (JAVA) 

CodeChef submission 27240 (JAVA) plaintext list. Status: WA, problem C4, contest MAY09. By rosyish (rosyish), 2009-05-09 19:46:42.
  1. import java.io.*;
  2. import java.util.*;
  3. public class Main {
  4.     
  5.     public static void print(Object... ob){
  6.         System.out.println(""+Arrays.deepToString(ob));
  7.     }
  8.     
  9.     public static final int ival(String s){
  10.         return Integer.parseInt(s);
  11.     }
  12.     
  13.     public static boolean isIncrease(String s){
  14.         
  15.         for(int i=1;i<s.length();i++){
  16.             if(s.charAt(i)<s.charAt(i-1))return false;
  17.         }
  18.         return true;
  19.     }
  20.     
  21.     public static String minima(String s1,String s2){
  22.         if(s1.compareTo(s2)<0)return s1;
  23.         return s2;
  24.     }
  25.     
  26.     public static void main(String[] args)throws IOException {
  27.        
  28.          int T , NI , R , slen;
  29.         String shelf;
  30.         String INF = (char)('z'+11)+"";
  31.         InputStreamReader isr = new InputStreamReader(System.in);
  32.         BufferedReader br = new BufferedReader(isr);
  33.         T = ival(br.readLine());
  34.         
  35.        
  36.        
  37.         while(T-- > 0){
  38.             String[] line = br.readLine().split(" ");
  39.             NI = ival(line[0]);
  40.             shelf = br.readLine();
  41.             slen = shelf.length();
  42.             R = ival(br.readLine());
  43.             int[] nutri = new int[NI];
  44.             String[][] mins = new String[R+1][slen];
  45.             char[] sarr = shelf.toCharArray();
  46.             
  47.             for(int i=0;i<NI;i++){
  48.                 nutri[i] = ival(line[i+1]);
  49.             }
  50.             
  51.             for(int i=0;i<R+1;i++){
  52.                 for(int j=0;j<slen;j++){
  53.                     mins[i][j] = INF;
  54.                 }
  55.             }
  56.  
  57.             
  58.             int lastNutri = nutri[sarr[slen-1]-'a'];
  59.             if(lastNutri<=R) mins[lastNutri][slen-1] = ""+sarr[slen-1];
  60.             
  61.             for(int n=slen-2;n>=0;n--){
  62.                 for(int m=0;m<R+1;m++){
  63.                       int nut = nutri[sarr[n]-'a'];
  64.                       if(m-nut<0)mins[m][n] = mins[m][n+1];
  65.                       else if(m==nut)mins[m][n] = minima(mins[m][n+1],sarr[n]+"");
  66.                       else{
  67.                           if(isIncrease(sarr[n]+mins[m-nut][n+1]) && !mins[m-nut][n+1].equals(INF)){
  68.                               mins[m][n] = minima(mins[m][n+1],sarr[n]+mins[m-nut][n+1]);
  69.                           }
  70.                           else{
  71.                               mins[m][n] = mins[m][n+1];
  72.                           }
  73.                       }
  74.             }
  75.             
  76.                
  77.         }
  78.            if(mins[R][0].equals(INF))System.out.println("IMPOSSIBLE");
  79.            else System.out.println(mins[R][0]);
  80.         
  81.     }
  82.  
  83.     }   
  84.  
  85.     
  86. }

Comments