글 읽기 - 반례가 있을까요?

04_miffy 4년 전 0

문제의 예시와 다른 글들의 모든 testcase가 통과되지만 문제는 통과하지 못합니다.

혹시 다른 반례가있다면 알려주실 수 있으실까요?

#include <iostream>
#include <queue>

#define MAX 500000

using namespace std;

bool visited[2][MAX] = {false,};
queue<int> q;
int n, k, t=0;
int (*operation[3])(int) = {
    [](int a){return a*2;},
    [](int a){return a-1;},
    [](int a){return a+1;}
};

int main() {
    void bfs(int idx);
    
    cin >> n >> k;
    
    if (n >= MAX || k >= MAX) {
        cout << -1;
        exit(0);
    }
    q.push(n);
    bfs(n);
    
    cout << -1;
}

void bfs(int idx) {
    while(!q.empty()) {
        int size = q.size();
        
        for(int i=0; i<size; i++) {
            int front = q.front(); q.pop();
            if(front == k) {
                cout << t;
                exit(0);
            }
            
            if(visited[front%2][front]) continue;
            visited[front%2][front] = true;
            
            for(int j=0; j<3; j++) {
                int newN = operation[j](front);
                
                if(newN > MAX || newN < 0) continue;
                
                q.push(newN);
            }
        }
        t=t+1;
        k=k+t;
    }
}

djm03178 4년 전 2

500000 500000

04_miffy 4년 전 0

아 0이 나와야하는데 -1이 나요네요! 하지만 고쳐도 결과는 틀렸다고합니다..

#include <iostream>
#include <queue>

#define MAX 500000

using namespace std;

bool visited[2][MAX] = {false,};
queue<int> q;
int n, k, t=0;
int (*operation[3])(int) = {
    [](int a){return a*2;},
    [](int a){return a-1;},
    [](int a){return a+1;}
};

int main() {
    void bfs(int idx);
    
    cin >> n >> k;
    
    if (n > MAX || k > MAX) {
        cout << -1;
        exit(0);
    }
    q.push(n);
    bfs(n);
    
    cout << -1;
}

void bfs(int idx) {
    while(!q.empty()) {
        int size = q.size();
        
        for(int i=0; i<size; i++) {
            int front = q.front(); q.pop();
            if(front == k) {
                cout << t;
                exit(0);
            }
            
            if(visited[front%2][front]) continue;
            visited[front%2][front] = true;
            
            for(int j=0; j<3; j++) {
                int newN = operation[j](front);
                
                if(newN > MAX || newN < 0) continue;
                
                q.push(newN);
            }
        }
        t=t+1;
        k=k+t;
    }
}

djm03178 4년 전 2

11 1

정답: 4

출력: 5

04_miffy 4년 전 0

말씀해주신 반례를 풀으려고 하였으나, 제 로직으로는 잘 풀리지 않습니다.

저또한 다른분들과 같이 홀/짝으로 생각하였습니다만, 이런식으로 결과가 나옵니다.

왼쪽이 수빈이의 위치이고 오른쪽이 동생의 위치입니다.

이에 혹시 아이디어를 주실 수 있으실까요??

04_miffy 4년 전 0

제 코드는 이렇습니다.

#include <iostream>
#include <queue>

#define MAX 500000

using namespace std;

bool visited[2][MAX+1] = {false,};
queue<int> q;
int n, k, t=0; // k: 동생
int (*operation[3])(int) = {
    [](int a){return a-1;},
    [](int a){return a+1;},
    [](int a){return a*2;}
};

int main() {
    void bfs(int idx);
    
    cin >> n >> k;
    
    if (n >= MAX || k >= MAX) {
        cout << -1;
        exit(0);
    }
    
    q.push(n);
    bfs(n);
    
    cout << -1;
}

void bfs(int idx) {
    
    while(q.size()) {
        k = k + t;
        int size = q.size();

        for(int i=0; i<size; i++) {
            
            // 1 time
            int front = q.front(); q.pop();
            if(front == k) {
                cout << t << endl;
                exit(0);
            }
            
            if(visited[t%2][front]) continue;
            visited[t%2][front] = true;
            
            for(int j=0; j<3; j++) {
                int newN = operation[j](front); // 수빈이의 새로운 위치
                
                if(newN > MAX || newN < 0) continue;
                
                q.push(newN);
            }

        }
        t = t + 1;
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 있을까요?

04_miffy 4년 전 0

djm03178 4년 전 2

04_miffy 4년 전 0

djm03178 4년 전 2

04_miffy 4년 전 0

04_miffy 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말