OJ Board

Code: Select all

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> sz, used;
int total, stick_size;

bool ok( int sum, int val, int piece ) {
    if( sum == 0 && piece == total ) return true;
    if( piece == total ) return false;
    int last = -1;

    for( int i = 0; i < sz.size(); ++i ) {
        if( used[i] == 1 ) continue;
        if( last == sz[i] ) continue;

        used[i] = 1;

        if( val - sz[i] == 0 ) {
            if( ok( sum-sz[i], stick_size, piece+1 ) )
                return true;
        } else if( val - sz[i] > 0 ) {
            if( ok( sum-sz[i], val-sz[i], piece ) )
                return true;
        }           

        used[i] = 0;            
        last = sz[i];    
    }
    return false;
}

int solve( int sum )
{
    used = vector<int>( sz.size(), 0 );

    random_shuffle( sz.begin(), sz.end() );

    int sol = (int)( sqrt( (double)sum ) + .5 ) + 1;
    for( ; sol > 0; --sol ) {
        if( sum % sol != 0 ) continue;
    
        stick_size = sum / sol;
        total = sol;
        
        if( ok( sum, stick_size, 0 ) ) return stick_size;
    }

    return sum;
}


int main( void )
{
    for( int n; scanf( "%d", &n ) && n != 0; ) {
        int sum = 0;
        sz.resize( n ); 
        for( int i = 0; i < n; ++i ) {
            scanf( "%d", &sz[i] );
            sum += sz[i];
        }
        printf( "%d\n", solve( sum ) );
    }
return 0;
}

Code: Select all

import java.io.*;
import java.util.*;
public class Main {

	
	public static void main(String[] args) {
		Lectura leer = new Lectura("entrada.txt");
		leer.Abrir();
		int casos = leer.getCasos();
		//System.out.println(casos);
		String parte1=leer.getParte1();
		//System.out.println(parte1);
		String parte2=leer.getParte2();
		//System.out.println(parte2);
		ArrayList dinamico1 = new ArrayList();
		ArrayList dinamico2 = new ArrayList();
		Scanner scan1 = new Scanner(parte1);
		Scanner scan2 = new Scanner(parte2);
		while(scan1.hasNext()){
			dinamico1.add(scan1.nextLine());
		}
		//System.out.println(dinamico1);
		while(scan2.hasNext()){
			dinamico2.add(scan2.nextLine());
		}
		//System.out.println(dinamico2);
	
		for(int i=0;i<casos;i++){
			int cantidad = Integer.parseInt(dinamico1.get(i).toString());	
			if(cantidad<=50){
				//System.out.println(cantidad);
				String dato = dinamico2.get(i).toString();
				//System.out.println(dato);
				int largo=cantidad;
				int[] sticks = new int[largo];
				int k=0;
				StringTokenizer token = new StringTokenizer(dato);
				while(token.hasMoreTokens()){
					String aux=token.nextToken();
					int aux1=Integer.parseInt(aux);
					sticks[k]=aux1;
					k++;
				}
				int[] sticksAnterior = sticks;
				Quicksort quick = new Quicksort();
				quick.ordena(sticks);
				int max = sticks[0];
				int suma = 0;
				//System.out.println(max);
				
				for(int j=0;j<sticks.length;j++){
					suma = suma + sticks[j];			
				}
			
			//System.out.println(sum);
			for(int meta = max; meta<=suma;meta++){
				if(suma%meta==0){
					 int particiones = suma/meta;
					 if(particiones(sticks,particiones)){
						 System.out.println(meta);
						 break;
					 }
					 
				}
			}
		}
		else
		{
		System.out.println("ERROR");
		}
			
	}
}
	static boolean particiones(int [] sticks, int partes){
		int n=sticks.length;
		boolean M[]= new boolean[partes+1];
		M[1]=true;
		for(int i=1;i<n;i++){
			for(int j=sticks[i];j<partes+1;j++){
				M[j]=M[j]||M[j-sticks[i]];
			}
		}
		return M[partes];
	}
}