TOPIC

WA 20% ???

Ygor Ribeiro asked 3 years ago

#include<bits/stdc++.h>

using namespace std;

#define oo 0x3f3f3f

int bfs(int ini, int fim){
    int dist[100010];
    memset(dist, oo, sizeof dist);
    dist[ini] = 0;
    queue<int> fila;
    fila.push(ini);
    while(!fila.empty()){
        int x = fila.front();
        fila.pop();
        int y = x * 2;
        //printf("%d\n",x);
        if(dist[y] > dist[x] + 1 && y >= 0 && y < 10001){
            dist[y] = dist[x] + 1;
            fila.push(y);
        }
        y = x * 3;
        if(dist[y] > dist[x] + 1 && y >= 0 && y < 10001){
            dist[y] = dist[x] + 1;
            fila.push(y);
        }
        y = x / 2;
        if(dist[y] > dist[x] + 1 && y >= 0 && y < 10001){
            dist[y] = dist[x] + 1;
            fila.push(y);
        }
        y = x / 3;
        if(dist[y] > dist[x] + 1 && y >= 0 && y < 10001){
            dist[y] = dist[x] + 1;
            fila.push(y);
        }
        y = x + 7;
        if(dist[y] > dist[x] + 1 && y >= 0 && y < 10001){
            dist[y] = dist[x] + 1;
            fila.push(y);
        }
        y = x - 7;
        if(dist[y] > dist[x] + 1 && y >= 0 && y < 10001){
            dist[y] = dist[x] + 1;
            fila.push(y);
        }

    }
    return dist[fim];
}

int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",bfs(a,b));

    return 0;
}

Remember not post solutions. Your post may be reviewed by our moderators.

  • Ygor Ribeiro replied 3 years ago

    Obrigado Eduardo, abraço!

  • Eduardo Theodoro Bogue replied 3 years ago

    Olhando muito rapidamente o seu código acredito que o erro seja em você colocar a condição y < 10001. Por exemplo, seja N = 5000 e M = 7500, temos que N pode chegar a M em 2 passos (5000*3 -> 15000/2 -> 7500). Perceba que forçando a condição que y < 10001 essa solução não será atingida.

    Abraços!

    MOD