TOPIC

PROBLEM 1897 - URI Fórum 1.0

URI Online Judge asked 5 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Leonardo Lima replied 4 years ago

    The input "95 12" maybe the cause of 10% error

  • teste876 replied 5 years ago

    Valeu cara! Malditos if's !!! rsrs. É preciso ter atenção com eles.

  • Emanuel B. replied 4 years ago

    Preciso de ajuda - creio que bfs resolva o problema, mas estou tomando WA 20%. Até agora, tenho:

    # -*- coding: utf-8 -*-

def bfs(orig,dest):
    LIM = 10001
    INF = 2**31
    distance = [INF for n in range(0,2*LIM)]

    distance[orig] = 0
    Q = [orig]

    while len(Q) > 0:
        cur = Q.pop()
        if cur == dest:
            return distance[cur]
        lst = [cur*2,cur*3,cur//2,cur//3,cur+7,cur-7]
        for n in lst:
            if n > -1 and n < LIM:
                if distance[n] == INF:
                    distance[n] = 1 + distance[cur]
                    Q.insert(0,n)
    return -1

N,M = [int(x) for x in input().split()]
print(bfs(N,M))

  • 🧙The Install Wizard 🧙 replied 5 years ago

    Estude um pouco sobre busca em largura.

  • Matheus Eduardo da Silva Ramos replied 5 years ago

    Pessoal, olá Preciso resolver este exercício com C. Além das condições básicas, que são se N 2 ou 3 ou /2 ou /3 ou +7 ou -7 for = M, ele conta +1 e já para, não consegui fazer mais nada. Todas as formas que consigo imaginar, gerariam trocentas operações possíveis, pra pegar qual gastou menos e imprimir. Alguém pode me dar uma luz? hehe Obrigado desde já

  • Mateus Melo replied 5 years ago

    Seu código está quase correto. Repare na linha 11 do seu código, você digitou:

    cin>>n,m;

    Mas o correto seria:

    cin>>n>>m;

    Além disto, seu código imprime um número amais do que deveria. Ex:

    1 2
1 1

    Seu código imprime:

    2 
1

    Mas o certo seria:

    1
0

    Conserte isto e receberá accepted!

  • Luyza Ellen replied 5 years ago

    Realizei as alterações que você falou , mas o programa não imprime mais o resultado. E não consigo encontrar o erro. 

    #include<iostream>
#include<map>
#include<queue>

using namespace std;
int bfs(int origem, int destino);

int main()
{
    int n,m;
    cin>>n,m;
    cout<<bfs(n, m) <<endl;

    return(0);
}

int bfs(int origem, int destino)
{
    queue<int> fila;
    map<int,int> mapa;
    int vertice;
    fila.push(origem);
    mapa[origem] = 1;
    if(origem == destino){
        return 1;
    }
    while(!fila.empty())
    {
        vertice = fila.front();

        if(mapa[vertice*2]==0){
            fila.push(vertice*2);
            mapa[vertice*2] = mapa[vertice]+1;
        }
        if(mapa[vertice*3]==0){
            fila.push(vertice*3);
            mapa[vertice*3] = mapa[vertice]+1;
        }
        if(mapa[vertice/2]==0){
            fila.push(vertice/2);
            mapa[vertice/2] = mapa[vertice]+1;
        }
        if(mapa[vertice/3]==0){
            fila.push(vertice/3);
            mapa[vertice/3] = mapa[vertice]+1;
        }
        if(mapa[vertice+7]==0){
            fila.push(vertice+7);
            mapa[vertice+7] = mapa[vertice]+1;
        }
        if(mapa[vertice-7]==0){
            fila.push(vertice-7);
            mapa[vertice-7] = mapa[vertice]+1;
        }
        if(mapa[destino]>0)
            return mapa[destino];
        fila.pop();
    }

}

  • Mateus Melo replied 5 years ago

    Pense no seguinte caso:

    1 9

    A saída gerada deveria ser:

    2

    Mas seu código imprime na minha máquina:

    2147483647

    Perceba que ao entrar na função bfs, seu código primeiramente testará se a origem é igual ao destino e caso não seja, efetuará todas as operações solicitadas na questão(+7,-7,2,3,/2,/3), e caso a origem após alguma dessas operações seja igual ao destino, insere o termo na fila. mas e se após alguma dessas operações a origem não for igual ao destino? No caso:

    1 9

    1+7=8 1-7=6 12=2 13=3 1/2=0 1/3=0 nenhum desses valores é igual a 9. Então, você vai tirar o termo origem da fila, a fila ficará vazia e como você não declarou nenhum retorno na sua função, ela poderá retornar qualquer valor. A primeira coisa que você tem que pensar, é que caso após efetuar alguma dessas operações você deixar a origem igual ao destino, você já pode retornar o valor do mapa[destino] e, caso você não encontre, você enfileira os valores e continua a procurar.

  • Luyza Ellen replied 5 years ago

    retirei essa linha de código e o problema passou a não apresentar nenhuma saída. Alguém poderia me ajudar a resolver o problema??

  • Thalyson Nepomuceno replied 5 years ago

    acho que o erro está o retorno da função, sempre ta retornando 0.

    if(vertice == destino){
            return 0;
        }

  • Luyza Ellen replied 5 years ago

    Alguém pode me explicar o que tem de errado com o meu código? Sou iniciante em matéria de grafos. 

    #include<iostream>
#include<map>
#include<queue>

using namespace std;

int bfs(int origem, int destino);
int main()
{
    int origem,destino;
    cin>>origem>>destino;
    cout<<bfs(origem,destino)<<endl;

    return(0);
}

int bfs(int origem , int destino)
{
    queue<int> fila;
    map<int,int> mapa;
    int vertice;
    mapa[origem] = 1;
    fila.push(origem);
    while(!fila.empty())
    {
        vertice = fila.front();
        if(vertice == destino){
            return 0;
        }
        else
        {
            if(vertice*2==destino){
                mapa[vertice*2]= mapa[vertice]+1;
                fila.push(vertice*2);
            }
            if(vertice*3==destino){
                mapa[vertice*3]= mapa[vertice]+1;
                fila.push(vertice*3);
            }
            if(vertice/2==destino){
               mapa[vertice/2]= mapa[vertice]+1;
                fila.push(vertice/2);
            }
            if(vertice/3==destino){
                 mapa[vertice/3]= mapa[vertice]+1;
                fila.push(vertice/3);
            }
            if(vertice+7==destino){
                mapa[vertice+7]= mapa[vertice]+1;
                fila.push(vertice+7);
            }
            if(vertice-7==destino){
                mapa[vertice-7]= mapa[vertice]+1;
                fila.push(vertice-7);
            }
        }
        fila.pop();
    }

}

  • Jhonatan Gomes replied 5 years ago

    Obrigado pela dica! Eu havia resolvido usando essa ideia, só que utilizei um set.

    Meu problema não era em relação ao tamanho, acho que há algum caso que um número negativo leva mais rápido ao resultado. Eu verificava se o valor era negativo antes de testar se já havia utilizado aquele valor e recebia WA 10%, mas depois que mudei para o set não precisava mais dessa verificação e recebi o accepted!

  • Mateus Melo replied 5 years ago

    Você pode utilizar o map de c++ para guardar os números já visitados, desta forma, você não vai ter que se preocupar com o tamanho.

  • Jhonatan Gomes replied 5 years ago

    Qual foi o tamanho que você definiu para o vetor de visitados? Estou com o mesmo problema, recebendo 10%

  • ROP replied 5 years ago

    estou c o mesmo erro de 10%, minha ideia também foi tratar como bfs

  • Mateus Melo replied 5 years ago

    Você já tentou tirar esta linha:

    if(par.first>30001 || par.first<0){continue;}

    E aumentar o tamanho do vector visatados?

  • teste876 replied 5 years ago

    Alguém pode liberar mais casos de testes? Estou com 10% WA...

    ACC