RATIO 질문합니다.

  • gwpark
    gwpark

    import java.io.*;
    
    public class Main {    
        static BufferedReader stdin
                = new BufferedReader(new InputStreamReader(System.in));
    
        static int T;
        static long N;
        static long M;
        static long[] res;
    
        public static void main(String[] args) throws Exception {   
            T = Integer.parseInt(stdin.readLine());
            res = new long[T];
            for(int t = 0; t < T; t++) {
                String[] tmp = stdin.readLine().split(" ");
                N = Long.parseLong(tmp[0]);
                M = Long.parseLong(tmp[1]);
                res[t] = solve();
            }
            for(long r : res)
                System.out.println(r);
        }
    
        static long solve() throws Exception {
            int T = (int)((double) M / N * 100) + 1;    // target
    
            // impossible to reach
            if(T == 100 || T == 101)
                return -1;
    
            // 100 * (M + n) / (N + n) >= T
            //      becomes n >= (T * N - 100 * M) / (100 - T)
            double n = (double)(T * N - 100 * M) / (100 - T);
            // Math.ceil to make as an integer
            long numWin = (long)Math.ceil(n);
    
            if(numWin <= 0 || numWin > 2000000000)
                return -1;
    
            // just in case ......
            for(int i = -500; i <= 500; i++) {
                if(numWin + i > 0) {
                    int curr 
                            = (int)((double)(M + numWin + i) 
                                    / (N + numWin + i) * 100);
                    if(curr >= T)
                        return numWin + i;
                }
            }
    
            return numWin;
        }
    }
    

    수식으로 간단히 구해져서 쉽게 끝나겠거니 했는데 계속 오답이 나오네요. 너무 답답해서 "just in case"라고 쓰인 부분까지 추가해서 혹시 모를 연산 에러(?)를 막으려고까지 했는데 계속 오답입니다... 도와주십시오 ㅠ


    10년 전
4개의 댓글이 있습니다.
  • 샥후
    샥후

    모든 경우에 대해 target이 제대로 구해질지 확인해보세요


    10년 전 link
  • gwpark
    gwpark

    샥후님 정말 감사합니다. 알아냈습니다.

    int T = (int)((double) M / N * 100) + 1; // 기존 코드 (오답)
    int T = (int)((double)(M * 100) / N) + 1; // 수정된 코드 (정답)


    10년 전 link
  • Being
    Being

    원칙적으로 double은 사용하지 않을 수 있으면 사용하지 않는 것이 좋습니다. 이 경우에는 충분히 정수만으로 계산할 수 있지요.


    10년 전 link
  • gwpark
    gwpark

    예... 그렇죠 ㅎㅎ...
    double은 최대한 자제해야겠습니다.
    IEEE 754... 알고도 당한 느낌입니다 ㅎㅎ


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.