Mostrando las entradas con la etiqueta cola de equipo. Mostrar todas las entradas
Mostrando las entradas con la etiqueta cola de equipo. Mostrar todas las entradas

lunes, diciembre 13, 2010

Cola de Equipo - Problema UVA 540

El problema de colas de equipo se puede resolver en java utilizando una cola de colas. El enunciado del mismo se encuentra en el enlace http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=481


import java.io.*;
import java.util.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
    }

    void Begin() throws Exception {
        int cont = 0;
        while(true) {
            cont++;
            // Cada caso comienza con un numero de equipos t entre 1 y 1000
            int t = Integer.parseInt(in.readLine());
            if(t==0) break;                     // Si t=0, el proceso termina
            System.out.println("Scenario #" + cont);
            // En este mapa se relaciona cada elemento con el equipo al que pertenece
            Map<Integer, Integer> mapa = new HashMap<Integer, Integer>();
            // Para cada uno de los equipos
            for (int i=0; i<t; i++) {
                String[] tmp = in.readLine().split("\\s+");
                // El primer número de la línea es la cantidad de miembros del equipo
                int numMiembros = Integer.parseInt(tmp[0]);
                for (int j = 1; j<=numMiembros; j++) {
                    mapa.put(Integer.parseInt(tmp[j]), i);  // Cada miembro se guarda en el mapa
                }
            }
            String instruccion;
            Queue<Queue> colaE = new LinkedList<Queue>();   // Cola de colas
            do {
                // Cada renglón es una instruccion ENQUEUE, DEQUEUE o STOP
                String[] tmp = in.readLine().split("\\s+");
                instruccion = tmp[0];
                // Si es ENQUEUE la segunda parte de la instrucción es el valor a encolar
                if(instruccion.equals("ENQUEUE")) {
                    int valor  = Integer.parseInt(tmp[1]);  // Valor a encolar
                    int equipo = mapa.get(valor);           // Equipo al que pertenece
                    boolean flag = true;
                    // Identifica si en la cola hay algún miembro de su equipo
                    for (Queue<Integer> x : colaE) {    
                        if (x.isEmpty()) colaE.remove(x);
                        if (!x.isEmpty()) {
                            // Si hay un miembro del equipo se agrega al final de esa subcola
                            if (mapa.get(x.peek()) == equipo) {
                                x.add(valor);
                                flag = false;
                                break;
                            }
                        }
                    }
                    if(flag) {
                        // Si no hay miembros del equipo en la cola, crea una nueva subcola y se agrega
                        Queue<Integer> temporal = new LinkedList<Integer>();
                        temporal.add(valor);
                        colaE.add(temporal);
                    }
                }
                // Si es DEQUEUE se eliminan las subcolas vacías y se retira el primer elemento
                if (instruccion.equals("DEQUEUE")) {
                    while (colaE.peek().size() == 0) colaE.remove();
                    System.out.println(colaE.peek().poll());
                }
                if(instruccion.equals("STOP")) System.out.println();
            } while (!instruccion.equals("STOP"));
        }
    }
}

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...