TEMA

PROBLEM 1340 - URI Fórum 1.0

URI Online Judge preguntado 8 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • Gabriel Duarte respondido 5 years ago

    Não tem como você descobrir qual é o caso que está falhando em seu código, todos os inputs são ocultos, essa análise tem que ser na mão, tentar gerar casos que quebrem mesmo.

    MOD
  • Hamilton José Brumatto respondido 5 years ago

    Apesar de várias análise, minhas submissões retornam com "wrong answer 10%" Há alguma forma de verificar onde se dá a discrepância?

  • Matheus Carvalho respondido 6 years ago

    estou recebendo RunTime Error, porém já estou a dias tentando entender o que tem de errado e não acho, quem estiver disposto a me ajudar, desde já, grato!

    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    
    public class Main {
        static int[] pilha;
        static int heapSize = 0;
        static int[] count = new int[3];
        static int x1 = 0;
        static int x2 = 0;
        static int inicio = 0;
        static int fim = 0;
        static int[] vFilaInsere;
        static int[] vFilaPrioInsere;
        static int[] vFilaRetira;
        static int[] vFilaPrioRetira;
    
        public static void filaInsere(int x, int i) {
            vFilaInsere[i] = x;
        }
    
        public static int filaRetira(int j) {
            return vFilaInsere[j];
        }
    
        public static boolean pilhaVazia() {
            return (inicio == fim);
        }
    
        public static boolean pilhaCheia() {
            return (fim == pilha.length);
        }
    
        public static void push(int x) {
            if (!pilhaCheia()) {
                pilha[fim++] = x;
            }
        }
    
        public static int pop() {
            int aux;
            if (!pilhaVazia()) {
                aux = pilha[fim - 1];
                fim--;
                return aux;
            } else {
                return -100000000;
            }
        }
    
        private static void filaPrioInsere(int x) {
            int pai, filho, swap;
            filho = heapSize;
            pai = (filho - 1) / 2;
            vFilaPrioInsere[heapSize] = x;
            while (vFilaPrioInsere[pai] < vFilaPrioInsere[filho]) {
                swap = vFilaPrioInsere[pai];
                vFilaPrioInsere[pai] = vFilaPrioInsere[filho];
                vFilaPrioInsere[filho] = swap;
                filho = pai;
                pai = (pai - 1) / 2;
            }
            heapSize++;
        }
    
        public static int filaPrioridadeRetira() {
            int raiz = vFilaPrioInsere[0];
            swapPosicao();
            return raiz;
        }
    
        public static void swapPosicao() {
            heapSize--;
            for (int i = 0; i < heapSize; i++) {
                vFilaPrioInsere[i] = vFilaPrioInsere[i + 1];
            }
            maxHeapify(0, heapSize);
        }
    
        private static void maxHeapify(int i, int vetorSize) {
            int maior = 2 * i + 1;
            int direita = maior + 1;
            if (maior < vetorSize) {
                if (direita < vetorSize
                        && vFilaPrioInsere[maior] < vFilaPrioInsere[direita]) {
                    maior = direita;
                }
                if (vFilaPrioInsere[maior] > vFilaPrioInsere[i]) {
                    swap(maior, i);
                    maxHeapify(maior, vetorSize);
                }
            }
        }
    
        public static void swap(int j, int jProx) {
            int aux = vFilaPrioInsere[j];
            vFilaPrioInsere[j] = vFilaPrioInsere[jProx];
            vFilaPrioInsere[jProx] = aux;
        }
    
        public static void zerar() {
            for (int i = 0; i < vFilaInsere.length; i++) {
                filaInsere(0, i);
                vFilaPrioInsere[i] = 0;
                pop();
            }
            x1 = 0;
            x2 = 0;
        }
    
        public static void main(String[] args) throws java.lang.Exception {
            BufferedReader input = new BufferedReader(new InputStreamReader(
                    System.in));
            String size1;
            int comando;
            int size;
            int i = 0;
            size1 = input.readLine();
    
            while (!size1.equals("")) {
                size = Integer.parseInt(size1);
                count[0] = 0;
                count[1] = 0;
                count[2] = 0;
                heapSize = 0;
                vFilaInsere = new int[size];
                vFilaPrioInsere = new int[size];
                vFilaRetira = new int[size];
                vFilaPrioRetira = new int[size];
                pilha = new int[size];
                for (i = 0; i < size; i++) {
                    String linha = input.readLine();
                    comando = Integer.parseInt(linha.substring(0, 1));
                    int valor = Integer
                            .parseInt(linha.substring(2, linha.length()));
                    if (comando == 1) {
                        filaInsere(valor, x1);
                        push(valor);
                        filaPrioInsere(valor);
                        x1++;
                    } else if (comando == 2) {
                        int recebido = filaRetira(x2);
                        if (recebido != valor) {
                            count[0] = 1;
                        }
                        recebido = pop();
                        if (recebido != valor) {
                            count[1] = 1;
                        }
                        recebido = filaPrioridadeRetira();
                        if (recebido != valor) {
                            count[2] = 1;
                        }
                        x2++;
                    }
                }
                if (count[0] + count[1] + count[2] == 3) {
                    System.out.println("impossible");
                } else if (count[0] + count[1] + count[2] < 2) {
                    System.out.println("not sure");
                } else {
                    if (count[0] == 0) {
                        System.out.println("queue");
                    }
                    if (count[1] == 0) {
                        System.out.println("stack");
                    }
                    if (count[2] == 0) {
                        System.out.println("priority queue");
                    }
                }
                zerar();
                size1 = input.readLine();
            }
        }
    }
  • Cristhian Bonilha respondido 8 years ago

    Consegui encontrar meu erro, obrigado!

  • Frank P. Tominc respondido 8 years ago

    Olá Cristhian

    Tenho mais alguns casos de teste aqui, teste com esses e veja se o resultado bate

    Imput:

    8
    1 36
    1 65
    2 65
    1 75
    1 62
    1 42
    1 58
    2 75
    10
    1 84
    1 59
    1 51
    2 51
    1 41
    1 59
    2 59
    1 70
    1 67
    2 67
    10
    1 24
    1 37
    1 87
    1 25
    1 74
    1 9
    2 87
    1 64
    1 49
    2 74
    7
    1 84
    1 36
    1 61
    1 4
    2 4
    1 61
    2 61
    8
    1 76
    1 83
    1 22
    1 11
    1 8
    1 48
    2 83
    1 90
    9
    1 1
    2 1
    1 36
    1 85
    1 4
    2 4
    1 51
    1 15
    2 15
    9
    1 64
    1 85
    1 33
    1 34
    1 58
    1 70
    2 85
    2 69
    2 64
    9
    1 72
    1 20
    2 72
    2 20
    1 89
    1 60
    1 39
    2 89
    1 77
    5
    1 63
    2 63
    1 57
    1 66
    1 73
    2
    1 49
    2 49
    10
    1 48
    1 90
    1 81
    2 48
    1 42
    2 90
    2 81
    2 42
    1 44
    1 63
    7
    1 88
    1 63
    2 88
    1 90
    2 63
    1 73
    1 15
    3
    1 86
    1 64
    2 86
    7
    1 38
    1 68
    1 14
    2 38
    1 27
    1 83
    2 68

    Output:

    priority queue
    stack
    priority queue
    stack
    priority queue
    stack
    impossible
    not sure
    not sure
    not sure
    queue
    queue
    not sure
    queue
  • Cristhian Bonilha respondido 8 years ago

    Alguém consegue achar o erro?

    [spoiler removido]

    problema resolvido