TEMA

PROBLEM 1401 - URI Fórum 1.0

URI Online Judge preguntado 7 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • Thairone Simões Loureiro respondido 4 years ago

    Tente as entradas: 1 aac

  • Peter respondido 4 years ago

    Estou recebendo 10% wrong. Alguem pode me ajudar?

    #include<stdio.h>
#include<string.h>
#include<stdlib.h>

int verifica(int pos, char aux[], char valor){
    int i;
    for(i = 0; i < pos; i ++){
        if(aux[i] == valor)
            return 0;
    }
    return 1;
}

void backtracking(int i, char vetor[], char aux[], int tam){
    int j;
    for(j = 0; j < tam; j ++){
        if(verifica(i, aux, vetor[j]) == 1){
            aux[i] = vetor[j];
            backtracking(i + 1, vetor, aux, tam);
        }
    }
    if(i + 1 == tam){
        aux[tam] = '\0'; 
        puts(aux);
    }
}

void selection_sort(char vetor[], int tam){
    int i, j, min;
    char aux;
    for(i = 0; i < tam - 1; i ++){
        min = i;
        for(j = i + 1; j < tam; j ++){
            if(vetor[j] < vetor[min]) min = j;
        }
        if(min != i){
            aux = vetor[i];
            vetor[i] = vetor[min];
            vetor[min] = aux;
        }
    }
}

int main(){
    int tam, n;
    char vetor[20], aux[20];
    scanf("%d", &n);
    getchar();
    do{
        gets(vetor);
        tam = strlen(vetor);
        selection_sort(vetor, tam);
        backtracking(0, vetor, aux, tam);
        printf("\n");
        n --;
    }while(n > 0);
}

  • Miguel Mendes respondido 6 years ago

    Eu também só consegui resolver usando a biblioteca do C++.

    Da primeira vez ganhei TLE usando backtracking.

  • Wyllian Brito respondido 6 years ago

    Fiz usando a biblioteca do c++, a complexidade pra n chamadas é O(n!)

  • Jean Costa respondido 6 years ago

    Eu fiz meu algoritmo em O(n*n!) e estou tomando TLE. Existe alternativa mais eficiete? Alguém tem alguma dica?