[editorial] SRM 395 Div 1

  • Neon
    Neon

    250
    1. 첫인상
    보통 div1이라도 250은 생각없이 마구 풀면 풀립니다. 그래서 일반적으로 생각 가능한 수준으로 다음과 같이 알고리즘을 설계했습니다.
    a. sneakTime이 walkTime*2보다 크면 그냥 walkTime을 써서 (x,y)까지 이동한다.
    이 경우 답은 result = (x+y)*walkTime
    b. sneakTime이 walkTime*2보다 작으면 대각 이동을 써서 (min(x,y),min(x,y))까지 이동한 다음 walk한다.
    이 경우 답은 result = (min(x,y)*sneakTime + (max(x,y)-min(x,y))*walkTime)
    2. 근데 TestCase가 굉장히 친절하게 나와줬습니다. 한가지를 더 생각해야 합니다.
    c. sneakTime*2가 walkTime*2보다 작으면(... 뭥미?) 최대한 대각 이동만을 써서 이동한 후, 어쩔 수 없는 경우에만 walk한다.
    이 경우 답은... #define MIN min(x,y) #define MAX max(x,y) #define DIFF MAX-MIN
    result = MIN * sneakTime + floor(DIFF/2)*sneakTime*2 + (DIFF%2)*walkTime
    500
    1. 건물들이 어떻게 놓여 있던간에, 그중 제일 큰 건물이 하나 있을 것입니다.
    2. 제일 큰 건물 왼쪽에 있는 건물들은 오른쪽에서 보이지 않을 것이고, 오른쪽에 있는 건물들은 왼쪽에서 보이지 않을 것입니다.
    3. 즉,

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


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