Poj Solution 1416

http://poj.org/problem?id=1416

/* @author: */
import java.util.*;
 public class Main {  
 private int target;
 private char num[];
 private int max;
 private StringBuffer s;
 private StringBuffer result;
 boolean check;

public Main(int target,char num[]){
    this.target=target;
    this.num=num;
    max=0;
     s=new StringBuffer("");
     result=new StringBuffer("");
}

public boolean getCheck(){
    return check;
}

public int getMax(){
   return max;
}

public String getResult(){
   return result.toString();
}

private boolean isOk(){
  int sum=0;
 for(int i=0;i< num.length;i++){
    sum+=num[i]-'0';
  } 
   if(sum>target) return false;
   else return true;
}

void  dfs(int startIndex,int sumTotal){
  int i,t=0;
  if(startIndex==num.length)
  {
    if(sumTotal==max){
        check=false;
     }else if(sumTotal>max){
        check=true;
        max=sumTotal;
        result=s;
      }
   }
  for(i=1;i< num.length-startIndex+1;i++){
     t*=10;
    t+=num[startIndex+i-1]-'0';
    if(t+sumTotal>target)
     return;
    StringBuffer tt=new StringBuffer(s);
    s.append(Integer.toString(t)).append(" ");

    dfs(startIndex+i,sumTotal+t);
    s=tt;
  }
}

public static void main(String args[]){
 Scanner sc=new Scanner(System.in);
  while(sc.hasNext())
  {
  
   int target=sc.nextInt();
   char num[]=sc.next().toCharArray();
    if(target==0)
      break;
    Main m=new Main(target,num);
    if(!m.isOk())
       System.out.printf("errorn");
    else{
      m.dfs(0,0);
     if(!m.getCheck())
         System.out.printf("rejectedn");
     else{
       System.out.print(m.getMax()+" ");
       System.out.println(m.getResult());
     }

     }
      
  }
 }
}

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *