Cod sursa(job #1708734)

Utilizator trebedeaTraian Rebedea trebedea Data 27 mai 2016 21:18:08
Problema Sate2 Scor Ascuns
Compilator java Status done
Runda Marime 4.25 kb
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class Main {
   public int N, M, K;
   public int[] v;
    
   private boolean solutieThreePartition() {
        boolean[][] A;
      
    	if (M % 3 != 0)
	     return false;
    	

    	M /= 3;
		
        A = new boolean[M+1][M+1];
        boolean[][] aux = new boolean[M+1][M+1];
       
        //init dinamica
        A[0][0] = true;
		
        //recurenta dinamica
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= M; j++) {
				for (int k = j; k <= M; k++) {
					if (A[j][k] == false){
						if (j >= v[i]){
							aux[j][k] = A[j][k] || A[j - v[i]][k];
						}
					
						if (k >= v[i]){
							aux[j][k] = A[j][k] || A[j][k - v[i]];
						}
					 }
				}
			}

			for (int j = 0; j <= M; j++) {
				for (int k = j; k <= M; k++) {
					if (aux[j][k] == true){
						A[j][k] = aux[j][k];
						A[k][j] = A[j][k];
					}
				}
			}	
		}
		
		return A[M][M];
    }

    private boolean solutieFourPartition() {
        boolean[][][] A;
      
    	if (M % 4 != 0)
            return false;
    	
    	M /= 4;
		
        A = new boolean[M+1][M+1][M+1];
        boolean[][][] aux = new boolean[M+1][M+1][M+1];
        A[0][0][0] = true;
		
        //recurenta dinamica
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= M; j++) {
				for (int k = 0; k <= M; k++) {
					for (int l = 0; l <= M; l++) {
						if (A[j][k][l] == false){
							if (j >= v[i]){
								aux[j][k][l] = A[j][k][l] || A[j - v[i]][k][l];
							}
							if (k >= v[i]){
								aux[j][k][l] = A[j][k][l] || A[j][k - v[i]][l];
							}
							if (l >= v[i]){
								aux[j][k][l] = A[j][k][l] || A[j][k][l - v[i]];
							}
						}
					}
				}
			}

			for (int j = 0; j <= M; j++) {
				for (int k = 0; k <= M; k++) {
					for (int l = 0; l <= M; l++) {
						if (aux[j][k][l] == true){
							A[j][k][l] = aux[j][k][l];
							A[k][j][l] = A[j][k][l];
						}
					}	
				}
			}	
		}
		
		return A[M][M][M];
    }

    public static void main(String[] args) {
	ABC rezolvare = new ABC();

	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;
	int T;

 	try {
		br = new BufferedReader(new InputStreamReader(
	        		new FileInputStream("sate.in")));
	      	out = new PrintWriter(new BufferedOutputStream(
				new FileOutputStream("sate.out")));
	     	
		st = new StringTokenizer(br.readLine());
        	T = Integer.parseInt(st.nextToken());

		for(int j=0; j< T; j++){
			st = new StringTokenizer(br.readLine());
			rezolvare .N = Integer.parseInt(st.nextToken());
	        	rezolvare .M = Integer.parseInt(st.nextToken());
	        	rezolvare .K = Integer.parseInt(st.nextToken());
		    	//System.out.println(rezolvare.N + " " + rezolvare.M + " " + rezolvare.K + " ");

		     	int i = 0;
			rezolvare.v = new int[rezolvare.N];
			st = new StringTokenizer(br.readLine());
		       while (st.hasMoreElements()) {
	       		rezolvare.v[i++] = Integer.parseInt(st.nextToken());
	        	}

			boolean rez = false;
			switch (rezolvare .K) {
	            		case 3:  
	            			rez = rezolvare.solutieThreePartition();
	    				break;
		       	case 4:
	            			rez = rezolvare.solutieFourPartition();
	            			break;
			}            
	        
			//solutie
			if (rez == true){
				if (j!=(T-1))
					out.write("DA\n");
				else
					out.write("DA");
				//System.out.println("Exista solutie");
			} else {
				if (j!=(T-1))
					out.write("NU\n");
				else
					out.write("NU");
			}
			
			//afisare matrice solutie
			//rezolvare.printSolutie();
		}

	        
	    	out.close();
		br.close();
	    	
	} catch (Exception e) {
		e.printStackTrace();
	}
    }
    
	private void printInputVector() {
    		System.out.println("Vectorul de intrare are dimensiune " + N);
    		System.out.println("si componentele");
		for (int i=0; i<N; i++) {
			System.out.print(v[i] + " ");
		}
		System.out.println("");
	}
	
	/*private void printMatrix() {
    		System.out.println("\n####### Solutia este ##########");
       	for (int i = 0; i < sumape3+1; i++){ 
        		for(int j = 0 ; j < sumape3+1; j++)
    				System.out.print(M[i][j] + " ");
       	 	System.out.println();
       	 }
       }*/

}