글 읽기 - [C] 반례 들어주실 분 찾습니다.

kms1212 1년 전 0

물병의 개수를 a, 옮길 수 있는 물병의 수를 b라 정하면 a - (a보다 작은 2의 거듭제곱) <= 0이거나 b=0일 때까지 a에서 a보다 작은 2의 거듭제곱을 빼주었을 때 문제에서 나오는 예시 결과는 모두 만족하였으며 소스의 66번째줄의 테스트에서부터도 a = 1에서부터 10000000까지 1452의 간격으로, b = 1에서부터 1000까지 13의 간격으로 모든 값이 테스트 조건(문제에 사용된 함수를 f(a, b)라 정하면 f(a + f(a, b), b) 는 항상 0과 같음)에 만족하였습니다.

문제의 3번째 예시 결과를 예로 들자면,

a = 1000000 -> 475712 -> 213568 -> 82496 -> 16960 (b = 5 -> 4 -> 3 -> 2 -> 1)

result = 32768 - 16960 = 15808(b = 1 -> 0)

하여 result = 15808이라는 결과가 도출되었습니다.

어떤 값을 대입해봐도 상기한 테스트 조건에 만족하는 값이 나오니 문제를 해결할 방법을 모르겠습니다 ㅠㅠ

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

int pwr(int x, int n) {
    if (n == 0)
        return 1;
    for (int tmp = x; n > 1; n--)
        x *= tmp;
    return x;
}

int calc (int a, int b) {
    int largestSquare = 1;
    b--;
    
    if (largestSquare == a) {
        return 0;
    }
    for (int i = 0;; i++) {
        largestSquare *= 2;
        if (largestSquare == a) {
            return 0;
        }
        if (largestSquare * 2 > a)
            break;
    }
    
    if (b == 0) {
        int largestSquare = 1; 
        if (largestSquare == a) {
            return 0;
        } 
        for (int i = 0;; i++) {
            largestSquare *= 2;
            if (largestSquare == a) {
                return 0;
            }
            if (largestSquare * 2 > a)
                break;
        }
        return largestSquare * 2 - a;
    }
    
    a -= largestSquare;
    if (!a)
        return 0;
    int result = calc(a, b);
    
    return result;
}

int main(int argc, char** argv) {
    int a, b, result = 0;
    #define TEST
#ifndef TEST
    scanf("%d %d", &a, &b);
    
    result = calc(a, b);
    
    printf("%d\n", result);
    
#else
    for (int j = 1; j < 1000; j += 13) {
        for (int i = 1; i < 10000000; i += 1452) {
            result = calc(i, j);
            
            printf("%d %d %d ", i, j, result);
            result = calc(i + result, j);
            
            printf("%d\n", result);
            
            if (result) {
                printf("Error %d %d", i, j);
                exit(0);
            }
        }
    }
#endif
}

kms1212 1년 전 1

디버그 출력을 지우지 않았네요..

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

문제

문제

출처

ICPC

[C] 반례 들어주실 분 찾습니다.

kms1212 1년 전 0

kms1212 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말