TOPIC

PROBLEM 1340 - URI Fórum 1.0

beecrowd asked on Apr 27 2013

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • hjbrumatto replied 7 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?

  • gduarte replied 7 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

  • crbonilha replied on Jun 25 2013

    Alguém consegue achar o erro?

    [spoiler removido]

    problema resolvido

  • mcarvalho7 replied 8 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();
        }
    }
}

  • crbonilha replied on Jun 27 2013

    Consegui encontrar meu erro, obrigado!

  • fptominc replied on Jun 27 2013

    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