srm382 D2-easy

  • nocut98
    nocut98

    대략 요딴 식으로 짯었죠. (컴파일러 간 차이에 대한 질문인데요)
    [code c++]
    vector findMaxAverage(vector a, int K) {
    int i, k;
    double max = 0, t;
    int ri, rj;
    for(k = K; k<=a.size(); ++k) {
    for(i=a.size()-k; i>=0; --i) {
    t = (double)accumulate(&a[i], &a[i+k], 0)/(double)k;
    // cout << t << ", " << i << "," << k << endl;
    if(max <= t) {
    max = t;
    ri = i;
    rj = i+k-1;
    }
    }
    }
    vector r;
    r.push_back(ri);
    r.push_back(rj);
    return r;
    };
    // 테스트 코드 입니다.
    int a[] = {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000};
    int K = 21;
    int main(int argc, char* argv[])
    {
    vector aa;
    aa.assign(&a[0], &a[sizeof(a)/sizeof(a[0])]);
    vector r = findMaxAverage(aa, K);
    printf("(%d, %d)", r[0], r[1]);
    return 0;
    }
    [/code]
    제가 가진 VC++에서 컴파일 해보면, 정답인 (0,20)이 제대로 나옵니다.
    하지만, 탑코더에서 시스템 테스트를 돌리면 29, 49가 나옵니다(시스템 테스트로 안드로메다 고고씽~)
    도대체 뭐가 문제인 걸까요. g++을 별로 써본적이 없어서 어떤 주의 사항이 있는 건지 잘 모르겠네요.
    그리고 시스템 테스트에서 에러가 나서 출력값을 확인해 볼 방법도 없고, 값이 길어서 테스트에다 밀어넣지도 못하겠고...
    도무지 이해가 안가는 군요 ㅡ.ㅡ;;;
    덧... 제가 가진 cygwin 의 g++컴파일러로 컴파일해봐도 0, 20이 나오는데, 시스템 테스트만 계속 값이 이상하게 나오네요 ㅡ.ㅡ;;

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    17년 전
4개의 댓글이 있습니다.
  • helloneo
    helloneo

    precision error인것같네요.. 이렇게하면 pass 하네요..
    [code]
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    class ContiguousSubsequences {
    public:
    vector findMaxAverage(vector a, int K) {
    int i, k;
    double max = 0, t;
    int ri, rj;
    for(k = K; k<=a.size(); ++k) {
    for(i=a.size()-k; i>=0; --i) {
    t = (double)accumulate(&a[i], &a[i+k], 0)/(double)k;
    if(max - 0.0000001 < t) {
    max = t;
    ri = i;
    rj = i+k-1;
    }
    }
    }
    vector r;
    r.push_back(ri);
    r.push_back(rj);
    return r;
    }
    };
    [/code]
    근데 eps를 너무 작게해도 fail이군요.. -_-


    17년 전 link
  • nocut98
    nocut98

    아 그렇죠. 문제의 부분은
    t = (double)accumulate(&a[i], &a[i+k], 0)/(double)k;

    이 부분이죠.
    그렇게 해결된다 하더라도 설마 코딩할 때마다 if(max - 0.0000001 < t) { 요런 코드를 추가할 순 없는 노릇이고
    뭔가 지속적으로 해결할 수 있는 방법을 알고 싶어요


    17년 전 link
  • nocut98
    nocut98

    해결이 안되는 문제인가 보더군요. double형은 ==를 쓰지 말라고 합니다 ㅡ.ㅡ;;;(응? 뭐지?)
    discussion 에서 보고 내린 나름 해결책은

    #define same(a,b) (fabs(a-b)<0.0000001)
    if(same(max,t)||max<t)      // 원래 if(max <= t) 였었는데 바꿨습니다. -_-;;;
    

    이구요. 혹시 더 좋은 해결책을 아시는 분은 알려주세요 :)
    자문자답2 : 그냥 long double 형으로 쓰니 해결되더군요. 앞으로는 long double형을 애용해야 겠네효 ㅡ.ㅡ;;;


    17년 전 link
  • JongMan
    JongMan

    음.. 실수에 관한 것은 굉장~ 히 복잡한 주제이기 때문에.. 다음에 별개의 튜토리얼로 다루도록 하겠습니다.
    요점은, 특수한 경우를 제외하고는, double 이건 long double 이건, epsilon 값을 쓰건 쓰지 않건 실수 연산은 완전하지 않을 수밖에 없다는 것입니다. 실수 연산을 안심하고 사용할 수 있는 경우는, 전체 알고리즘이 floating point stable 한 경우에만 해당되죠.
    아~ 이것도 언젠가 꼭 써야 할 주제인데 언젠가는 반드시.. ^^;


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