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"));
        }
    }
}

3 comentarios:

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...